# Where/how should A Star tie breaking occur?

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?

• 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? Commented Oct 18, 2015 at 18:05
• 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. Commented Oct 18, 2015 at 18:25
• @wondra Look at this... might make it more clear than what i'm saying: codeguru.com/csharp/csharp/cs_misc/designtechniques/article.php/… Commented Oct 18, 2015 at 18:25

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.