1
\$\begingroup\$

I'm currently researching for a summary paper on the different variants of A* search algorithm and how they are used in games and I stumbled across the name HPA*. I've heard that it's much more faster than traditional A* but I don't understand it completely. There's hardly any videos or articles written about it so I tried reading a research paper on it and I'm having trouble grasping it. All I can understand is it divides the huge graph in many smaller segments(divide and rule), it creates clusters(subgrids) and precomputes optimal distance between clusters etc..

I would be grateful to any of you if you helped explain it! Thanks in advance.

\$\endgroup\$
3
5
\$\begingroup\$

One of the creators of HAA* (a generalization of HPA*) wrote a very accessible article explaining how it works on aigamedev.com. Unfortunately that site seems to be dead, but fortunately archive.org has the article archived.

I highly recommend reading it, but to summarize: HPA* breaks the map into chunks. In each chunk, you identify the possible entrances/exits to the chunk, and cache the paths/distances between them. You can then use this to create a graph of the chunks which is much smaller and faster to path-find over than the original map.

Example

The paths you find with this method are only near optimal, but (after the initial setup cost) the pathfinding runs much more quickly than plain A*. You can even group the chunks into larger chunks recursively (hence the "H" in "HPA", meaning "Hierarchical") for greater speed benefits.

For more details, see the original paper.

\$\endgroup\$
1
  • \$\begingroup\$ Appreciate your answer. How is the grid really divided into chunks or how is the heuristic evaluated for the hierarchy? \$\endgroup\$ – Ixion Chowdhury May 17 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.