2
\$\begingroup\$

I've recently written a path finding script that utilizes a basic implementation of the A Star algorithm. It works fine but is not very fast. This is due, at least in part, to the fact that it isn't optimized at all. Through a bit of searching through this site and others I've realized that at least one thing I need is a tie breaking procedure that updates the heuristic values of nodes in the open list. Currently, whenever the pathfinder function is initiated. The pattern the finder takes pretty much expands outward in all directions from the point of origin until the target node is found. I've seen several videos that show A Star almost immediately traveling towards the target node thus eliminating many checks and ultimately speeding up the process. I believe this is due to a tie breaking procedure.

My question is... At what point in the process should I be applying the tie breaking procedure and is there a better modifier to add to the heuristic aside from the below code?:

Node.heuristic += (Mathf.Abs((Node.x * endNodeVector.z) - (endNodeVector.x * Node.z)) * 0.001F);

This seems to be the most common that I have found. However, for some reason, this doesn't seem to effect the algorithm at all. It still searches in all directions from the origin position. What am I missing to make my A Star favor open list nodes that are closer to the target?

Improve this question
\$\endgroup\$
3
  • \$\begingroup\$ Why are you multiplying X by Z? Apart from that, do you choose the node with the lowest f+h or just pick the first on -unsorted- list? \$\endgroup\$
    – wondra
    Oct 18, 2015 at 18:05
  • \$\begingroup\$ The original implementation ( no tie breaking modifier added to the h) chooses the first occurrence of the lowest f value in the open list. The line of code I provided in the question is the heuristic being modified for tied lowest f values in the open list. The intention of the modifier is to make the farther from target tied node have a slightly higher h (and f) than the node with the shortest distance to target. The multiplication of the node.x and endNode.z creates a modifier to apply to the heuristic. \$\endgroup\$
    – GeoJohn
    Oct 18, 2015 at 18:25
  • \$\begingroup\$ @wondra Look at this... might make it more clear than what i'm saying: codeguru.com/csharp/csharp/cs_misc/designtechniques/article.php/… \$\endgroup\$
    – GeoJohn
    Oct 18, 2015 at 18:25

1 Answer 1

Reset to default
1
\$\begingroup\$

The tie-breaker is the heuristic.

The next node to process is the one with the lowest f = g+h where g is the known cost from start to the node and h is the estimated cost from the node to the destination.

To guarantee you get the shortest path this h must underestimate the remaining cost. A common one is the path as the crow flies.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ I was thinking that tie breaking applied to a situation where you have two or more nodes that all have the lowest F value. In other words... Say there are two nodes in the open list with an F value of 4 and all other nodes in the list have an F value of 5 or more. Is it not important to choose the node that is closest to the target of the tied nodes? \$\endgroup\$
    – GeoJohn
    Oct 18, 2015 at 19:19
  • \$\begingroup\$ @GeoJohn no because both have the same expected cost for the total path to the goal. After you expand that node the list will contain the 4 value still and the neighbors will likely be larger. \$\endgroup\$
    – ratchet freak
    Oct 18, 2015 at 19:35
  • \$\begingroup\$ Okay, that makes sense. It seams that I was thinking about the whole tie breaking thing incorrectly. Also, on another note... I just realized that a problem I had was using an h value calculation that wasn't proportional to the g value. I was using 1 and 1.4 multiplied by 10 for my G cost but not multiplying my h by 10. This was causing a large number of nodes to be unnecessarily expanded. \$\endgroup\$
    – GeoJohn
    Oct 18, 2015 at 20:38
  • 1
    \$\begingroup\$ @GeoJohn that way, you accidentally learned how A* really work. The speed of convergence(or divergence!) is determined by "quality" of heuristic, by choosing poor(too low) h the algorithm moved in somewhat correct direction but was not particularly fast. \$\endgroup\$
    – wondra
    Oct 18, 2015 at 22:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .