A* Search maze algorithm
A* search explores the cells that look closest to the exit first, while still guaranteeing the shortest path.
How it works
A* scores every cell with f = g + h: g is the steps taken from the start, h is a guess of the steps left (here the Manhattan distance to the exit, which never overestimates). It always expands the cell with the lowest score, using a priority queue.
Because h never overestimates, the first time A* reaches the exit is along a shortest path, like BFS. But it leans toward the goal, so it usually explores far fewer cells. In a maze, walls often force it the long way round, and then it behaves more like BFS.
What to watch for
Watch the exploration stretch toward the bottom-right corner instead of spreading evenly, and fill in sideways only when walls block the way.
Properties
- Shortest path
- Always (admissible heuristic)
- Finds the exit
- Always, if there is one
- Explores
- Usually less than BFS
- Memory
- Priority queue
Race it
Same maze, same speed, first to the exit wins: A* Search vs Dijkstra. Or put it in a gauntlet, where the winner stays on.
FAQ
What heuristic does this A* use?
Manhattan distance to the exit: rows plus columns, since moves are up, down, left and right.
Is A* always faster than Dijkstra?
It never explores more than Dijkstra with the same tie-breaking, and usually explores much less, because the heuristic points it at the goal.