This article was published for AiGameDev.com PREMIUM members, available by subscription. You can join here in a minute or less. If you're already a member, log-in from the top right menu.

Premium Teaser
SHPA.icon

SHPA*: Improving Hierarchical Pathfinding Performance by Maintaining A Static Hierarchy with HPA*

Alex Kring on January 21, 2010

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*.

This article was written by Alexander Kring, Gameplay Programmer at Nihilistic Software and previously AI Engineer at Electronic Arts. The algorithm described was reimplemented by Nick Samarin in the AI Sandbox, under the guidance of Alex J. Champandard — who also suggested improvements to the algorithm.