A* Implementation for Thief of Thieves

astar.js

/*!
 * A* pathfinding algorithm implementation based on the the pseudo-code
 * from the Wikipedia article (http://en.wikipedia.org/wiki/A_star)
 * Date: 02/05/2013
 */

"use strict";

// Node of the search graph
function GraphNode(x, y) {
    this.x = x;
    this.y = y;
    this.hash = x + "" + y;
    this.f = Number.POSITIVE_INFINITY;
}

// Constructor for the pathfinder. It takes a grid which is an array of arrays
// indicating whether a position is passable (0) or it's blocked (1)
function AStar(grid) {
    // Compares to nodes by their f value
    function nodeComparer(left, right) {
        if (left.f > right.f) {
            return 1;
        }

        if (left.f < right.f) {
            return -1;
        }

        return 0;
    }

    // Manhattan heuristic for estimating the cost from a node to the goal
    function manhattan(node, goal) {
        return Math.abs(node.x - goal.x) + Math.abs(node.y - goal.y);
    }

    // Gets all the valid neighbour nodes of a given node (diagonals are not
    // neighbours)
    function getNeighbours(node) {
        var neighbours = [];

        for (var i = -1; i < 2; i++) {
            for (var j = -1; j < 2; j++) {
                // Ignore diagonals
                if (Math.abs(i) === Math.abs(j)) {
                    continue;
                }

                // Ignore positions outside the grid
                if (node.x + i < 0 || node.y + j < 0 ||
                    node.x + i >= grid[0].length || node.y + j >= grid.length) {
                    continue;
                }

                if (grid[node.y + j][node.x + i] === 0) {
                    neighbours.push(new GraphNode(node.x + i, node.y + j));
                }
            }
        }

        return neighbours;
    }

    // Builds the path needed to reach a target node from the pathfinding information
    function calculatePath(parents, target) {
        var path = [];

        var node = target;
        while (typeof node !== "undefined") {
            path.push([node.x, node.y]);
            node = parents[node.hash];
        }

        return path.reverse();
    }

    // Searches for a path between two positions in a grid
    this.search = function(start, end) {
        var fCosts = new BinaryHeap([], nodeComparer);
        var gCosts = {};
        var colors = {};
        var parents = {};

        // Initialization
        var node = new GraphNode(start[0], start[1]);
        var endNode = new GraphNode(end[0], end[1]);
        node.f = manhattan(node, endNode);

        fCosts.push(node);
        gCosts[node.hash] = 0;

        while (!fCosts.isEmpty) {
            var current = fCosts.pop();

            // Have we reached our goal?
            if (current.x === endNode.x && current.y === endNode.y)
            {
                return calculatePath(parents, endNode);
            }

            // Mark the node as visited (Black), and get check it's neighbours
            colors[current.hash] = "Black";

            var neighbours = getNeighbours(current);
            for (var i = 0; i < neighbours.length; i++)
            {
                var neighbour = neighbours[i];

                if (colors[neighbour.hash] === "Black") {
                    continue;
                }

                // If we had not visited the neighbour before, or we have found a faster way to visit the neighbour, then update g and calculate f
                if (typeof gCosts[neighbour.hash] !== "Undefined" || gCosts[current.hash] + 1 < gCosts[neighbour.hash]) {
                    parents[neighbour.hash] = current;
                    gCosts[neighbour.hash] = gCosts[current.hash] + 1;
                    neighbour.f = gCosts[neighbour.hash] + manhattan(neighbour, endNode);

                    // Neighbour not visited before, mark it as a potential candidate ("Gray")
                    if (typeof colors[neighbour.hash] !== "Undefined") {
                        colors[neighbour.hash] = "Gray";
                        fCosts.push(neighbour);
                    }
                    else { // We have found a better way to reach this node
                        fCosts.decreaseItem(neighbour);
                    }
                }
            }
        }

        return [];
    };
}