Skip to content

Instantly share code, notes, and snippets.

@chrishamant
Created August 24, 2011 14:28
  • Star 14 You must be signed in to star a gist
  • Fork 7 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save chrishamant/1168189 to your computer and use it in GitHub Desktop.
A* pathfinding
/**
* A* (A-Star) Pathfinding Algorithm in JavaScript
* @author Matthew Trost
* @license Creative Commons Attribution-ShareAlike 3.0 Unported License
* @datepublished December 2010
*/
function astar (map, heuristic, cutCorners) {
var listOpen = [];
var listClosed = [];
var listPath = [];
var nodeGoal = createTerminalNode(map, heuristic, "g", null);
var nodeStart = createTerminalNode(map, heuristic, "s", nodeGoal);
addNodeToList(nodeStart, listOpen);
var n;
while (!isListEmpty(listOpen)) {
n = returnNodeWithLowestFScore(listOpen);
addNodeToList(n, listClosed);
removeNodeFromList(n, listOpen);
if (areNodesEqual(n, nodeGoal)) {
pathTo(n, listPath);
listPath.reverse();
return listPath;
}
n.makeChildNodes(map, heuristic, cutCorners, nodeGoal);
cullUnwantedNodes(n.childNodes, listOpen);
cullUnwantedNodes(n.childNodes, listClosed);
removeMatchingNodes(n.childNodes, listOpen);
removeMatchingNodes(n.childNodes, listClosed);
addListToList(n.childNodes, listOpen);
}
return null;
}
function pathTo (n, listPath) {
listPath.push(new NodeCoordinate(n.row, n.col));
if (n.parentNode == null)
return;
pathTo(n.parentNode, listPath);
}
function addListToList(listA, listB) {
for (x in listA)
listB.push(listA[x]);
}
function removeMatchingNodes (listToCheck, listToClean) {
var listToCheckLength = listToCheck.length;
for (var i = 0; i < listToCheckLength; i++) {
for (var j = 0; j < listToClean.length; j++) {
if (listToClean[j].row == listToCheck[i].row && listToClean[j].col == listToCheck[i].col)
listToClean.splice(j, 1);
}
}
}
function cullUnwantedNodes (listToCull, listToCompare) {
var listToCompareLength = listToCompare.length;
for (var i = 0; i < listToCompareLength; i++) {
for (var j = 0; j < listToCull.length; j++) {
if (listToCull[j].row == listToCompare[i].row && listToCull[j].col == listToCompare[i].col) {
if (listToCull[j].f >= listToCompare[i].f)
listToCull.splice(j, 1);
}
}
}
}
function areNodesEqual (nodeA, nodeB) {
if (nodeA.row == nodeB.row && nodeA.col == nodeB.col)
return true;
else
return false;
}
function returnNodeWithLowestFScore (list) {
var lowestNode = list[0];
for (x in list)
lowestNode = (list[x].f < lowestNode.f) ? list[x] : lowestNode;
return lowestNode;
}
function isListEmpty (list) {
return (list.length < 1) ? true : false;
}
function removeNodeFromList (node, list) {
var listLength = list.length;
for (var i = 0; i < listLength; i++) {
if (node.row == list[i].row && node.col == list[i].col) {
list.splice(i, 1);
break;
}
}
}
function addNodeToList (node, list) {
list.push(node);
}
function createTerminalNode (map, heuristic, nodeType, nodeGoal) {
var mapRows = map.length;
var mapCols = map[0].length;
for (var row = 0; row < mapRows; row++) {
for (var col = 0; col < mapCols; col++) {
if (map[row][col] == nodeType) {
return new Node(row, col, map, heuristic, null, nodeGoal);
}
}
}
return null;
}
function returnHScore (node, heuristic, nodeGoal) {
var y = Math.abs(node.row - nodeGoal.row);
var x = Math.abs(node.col - nodeGoal.col);
switch (heuristic) {
case "manhattan":
return (y + x) * 10;
case "diagonal":
return (x > y) ? (y * 14) + 10 * (x - y) : (x * 14) + 10 * (y - x);
case "euclidean":
return Math.sqrt((x * x) + (y * y));
default:
return null;
}
}
function NodeCoordinate (row, col) {
this.row = row;
this.col = col;
}
function Node (row, col, map, heuristic, parentNode, nodeGoal) {
var mapLength = map.length;
var mapRowLength = map[0].length;
this.row = row;
this.col = col;
this.northAmbit = (row == 0) ? 0 : row - 1;
this.southAmbit = (row == mapLength - 1) ? mapLength - 1 : row + 1;
this.westAmbit = (col == 0) ? 0 : col - 1;
this.eastAmbit = (col == mapRowLength - 1) ? mapRowLength - 1 : col + 1;
this.parentNode = parentNode;
this.childNodes = [];
if (parentNode != null) {
if (row == parentNode.row || col == parentNode.col)
this.g = parentNode.g + 10;
else
this.g = parentNode.g + 14;
this.h = returnHScore(this, heuristic, nodeGoal);
}
else {
this.g = 0;
if (map[row][col] == "s")
this.h = returnHScore(this, heuristic, nodeGoal);
else
this.h = 0;
}
this.f = this.g + this.h;
this.makeChildNodes = function (map, heuristic, cutCorners, nodeGoal) {
for (var i = this.northAmbit; i <= this.southAmbit; i++) {
for (var j = this.westAmbit; j <= this.eastAmbit; j++) {
if (i != this.row || j != this.col) {
if (map[i][j] != "u") {
if (cutCorners == true)
this.childNodes.push(new Node(i, j, map, heuristic, this, nodeGoal));
else {
if (i == this.row || j == this.col)
this.childNodes.push(new Node(i, j, map, heuristic, this, nodeGoal));
}
}
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment