Sign in to follow this  

Hierarchical Path-Finding

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

This topic is 4864 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this