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>
17 comments:
I am kinda curious what side project might require that :D
Oh, just a little iPhone-sized tank game I spend a few minutes every now and then coding when I'm bored.
What about this http://webreflection.blogspot.com/2006/10/javascript-path-finder-with-star.html?
Thanks for this. It is nice and simple. There is one bug though. You are using Math.floor around Math.sqrt in the heuristic function. This causes the path to take odd diagonal routes that are not optimal. If you take that out then it is fine.
Also you can speed it up by using this heuristic instead:
var x = current_node.x-destination.x;
var y = current_node.y-destination.y;
return x*x+y*y;
Thanks, id. I integrated your improvement.
I'm reusing your code in my path finding simulator (DF related) and I transformed it a lot so it support some more complex path finding scheme and benchmarking. I've found a small bug in your node object this.g = f;
You can see my work at http://niseg.moshela.com/test_maze.html
I recently added optimizations including insert in order and bit vectors for open and closed queue ( O(1) check if a node is in there). This made the code run a few orders of magnitude faster. I've tested on a 128X128 version and performance improved from 13 seconds to about 15ms .
Thank you, Moshe! I fixed that bug.
I hope you tested my code before you took it all. ;) It's has tons of commented stuff . I don't think it would work now because I changed the heuristic into a wrapper....
I'll explain about the board types anyways I changed the way it looks at neighbors to do this better:
- type 0 - original code excluding the vector cost per step (it's +1),
- type 1 - weighted A* there is another board with "weights" and an array with their values. this is similar to how Dwarf fortress does it.
- type 2 is a room navigation should be careful due to my use of [y][x] arrays. my room has array of dests and an x,y center point they are also aranged in a 2d array like the original code.
- type 3 is a is a special in room navigation mode which ignore rooms that are not in the start and destination room - it's only useful when going from 1 room to it's neighbor
The limit will limits the weights it's fairly half baked . I wanted to limit A* in my more advanced algorithms. This is how mode 3 was born .
I might be moving to 3D soon . Your code was a great starting point.
I added my two optimizations to your original file(commented replaced code) and named it:
http://niseg.moshela.com/for_46dog/a_star_46dog_opt.js
I tested them on my very old version (10 out of 50) which used the original file. I used a double comb maze( this will fool A* to go through all dead ends):
http://niseg.moshela.com/for_46dog/old_maze.html?maze=00807FFE00AA7FAA00AA7FAA00AA7FAA00AA7FAA00AA7FAA00AA7FAA00000000
It seems to work fine .
Someone found a bug in my "Insert in Order" into open queue . I fixed the bug and updated the files (my heavily modified A* and the lightly optimized version).
I hope this would helps anyone that want to use this code . The gains you get are from bit vectors are huge . I've seen a similar optimization on other JS A* implementations that use a "visited" variable. The insert in order only give a very minor gain (about 30% faster on 128X128) so it's reasonable not to use it.
Can you clarify what kind of license your a star code would be under? I'd like to use it in a non commercial for fun but public project.
The most permissive license I could find was the MIT license, so I slapped that on it. Basically, you can do whatever you want with the code, commercial or not.
Thanks!
Hi! I hope you don't mind, I added this to the jsGameSoup library. Here is the documentation page for my modified version. Thank you!
I don't know if anyone still reads these comments but how would you edit this to not use diagonal movement? I have tried myself but I cannot get it to work.
Thanks.
Thank you for the very fast reply! I can't believe I didn't think of the answer when I looked at what you had done. Thank you!
Jack, I tweaked the code a little for you. You can now pass another parameter into the a_star() function, a boolean that indicates whether diagonals should be allowed.
Post a Comment