A* Pathfinding For Large Distances

Game Mechanics
#1

I have a situation where I am using the A* pathfinding method to move a creature across a tile based world.
This particular world can be extremely large and has many obstacles obstructing a creature’s path (trees in this case).
When calculating paths over semi-short distances there is not a problem. However, there are huge freezes which take
place when I try to calculate a path over three hundred tiles away (or so). And yes this is because I haven’t multi threaded
pathfinding yet, but I feel it would still be too slow even after threading it.

Anyways, here’s a picture to give you a sense of the scale.

848×673 35.3 KB

That isn’t even the whole world, the minimap only shows 200 x 200 tiles whereas the full world may be infinite in size depending on the world generation rules.

I have heard that certain games, such as dwarf fortress I think? Split up their worlds into regions and somehow use those regions to improve the performance
of the pathfinding. Conveniently, I already have every world split up into 16 x 16 chunks which are currently acting as a method to define biomes, but I’m thinking
I can also use them for the purpose of quicker pathfinding.

I am not sure how this mechanically works. I am thinking the way this functions is that a path from the center of each region to all adjacent regions is calculated
and then cached, but I’m not sure. Not to mention that would significantly decrease shortest path accuracy.

So how can I use world regions to help improve long distance pathfinding? Or if there’s a better way in general, please let me know :).

Edit
I now realize this probably belongs in the artificial intelligence section.

#2

Search for hierarchical pathfinding.
You basically create graph(s) with different levels of detail so that you only need to use full pathfinding for the nearest tiles.

chunks work well with this, you can build a graph from these chunks:
-every connected walkable area in a chunk is a distinct node
-if node B can be reached (with A*) from node A => connect nodes with an edge
-do this only for chunks that are touching on the edge/corner to limit graph complexity

this graph should be much faster to navigate in, just do it in real-time
You can do this simplification multiple times for even more optimization.

http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/

#3

Depending on how your map looks, hierarchical pathfinding may have problems. Consider a chunk where the a river crosses it horizontally. In this case, the chunk is “enterable” from all four sides, but it’s not possible to go from the top to the bottom and vice versa, and if you enter on the top right you can only exit at the top and top left. The chunk is essentially two completely separated areas in this case. Another funny case is if you have a chunk which only the corners are walkable. Again, all 4 directions are technically enterable, but you can’t really go anywhere from there. Handling cases like that is the most complex part of implementing hierarchical pathfinding.

#4

[quote]chunks work well with this, you can build a graph from these chunks:
-every connected walkable area in a chunk is a distinct node
-if node B can be reached (with A*) from node A => connect nodes with an edge
-do this only for chunks that are touching on the edge/corner to limit graph complexity
[/quote]
Not the whole chunk is getting one node, but every connected part of the chunk does.
You can find this out by doing flood-fill or whatever until every walkable tile inside the chunk has been visited. This should work nicely.
node!=chunk

#5

Ok, so you’re saying that I can cache the nodes I know are walkable which will speed up the process. That’s a good idea. And then through the process of hierarchical pathfinding, I can connect entire chunks to each other in the same manor by seeing which tiles along the edges or corners of each adjacent chunk connect to each other.
Is that what you were saying when you said [quote]-do this only for chunks that are touching on the edge/corner to limit graph complexity
[/quote]
I will read the article you sent, thank you.

[quote]Depending on how your map looks, hierarchical pathfinding may have problems. Consider a chunk where the a river crosses it horizontally. In this case, the chunk is “enterable” from all four sides, but it’s not possible to go from the top to the bottom and vice versa, and if you enter on the top right you can only exit at the top and top left. The chunk is essentially two completely separated areas in this case. Another funny case is if you have a chunk which only the corners are walkable. Again, all 4 directions are technically enterable, but you can’t really go anywhere from there. Handling cases like that is the most complex part of implementing hierarchical pathfinding.
[/quote]
I can really see how this would be a pain to deal with. Finding an elegant solution would probably be a particularly difficult task.

#6

Divide map grid into sub-grids. Flood fill each unique traversable area on each sub-grid of, say, 16x16 to get a small number of “territories” (uniquely number each one for the entire world map) which becomes nodes in a low-resolution A* pathfinder (probably just 1 for most). After whole map has been done, scan along each edge to find out which territories can reach which other adjacent territories and that defines the topology.

Now in your game you do a low-res A* search first to get the shortest paths across the sub-grid in terms of the territories. You can discard any grid points in your main A* search that are not part of this set, thus massively cutting down on your open search set.

There are further optimisations you could do but I bet that’s good enough.

Cas :slight_smile:

#7

A couple of other minor optimisations:

  • Don’t use A* at first, try a Bresenham line to run straight at the target - it’s extremely cheap and for shorter distances likely to succeed anyway
  • When total distance is small-ish, say under 32 tiles, don’t bother with the low-res search first

Cas :slight_smile:

#8

Another problem with hierarchical pathfinding is that sometimes it doesn’t produce the fastest path. Consider this example:

[tr][td]Start[/td][td]Maze[/td][/tr]
[tr][td]Field[/td][td]Goal[/td][/tr]

A hierarchical pathfinder may consider the path through Maze to be equally fast as the path through Field when only looking at which walkable sections are connected to each other, even though the path through an open field will be faster than going through a massive maze.

Here’s a cool idea to solve that: For each chunk, we identify the edge tiles that lead to other chunks and add these to a list of “portals”, AKA tiles that you can move to a different chunk from. For each of these portal tiles, we precompute the path length/cost to every other portal tile in the same chunk (we could precompute the entire path, but that would take a huge amount of memory. This would have some interesting effects on the number of tiles searched. In my experience, the cost of pathfinding is not very related to the number of tiles traversed by the algorithm, but the number of tiles “investigated” (= tiles visited*average neighbor count). Hence, to compare the investigation count of a 128x128 chunk:

  • Brute forcing: 128x128 tiles x 4 neighbors each = 65 536 tiles investigated.
  • Edge to edge: 127x4 tiles, each with 127x4-1 “neighbors” each = 257 556 tiles investigated.

Owww. That was not a very good idea. The connections are edgeCount^2, which actually scales worse than just traversing all those tiles instead. We’ll have to cheat a little. If we assume that we may have multiple adjacent portal tiles, we could replace them with a single centered portal tile to reduce the number of edges. If we decide to merge up to 5 portal tiles into a single portal tile (basically we only have a portal tile every 5 edge tiles instead of for every edge tile), we’d end up with only 25*4 edge tiles per side, or 100 in total.

  • Edge to edge (every 5 tiles): 25x4 tiles, each with 25x4-1 “neighbors” each = 9 900 tiles investigated.

That’s a reduction by a factor of 6.6, which is pretty good. Another cool thing that this would allow for is that we could basically precompute some paths between edges if we realize that those are beings searched often (or all of them if memory allows for it). That would mean that we only need to find the path to the best edge tile of the start and the goal chunks and then the hierarchical system will kick in, and all paths that those have will already be precomputed in memory. The entire algorithm would look something like this:

  1. Figure out what princec territory the start and end tiles belong to. We will only need to path-find tile-by-tile in these two territories.
  2. Start with the start tile and start exploring using standard A*.
  3. Once we reach a portal tile and we’re not in either the start or end territories anymore, we will purely pathfind using precomputed edge-to-edge portals between chunks, effectively skipping the entire inside of each intermediate territory.
  4. As soon as we enter the goal territory, we switch to tile-by-tile pathfinding again to locate the exact target tile.
#9

Also how accurate does this even have to be? In the screenie it looks like a sheep - surely only an omniscient computer science major sheep would be able to first see all the trees and rivers ahead in the whole world, then calculate the shortest path around them, then take it :slight_smile: Maybe it could find its way more realistically via sheep-like trial and error?!