Two earlier posts (An A* Drama and A Cross-Country A*) introduced the A* algorithm, how it manages to find the shortest path (more on this below), and how it can also handle terrain costs.  This post was meant to cover a minor point that was purposely omitted until now.

Unfortunately, this post must also serve as a mea culpa in which I need to apologize for a gross error in my previous two explanations.  The error became apparent as I worked up this column for last month’s installment and the discovery of the error derailed that post in favor of the one on compression and the pigeon hole principle.

In the previous two A* posts, the explanation stated that the scoring of the spots placed on the open list consisted of two parts: 1) the terrain cost (the cost to move onto the spot) and 2) the heuristic cost (an estimate of how far the spot is from the goal).  I forgot to include the total cost from the starting space, which is the sum total of all the movement costs to get to that spot.  Tracking that cost is vital to performing the re-parenting step that takes out any ‘kinks’ in the path that result from random choices the algorithm must make when picking between two spots of equal cost.

Despite this omission, the algorithm actually performed quite well in the two cases examined and it found the shortest pay in the wayfarer example (A Cross-Country A*) where the terrain costs were the primary driver and no obstacles were present.  It fared slightly worse in the original example with the angry snake and the man who poked him (An A* Drama), finding almost the shortest path, being only one step too long.  Sadly, that error escaped my notice for some time.

Fortunately, the error came and presented itself quite clearly when I returned to the snake v. man drama to explain re-parenting.   To see what re-parenting involves consider this step in the snake’s pursuit of his vengeance.

Faced with two spaces, (7,1) and (7,2), with the same total cost of 8 – 1 for terrain (upper right) and 4 for the heuristic (lower left), for a movement cost of 5 (lower right), and a cost of 3 steps from the starting space (black square in the center) – the snake randomly chooses to explore gird space (7,2).  Doing so opens up (i.e. places on the open list) spots (7,1), (8,1), (6,2), (8,2), (6,3), (7,3), and (8,3), parents them all to (7,2), and scores them all as having a total cost from the starting space of 4, since any path to these spaces must first go through (7,2), which is 3 steps away from the starting space.

The key point to note, is that the shortest path from the starting space to spaces (6,3) and (7,3) (for a total cost from start of 3) passes through spot (6,2), which is not explored first because of its greater cost.  As a result, the current path to either (6,3) or (7,3) first goes past them to the right while it approaches from below before going back to the left as it arrives; the last three spots in the path are connected as (6,1) -> (7,2) -> (6,3).  Because of its shape, I call such a sub-optimal path a kink.

Now that we recognized the kink, what are we to do with it?  Well, for the time being we just let it alone.  When the algorithm finally explores one of these points, we simply look to see if shifting its parent from (7,2) to some other nearby space will lower the total cost from the starting spot.  If so, then the parent is changed and the algorithm continues essentially unchanged.

To be concrete, consider the situation a bit further in the snake’s search for a path to his foe.  After meandering in the lower right for a while, the snake’s exploration has carried him to space (7,3), which, as a reminder, has received a total cost from the start space of 4 and which is parented to (7,2).

As the snake explores space (7,3), he looks around to see if re-parenting the space to any of the neighboring spaces will lower the total cost from the starting space.  He notes that re-parenting (7,3) to (6,2) will lower that total cost from the starting space by 1 and he does so.  The box containing the new cost has been colored orange to reflect this change.

Because (7,4) had been opened and scored when (8,3) was explored, it also will be re-parented when the snake recognizes the strategic importance of slithering through (7,4).

The final path requires the snake to make 10 steps to reach his victim.

It is a matter of a few minutes of playing with other paths to convince oneself that this is the smallest cost to wreak his revenge.  Of course, the path passing through (6,3) -> (7,4) is equally short but won’t be found by the A* since the heuristic scoring tends to pull the paths to the right even though the ‘escape route’ requires moving to the left.  Also note, that without re-parenting, the kink would have cost an extra step, driving the total cost to 11.

So, there you have it.  A corrected and complete presentation of the A* algorithm.  Sorry for the confusion, but, at least, the error helped to frame the importance of re-parenting in finding the shortest path.