A* (pronounced "A-star") searches for a route between nodes in a graph. Peter Hart, Nils Nilsson and Bertram Raphael introduced it in 1968. It is used for tasks such as moving characters through a game map.
The search gives each candidate node a score: f = g + h. Here, g is the cost of the best route found to that node so far, and h is a heuristic: an estimate of the remaining cost to the goal. A* explores the candidate with the lowest score next.
In this demo, horizontal and vertical moves cost 1, diagonal moves cost the square root of 2, and the heuristic is the straight-line distance to the goal. Add walls to see how obstacles change the search. Turn off Auto step in Settings and info to follow it one step at a time.
Cost so far: Dijkstra's algorithm prioritises the cost already travelled. Setting A*'s heuristic to zero gives the same search priority.
Estimated cost ahead: Greedy best-first search considers only the estimate to the goal. A* adds that estimate to the cost so far, balancing progress towards the goal with the route already taken.
Finding a least-cost path: On a finite graph with non-negative movement costs, standard A* can guarantee a least-cost path if the heuristic never overestimates the remaining cost and is zero at the goal. Such a heuristic is admissible. If visited nodes are not reopened when a better route is found, the heuristic must also be consistent: its estimate cannot drop by more than the cost of a step. The guarantee depends on the stopping rule too: the goal must be selected as the next node to explore, not just discovered as a neighbour.
Speed and memory: A useful heuristic can reduce the number of nodes explored compared with Dijkstra's algorithm, but there is no universal time or memory advantage. A* stores candidate nodes and route information, which can use substantial memory on large maps. An overestimate may guide the search more directly, but loses the general least-cost guarantee.
I built this visualisation to make the search easier to follow. It is an educational demo, not a guarantee that every displayed route is optimal.