Simple A* Pathfinding
var AStar; | |
(function () { | |
var Node = function (index, x, y, parent) { | |
this.index = index; | |
this.x = x; | |
this.y = y; | |
this.parent = parent || null; | |
this.f = 0; | |
this.g = 0; | |
}; | |
Node.prototype.getDistance = function (node) { | |
return ( | |
Math.abs(this.x - node.x) | |
+ Math.abs(this.y - node.y) | |
); | |
}; | |
var Map = function (grid) { | |
this.grid = grid; | |
this.width = grid[0].length; | |
this.height = grid.length; | |
}; | |
Map.prototype.isWalkable = function (x, y) { | |
if ( | |
x < 0 | |
|| y < 0 | |
|| x >= this.width | |
|| y >= this.height | |
) { | |
// Outside the map. Totally NOT walkable! | |
return false; | |
} | |
return (!this.grid[y][x]); | |
}; | |
Map.prototype.makeNode = function (x, y, parent) { | |
return new Node( | |
(x + (y * this.width)), | |
x, y, parent | |
); | |
}; | |
Map.prototype.getAdjacent = function (n) { | |
var a = []; | |
// North | |
if (this.isWalkable(n.x, n.y - 1)) { | |
a.push(this.makeNode(n.x, n.y - 1, n)); | |
} | |
// South | |
if (this.isWalkable(n.x, n.y + 1)) { | |
a.push(this.makeNode(n.x, n.y + 1, n)); | |
} | |
// West | |
if (this.isWalkable(n.x - 1, n.y)) { | |
a.push(this.makeNode(n.x - 1, n.y, n)); | |
} | |
// East | |
if (this.isWalkable(n.x + 1, n.y)) { | |
a.push(this.makeNode(n.x + 1, n.y, n)); | |
} | |
return a; | |
}; | |
AStar = function (grid, startX, startY, goalX, goalY) { | |
// The search area | |
var map = new Map(grid); | |
// The start and goal nodes | |
var start = map.makeNode(startX, startY); | |
var goal = map.makeNode(goalX, goalY); | |
// List to keep track of open and closed nodes | |
var openList = [start]; | |
var closedList = []; | |
var len = 0; | |
while (len = openList.length) { | |
var minF = { | |
index: -1, | |
f: Infinity | |
}; | |
// Find the node on the open list | |
// with the lowest F | |
for (var i = 0; i < len; ++i) { | |
if (openList[i].f < minF.f) { | |
minF.f = openList[i].f; | |
minF.index = i; | |
} | |
} | |
// Remove this node from the open list | |
var node = openList.splice(minF.index, 1)[0]; | |
if (node.index === goal.index) { | |
// Hooray! We found the goal node! | |
// Create the final path | |
var path = []; | |
do { | |
path.push([node.x, node.y]); | |
} while (node = node.parent); | |
// ...and flip it so it's in the right order | |
path.reverse(); | |
return path; | |
} else { | |
// Haven't found the goal node yet... | |
// Get adjacent nodes | |
var adjacent = map.getAdjacent(node); | |
// Calculate values for adjacent nodes | |
// and add them to the open list if | |
// they aren't already closed | |
for (var i = 0, j = adjacent.length; i < j; ++i) { | |
var n = adjacent[i]; | |
if (!closedList[n.index]) { | |
n.g = (node.g + n.getDistance(node)); | |
n.f = (n.g + n.getDistance(goal)); | |
openList.push(n); | |
closedList[n.index] = true; | |
} | |
} | |
} | |
} | |
// We didn't find a path to the goal :( | |
return null; | |
}; | |
}()); |
<!DOCTYPE html> | |
<html lang="en"> | |
<head> | |
<title>A* Pathfinding Example</title> | |
</head> | |
<body> | |
<script src="astar.js"></script> | |
<script> | |
var map = [ | |
[0, 0, 0, 1, 0], | |
[0, 1, 0, 1, 0], | |
[0, 1, 0, 0, 0], | |
[0, 1, 1, 1, 0], | |
[0, 0, 0, 1, 0] | |
]; | |
var path = AStar(map, 0, 0, 4, 4); | |
if (path) { | |
for (var i = 0; i < path.length; ++i) { | |
console.log(path[i]); | |
} | |
} else { | |
console.log("No path found :("); | |
} | |
</script> | |
</body> | |
</html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment