A* Algorithm

A popular pathfinding and graph traversal algorithm that is highly favored for its performance and accuracy.

How it works

A* combines the cost to reach a node (g) with a heuristic estimate of the remaining distance to the goal (h) to compute a priority score f = g + h. It maintains an open list of candidate nodes sorted by f and always expands the node with the lowest score first. When the goal is reached, the shortest path is reconstructed by backtracking through parent pointers. The heuristic must be admissible — never overestimating — to guarantee an optimal result.

Why it matters

A* is the go-to algorithm in robotics, game AI, and mapping applications because it finds the shortest path far more efficiently than brute-force search. It powered early GPS navigation and remains central to NPC pathfinding in games. As AI systems increasingly control physical robots and autonomous vehicles, A*'s balance of speed and optimality makes it indispensable.