A* Pathfinding

For JavaScript and Beyond

By Ash Blue / Clever Crow Games / HTML5 in Action / @ashbluewd

What is AI pathfinding?

Process of discovering a path through obstacles
between two points

Just for games?

No! Pathfinding is important for building complex HTML5 apps

Fastest Route
Acquire Resources
Robotics Engineering

Popular Pathfinding Algorithms

A* (Golden Solution)

  • Customizable
  • Fast
  • Reusable
  • Minimal code

A* In Action

Get our hero to the treasure with the shortest path

(click to move)

Break Map Into Voxels

  • Use largest blocks possible
  • Small voxels hurt performance

Identify Tile Types

  • Identify blockers
  • Get walkable tiles with cost
0: Blocked 1: Open 2: Water Start End

Count Steps

  • A* steps examines 1 tile at a time with neighbors (step)
  • Lower step count / distance prioritized

Distance Heuristics

  • Estimates distance to goal
  • Manhattan or Euclidean?
  • Demo uses Manhattan for speed

function euclidean (xC, yC, xT, yT) {
    var dx = xT - xC, dy = yT - yC;
    return Math.sqrt((dx * dx) + (dy * dy));
}

function manhattan (xC, yC, xT, yT) {
    var dx = Math.abs(xT - xC), dy = Math.abs(yT - yC);
    return dx + dy;
}
                        

Heuristic in Action

  • Displayed value is estimated distance to target
  • Accurate in most cases

Open and Closed Sets

  • Open: Yet to be evaluated
  • Closed: Evaluated tile
  • A* Always chooses best open
  • Best open found through heuristic + step cost

Putting Everything Together

  • Total = Steps + Heuristic
  • Click for interactive walkthrough

Map API

Method Overview

  1. setMap
  2. outOfBounds
  3. getNeighbors

setMap

  • Break map down to voxels
  • Use a multi-dimensional array (usually 2D)
  • HTML/CSS users loop through data via jQuery
  • Complex games require looking at multiple maps (collision, entities, other)

OutOfBounds

  • Check for overflowing indices on map data
  • Prevents errors from crashing the app

window.Map = window.Class.extend({
    ...
    outOfBounds: function (x, y) {
        return x < 0 || x >= this.data[0].length ||
        y < 0 || y >= this.data.length;
    },
    ...
});

GetNeighbors

  • Find all open adjacent tiles
  • Tweak for diagonal by returning corners here
  • Add 3D z-index by returning tiles above and below

window.Map = window.Class.extend({
    ...
    getNeighbors: function (x, y) {
        var neighbors = [];

        // Check top, right, bottom, left (clockwise)
        if (!this.blocked(x, y - 1)) neighbors.push(new window.Tile(x, y - 1));
        if (!this.blocked(x + 1, y)) neighbors.push(new window.Tile(x + 1, y));
        if (!this.blocked(x, y + 1)) neighbors.push(new window.Tile(x, y + 1));
        if (!this.blocked(x - 1, y)) neighbors.push(new window.Tile(x - 1, y));

        return neighbors;
    },
    ...
});

Completed Map


window.Map = window.Class.extend({
    data: null, // Current map

    init: function (data) {
        this.data = data;
    },

    outOfBounds: function (x, y) {
        return x < 0 || x >= this.data[0].length ||
            y < 0 || y >= this.data.length;
    },

    getWidthInTiles: function () {
        return this.data[0].length;
    },

    getHeightInTiles: function () {
        return this.data.length;
    },

    blocked: function (x, y) {
        if (this.outOfBounds(x, y)) {
            return true;
        }

        if (this.data[y][x] === 0) {
            return true;
        }

        return false;
    },

    getNeighbors: function (x, y) {
        var neighbors = [];

        if (!this.blocked(x, y - 1)) neighbors.push(new window.Tile(x, y - 1));
        if (!this.blocked(x + 1, y)) neighbors.push(new window.Tile(x + 1, y));
        if (!this.blocked(x, y + 1)) neighbors.push(new window.Tile(x, y + 1));
        if (!this.blocked(x - 1, y)) neighbors.push(new window.Tile(x - 1, y));

        return neighbors;
    },


    getCost: function (xC, yC, xT, yT) {
        return this.data[yT][xT];
    }
});
                        

Pathfinder API

  • Navigates through map data
  • Each creature will need its own pathfinder
  • Returns a completed path that can be navigated

Topic Overview

  1. Close commands
  2. Open commands
  3. findPath Walkthrough
  4. Assembling a path

Close Commands

Simple interface to manage closed tiles


window.PathFinder = window.Class.extend({
    ...
    // New closed tile
    addClosed: function (step) {
        this.addHistory(step, 'closed');
        this.closed.push(step);
        return this;
    },

    // Check for existing closed tile
    inClosed: function (step) {
        for (var i = 0; i < this.closed.length; i++) {
            if (this.closed[i].x === step.x && this.closed[i].y === step.y)
                return this.closed[i];
        }

        return false;
    },
    ...
});
                        

Open Commands

Used to store and analyze group data


window.PathFinder = window.Class.extend({
    ...
    // Adds a new tile
    addOpen: function (step) {
        this.open.push(step);
        return this;
    },

    // Removes an existing tile
    removeOpen: function (step) {
        for (var i = 0; i < this.open.length; i++) {
            if (this.open[i] === step) this.open.splice(i, 1);
        }
        return this;
    },

    // Check if the step is already in the open set
    inOpen: function (step) {
        for (var i = 0; i < this.open.length; i++) {
            if (this.open[i].x === step.x && this.open[i].y === step.y)
                return this.open[i];
        }

        return false;
    },

    // Get the best possible tile from the open set
    getBestOpen: function () {
        var bestI = 0;
        for (var i = 0; i < this.open.length; i++) {
            if (this.open[i].f < this.open[bestI].f) bestI = i;
        }

        return this.open[bestI];
    },
    ...
});
                        

findPath Walkthrough

This walks through the map API data finds a walkable path


window.PathFinder = window.Class.extend({
    ...
    findPath: function (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 window.Step(xC, yC, xT, yT, this.step, false));

        while (this.open.length !== 0) {
            this.step++;
            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 = this.map.getNeighbors(current.x, current.y);
            for (i = 0; i < neighbors.length; i++) {
                this.step++;

                // Get current step and distance from current to neighbor
                stepCost = current.g + this.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 window.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;
    },
    ...
});
                        

Assembling a path

Assemble walkable path from closed group


window.PathFinder = window.Class.extend({
    ...
    // Recursive path building method
    buildPath: function (tile, stack) {
        stack.push(tile);

        // Look at every parent and step back until no parents are left
        if (tile.parent) {
            return this.buildPath(tile.parent, stack);
        } else {
            return stack;
        }
    },
    ...
});
                        

Completed Pathfinder


window.PathFinder = window.Class.extend({
    map: null, // Map class reference
    closed: null, // Taken steps
    open: null, // Available steps that can be taken
    history: null,
    step: 0, // Step count
    maxSearchDistance: 100, // Maximum number of steps that can be taken before shutting down a closed path

    init: function (map) {
        this.closed = [];
        this.open = [];
        this.history = [];
        this.map = map;
    },

    addOpen: function (step) {
        this.addHistory(step, 'open');
        this.open.push(step);
        return this;
    },

    // Remove a step that already exists by object memory address (not actual x and y values)
    removeOpen: function (step) {
        for (var i = 0; i < this.open.length; i++) {
            if (this.open[i] === step) this.open.splice(i, 1);
        }
        return this;
    },

    // Check if the step is already in the open set
    inOpen: function (step) {
        for (var i = 0; i < this.open.length; i++) {
            if (this.open[i].x === step.x && this.open[i].y === step.y)
                return this.open[i];
        }

        return false;
    },

    // Get the lowest costing tile in the open set
    getBestOpen: function () {
        var bestI = 0;
        for (var i = 0; i < this.open.length; i++) {
            if (this.open[i].f < this.open[bestI].f) bestI = i;
        }

        return this.open[bestI];
    },

    addClosed: function (step) {
        this.addHistory(step, 'closed');
        this.closed.push(step);
        return this;
    },

    // Check if the step is already in the closed set
    inClosed: function (step) {
        for (var i = 0; i < this.closed.length; i++) {
            if (this.closed[i].x === step.x && this.closed[i].y === step.y)
                return this.closed[i];
        }

        return false;
    },

    addHistory: function (step, group) {
        this.history.push({
            step: step,
            group: group
        });
    },

    findPath: function (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 window.Step(xC, yC, xT, yT, this.step, false));

        while (this.open.length !== 0) {
            this.step++;
            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 = this.map.getNeighbors(current.x, current.y);
            for (i = 0; i < neighbors.length; i++) {
                this.step++;

                // Get current step and distance from current to neighbor
                stepCost = current.g + this.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 window.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;
    },

    // Recursive path buliding method
    buildPath: function (tile, stack) {
        stack.push(tile);

        if (tile.parent) {
            return this.buildPath(tile.parent, stack);
        } else {
            return stack;
        }
    },

    reset: function () {
        this.closed = [];
        this.open = [];
        return this;
    }
});
                        

Pathfinding with gravity

For use with platformers and other games requiring gravity

Clearance values

For when moving characters takes up more than one tile

  • Just a few lines for A*
  • Requires an extra map of data

Tutorial

Boxed JS pathfinding solutions

Not many solutions out there yet. Most are weekend hack projects (not maintained). These are two of the best.

More learning resources

Any Questions?