A* Pathfinding Demo

Author: Ash Blue

In tile based games the most popular pathfinding algorithm is A* (pronounced A Star). It allows you to search through tiles on a two-dimensional plane. But can be easily upgraded to allow three-dimensional searching. There are faster algorithms out there, but this one is by far the most customizable and easy to implement.

The following interactive demo focuses on implementing A Star in the context of a tile game. If you wanted to implement it on a two-dimensional sidescroller you may want to think about implementing it differently.Click on the map to toggle blockers.

Set the start/end point by clicking their corresponding buttons. Then click Find Path to activate the demo. For more details see the legend.

Tile Stats Overview

F = Calculated Total

Sum of the heuristic (H) and current step cost (G)

G = Step Cost

Total number of steps required to walk here from the start tile.

H = Heuristic Estimate

Heuristic uses Manhattan distance. Measures distance from current tile to the goal.

Level

Current level of the tile. Rating of 1 - 4. No rating present means a 1 will be assumed.

F G H

Movement Rules

• Player can only move up/down one level at a time. This means a player cannot go from level 1 to 3.
• It costs 2 movement points to move up/down a level.

Implementation Code

For a full overview of how this was implemented please download and review the source code with comments.

function findPath(xC, yC, xT, yT) {
    var current, // Current best open tile
        neighbors, // Dump of all nearby neighbor tiles
        neighborRecord, // Any pre-existing records of a neighbor
        stepCost, // Dump of a total step score for a neighbor
        i;

    // You must add the starting step
    this.reset()
        .addOpen(new jp.Step(xC, yC, xT, yT, this.step, false));

    while (this.open.length !== 0) {
        current = this.getBestOpen();

        // Check if goal has been discovered to build a path
        if (current.x === xT && current.y === yT) {
            return this.buildPath(current, []);
        }

        // Move current into closed set
        this.removeOpen(current)
            .addClosed(current);

        // Get neighbors from the map and check them
        neighbors = jp.map.getNeighbors(current.x, current.y);
        for (i = 0; i < neighbors.length; i++) {
            // Get current step and distance from current to neighbor
            stepCost = current.g + jp.map.getCost(current.x, current.y, neighbors[i].x, neighbors[i].y);

            // Check for the neighbor in the closed set
            // then see if its cost is >= the stepCost, if so skip current neighbor
            neighborRecord = this.inClosed(neighbors[i]);
            if (neighborRecord && stepCost >= neighborRecord.g)
                continue;

            // Verify neighbor doesn't exist or new score for it is better
            neighborRecord = this.inOpen(neighbors[i]);
            if (!neighborRecord || stepCost < neighborRecord.g) {
                if (!neighborRecord) {
                    this.addOpen(new jp.Step(neighbors[i].x, neighbors[i].y, xT, yT, stepCost, current));
                } else {
                    neighborRecord.parent = current;
                    neighborRecord.g = stepCost;
                    neighborRecord.f = stepCost + neighborRecord.h;
                }
            }
        }
    }

    return false;
}

References

• Introductory A* tutorial used to create this demo
• Pseudo-code used to generate this tutorial