A-star (commonly written A*) is a graph traversal and pathfinding algorithm widely used in games and robotics. It finds the shortest path between a start node and a goal node by combining two costs:
g(n)— the actual cost from the start to the current nodeh(n)— a heuristic estimate of the cost from the current node to the goal
The algorithm always expands the node with the lowest f(n) = g(n) + h(n), using a priority queue (min-heap). This makes it both complete (it will find a path if one exists) and optimal (it will find the shortest path), as long as the heuristic never overestimates the true cost (i.e., it is admissible).
Compared to Dijkstra’s algorithm (which only uses g), A-star is dramatically faster in practice because the heuristic guides the search toward the goal instead of expanding in all directions equally.
Common heuristics:
- Manhattan distance — for grid-based movement without diagonals
- Euclidean Distance — for free movement in any direction
- Chebyshev distance — for grid-based movement with diagonals
Used in DonAI Navigation - 3D Pathfinding for Flying Enemies for 3D voxel-based pathfinding.