A demo of the A* pathfinding algorithm.
Finds the shortest distance between the blue and red objects.
Click and drag the blue and red pieces to move them.
Click a tile to toggle its state as a wall.
Press the 'd' key to toggle whether diagonal movement is permitted.
Press the 'r' key to clear all walls on the grid.
Press the 's' key to toggle the g, h and f scores for each tile that is inspected.
Press the 'p' key to toggle the path visibility. Might be useful if the path is obscuring the scores.
Press the 't' key to toggle the time to compute the algorithm in milliseconds.
A* is the most used algorithm for finding the shortest path in general cases. The algorithm itself is a combination of Dijkstra's algorithm and an aproximate heuristical approach. You can perform the A* algorithm by computing the heuristic in many different ways, in my demo I used the manhattan method.
My implementation is functional but not necessarily efficient. There are many ways it could be improved. This is my solution in Haxe.