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

Brute Force
Monte Carlo
Dijkstra
Many others

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

Abstracts map data from pathfinder
Most A* customization happens here
Using John Resig's Simple JavaScript Inheritance
for instances

Method Overview

setMap
outOfBounds
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

Close commands
Open commands
findPath Walkthrough
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

JavaScript library: Pathfinding Platformer
Currently used for A Dragon Named Coal's companion system
Trick to A* with gravity is figuring out where you can't move and ledge dropoffs

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?

Stay in contact: @ashbluewd
Get the slides: http://tim.pe/30q