Jump to content
  • Advertisement
Sign in to follow this  
sidwinda

Need help to understand HPA*

This topic is 4974 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I want to try to implement HPA*, which in the paper "Near Optimal Hierarchical Path-Finding by A.Botea,M Muller, and J.Schaeffer. http://www.cs.ualberta.ca/~jonathan/Papers/Papers/jogd.pdf However I have difficulty in understanding it. May be partly because my first language is not English. The part that confuse me is the Table 1 results (page 25) for the example results that is given. I just can not figure out how to get the number of expanded nodes in L-1 and L-2 rows. The explanation in the paper is on page 12-15, however when I read it just make me confuse. Can someone please help to understand it? Thank you

Share this post


Link to post
Share on other sites
Advertisement
"I just can not figure out how to get the number of expanded nodes in L-1 and L-2 rows."

They most likely count the number of unique nodes that have been put on A*'s open list during the A* searches for level 1 respectively 2.

William

Share this post


Link to post
Share on other sites
First, Thank you for the response.

That's is what I think too.
However on the table1 the L-1 row for the SG part, it has 16 nodes. When I try to calculate it by my own it is 17. Did I make a mistake ?

One more question, for the low-level search, the heuristic that the paper used is Manhattan distance. How about for the level 1 and 2 abstraction ?

Thank you

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!