Interactive demo
A* Search
A* (A star), published in 1968 by Peter Hart, Nils Nilsson and Bertram Raphael, is the standard pathfinding algorithm in games and robotics. It expands cells by the cost so far plus an estimate of the remaining distance.
Draw walls or mud on the grid and drag the start and the goal. Once a search is finished, every change is searched again right away. Raise the heuristic weight above 1: A* expands fewer cells, but the path may cost more. With diagonal moves, the Manhattan heuristic overestimates and can cost the optimal path too.
Playback
- Expanded
- –
- Frontier (max.)
- –
- Path cost
- –
Press Play or Next Step to start the search.
Grid
Options
Legend
- Start (drag to move)
- Goal (drag to move)
- Wall
- Mud
- Frontier (open list)
- Visited (closed list)
- Expanded right now
- Path
Properties
Optimal
Conditionally
Optimal with weight 1 and an estimate that never overestimates. Manhattan does overestimate when diagonal moves are allowed.
Weighted cells
Yes
The cost so far includes the mud, as in Dijkstra's algorithm.
Heuristic
Yes
f = g + w · h: the cost so far plus the weighted estimate of the rest.
Any angle
No
Moves from cell to cell, straight or diagonally.
All pathfinding algorithms compared
| Algorithm | Optimal | Weighted cells | Heuristic | Any angle |
|---|---|---|---|---|
| Breadth-First Search | Without mud and diagonals | No | No | No |
| Depth-First Search | No | No | No | No |
| Dijkstra's Algorithm | Yes | Yes | No | No |
| Bidirectional Search | Yes | Yes | No | No |
| Greedy Best-First Search | No | No | Yes | No |
| A* Search this page | With weight 1 and an admissible heuristic | Yes | Yes | No |
| Jump Point Search | Without mud | No | Yes | No |
| Theta* | No | Shortcuts over open ground only | Yes | Yes |
1. f = g + h
For every cell, g is the cost of the best path found from the start and h is the estimated cost to the goal. A* always expands the cell with the smallest f = g + h, the most promising path through it. Ties go to the cell closer to the goal.
2. Admissible estimates
If h never overestimates the real remaining cost, A* finds the cheapest path, and the better h is, the fewer cells it expands. With h = 0 it is Dijkstra's algorithm; the octile distance is the best safe estimate for grids with diagonal moves.
3. Weighted A*
With f = g + w · h and w > 1, the estimate counts more: the search heads for the goal more directly and expands fewer cells. The path then costs at most w times the optimum. With large weights, A* behaves like greedy best-first search.
Credits
- Peter E. Hart, Nils J. Nilsson and Bertram Raphael: A Formal Basis for the Heuristic Determination of Minimum Cost Paths (IEEE Transactions on Systems Science and Cybernetics, 1968).