celsogg/astar.js

## 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;
}

## 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>

## 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;
}
	/*
	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;
	}
	<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>
	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;
	}