A* shortest path in Javascript
Comments: 3 - Date: August 27th, 2009 - Categories: Programming
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.
Comment by Dave - August 31, 2009 @ 12:30 pm
Very cool! I did something similar for a school project a while back:
http://oranchak.com/?p=327
Pingback by Walking directions in a warehouse (part 2) | M3 ideas - September 27, 2014 @ 12:32 am
[…] used Will Thimbleby’s wonderful illustration of A* shortest path in Javascript. We can drag and drop the start and stock locations to move them around and recalculate the path, […]
Comment by gweltaz - April 26, 2022 @ 1:03 pm
love it. I’ve learnt so much about will thimbleby and i will create a wikipedia page for him. Go tchek my intagram
pourquoi elir un président qui 5 maison? je laisse le sujet a dautres gens
i cry everynight
i like kiwi with caramel
gweltaz and owen twins (consaguinité)
Leave a comment