Friday, April 12, 2019

Efficient Pathfinding in a Minecraft type world

As I said in my previous post, I want fairly complex NPC AIs where they sorta feel like you are playing with someone else. I want to have 5-10 of them all doing various things. To do this, the first piece of code I need is fast pathfinding: code that describes how to get from point A to point B. My criteria for this pathfinding algorithm is:

- Fast: queries take just a few milliseconds
- Not very much preprocessing is required
- Intermediate results can be reused when possible (pathing is only slow the first time it is called in a new area)
- Works in a 3D minecraft type cube world
- When blocks are removed or added, it doesn't have to change very much

I did a lot of looking around, but wasn't able to find something that did what I wanted, so I just came up with my own algorithm. It has three key functions:

Generate pathing chunk: Given a chunk, generate a "pathing chunk"

This "pathing chunk" should abstract all the blocks in that chunk into "regions". Currently there are two types of regions:

- Walking regions:
  1. If a block can be stood on (is solid and has enough air above it), start a walking region (call this region H) at that block.
  2. Spread out to that block's 4 adjacent horizontal neighbors: if they can also be stood on and are in this chunk, add them to region H. Also spread out to the block below us and add it to region H, if it is solid and in this chunk. If a block is spread out to, repeat step 2.
      - If we are spreading to a horizontal neighbor (call this neighbor X) but we cannot be stood on, look up to find the block above us that can be stood on (call this block above us Y).  Make sure we can jump from X to Y, and that there isn't a block in the way. This prevents situations like this:
AB
XA
BY
BB

B is a block
A is air
X and Y are also air, we can't jump from Y to X (or vice versa) because the B is in the way above.

3. If our horizontal neighbor cannot be stood on and does not have a block below it that we can jump from it to us, make a "falling region" (call it region W) that just goes straight down until it hits a solid block, in which case it connects to the region there  Connect H to W, so we can go from H to W (but not from W to H: the connections are directional).


Connect two pathing chunks: Given two neighboring chunks, connect regions that can reach each other

I want to abstract this from the logic above, so this post will be cleaned up a bit in the future once I figure that out. That'll let me make more generic kinds of pathing regions such as "dig here" and such.

Pathfind: My pathfinding can now work like this:

1. Generate pathing chunk in goal and start regions (if needed)
2. Generate pathing chunk in regions adjacent to start (if needed).
Do A* pathfinding in this "metagraph" of regions connected to each other. When computing the cost to go between two regions, do A* inside those regions (this is pretty cheap since regions are usually relatively small). Caching can also help here so we don't need to repeatedly A* between regions.




And that's it :) You can find the code that implements this idea here. It's fairly simple conceptually: just make a "metagraph" of "traversable regions" and then pathfind through those. The details are a little tricky and I'm still fiddling with ways to clean this code a bit. Ideally I'd like to seperate the logic of "connect two chunks" from the logic of spreading and creating regions, because that'll simplify things and make it much nicer to create regions, but that's currently in the works.

The nice part about this is that it satisfies all my criteria: when a block is modified, only that pathing chunk and the connection to it's adjacent chunks needs to be updated. Pathing chunks are fairly quick for me to make, and once they are complete then pathing can be done over hundreds of blocks very quickly :)

I considered doing something hierarchical, and perhaps I'll do that in the future, but as is the performance of this was good enough that I didn't really see a need for that.





Status so far

This project actually started around November of 2018, but after spending 4-5 months on it I decided it might be fun to write a blog so I can better document my progress, and share any insights I've gained during programming.

Here is what it looks like so far:

Currently, it has:


- Lighting:

I haven't implemented "smooth lighting" yet, but otherwise I'm pretty happy with this.

I have a "heightmap" thing that keeps track of the highest solid block at each x,z coordinate, and gives that block sunlight. This sunlight will spread out: if not touching the sun, a block's sunlight = (max of neighbor's sunlight values) - 1, clamped to have a minimum value of 0 and a maximum value of 15.

There is also a "block lighting" value that trickles in a similar way: If it is not producing light, a block's blocklight = (max of neighbor's blocklight values) - 1, clamped to have a minimum value of 0 and a maximum value of 15.

The shader has both these values, and also has a value for how "sunny" it is (from 0 to 1) that is multiplies to sunlight. In pseudocode


sunLevel = (value from 0 to 1, 0.1 at night, 1 at noon, can smoothly change at sunset)
sunLight = (value from 0 to 15)
blockLight = (value from 0 to 15)

actualLight = max(sunLevel*sunLight, blockLight)

this lets me not have to run lighting updates when it gets dark at night. I also used "tinting" so in dim lighting things get a blue shade similar to how this happens irl, due to the biology of our eyes. There isn't actually a daylight cycle yet, but there is a global "sunLevel" variable that I can change to make it look like night.

- Raycasting: I wrote code that raycasts to find when your mouse hits a block. It also raycasts to let you move around, so even if you are falling at a very fast speed you won't fall through blocks.

- Hold down shift so not fall off edges (like sneaking in minecraft)

- Block Entities and player inventories. There can be stacks of items, and items can have durability and break

- Crafting and custom recipes

- Fairly basic generation: I have caves using a perlin worms algorithm and basic hills just using perlin noise, but this could be vastly improved and is probably going to be my main next focus. I'm still tweaking with what makes a nice API here.

- Rendering: I have 16x16x16 chunks (this size might change). My world is infinite horizontally and vertically, so you can dig down as much as you want and never hit bedrock. Today I moved the rendering code to a seperate thread which makes everything feel much smoother. I don't show block faces that aren't exposed to air.

I also have a system for custom "block models" where using a format very similar to minecraft's format. This allows me to make things like this (ignore the gross textures this is just an example)


My physics engine/raycasting will actually look at the small models themselves (by raycasting to each triangle) and not just treat them as a entire block, so you get nice behavior like only breaking a torch if you click on it, and being able to breat the block below it.

- Saving: Words can be named, saved, and loaded (but the format is pretty gross right now and takes 10 seconds or so to save and load a world - I plan on improving this in the future)

I'm desigining everything to be very modular and nice to use (in terms of coding), so adding new recipes and blocks with custom behaviors is very easy to do.

- Pathfinding: I'm really happy with my current pathfinding system, it can pathfind very quickly around hundreds of blocks efficiently, but I think it'll require a seperate blog post to explain in full. There is still some things I want to do with this to enable mobs to strategically build and such as part of their pathing. I really like games like dwarf fortress and rimworld, and I'd like to have much more complex NPC AI. For those of you that follow Tango Tek's Villager Mod series, that is more along the lines of kind of gameplay that I am going for: You are a player yourself, but you interact with NPCs quite a bit to do things in the world. Except, I also want the NPC so be builing things as well with you. I want them to feel like someone you are playing with.

- Multiplayer: I don't have this yet, but this is very important to me and is a big todo in the near future.






Introduction

I've always thought voxel type games were such a cool idea. Many years ago (around 2010) I wrote basic marching tetahedrons code and was tinkering with a basic engine, but it never got very far. A bit after that, I learned about Minecraft. This was back in the Alpha days, but I still loved that game so much. It did so much of what I wanted in an open world creative building time game, and it was so exciting to see how well a game like that could actually work.

Ever since then, I've tinkered with making cube type engines from time to time, but never got very far. Recently, I decided to create VR Sand (a falling sand/powder toy type game), and my design decisions ended up leading me to understanding quite a bit about how to render large amounts of cube efficiently. I realized that similar code could be used for a blocky type engine (in Unity), and decided to get started. This blog will be documenting the progress on making a game/engine of sorts. I don't really have any major goals, this is just something I really enjoy making so I figured I'd see wherever it goes. My code is all open source, you can find it at https://github.com/Phylliida/Blocks


Rendering Lots of Blocks Efficiently in Unity

The last few weeks I've spent trying to see how many blocks I can render, while keeping everything at a nice frame rate (30-60fps) with ...