The A* algorithm finds the _cheapest_ way to get from a start point to an end point on the map. Each map tile has a value or cost associated with it. The algorithm plots paths until it finds the most economical means of traversing the map from s to f. This path may not appear to the be most direct but it is the most thrifty traverse. An heuristic (or estimated average cost per map tile) is used to base the path finding on. The cheaper the heuristic (or average cost), the longer the path finding--measured in milliseconds in the above demo.
Instructions
Use the arrow keys to move around the isometric map. Visible matrix = 15x15, actual matrix = 30x30
Click tiles to activate, then click on the map to place them. Hold the shift and control (command) keys to lock along the x and y axis.
Define a start and finish point for the path search by selecting the 's' and 'f' tiles and clicking the map to set the point.
The slider affects the heuristic (average tile cost) used for the A* pathfinding (sort) algorithm. By raising the value, the sort is faster though the path may be _longer_, the smaller the heuristic, the longer the search time.
Click the buttons to reset map (and perform the search--though it does this automatically now.)
The 'see-thru' button creates transparent walls... making it easier for placing the start and finish nodes.
The A* basic algorithm was created by John Kanding who was kind enough to make his source available. You can find John's A* implementation here
