A* path finding algorithm for impactjs game engine

a_star.js

// A* path finding algorithm for impactjs game engine
// adapted from http://stormhorse.com/a_star.js
// via http://46dogs.blogspot.com/2009/10/star-pathroute-finding-javascript-code.html
// impact-ified by jminor - http://pixelverse.org/

/* Example:
	this.pathFinder = new PathFinder();

	var start = [((this.pos.x+this.size.x/2) / tilesize).floor(), ((this.pos.y+this.size.y/2) / tilesize).floor()];
	var destination = [((target.pos.x+target.size.x/2) / tilesize).floor(), ((target.pos.y+target.size.y/2) / tilesize).floor()];
	var board = ig.game.collisionMap.data;
	var columns = ig.game.collisionMap.width;
	var rows = ig.game.collisionMap.height;

	this.plan = this.pathFinder.a_star(start, destination, board, columns, rows);

	if (this.plan && this.plan.length > 0)
		this.moveTowards(this.plan[0]);
*/

ig.module( 
	'game.a_star' 
)
.requires(
	'impact.game'
)
.defines(function(){

Node = ig.Class.extend({
    /* Each node will have these properties: 
     X position
     Y position
     Index of the node's parent in the closed array
     Cost from start to current node (g)
     Heuristic cost from current node to destination (h)
     Cost from start to destination going through the current node (f)
	 Hash to uniquely identify this node quickly
	 Closed bit to quickly tell if this node is in the open or closed list
    */

    init: function(x, y, parent_index)
    {
    	this.x = x;
    	this.y = y;
    	this.parent_index = parent_index;
    	this.g = -1;
    	this.h = -1;
    	this.f = -1;
		this.hash = ""+x+","+y;
		this.closed = false;
    }	
});

PathFinder = ig.Class.extend({
	
	init: function() {
	},

    a_star: function(start, destination, board, columns, rows)
    {
    	//Create start and destination as true nodes
    	start = new Node(start[0], start[1], -1);
    	destination = new Node(destination[0], destination[1], -1);

		var nodes = {}; //Map of nodes hashed by node.hash
    	var open = []; //List of open nodes (nodes to be inspected)
    	var closed = []; //List of closed nodes (nodes we've already inspected)

    	var g = 0; //Cost from start to current node
    	var h = this.heuristic(start, destination, board, columns, rows); //Cost from current node to destination
    	var f = g+h; //Cost from start to destination going through the current node

    	//Push the start node onto the list of open nodes
    	open.push(start);
		nodes[start.hash] = start;
		nodes[destination.hash] = destination;

    	//Keep going while there's nodes in our open list
    	while (open.length > 0)
    	{
    		//Find the best open node (lowest f value)

    		//Alternately, you could simply keep the open list sorted by f value lowest to highest,
    		//in which case you always use the first node
    		var best_cost = open[0].f;
    		var best_node = 0;

    		for (var i = 1; i < open.length; i++)
    		{
    			if (open[i].f < best_cost)
    			{
    				best_cost = open[i].f;
    				best_node = i;
    			}
    		}

    		//Set it as our current node
    		var current_node = open[best_node];

    		//Check if we've reached our destination
    		if (current_node.x == destination.x && current_node.y == destination.y)
    		{
    			var path = [destination]; //Initialize the path with the destination node

    			//Go up the chain to recreate the path 
    			while (current_node.parent_index != -1)
    			{
    				current_node = closed[current_node.parent_index];
    				path.unshift(current_node);
    			}

    			return path;
    		}

    		//Remove the current node from our open list
    		open.splice(best_node, 1);

    		//Push it onto the closed list
    		closed.push(current_node);
			current_node.closed = true;

    		//Expand our current node (look in all 8 directions)
			var new_nodes = this.neighbors(current_node, board, columns, rows);
			for (var node_index=0; node_index<new_nodes.length; node_index++) {
				var new_node = new_nodes[node_index];
				var is_destination = (destination.x == new_node.x && destination.y == new_node.y);
				if (board[new_node.y][new_node.x] == 0 //If the new node is open
					|| is_destination) //or the new node is our destination
				{
					// Do we already know about this node?
					var found_in_closed = false;
					var found_in_open = false;
					var existing_node = nodes[new_node.hash];
					if (existing_node) {
						if (existing_node.closed) {
							found_in_closed = true;
						}else{
							// normally we would say this: found_in_open = true;
							// but the destination is never in either list
							found_in_open = !is_destination;
						}
					}

					//If the node is already in our closed list, skip it.
					if (found_in_closed) {
						continue;
					}

					//If the node is in our open list, use it.  Also use it if it is the destination (which is never in either list)
					if (!found_in_open || is_destination)
					{
						//var new_node = new Node(new_node.x, new_node.y, closed.length-1);
						new_node.parent_index = closed.length-1;

						new_node.g = current_node.g + this.heuristic(current_node, new_node, board, columns, rows);
						new_node.h = this.heuristic(new_node, destination, board, columns, rows);
						new_node.f = new_node.g+new_node.h;
						
						if (isNaN(new_node.g) || isNaN(new_node.h) || isNaN(new_node.f)) {
							console.log("NaN heuristic?", new_node);
							debugger;
						}

						open.push(new_node);
						nodes[new_node.hash] = new_node;
					}
				}
			}
    	}

    	return [];
    },

	neighbors: function(current_node, board, columns, rows)
	{
		var nodes = [];
		for (var new_node_x = Math.max(0, current_node.x-1); new_node_x <= Math.min(columns-1, current_node.x+1); new_node_x++)
			for (var new_node_y = Math.max(0, current_node.y-1); new_node_y <= Math.min(rows-1, current_node.y+1); new_node_y++)
			{
				nodes.push(new Node(new_node_x, new_node_y, -1));
			}
		return nodes;
	},

    //An A* heurisitic must be admissible, meaning it must never overestimate the distance to the goal.
    //In other words, it must either underestimate or return exactly the distance to the goal.
    heuristic: function(current_node, destination, board, columns, rows)
    {
    	//Find the straight-line distance between the current node and the destination.
        var x = current_node.x-destination.x;
        var y = current_node.y-destination.y;
        return x*x+y*y;  // this is faster and doesn't seem to change the results
        // return Math.sqrt(x*x + y*y);
        // return Math.sqrt(Math.pow(current_node.x-destination.x, 2)+Math.pow(current_node.y-destination.y, 2));
    }

});

});