A* Pathfinding

A* pathfinding is a pathfinding algorithm very commonly used in games because of its performance in small-to-medium-sized node graphs, its reliability in finding the shortest path from A to B, and its ability to be tweaked and modified. This makes it ideal for determining a path from one entity located on a node graph to another, for example in the case of an angry dungeon-dwelling goblin trying to find the shortest path to the intruding player.

The specific algorithm I have implemented boils down to the following:

1. Set the current node to be the starting path node and add it to the open list. The current node is the node we’re currently processing and focusing on. The open list is a list of nodes which have adjacent nodes we haven’t looked at yet.
2. While the open list isn’t empty, do the following:
   1. Add the current node to the closed list and remove it from the open list. The closed list is a list of nodes we’ve finished processing and don’t have to come back to.
   2. For each node adjacent to current node, do the following:
      1. If the adjacent node isn’t traversable or is in the closed list then skip steps 2.2.2 and 2.2.3.
      2. If it’s not already in the open list then add it to the open list and set its parent node to the current node. This is important for generating the actual path later: we need to be able to trace our way back to the starting path node. We now need to calculate the node’s G and H components. The G component is calculated by taking the G component of the current node and adding to it the distance between the current node and the adjacent node. The H here stands for Heuristic, and hence is an approximation of how far the node is from the target node. In my implementation the H component is simply the distance between the node and the target node, ignoring any obstacles.
      3. If the adjacent node is already in the open list then we can check to see if we can improve its G component. All we need to do is compare the current G component with what the G component would be if the current node was its parent. If it’s lower in the latter case then we update the G component with the new value and also update its parent node.
   3. Check to see if the open list is empty. If it is this means that there is no path available and the process stops.
   4. Search the open list for the node with the lowest F component (G + H) and set the current node to it.
   5. Check to see if the current node is now the same as the target node. If it is then we can generate our path. This is simply a case of adding current node to the path, setting current node to the parent node of current node, and repeating this process until current node is the node we started pathfinding from; the start node.
   6. If the open list isn’t empty and we’ve still yet to find our target, then repeat steps (2.1) through (2.4).

While a bit of a mouthful, that’s all there is to it! The actual code that goes along with this implementation is by no means complicated at all and is extremely straight forward. I’ve written an implementation of this algorithm in JavaScript so it can be easily available on the web. While most of the actual JS file consists of code for the UI and utility methods, there are two relevant chunks of code: the findPath() function, and the PathNode class.

First, let’s have a look at the class we’ll be using to represent each node:

// A* PATHFINDING IMPLEMENTATION
// -----------------------------

/**
 * Represents a single node in a larger collection of nodes
 * @param x PathNode X position
 * @param y PathNode Y position
 * @param z PathNode Z position
 * @param walkable Specifies whether the node is traversable or not
 */
function PathNode(x, y, z, walkable) {
    this.pos = new Vec3(x, y, z);
    this.walkable = walkable;

    this.g = 0; // G: distance to path start via linked parent nodes
    this.h = 0; // H: distance to path target (estimated via)
    this.f = 0; // F: Overall score

    this.adjacentNodes = []; // List of nodes that can be accessed from this one
    this.parentNode = null; // The node which this node points back to for when
                            // tracing a path back to the start

    /** Set the parent node of this node */
    this.setParent = function(parentNode) {
        this.parentNode = parentNode;

        // Here the G component of the node is calculated by taking the parent
        // node's G component and increasing it by the
        // distance between the two nodes
        this.g = parentNode.g + Vec3.distance(parentNode.pos, this.pos);

        // Update the F component
        this.f = this.g + this.h;
    }

    /** Set the path's target node */
    this.setTarget = function(targetNode) {
        // The H component of the node is calculated here by finding the distance
        // between this node and the specified target node
        this.h = Vec3.distance(targetNode.pos, this.pos);

        // Update the F component
        this.f = this.g + this.h;
    }
}

While I’m using the word “class” JS is of course a prototypal language where everything is an object. This allows us to use functions in a similar way to how we might use classes in a more Object-Oriented feature-rich language like C++, because these functions can have attributes and can be instantiated.

First of all when we call PathNode to instantiate a new PathNode object, we pass in four parameters: an X, Y, and Z position, and a flag (walkable) which represents whether the node we’re creating is traversable by entities or not. Next we have the properties that are needed for the pathfinding algorithm:

• The three pathfinding scores/components: G, H, and F.
• An array of nodes representing all the nodes which can be directly accessed from this one.
• This node’s parentNode.

Finally we have a couple of methods which the pathfinding algorithm will use to set the node’s G and H components.

That’s all there really is to it; nothing particularly special. The main thing to note regarding this is that it’s designed to be quite flexible. The nodes can be positioned anywhere within 3D space, for example we could have a vast collection of nodes littered across the surface of some 3D terrain, providing us with a system that allows entities to navigate across virtual mountain ranges. Once we have our nodes positioned, the actual links between them exist by the contents of each node’s adjacentNodes array. We might have nodes with just a few nearby neighbours, or we could have some nodes that have a bunch of neighbours, some near, some very far away. However just because we can have these complex node graphs doesn’t mean we have to! We can set up a uniform 2D node graph quite easily, enabling us to use this implementation not just in 3D games with complex terrain, but also 2D games that might have restricted tile-based entity movement - a 2D dungeon crawler for example.

Now that we know how a PathNode works, let’s have a look at the main attraction; the findPath() function itself:

/**
 * Uses the A* Pathfinding algorithm to find a path of nodes between two specified nodes
 * @param startNode The PathNode where the path begins
 * @param targetNode The PathNode we want to search towards
 * @returns The path, if found. Returns an empty array if no path can be found
 */
function findPath(startNode, targetNode) {
    var openList = [startNode]; // Nodes that haven't been processed - initially
                                // just the start node.
    closedList = []; // Nodes that have been processed.
    var currentNode = startNode; // The current node being looked at.

    // Only while we still have nodes to process...
    while (openList.length != 0) {
        // First we swap the node out from the openList and in to the closedList
        closedList.push(currentNode);
        remove(openList, currentNode);

        // For each of the nodes accessible via the current node...
        for (var n = 0; n < currentNode.adjacentNodes.length; n++) {
            var adj = currentNode.adjacentNodes[n];

            // If we can't walk on it, don't bother do anything with it.
            if (adj.walkable) {
                // If we've never touched it before then give it a parent, set the
                // target, and add it to the open list for future processing.
                if (closedList.indexOf(adj) == -1 && openList.indexOf(adj) == -1) {
                    adj.setParent(currentNode);
                    adj.setTarget(targetNode);
                    openList.push(adj);

                } else if (adj.g > currentNode.g + Vec3.minus(currentNode.pos, adj.pos).magnitude())
                    // We've already calculated this nodes F value, but we can check
                    // if we can improve it! If the G value is better when the
                    // current node is the parent, then make the switch.
                    adj.setParent(currentNode);
            }
        }

        var openListLength = openList.length;

        // If there are no more nodes in the open list then we couldn't find a path,
        // return empty handed.
        if (openListLength == 0) {
            return [];
        } else {
            // Find the next node with the lowest F score to be processed.
            currentNode = openList[0];
            for (var n = 1; n < openListLength; n++) {
                if (openList[n].f < currentNode.f)
                    currentNode = openList[n];
            }
        }

        // Check to see if we've found the target node.
        if (currentNode == targetNode) {
            var path = [];
            currentNode = currentNode.parentNode;

            // Simply trace our way back to the start node via all of the parent
            // nodes.
            while (currentNode != startNode) {
                path.push(currentNode);
                currentNode = currentNode.parentNode;
            }

            // The path is back-to-front at the moment with the target at the
            // begginning - so we return the reversed path.
            return path.reverse();
        }
    }
}

The two things the A* pathfinding algorithm needs to know about to do its job are the node where our path begins, and the node where we want our path to take us to - so we pass these in to the function as arguments. As this really is just a direct implementation of the algorithm that was outlined toward the beginning of this post, there’s not much to say about the code. As mentioned before, in terms of actual code it’s relatively simple.

Something worth talking about is the way that the path is generated once the algorithm has been successful. The first thing we do after finding out the node currently being processed is actually the target node is setting the currentNode variable to the target node’s parent:

currentNode = currentNode.parentNode;

This is because this specific implementation is tweaked so that the generated path takes us next to the target, and not on the target. This behaviour is desirable when an entity wants to find another entity, such as when an enemy might want to get near the player to attack them, or an NPC trying to get close to a door to open it. If we did actually want the path to lead us on to the target, then we simply would skip this step. The rest of the path generation is extremely simple and consists of two steps:

• Add currentNode to the path array
• Set currentNode to the parentNode of currentNode
• Repeat the above until currentNode is equal to startNode

Or in actual JavaScript:

while (currentNode != startNode) {
    path.push(currentNode);
    currentNode = currentNode.parentNode;
}

See; easy! We could happily stop there and return the path we’d have at the moment, however I’d like the path the entity recieves to be in the reverse order:

return path.reverse();

To me this makes more sense. This way the index of any given node in the path array corrisponds with how far into the path the node actually is. The node path[0] will be the first node that an entity will travel to on its path, path[1] will be the next, and so on.

You can play around with the implementation here. Prior to having any knowledge of how A* pathfinding worked I found this article by Patrick Lester which explains it excellently.

Update: The link to the article above has since been disabled. There are plenty of online resources out there which do a great job at breaking down and explaining this algorithm if this article doesn’t quite do it for you. Here’s one such example on YouTube.