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 abool[,]
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 anIsWalkable(x, y)
method. - The GameWorld implements 'IGrid' and contains an implemented
IsWalkable
method. - When
IsWalkable
is called by the pathfinder, the world callsGetChunk(x, y
but does not load a chunk from disk if isn't not already in memory. If a chunk is found, thebool[,]
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?