Skip to content

Instantly share code, notes, and snippets.

@celsogg

celsogg/astar.js

Last active December 31, 2018 19:39
Show Gist options
  • Save celsogg/0ec392fb82674d8b148e to your computer and use it in GitHub Desktop.
Save celsogg/0ec392fb82674d8b148e to your computer and use it in GitHub Desktop.
Download ZIP
A * (A Star) Algorithm written in javascript, and a test
Raw
astar.js
/*
example:
var map = [ [0,0,0,0,0,1,1,0],
[0,0,0,0,1,0,0,0],
[0,1,1,0,1,0,0,0],
[0,0,0,0,1,0,1,0],
[0,1,1,0,0,0,1,0],
[0,0,0,0,0,0,1,0] ];
var start = {x:0, y:0};
var goal = {x:7, y:4};
returns an array of {x: , y: } to goal
*/
function aStar (map, start, goal) {
var closedSet = [];
var openSet = [];
var mh = map.length;
var mw = map[0].length;
var cameFrom = new Array2d(mh, mw, null );
var gScore = new Array2d(mh, mw, 0);
var fScore = new Array2d(mh, mw, 0);
openSet.push(start);
gScore[start.y][start.x] = 0;
fScore[start.y][start.x] = h(start, goal);
var current = {};
var neighbors = [];
while (openSet.length > 0) {
current = openSet[0]; // the first is the one with the lowest fScore
if (current.x == goal.x && current.y == goal.y)
return reconstructPath(cameFrom, goal, start);
closedSet.push( openSet.shift() );
neighbors = getNeighbors ( current , map, mh, mw);
var tentativeGScore = 0;
for (var i=0 ; i< neighbors.length; i++){
var n = neighbors[i];
if ( isIn(n, closedSet) ) continue;
tentativeGScore = gScore[current.y][current.x] + 1;
if ( !isIn(n,openSet) || tentativeGScore < gScore[n.y][n.x]){
cameFrom[n.y][n.x] = current;
gScore[n.y][n.x] = tentativeGScore;
fScore[n.y][n.x] = tentativeGScore + h(n, goal);
if ( !isIn(n, openSet) )
insertOrdered (n, openSet, gScore);
}
}
}
return null;
}
function insertOrdered (elem, arr, score) {
var i = 0;
while ( i < arr.length && score[elem.y][elem.x] > score[arr[i].y][arr[i].x] )
i++;
arr.splice(i, 0, elem);
}
function getNeighbors (n, map, h, w){
var nx = n.x;
var ny = n.y;
var r = [];
if (nx > 0 && map[ny][nx-1] == 0)
r.push({x: nx-1, y:ny}); //left
if (nx < w-1 && map[ny][nx+1] == 0)
r.push({x: nx+1, y:ny}); //right
if (ny > 0 && map[ny-1][nx] == 0)
r.push({x: nx, y:ny-1}); //up
if (ny < h-1 && map[ny+1][nx] == 0)
r.push({x:nx, y:ny+1}); //down
return r;
}
function reconstructPath (cameFrom, current) {
var path = [];
while ( cameFrom[current.y][current.x] != null ) {
path.push(current);
current = cameFrom[current.y][current.x];
}
return path.reverse();
}
function h (start, goal) {
return Math.abs(start.x-goal.x) + Math.abs(start.y-goal.y);
}
function Array2d (firstDim, secondDim, val) {
var arr = [];
for (var i = 0; i < firstDim; i++) {
arr[i] = [];
if ( typeof val !== 'undefined')
for (var j = 0; j < secondDim; j++) {
arr[i][j] = val;
};
};
return arr;
}
function isIn (point, list) {
for (var i = 0; i < list.length; i++) {
if (point.x == list[i].x && point.y == list[i].y)
return true;
};
return false;
}
Raw
index.html
<html>
<head>
<title></title>
<meta charset="utf-8">
<style type="text/css">
tr {
height:30px;
}
td {
width:30px;
}
</style>
<script type="text/javascript" src="astar.js"></script>
</head>
<body>
<div id="points" style="width: 720px"></div>
<script type="text/javascript" src="test.js"></script>
</body>
</html>
Raw
test.js
var m =
"000001000100000000010000100000"+
"001001010100110110010000100000"+
"000001010000100000010000000000"+
"001101010101111011111100111111"+
"111001000100000000000000000000"+
"000001010001111110011111001100"+
"010111010100000000010000000000"+
"000000010100000000000000000000"+
"000000000000000010000000000000"+
"111111111111111111111111111111";
var start = {x:0, y:0};
var goal = {x:29, y:1};
console.time('aStar');
var map = stringToMap(m, 30, 10);
var result = aStar( map, start, goal);
console.timeEnd('aStar');
console.log(listToString(result));
document.getElementById("points").innerHTML = listToString(result);
var table = "<table>";
for (var i = 0; i < map.length; i++) {
table += "<tr>";
for (var j = 0; j < map[0].length; j++) {
if (map[i][j] != 0)
table += '<td id="'+j+'-'+i+'" style="background-color:#C5253E;"></td>';
else
table += '<td id="'+j+'-'+i+'" style="background-color:#EAD094;"></td>';
};
table += "</tr>";
};
table += "</table>";
document.getElementById("points").innerHTML = table;
document.getElementById(start.x+'-'+start.y).style.backgroundColor = "#254B4F" ;
for (var i = 0; i < result.length; i++) {
document.getElementById(result[i].x+'-'+result[i].y).style.backgroundColor = "#946652" ;
};
document.getElementById(goal.x+'-'+goal.y).style.backgroundColor = "#2F5D5E" ;
function stringToMap (str, width, height) {
var map = new Array(height);
var c = 0;
for (var i = 0; i < height; i++) {
map[i] = new Array(width);
for (var j = 0; j < width; j++) {
map[i][j] = parseInt(str[ c ]);
c++;
};
};
return map;
}
function listToString (arr) {
var str = "";
for (var i = 0; i < arr.length; i++) {
str += "("+arr[i].x+","+arr[i].y+") ";
};
return str;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment