Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


A* hysteresis on an arbitrary graph


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 TheComet   Crossbones+   -  Reputation: 1986

Like
0Likes
Like

Posted 14 November 2013 - 12:38 PM

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?


YOUR_OPINION >/dev/null

Sponsor:

#2 ApochPiQ   Moderators   -  Reputation: 17622

Like
0Likes
Like

Posted 14 November 2013 - 12:57 PM

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.

#3 Andy Gainey   Members   -  Reputation: 2577

Like
3Likes
Like

Posted 14 November 2013 - 01:28 PM

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.



"We should have a great fewer disputes in the world if words were taken for what they are, the signs of our ideas only, and not for things themselves." - John Locke




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS