Sketch for Hierarchical Pathfinding Using Detour

Several people have asked me how to implement hierarchical pathfinding using Detour, usually because they have so much pathfinding data that it is not feasible to keep it all in memory. This is common scenario in MMO game for example.

If I were to build an MMO pathfinding from ground up, I would make sure the world structure would have easy to use abstraction already build it. That is, if I were to travel long distances, then it makes sense to find path via certain land marks first and then in final stage find the actual path.

If you need to retrofit pathfinding to existing game, the following method might work for you.


Tiles as Path Abstraction
Detour allows you to break down the world into tiles and lot in only the data that you need. This data structure can be exploited to create hierarchical path finder.

The idea is that you first find which tiles needs to be travelled in order to get to the destination and then you find path within one tile at a time until you reach the destination. We need connectivity graph between the tiles to do the high level search.


Building High Level Graph

Take a look at a the highlighted tile in above picture. There are two separate contiguous areas A and B in that tile. A is at the street level and B is partially underground. The areas are not connected, so depending how you enter the tile, each tile may have different kind of connectivity to neighbour tiles.

The first step in building the higher level graph is to identify these contiguous areas of the navmesh. The simplest way to do this is to first find all the portal edges of the tile and flood fill along the polygons and visit all the portal edges of the mesh. Finally you can use this data to identify contiguous areas and which portals belong to them.

In order to build navigation graph from this data we need to deduct A* nodes from the data. There are several ways to do this, I'll explain two of them: 1) Nodes at portals, 2) Nodes at area centers. These two methods allow to trade off quality of the path and speed of the search.


Nodes at Portal Edges



As the name implies this method places an A* node at each portal edge center. After that the area information is used to connect the nodes within single area to each other and finally, using all the tile data, nodes at overlapping (connected) edges are at the merged.

This method allows higher quality paths if you use actual path distance between the nodes instead of using euclidean distance between the nodes. The con of this method is that it can potentially create a lot of nodes and links.


Nodes at Area Centers



This method places the A* nodes at the center locations of the contiguous areas. The connections between the nodes are calculated using the all the tile data just like the nodes were merged in the previous method.

Multiple links between area can be removed, and in general this method creates a lot less links than the portal center method. The trade off is that the high level path quality is likely to be worse than with the edge method.


Area Flags



If you want to use flags which enable and disable agent movement on the mesh, then you need to take this into account when building the high level graph. You should partition the mesh so that each area with different flags ends up having own node or link. In this case the nodes at area centers can be easier to implement.


Finding the Path

There are several ways to use this information to find path once you have found the high level path.

Firstly you could just load the tiles that are necessary to find path from the start location to the goal location. This is not the most effective way to do it, though. Ideally there should be a way to identity which tiles to visit during pathfinding. But if your main concern is memory, this method allows you to load the correct tiles and focus pathfinding.

Another way to use the information is to just find path within one tile. That is, always find path to the exit portal of the current tile and path find again from there. The tricky part is how to choose a good point at the exit portal. One way, perhaps a bit naively, would be to choose the nearest point on the edge and move there.



A bit more advanced method could be to use the the tile portals with the string pulling method Detour uses and find "straight" path along the tiles first and then use the intersection point between portal edge and the high level straight path as target to exit the current tile. Rinse and repeat until the goal location has been found.

Alternatively you could also use a "workspace" which is something like the next 4 tiles to get a bit more quality off the second method without trading off too much memory.


The key to optimize pathfinder, and applies here too, is to make a little work as possible. This is even more true when your world is dynamic, as a lot of work can potentially be thrown away when something changes.