Jump to content
  • Advertisement
Sign in to follow this  
TheComet

A* hysteresis on an arbitrary graph

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

The Astar algorithm requires a hysteresis to be calculated. The Manhatten method, for instance, is calculated as follows:

H = 10*(abs(currentX-targetX) + abs(currentY-targetY))

Now what happens if the graph I'm running the search on is arbitrary? I.e. the nodes aren't located in a spacial dimension, and nodes can have any amount of linked nodes ranging from 0 to 100? I don't really have any way of knowing what "currentX" or "currentY" even is. The only information I have are the links between nodes; each node holds a list of the nodes it is linked with.

 

Am I stuck with Dijkstra’s algorithm?

Share this post


Link to post
Share on other sites
Advertisement
The word you want is "heuristic" ;-)
 
In the case of an arbitrary graph, you're kind of up a creek unless you have additional data on each node that could be used to attempt to construct a heuristic, which it doesn't sound like you have.

One option is to precompute adjacency information (i.e. do a breadth-first expansion of the entire graph and store off distances between each pair of nodes in terms of number of "hops" between them) but that's pretty intensive in terms of storage use - O(n^2) in the number of nodes.

Share this post


Link to post
Share on other sites

If you have the ability to preprocess the data once, before running numerous quick searches later, then you could consider assigning standard Cartesian coordinates to your nodes to enable the standard A* heuristics.  Wikipedia: Graph Drawing # Layout Methods is possibly a good starting point for getting some ideas of how to do that assignment.  I suspect force-directed graph drawing is the most common.

 

You then also have the option of doing it in as many or as few dimensions as you want.  Higher dimension counts might produce more reasonable results if you tend to have very complex graphs, but will come at a higher runtime cost while doing a search.  Lower dimension counts will enable faster heuristic computation, but might make it very hard to intelligently arrange the nodes.  You'll either have a very costly preprocess step, or you'll end up with misleading heuristics producing expensive searches (or both).  Use two dimensions only if you know that your graphs are going to be relatively simple, and map pretty naturally to a two dimensional surface.

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!