Chunked A* Pathfinding Issues

Question

I've run into an issue with A* pathfinding in a chunked world.

This is my current setup:

• The world is designed in Tiled and exported as a .json file.
• I wrote a little program that converts the .json file into objects that are serialized into binary files the main game loads.
• Each chunk is stored in it's own file (-2_-1.cnk for example).
• Chunks contain an x, y, width, height, int[,] for tile ids and a bool[,] for solid flags.
• The GameWorld contains a Dictionary<Point, Chunk> to store the chunks.
• When the game needs to know which tile id exist at (x,y), the world first checks to see if the chunk is loaded. If not it is loaded from disk and stored in memory until it's unloaded.
• The pathfinder does not know about chunks, an IGrid interface is passed when FindPath is called, IGrid contains an IsWalkable(x, y) method.
• The GameWorld implements 'IGrid' and contains an implemented IsWalkable method.
• When IsWalkable is called by the pathfinder, the world calls GetChunk(x, y but does not load a chunk from disk if isn't not already in memory. If a chunk is found, the bool[,] is checked to see if the tile is solid or not. If a chunk is not found, the tile is considered solid.

Pathfinding runs fine, search time range between 0.3ms - 9ms; though I have noticed that there are some corners that take ~40ms to search.

But as for my issue. Say I have a valid, accessible tile that a path can be found for, only it's close to the border of a chunk and can only be reached by leaving the current chunk and moving into an adjacent chunk. This image should be a better representation:

The red lines are the chunk borders, the yellow circle is the goal, the pink circle is the start and the blue line is the path.

For this example, pretend everything ABOVE the red chunk is an unloaded chunk, below the red line is loaded, and the player CAN SEE the goal tile. Diagonal movement is allowed, but not when moving next to a solid tile, so slipping between the trees diagonally is not allowed.

The pathfinder will keep searching the loaded chunk until it reaches the border, the chunk above is not loaded, so any tiles outside the current chunk are 'solid'. The pathfinder will continue to search available tiles in the loaded chunks until it's checked them all and decided a path could not be found.

A work around for this is to allow the pathfinder to load chunks when it reaches chunk borders, but this doesn't seem like a very clean solution.

Is there any way around this? The map is static and will not change, so I can pre-compute 'something' when I convert the map from the .json file.

One solution might be to flood fill each accessible 'region' in each chunk, only allowing paths with goals in the same region the player is standing in. But that would break if the player is standing on the boundary of two chunks, they would have different regions.

Or I'm just way over thinking this and I should just increase the chunks loaded distance so there's more overlap with the on screen and off screen chunks. Then just limit the pathfinding to have a max_search_length limit and stop when it's searched for too long.

Any thoughts?

Answer 1

Store PF information in a different struct/object (since you said it never changes). You only need 1 bit for every tile anyway, or 1 byte if you want to handle different tile speeds, it should't take too much memory. This might come handy for circunstances where the PF actually needs to skip several chunks in order to reach a goal.

Answer 2

• The binary data of whether or not a tile is occupied is much smaller than the rest of the map. You can store this in your json data as a binary string. For a 1024 x 1024 chunk, that's just 131 kilobytes, which should be very easy to load.

• If just loading the binary metadata is unpalatable to you, you could modify A* in the following way: assume every unloaded tile is passable. If later any cell along your path is loaded and found to be unpassable, you replan the path. This sounds like a dumb algorithm but it's actually not that bad. If you want something that's optimal, you can use D*, which is actually not that different from just replanning.

Answer 3

When you are near the edge of your loaded chunks, you should be loading more (in the background), and that will reduce the lag time as you travel long distances.

One option is to instead of considering unloaded chunks to be unwalkable consider them unknown. In a first pass you consider them as unwalkable tiles, when path finding fails in that case you can do a second pass where you actually load those chunks.

You can also use a bidirectional A*. That way, if one side ends in a dead end in the first pass, you can skip the second pass.

Also, if it's a pregenerated map it should be possible to load the walk-able state separately (which will be cheaper to load and keep in memory) and even keep the entire map's walk-able state loaded as a bitmap.