Another problem with hierarchical pathfinding is that sometimes it doesn't produce the fastest path. Consider this example:
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.