In 2004, Botea, Muller, and Schaeffer published the HPA* algorithm (Hierarchical Path-Finding A*), which arguably describes the most popular hierarchical path-finding implementation in the video games industry. One of the most pressing concerns for HPA* is the complexity involved in modifying the graph hierarchy, which is required for connecting arbitrary start and goal nodes. Maintaining a dynamic hierarchy slows performance, and complicates programming and debugging. This paper explains the problems with modifying the graph hierarchy, and then shows how the SHPA* algorithm alleviates these problems by maintaining a static hierarchy. Compared to HPA*, SHPA* is shown to be up to nine times faster in the best case, and about twice as fast for many common cases, while finding paths that are within 4% optimality of HPA*.
SHPA*: Improving Hierarchical Pathfinding Performance by Maintaining A Static Hierarchy with HPA*
Alex Kring on January 21, 2010
Access the rest of this feature by joining industry experts and other professionals as a PREMIUM member in the leading Game AI training program.