A* Pathfinding
Draw walls on a grid, place start and end points, and watch A* find the shortest path. The algorithm maintains an open set of candidates and a closed set of explored nodes, choosing the next node by minimizing f(n) = g(n) + h(n) — the actual cost from the start plus a heuristic estimate to the goal. Compare with Dijkstra’s algorithm to see how the heuristic focuses the search.
f(n) = g(n) + h(n) · h = heuristic estimate to goal · g = cost from start
A* search algorithm
A* (pronounced “A-star”) was first described by Peter Hart, Nils Nilsson, and Bertram Raphael in 1968 at the Stanford Research Institute. It finds the shortest path between a start and goal node in a weighted graph by combining two pieces of information: g(n), the exact cost of the cheapest path from the start to node n, and h(n), a heuristic estimate of the cost from n to the goal. The algorithm always expands the node with the smallest f(n) = g(n) + h(n), guaranteeing an optimal path as long as the heuristic never overestimates the true cost (a property called admissibility).
Heuristics
The power of A* lies in the heuristic function. A good heuristic dramatically reduces the number of nodes explored. The Manhattan distance (|dx| + |dy|) is admissible for grids with 4-directional movement. The Euclidean distance (straight-line) is admissible for any movement model. The Chebyshev distance (max(|dx|, |dy|)) is admissible for 8-directional movement with uniform cost. When h(n) = 0, A* degenerates to Dijkstra’s algorithm, which explores uniformly in all directions. A better heuristic means fewer nodes explored, at the cost of more computation per node.
Dijkstra’s algorithm
Edsger Dijkstra published his algorithm in 1959. It finds shortest paths from a source to all nodes in a graph with non-negative edge weights. It is equivalent to A* with h(n) = 0 — it explores outward uniformly from the start, like ripples in a pond. This means it always explores more nodes than A* (or the same number in the worst case), but it does not require a heuristic function. Watching both algorithms side by side on the same grid beautifully demonstrates the value of informed search: A* focuses its exploration toward the goal while Dijkstra spreads evenly in all directions.
Real-world applications
A* and its variants are the backbone of pathfinding in video games, robotics, and navigation systems. Google Maps, GPS devices, and ride-sharing apps all use algorithms descended from A*. In video games, characters use A* to navigate around obstacles. Variations include Jump Point Search (for uniform-cost grids), D* Lite (for dynamic environments where obstacles move), and hierarchical pathfinding (for very large maps). The algorithm has also been applied to puzzle solving, protein folding, and automated planning.