A* Search: Smarter Pathfinding
A* combines the cost so far with an estimate of the cost remaining. Watch it head for the goal and find the same shortest path while exploring fewer cells.
📄 Illustrated notes · every chapter as a picture · printable
Quick quiz
3 questions to check your understanding.
Go deeper
University-level written lectures in The AI Lecture Hall:
Transcript
Introduction. Every time a game character walks around a wall or a map app plans a route, there is a good chance A star is involved. Published in 1968, it is still everywhere.
f = g + h. A star scores every cell with f equals g plus h. G is the cost already travelled from the start. H is a heuristic, an estimate of the distance still to go. A star always explores the cell with the lowest total f next.
Watching A*. Here is A star on the same maze. Watch the numbers at the top: f equals g plus h for the current cell. Instead of spreading evenly, it leans towards the goal, and only explores detours when walls force it to.
Comparison. All three found the same 37-move path here. Breadth-first explored 205 cells, A star 161. Greedy search, which only looks at h, explored just 76, but greedy search is not guaranteed to find the shortest path in general. A star is, if its heuristic never overestimates.
Greedy search. This is greedy best-first search. It chases whatever looks closest to the goal. On this maze it got lucky. On other mazes it can walk into long detours, because it ignores the cost already paid.
Recap. Remember. A star uses f equals g plus h. It always expands the lowest f. With a heuristic that never overestimates, it is guaranteed to find a shortest path, usually with far less exploration than blind search.