A* is a well known and popular shortest path algorithm. With the correct heuristic it is efficient and finds the optimal solution. Here’s a fun and simple Javascript implementation that makes use of the canvas element. The code is free (public domain) for anyone to use or improve.

The above demo lets you play with the algorithm. By clicking you can add/remove walls or drag the start (blue) or end (red) nodes. The shortest route is highlighted by a red line and the searched nodes are drawn from yellow to green by distance from the start node.

The options to the right of the map control how the path is calculated. Diagonal movement is considered as the same cost as straight movement, but the tweak diagonal cost toggle adjust the diagonal cost to be slightly more expensive so that nicer looking paths are preferred. This doesn’t alter the length of the found path only the number of nodes searched and the path’s appearance.

A tie breaker can be used to decided which nodes with the same estimated cost are preferred. Preferring new nodes is a very simple and efficient tie breaker. The prefer new nodes option toggles preferring new/old nodes, if old nodes are preferred then A* performs much worse especially for empty spaces. The dot product tie breaker is a different tie breaker that chooses paths that are closer to the straight line between the start and end for equal paths.

For more information on the A* algorithm and path finding I would recommend Amit’s A* Pages.