Skip to content

Instantly share code, notes, and snippets.

@jminor
Created February 15, 2011 17:49
Show Gist options
  • Star 10 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save jminor/827899 to your computer and use it in GitHub Desktop.
Save jminor/827899 to your computer and use it in GitHub Desktop.
A* path finding algorithm for impactjs game engine
// 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));
}
});
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment