AiGameDev.com
See you at the Game AI Conference 2010?

“Join leading experts and industry veterans in Paris on June 23-24 for the largest independent conference about artifical intelligence in video games.” — Alex

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.

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

Alex Kring

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.



Access the rest of this feature by joining industry experts and other professionals as a Member in the leading Game AI training program.

3 + 1 Great Reasons to Join!

If you're dedicated to artificial intelligence and game development, here are the top three reasons for becoming a member:

  • High-resolution video recordings of masterclasses and interviews.
  • Expert reports distilled from the wisdom of industry veterans.
  • Industrial-strength source code examples, libraries and demos.

Of course, if you're not satisfied there's a 100% money back guarantee. Just email us and let us know what to improve, and we'll refund you.

Subscribe Now...