Monday, October 12, 2009

A Star (A*) path/route finding Javascript code

For a little side project I was working on, I needed a Javascript implementation of the A Star (A*) path finding algorithm. I couldn't find a good/simple one online, so I coded my own. I'm posting it here in case anyone else is interested in using it. Example map:  
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:

Xirax said...

I am kinda curious what side project might require that :D

The Writer said...

Oh, just a little iPhone-sized tank game I spend a few minutes every now and then coding when I'm bored.

kls said...

What about this http://webreflection.blogspot.com/2006/10/javascript-path-finder-with-star.html?

id said...

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;

The Writer said...

Thanks, id. I integrated your improvement.

Moshe said...

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 .

The Writer said...

Thank you, Moshe! I fixed that bug.

Moshe said...

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.

Moshe said...

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 .

Moshe said...

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.

awl said...

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 Writer said...

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.

awl said...

Thanks!

Captain Science Man said...

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!

Jack said...

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.

Jack said...

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!

The Writer said...

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.