Open Review
path

Near-Optimal Hierarchical Pathfinding (HPA*)

Alex J. Champandard on October 11, 2007

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.

Grid Search A* (Star)

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
Grid Hierarchy

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?

Discussion 2 Comments

FreddieFreeloader on January 18th, 2008

It's definitely a very interesting algorithm, and seems incredibly easy to implement. Apart from the computational benefits I see two further bonuses. [LIST] [*]No obvious cheating by the AI. Hierarchical Pathfinding (as is the case with Hierarchical Planning) is much more similar to how humans would solve the problem. Perfect A* paths seem to suggest that the AI has perfect information and perfect recall. The imperfections would, in my opinion, add greatly to the illusion of human intelligence in NPCs. Of course the frequency of these imperfections is quite low, but then again we wouldn't wan't the AI behaving suboptimally often. That might seem human, though a stupid one at that. [*]I imagine the abstract graphs are very well suited for doing other kinds of tactical analysis. Suppose that the AI is aware of the location of two player bases. Using a flow algorithm, with the player bases as sources, the AI base as sink and the length of edges inversely proportional to the capacity, find the bottleneck edges, move to lower levels of abstraction for the grids that the bottleneck edges are located in and repeat. Hey presto, a choke-point algorithm that's feasible for even very large maps. [/LIST]

fidlej on September 22nd, 2009

Am I overlooking a link? I had to google to find the mentioned paper: [url]http://www.cs.ualberta.ca/~mmueller/ps/hpastar.pdf[/url] But thanks for the introduction to the paper.

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!