Example path:
The usage is simple. Make a single function call, passing in the start and destination x/y locations as arrays (e.g. [1, 2]), the board as a two-dimensional array (where 0 means a spot is open), and the number of rows and columns in your board. A final parameter indicates whether diagonal movement should be allowed.
<script>
path = a_star(start, destination, board, rows, columns, allow_diagonals);
</script>
The function will return an array of nodes from start to destination with the shortest path. The x/y values of each node can be accessed like so: path[0].x or path[0].y.
<script>
for (var i = 0; i < path.length; i++)
alert("X/Y of path node: "+path[i].x+"/"+path[i].y);
</script>
Download the A Star Javascript code.
Example implementation:
<html>
<body>
<script src="a_star.js"></script>
<script>
//Set the number of rows and columns for the board
var rows = 10;
var columns = 10;
//Create the board, setting random squares to be obstacles
var board = [];
for (var x = 0; x < columns; x++)
{
board[x] = [];
for (var y = 0; y < rows; y++)
{
//Give each square a 25% chance of being an obstacle
var square = Math.floor(Math.random()*4);
//0 = open, 1 = obstacle
if (square == 0)
board[x][y] = 1;
else
board[x][y] = 0;
}
}
//Set the start and destination squares (and guarantee they're not an obstacle)
var start = [1, 1];
board[1][1] = 0;
var destination = [8, 8];
board[8][8] = 0;
//Indicate whether we should do cardinal directions only (N, E, S, W) or diagonal directions as well
var allow_diagonals = true;
//Use A* to see if there's a path between them
var path = a_star(start, destination, board, rows, columns, allow_diagonals);
//Draw the board
for (var y = 0; y < rows; y++)
{
document.write("<div>");
for (var x = 0; x < columns; x++)
{
document.write("<div id='board_"+x+"_"+y+"' style='"
+ "float: left;"
+ " width: 20; height: 20;"
+ " border: thin solid black;"
+ " background-color: "+(board[x][y] == 0 ? "white" : "black")
+ "'></div>");
}
document.write("<div style='clear: both;'></div>");
document.write("</div>");
}
//Mark the start and end nodes a special border color
document.getElementById("board_" + start[0] + "_" + start[1]).style.borderColor = "yellow";
document.getElementById("board_" + destination[0] + "_" + destination[1]).style.borderColor = "yellow";
//Highlight the path
for (var i = 0; i < path.length; i++)
document.getElementById("board_" + path[i].x + "_" + path[i].y).style.backgroundColor = "red";
</script>
</body>
</html>
