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

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

Break Map Into Voxels

• Use largest blocks possible
• Small voxels hurt performance

Identify Tile Types

• Identify blockers
• Get walkable tiles with cost

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

• 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

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.

• EasyStar
• PathFinding.js

More learning resources

• Introduction to A*
• A* for any language (pseudo code)