Jump to content
  • Advertisement
Sign in to follow this  
White Rabbit

Hierarchical Path-Finding

This topic is 5173 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

Anyone here have any good papers on Hierarchical Path-Finding? All i find on google are rough descriptions and articles that you need to pay to get access to. Hierarchical Path-Finding applied to A* is of particular interest to me =). Thanks [Edited by - White Rabbit on August 20, 2004 11:10:08 PM]

Share this post

Link to post
Share on other sites
From what I have seen, much of the research in this area is currently comes from GIS (Geographic Information Systems) research, as they run searches over very large datasets. Most hierarchical search strategies are non optimal and are focused on very large data sets.

I don't know if the items they are optimizing for match what you would be optimizing for. For instance, there is a fair amount out there about optimizing storage of the graph, to avoid disk reads; this may be applicable to cache issues for game developers though.

Here are a few permutations which gave me hits on google:

gis hierarchical path
hierarchical pathfinding pdf
hierarchical wayfinding

Yun-Wu Huang has published many papers that may be of interest (http://citeseer.ist.psu.edu/cis?q=Yun-Wu+Huang)

If you aren't familar with the website citeseer (citeseer.ist.psu.edu), you may want to check it out as well. It has a huge collection of papers you can download.

One issue I hit when I started to look in to all of this is the difference between clustering and partitioning. Clustering tends to mean 'transforming a graph for human interpretation', and partitioning means 'transforming a graph based on an algorithm'. This isn't always the case, but it was a general pattern I hit at times. Be prepared to spend some time reviewing graph theory.

If you find anything that looks helpful, would you mind posting a link to it here? I am collecting papers on this topic as well.

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!