A* Search: Smarter Pathfinding — lecture notes
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.
0:001. 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.
0:142. 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.
0:333. 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.
0:504. 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.
1:105. 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.
1:256. 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.
Key takeaways
- A* scores cells with f = g + h and explores the lowest f first.
- With an admissible heuristic, A* is guaranteed to find a shortest path.
- On our maze: BFS explored 205 cells, A* 161, greedy 76 — all found the 37-move path.
- Greedy best-first search is fast but not guaranteed to be optimal.
Check yourself
- In f(n) = g(n) + h(n), what is h(n)?
Show answer
An estimate of the remaining cost to the goal — h is the heuristic estimate of the distance still to go.
- When is A* guaranteed to find a shortest path?
Show answer
When its heuristic never overestimates the true remaining cost — An admissible heuristic guarantees optimality.
- Greedy best-first search chooses cells using…
Show answer
Only h — Greedy search ignores the cost so far and chases the smallest estimate.
Go deeper
- Informed Search: Greedy Best-First and A* with Admissible Heuristics · The AI Lecture Hall
- Uninformed Search: BFS, DFS, Uniform-Cost and Iterative Deepening · The AI Lecture Hall
© 2026 Janin A Apurba, CSE, AUST · Advanced ICT Officer, CNRS-UNHCR. All rights reserved. Notes for the animated lecture at https://ai-in-motion.vercel.app/watch/a-star-search.html