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.