Skip to content

Instantly share code, notes, and snippets.

@paularmstrong
Forked from jminor/a_star.js
Created May 27, 2011 02:33
Show Gist options
  • Save paularmstrong/994534 to your computer and use it in GitHub Desktop.
Save paularmstrong/994534 to your computer and use it in GitHub Desktop.
A* path finding algorithm for impactjs game engine
/**
* AStar
*
* Created by Paul Armstrong on 2011-05-26.
* Copyright (c) 2011 Paul Armstrong Designs. All rights reserved.
*
* Based on: https://gist.github.com/827899
*/
ig.module('plugins.a-star')
.requires(
'impact.game'
)
.defines(function () {
PathFinderNode = function (pos, parent) {
var tileSize = ig.game.collisionMap.tilesize;
this.x = Math.floor(pos.x);
this.y = Math.floor(pos.y);
this.parent = parent;
this.g = -1;
this.h = -1;
this.f = -1;
this.hash = this.x + ',' + this.y;
this.closed = false;
};
PathMapNode = function (x, y, v) {
this.x = x;
this.y = y;
this.v = v;
};
PathFinder = ig.Class.extend({
start: null,
end: null,
board: null,
columns: null,
rows: null,
init: function (startEnt, endEnt, settings) {
this.columns = ig.game.collisionMap.width;
this.rows = ig.game.collisionMap.height;
this.tilesize = ig.game.collisionMap.tilesize;
this.start = new PathFinderNode({
x: (startEnt.pos.x / this.tilesize),
y: (startEnt.pos.y / this.tilesize)
}, -1);
this.end = new PathFinderNode({
x: ((endEnt.pos.x + endEnt.size.x / 2) / this.tilesize),
y: ((endEnt.pos.y + endEnt.size.y / 2) / this.tilesize)
}, -1);
this.board = this.getBoard(startEnt.size.x / 2);
// for (var i = 0; i < this.board.length; i++) {
// console.log(this.board[i]);
// }
ig.merge(this, settings);
},
getBoard: function (radius) {
var map = ig.game.collisionMap.data,
board = [],
tboard = map,
c = this.columns,
r = this.rows,
s = Math.ceil(radius / this.tilesize),
j = r, k = c,
node, neighbors, n, l, m;
while (s--) {
j = r;
board = [];
while (j--) {
k = c;
board.unshift([]);
while (k--) {
v = tboard[j][k];
node = new PathMapNode(k, j);
neighbors = this.getNodeNeighbors(node);
l = neighbors.length;
board[0][k] = v;
while (l--) {
n = neighbors[l];
if (tboard[n.y][n.x]) {
board[0][k] = 1;
continue;
}
}
}
}
tboard = board;
}
return board;
},
getPath: function () {
var nodes = {}, //Map of nodes hashed by node.hash
open = [], //List of open nodes (nodes to be inspected)
closed = [], //List of closed nodes (nodes we've already inspected)
g = 0, //Cost from start to current node
h = this.getHeuristic(this.start, this.end), //Cost from current node to destination
f = g + h, //Cost from start to destination going through the current node
bestCost, bestNode,
currentNode,
nNodes, nNode, exNode,
isEnd, fOpen,
path, fPath = [],
q;
//Push the start node onto the list of open nodes
open.push(this.start);
nodes[this.start.hash] = this.start;
nodes[this.end.hash] = this.end;
//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
bestCost = open[0].f;
bestNode = 0;
q = 1;
for (q; q < open.length; q++) {
if (open[q].f < bestCost) {
bestCost = open[q].f;
bestNode = q;
}
}
currentNode = open[bestNode];
//Check if we've reached our destination
if (currentNode.x === this.end.x && currentNode.y === this.end.y) {
path = [this.end]; //Initialize the path with the destination node
//Go up the chain to recreate the path
while (currentNode.parent !== -1) {
currentNode = closed[currentNode.parent];
path.unshift(currentNode);
}
q = path.length;
while (q--) {
fPath.unshift({
x: path[q].x * this.tilesize,
y: path[q].y * this.tilesize
});
}
return fPath;
}
//Remove the current node from our open list
open.splice(bestNode, 1);
//Push it onto the closed list
closed.push(currentNode);
currentNode.closed = true;
//Expand our current node (look in all 8 directions)
nNodes = this.getNodeNeighbors(currentNode);
q = 0;
for (q; q < nNodes.length; q++) {
nNode = nNodes[q];
isEnd = (this.end.x === nNode.x && this.end.y === nNode.y);
if (this.board[nNode.y][nNode.x] === 0 || isEnd) //or the new node is our destination
{
// Do we already know about this node?
fClose = false;
exNode = nodes[nNode.hash];
if (exNode) {
if (exNode.closed) {
continue;
} else {
// normally we would say this: fClose = true;
// but the destination is never in either list
fClose = !isEnd;
}
}
//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 (!fClose || isEnd) {
ig.merge(nNode, {
parent: closed.length - 1,
g: currentNode.g + this.getHeuristic(currentNode, nNode),
h: this.getHeuristic(nNode, this.end)
});
nNode.f = nNode.g + nNode.h;
open.push(nNode);
nodes[nNode.hash] = nNode;
}
}
}
}
return [];
},
getNodeNeighbors: function (node) {
var nodes = [],
x = Math.max(0, node.x - 1),
xMax = Math.min(this.columns - 1, node.x + 1),
y, yMax = Math.min(this.rows - 1, node.y + 1);
for (x; x <= xMax; x++) {
y = Math.max(0, node.y - 1);
for (y; y <= yMax; y++) {
nodes.push(new PathFinderNode({ x: x, y: y }, -1));
}
}
return nodes;
},
getHeuristic: function (start, end) {
var x = start.x - end.x,
y = start.y - end.y;
// stepped route
return Math.sqrt(x * x + y * y);
// most direct route
// return (x * x) + (y * y);
}
});
});
@Joncom
Copy link

Joncom commented Dec 29, 2019

The v property of PathMapNode is never used.

Edit 1: Also the fOpen variable in the getPath function is never used.

Edit 2: Also the f variable declared in getPath function is never used.

Edit 3: Same goes for g and h in getPath function.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment