A*: In Gratitude for Seunghyop Back's Introduction

Thanks & Introduction

I am writing this article in response to a previous article from seunghyop back titled "Very simple A* algorithm implementation". I prefer more direct means of communication, but I have not found a way to send a message directly to a Code Project user and exchange source code, so I am hoping that I use this site as intended by creating an article instead. This article is not intended as criticism, but as a thank you. I had not set out to share the changes initially, but then thought that I might as well share them, instead of simply letting them sit on my hard disk never to be looked at again. I hope I have followed all applicable etiquette in doing so. I consider the changes mainly suggestions and a matter of taste. I do not mean to start a competition between this and the original code.

Background

To my own shame, I had not familiarized myself with A* until recently even though I have worked as a software engineer for years. From what I have gathered in that short time, A* finds widespread application to this day and is being used in many popular big game titles, to name just one example. I was looking for the quickest possible introduction to A*, with a working implementation to tinker with, in order to make sure I had fully comprehended its algorithm. sounghyop's article is one of the first I stumbled on. Without a particular goal in mind (pun on pathfinding intended), I started tinkering with the source code provided and made some minor changes.

Changes to the Original Code

Here is a list of some changes I have made, in no particular order, with no claim for completeness:

I saw opportunity to replace the container "SortedCostNodeList" with .Net's SortedSet. A challenge here was that Nodes should be sorted by their cost, as defined by A*, so the implementation of IComparer passed to the SortedSet should distinguish nodes based on that attribute. However, SortedSet will ignore insertions of multiple elements it considers equal in value, while the A* implementation had to allow for multiple nodes for a given map location, each with different cost. That is because A*, as it generates a path to the goal node, can generate multiple possible paths that can intersect on the same location at times. If the NodeComparer had been left unchanged, the algorithm would likely get stuck in corners, because unchanged the set would have discarded nodes that would equal previous nodes on the map that should be left in the list "open" of not yet fully explored nodes.

I hope that the above explanation for the changes below made sense. If not, try to use the new implementation with the old IComparer implementations, run a few examples, and I am sure you will quickly come across examples where the algorithm will end a path in front of an obstacle, unable to backtrack its way around it. 

class NodeComparer : IComparer<Node>
{
    int IComparer<Node>.Compare(Node n1, Node n2)
    {
        if (n1.TotalCost == n2.TotalCost)
        {
            if (n1.X == n2.X && n1.Y == n2.Y)
            {
                return 0;
            }

            // Allow multiple nodes of equal cost but different coordinates.
            return -1;
        }

        return n1.TotalCost - n2.TotalCost;
    }
}

I have given such a long explanation in part because this change in the NodeComparer now allows to replace the original "SortedCostNodeList" of around 75 lines of code simply with the following:

public class NodeSet : SortedSet<Node>
{
    public NodeSet() : base(new NodeComparer()) { }
}

All operations and properties required by A* can be provided and are guaranteed by SortedSet. I have chosen this collection, because it seemed to provide the simplest interface for reducing the existing code. I have tried to simplify coding of the algorithm and did not intend to initially consider or discuss asymptotic runtime complexity at this time. That being said, I think one could improve the linear lookup that appears to be made in the method to determine better nodes than the current successor (or adjacent node) by filtering down candidates in the node sets to only those with a lower cost. The sets are already sorted by node cost, so one could avoid traversing the entire iterator of nodes. In particular, there is "GetViewBetween", but I have not spent time on looking at its possible benefits.

With these changes, some refactoring, and a little bit of Linq to increase expressiveness of operations on collections, the top level of the A* implementation was reduced to the following:

public static Node FindPath(Location start, Location goal)
{
    Node goalNode = new Node(goal);
    Node startNode = new Node(start, goalNode);

    NodeSet open = new NodeSet() {startNode};
    NodeSet closed = new NodeSet();

    while (open.Any())
    {
        Node best = open.Min;
        open.Remove(best);

        if (best.Coincides(goalNode))
        {
            goalNode.Parent = best.Parent;
            break;
        }

        foreach (Node successor in best.ConnectedNodes())
        {
            Node betterOpen = open.NodesBetterThan(successor);
            if (betterOpen != null)
            {
                continue;
            }

            Node betterClosed = closed.NodesBetterThan(successor);
            if (betterClosed != null)
            {
                continue;
            }

            if (betterOpen != null)
            {
                open.Remove(betterOpen);
            }

            if (betterClosed != null)
            {
                closed.Remove(betterClosed);
            }

            if (betterClosed == null && betterOpen == null)
            {
                open.Add(successor);
            }
        }

        closed.Add(best);
    }

    return goalNode;
}

Compared to the original, I have left the main code flow intact. I wanted to move as much code as possible that is not essential to the A* algorithm out of the main method, hoping to make its mechanics even more crisp and easy to grasp.

In my experience Linq code can easily result in taking up a significant portion of the overall runtime, so one needs to be careful particularly when using it in the main loop of an algorithm like this. I have not profiled this implementation, so I do not know how much it is actually taking up, but I am using it here, because I felt that some operations of the algorithm can be implemented in a particularly expressive and compact way by using Linq, such as the following:

public static class NodeSetExtensions
{
    public static Node NodesBetterThan(this NodeSet set, Node node)
    {
        return set.Where(n => node.TotalCost > n.TotalCost && n.Coincides(node)).FirstOrDefault();
    }
}

The above is implemented as an extension method, because I felt that the concept of "all nodes better than a given node" is much more cleanly expressed as the property of a set of nodes than as an independent operation on a set of nodes, which one could have implemented as a regular static method. Refer back to the code of the A* main loop above to see its use and compare how the code would "feel" if it were a regular method, instead of an extension.

There are other changes. Mostly, they implemented equivalent functionality. As far as I recall, there is just one change I made for convenience's sake: you can now "draw" start and goal position into the map. Failure to do so will actually result in an exception that I have not cared to handle so far.

Using the code

Draw a map to see A* at work! The map is now an array of strings, so you do not need to set commas all over anymore. Here is an example:

static string[] MapData = 
{
"    #######################              #####                      ",
"                  ####             #############  #####     ",
"     ####                #####        ##########                   ",
"     S###   ######            ##      ##############                   ",
"     ########    #                 #############                   ",
"            # #  #########                                        ",
"            # #        ###    ###   ###### ######                   ",
"            #G########  ##            #### ##########                 ",
"            #####      ###    ###########  ####                         ",
"             #        ############  ###                          ",
"             #                                    ",
};

In the above, "S" stands for "Start" (not for "sucks"), "G" stands for "Goal". Here is the path we end up with:

#######################              #####
 oooo     o   ####             #############  #####
o####oo oo ooo       #####oo      ##########
 o###  o######o  oo oo  oo##o     ##############
 ######## oo # oo  o  oo     o #############
        #o# o#########        oooooooo
        #o#  ooooo ###    ###   ######o######
        #o########o ##            ####o##########
        #####     o###    ###########o ####
         #       o############  ### o
         #        oooooooooooooooooo

Points of Interest

It was interesting for me to experience the zigzags A* can reportedly make first hand. It may be obvious for those already more familiar with A* than I was, but seeing concrete examples of it made it far more illustrative than trying to divine examples of these cases in your head alone. If you look at the above example, they can be seen clearly, mainly around obstacles.

It is important to understand that these do not impact the overall length of the path. If you compare every zig-zag with the number of nodes it would have taken to complete a straight line instead, you will be satisfied to see that the number of nodes would be the same in every case. The above example in particular contains a section around the middle of the path that, on first sight, appears to take a complete detour. However, the four steps it inserted in a right-upward diagonal direction would have been needed even if the path had been a straight line to the "entrance of the narrow hallway" to the right. If we were to disallow diagonal steps, which could easily be done by limiting the method "Node::ConnectedNodes", A* would drop those paths as it explores routes to the goal node in favor of shorter, straighter paths.