Skip to content

Instantly share code, notes, and snippets.

@velipso
Last active February 3, 2018 13:44
Show Gist options
  • Save velipso/c07cb1b79c46515ed4e66f4072acbfce to your computer and use it in GitHub Desktop.
Save velipso/c07cb1b79c46515ed4e66f4072acbfce to your computer and use it in GitHub Desktop.
Single function that implements A-Star pathfinding algorithm in ~75 lines of code
// PUBLIC DOMAIN
//
// Single function that implements A-Star pathfinding algorithm in ~75 lines of code
//
// (why use a huge library..?)
//
// Parameters:
// solid array of booleans (of size width * height) that determine if a tile is solid
// width width of the map
// height height of the map
// start starting point as an array of [x, y]
// end ending point as an array of [x, y]
// diag boolean if diagonal movements are allowed
//
// Returns:
// array of points, where array[0] is the start and array[array.length - 1] is the end
// or `false` if no path is found
//
function astar(solid, width, height, start, end, diag){
function heuristic(p1, p2){
return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
}
function applydir(pt, d, amt){
switch (d){
case 0: pt[0] -= amt; return pt;
case 1: pt[0] -= amt; pt[1] -= amt; return pt;
case 2: pt[1] -= amt; return pt;
case 3: pt[0] += amt; pt[1] -= amt; return pt;
case 4: pt[0] += amt; return pt;
case 5: pt[0] += amt; pt[1] += amt; return pt;
case 6: pt[1] += amt; return pt;
case 7: pt[0] -= amt; pt[1] += amt; return pt;
}
}
var open = [];
var from = [];
var steps = [];
var inopen = [];
for (var i = 0, size = width * height; i < size; i++){
from.push(-1);
steps.push(-1);
inopen.push(false);
}
open.push([start[0], start[1], heuristic(start, end)]);
inopen[start[0] + width * start[1]] = true;
steps[start[0] + width * start[1]] = 0;
while (open.length > 0){
var cur = open.shift();
var curk = cur[0] + cur[1] * width;
if (cur[0] == end[0] && cur[1] == end[1]){
var path = [];
var pp = [end[0], end[1]];
while (true){
path.unshift(pp);
if (pp[0] == start[0] && pp[1] == start[1])
return path;
pp = applydir([pp[0], pp[1]], from[pp[0] + pp[1] * width], -1);
}
}
inopen[curk] = false;
for (var d = 0, dstep = diag ? 1 : 2; d < 8; d += dstep){
var nxt = applydir([cur[0], cur[1]], d, 1);
var nk = nxt[0] + nxt[1] * width;
if (nxt[0] < 0 || nxt[0] >= width || nxt[1] < 0 || nxt[1] >= height || solid[nk])
continue;
var nsteps = steps[curk] + ((d % 2) ? 1.4142135623730951 : 1);
if (steps[nk] >= 0 && nsteps >= steps[nk])
continue;
from[nk] = d;
steps[nk] = nsteps;
nxt.push(nsteps + heuristic(nxt, end));
var inserted = false;
var hasold = inopen[nk];
inopen[nk] = true;
for (var i = 0; i < open.length && (hasold || !inserted); i++){
if (hasold && open[i][0] == nxt[0] && open[i][1] == nxt[1]){
open.splice(i, 1);
i--;
hasold = false;
}
else if (!inserted && open[i][2] > nxt[2]){
open.splice(i, 0, nxt);
inserted = true;
}
}
if (!inserted)
open.push(nxt);
}
}
return false;
}
// demo
astar([
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 1, 0, 0, 0, 0, 0, 1,
1, 0, 0, 1, 0, 0, 0, 0, 0, 1,
1, 0, 0, 1, 0, 0, 1, 0, 0, 1,
1, 0, 0, 1, 0, 0, 1, 0, 0, 1,
1, 0, 0, 0, 0, 0, 1, 0, 0, 1,
1, 0, 0, 0, 0, 0, 1, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
10, 8,
[1, 1], [8, 6],
true);
// => [[1,1],[2,2],[2,3],[2,4],[3,5],[4,4],[5,3],[6,2],[7,3],[8,4],[8,5],[8,6]]
@velipso
Copy link
Author

velipso commented Sep 12, 2016

public domain

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