Near-Optimal Hierarchical Pathfinding (HPA*)

You might think that over the decades, in-game navigation has been completely solved and that research can focus on different topics. Well, it’s not quite the case yet; there are still improvements being made to deal with greater numbers of actors and larger dynamic worlds.

This week’s Thursday Theory post looks into a significant improvement of pathfinding efficiency using a hierarchical A* algorithm from the GAMES Group at the University of Alberta.

Motivation

There are near-optimal hierarchical pathfinding algorithm addresses three common issues in modern video games:

1. Game worlds are increasingly dynamic, especially in proximity to human players. In these situations, paths are often invalidated (e.g. when a soldier gets shot while running a response is required). The majority of the pathfinding calculations are never used, specifically towards the end of the path.

2. Traditional A* algorithms must complete the search before returning a path, which often takes multiple frames of the game. On large maps, this can result in a delay in responsiveness once the character has requested the path and waits for the result.

3. Much of the information calculated by A* during an individual search is discared, never to be reused again by any other actors or searches. This is particularly a problem when the terrain is represented as a very detailed graph, as computation is thrown away.

Figure 1: A graph of a traditional A* (Star) grid search. [2]

Contribution

This paper by Botea, Müller, and Schaeffer shows how to resolve these problems using a combination of ideas:

• How to pre-process a grid to build a higher-level graph, repeatedly if necessary on multiple levels. This is done using a clustering algorithm that groups neighboring nodes together when appropriate.

• An algorithm to plan paths hierarchically on this graph by planning at the top level first, then recursively planning more detailed paths in the lower levels.

• A solution for caching paths that are often reused in the hierarchy, so a tradeoff can be made between memory and computation.

• A smoothing process for preventing unnecessary detours caused by the simplifications of the hierarchical representation of the graph.

Each of these parts of the solution is required for performance to improve without any drops in quality. However, you should be able to implement these features incrementally into a working pathfinder.

Abstract and References

This paper presents HPA* (Hierarchical Path-Finding A*), a hierarchical approach for reducing problem complexity in path-finding on grid-based maps. This technique abstracts a map into linked local clusters. At the local level, the optimal distances for crossing each cluster are pre-computed and cached. At the global level, clusters are traversed in a single big step. A hierarchy can be extended to more than two levels. Small clusters are grouped together to form larger clusters. Computing crossing distances for a large cluster uses distances computed for the smaller contained clusters.

Our method is automatic and does not depend on a specific topology. Both random and real-game maps are successfully handled using no domain-specific knowledge. Our problem decomposition approach works very well in domains with a dynamically changing environment. The technique also has the advantage of simplicity and is easy to implement. If desired, more sophisticated, domain-specific algorithms can be plugged in for increased performance.

The experimental results show a great reduction of the search effort. Compared to a highly-optimized A*, HPA* is shown to be up to 10 times faster, while finding paths that are within 1% of optimal.

You can download the paper from the site (PDF, 863 Kb).

Near-Optimal Hierarchical Pathfinding
A. Botea, M. Muller, and J. Schaeffer
Journal of Game Development, Volume 1

There’s a presentation available also (PDF, 566 Kb).

Near-Optimal Hierarchical Pathfinding (HPA*)
M. Lanctot
CMPUT 651 Presentation, September 2006

Figure 2: Example of building a hierarchical representation of a grid.

Evaluation & Discussion

Overall, this solution is very robust. Certain game studios have been using similar concepts for a few years already, but this paper does a great job of formalizing and improving the results.

Applicability to games: 9/10

Not all games benefit from a hierarchical terrain representation, or even require grid-based pathfinding. However, most do, so applicability is quite high. There are no reasons the algorithm wouldn’t work on navigation meshes or waypoint graphs, but this would require some prototyping.

Usefulness for character AI: 9/10

HPA* has many advantages for any type of actor, notably that a suggested direction would be returned much faster during pathfinding queries so a turning motion can start without delay. Also, having an automated clustering algorithm is useful for providing a high-level overview of the terrain to the actor without it requiring hand-editing.

Simplicity to implement: 8/10

The advantage of this solutions is that there’s a relatively clear path of incremental improvements that can be made to any functioning A* pathfinder. As with navigation in general, there are often problems that arise during the implementation, but with solid software engineering practices the hierarchical search, clustering, and path caching should be within the reach of most AI programmers.

How do you rate this hierarchical pathfinding solution?