Grid Search and A*
A grid is a graph where every open cell touches its four neighbours, so the shortest route through it is a breadth-first search: the frontier grows in rings of equal distance and the goal is reached the first time it is expanded. That search spends effort in every direction, including away from the goal. A* keeps the same frontier but expands the cell with the smallest g + h, distance so far plus a straight-line style estimate of what is left. As long as the estimate never overshoots, the goal still comes off the frontier with its true shortest distance, only after far fewer expansions.
A* from the top-left to the bottom-right. Every reached cell gets g, its distance so far, and the frontier is expanded in order of f = g + h, where h is the Manhattan distance to the goal ignoring walls. h never overestimates, so the first time the goal is expanded its path is shortest.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 20, with their answers.
Frontier by f: (1,0) f 9, (0,1) f 9. Which is expanded next?
Answer: (1,0) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (0,1) f 9, (2,0) f 9. Which is expanded next?
Answer: (0,1) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (2,0) f 9, (0,2) f 9. Which is expanded next?
Answer: (2,0) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (0,2) f 9, (2,1) f 9. Which is expanded next?
Answer: (0,2) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (2,1) f 9, (0,3) f 9. Which is expanded next?
Answer: (2,1) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (0,3) f 9, (2,2) f 9. Which is expanded next?
Answer: (0,3) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (2,2) f 9, (0,4) f 9. Which is expanded next?
Answer: (2,2) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (0,4) f 9, (3,2) f 9. Which is expanded next?
Answer: (0,4) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (3,2) f 9, (1,4) f 9, (0,5) f 9. Which is expanded next?
Answer: (3,2) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (1,4) f 9, (0,5) f 9, (4,2) f 9. Which is expanded next?
Answer: (1,4) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (0,5) f 9, (4,2) f 9, (2,4) f 9. Which is expanded next?
Answer: (0,5) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (4,2) f 9, (2,4) f 9, (1,5) f 9. Which is expanded next?
Answer: (4,2) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (2,4) f 9, (1,5) f 9, (4,3) f 9. Which is expanded next?
Answer: (2,4) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (1,5) f 9, (4,3) f 9, (3,4) f 9. Which is expanded next?
Answer: (1,5) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (4,3) f 9, (3,4) f 9, (2,5) f 9. Which is expanded next?
Answer: (4,3) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (3,4) f 9, (2,5) f 9, (4,4) f 9. Which is expanded next?
Answer: (3,4) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (2,5) f 9, (4,4) f 9, (3,5) f 9. Which is expanded next?
Answer: (2,5) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (4,4) f 9, (3,5) f 9, (4,1) f 11. Which is expanded next?
Answer: (4,4) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (3,5) f 9, (4,5) f 9, (4,1) f 11. Which is expanded next?
Answer: (3,5) with f 9. The smallest f wins; ties go to the cell added first.
Frontier by f: (4,5) f 9, (4,1) f 11. Which is expanded next?
Answer: (4,5) with f 9. The smallest f wins; ties go to the cell added first.
How it runs, step by step
A* from the top-left to the bottom-right. Every reached cell gets g, its distance so far, and the frontier is expanded in order of f = g + h, where h is the Manhattan distance to the goal ignoring walls. h never overestimates, so the first time the goal is expanded its path is shortest.
A star search on a 5 by 6 grid.
Expand (0,0), g = 0, f = 9. New neighbours (1,0), (0,1) get g = 1 and f = 9, 9. Frontier: 2.
Expand (0,0), 2 new cells.
Expand (1,0), g = 1, f = 9. New neighbours (2,0) get g = 2 and f = 9. Frontier: 2.
Expand (1,0), 1 new cells.
Expand (0,1), g = 1, f = 9. New neighbours (0,2) get g = 2 and f = 9. Frontier: 2.
Expand (0,1), 1 new cells.
Expand (2,0), g = 2, f = 9. New neighbours (2,1) get g = 3 and f = 9. Frontier: 2.
Expand (2,0), 1 new cells.
Expand (0,2), g = 2, f = 9. New neighbours (0,3) get g = 3 and f = 9. Frontier: 2.
Expand (0,2), 1 new cells.
Expand (2,1), g = 3, f = 9. New neighbours (2,2) get g = 4 and f = 9. Frontier: 2.
Expand (2,1), 1 new cells.
Expand (0,3), g = 3, f = 9. New neighbours (0,4) get g = 4 and f = 9. Frontier: 2.
Expand (0,3), 1 new cells.
Expand (2,2), g = 4, f = 9. New neighbours (3,2) get g = 5 and f = 9. Frontier: 2.
Expand (2,2), 1 new cells.
Expand (0,4), g = 4, f = 9. New neighbours (1,4), (0,5) get g = 5 and f = 9, 9. Frontier: 3.
Expand (0,4), 2 new cells.
Expand (3,2), g = 5, f = 9. New neighbours (4,2) get g = 6 and f = 9. Frontier: 3.
Expand (3,2), 1 new cells.
Expand (1,4), g = 5, f = 9. New neighbours (2,4), (1,5) get g = 6 and f = 9, 9. Frontier: 4.
Expand (1,4), 2 new cells.
Expand (0,5), g = 5, f = 9. Every open neighbour was reached already, so nothing joins the frontier.
Expand (0,5), 0 new cells.
Expand (4,2), g = 6, f = 9. New neighbours (4,3), (4,1) get g = 7 and f = 9, 11. Frontier: 4.
Expand (4,2), 2 new cells.
Expand (2,4), g = 6, f = 9. New neighbours (3,4), (2,5) get g = 7 and f = 9, 9. Frontier: 5.
Expand (2,4), 2 new cells.
Expand (1,5), g = 6, f = 9. Every open neighbour was reached already, so nothing joins the frontier.
Expand (1,5), 0 new cells.
Expand (4,3), g = 7, f = 9. New neighbours (4,4) get g = 8 and f = 9. Frontier: 4.
Expand (4,3), 1 new cells.
Expand (3,4), g = 7, f = 9. New neighbours (3,5) get g = 8 and f = 9. Frontier: 4.
Expand (3,4), 1 new cells.
Expand (2,5), g = 7, f = 9. Every open neighbour was reached already, so nothing joins the frontier.
Expand (2,5), 0 new cells.
Expand (4,4), g = 8, f = 9. New neighbours (4,5) get g = 9 and f = 9. Frontier: 3.
Expand (4,4), 1 new cells.
Expand (3,5), g = 8, f = 9. Every open neighbour was reached already, so nothing joins the frontier.
Expand (3,5), 0 new cells.
The goal comes off the frontier with g = 9. Nothing left on the frontier has a smaller f, and f never overestimates, so no shorter path exists.
Goal reached at distance 9.
Shortest path of 9 steps after expanding 21 of the 23 open cells. The heuristic pulled the search toward the goal, so cells leading away were left alone.
Path of 9 steps.
Remember
- On an unweighted grid, BFS reaches every cell first by a shortest path, ring by ring.
- A* expands the frontier by f = g + h; with an admissible h (never overestimating) it stays optimal.
- Manhattan distance is admissible on a four-direction grid because walls can only make paths longer.
Topics covered
Where this is used
RoboticsRobot navigation stacks
Nav2, the navigation stack most ROS 2 robots run, holds the world as an occupancy grid costmap built from lidar and SLAM, and its planners search exactly that grid: NavFn with Dijkstra or A*, Smac with A* and its hybrid variants. The grid is not a simplification imposed on the sensor data, it is the shape that data already has, so there is no graph to build first. Obstacles move, so the plan is discarded and re-searched on a timer as the costmap updates rather than computed once, which makes the cost of a single expansion matter alongside the quality of the path.
GamesGame agent pathfinding
Recast and Detour, the navigation library Unity, Unreal, Godot and O3DE each ship a version of, voxelises the level geometry into a grid and then runs A* over the polygons it builds out of those voxels. The search is weighted rather than a plain ring expansion: every polygon carries an area cost through the query filter, so a short route across mud can lose to a longer one on road, and that is why a BFS wavefront would not answer the same question. The heuristic is straight-line distance to the goal, which nothing on the mesh can beat while costs stay close to plain distance. The same library also exposes a heuristic-free flood for range queries, and the difference between the two is exactly what the heuristic is buying when there is only one target.
Electronics designMaze routing on boards and chips
Lee's algorithm, published in 1961 for this exact job, routes a wire by expanding a BFS wavefront from the source across a grid laid over the routing surface until it reaches the target, then walking the distance labels back to recover the track. The surface genuinely is a grid because the design rules quantise it: minimum track width and clearance set the cell size. It is slow and memory hungry next to the push-and-shove routers that replaced it, but it keeps the property they give up: if a route exists on that grid the wavefront finds one, and the one it finds is a shortest one.
LogisticsWarehouse floor robots
The drive units in an Amazon fulfilment centre navigate by reading fiducial stickers laid out in a grid on the floor, so the graph is the floor plan itself with nothing to convert. The hard part is that hundreds of them share it, so planners for floors like this search over cell and time pairs rather than cells: a square another robot has reserved is a wall, but only for the steps it holds it. Searching in time like this is what stops two robots being routed through the same square and deadlocking there.
Why it works this way
Mark a cell when you push it, not when you pop it
The test next !in g does two jobs at once: it records the distance and it marks the cell as seen, before that cell is ever expanded. Move the check to the moment a cell comes off the frontier and every cell gets pushed once per open neighbour, so a frontier that should hold one ring holds up to four copies of it. The answer still comes out right, which is why this bug survives a small test and only shows itself as memory and time blowing up on a large grid.
Why the goal is checked as it leaves the frontier, not as it is pushed
A cell's g is only known to be final when that cell is the smallest f on the frontier, because every other cell waiting there has an f at least as large and a heuristic that never overestimates rules out a cheaper route through any of them. Testing for the goal inside the neighbour loop instead returns the first route that happens to touch it, which under A* need not be the shortest. On a plain unweighted BFS the two are the same and checking at push saves you one ring, but keeping the check on the pop is what lets the same loop stay correct once cells have costs.
Manhattan stops being admissible the moment diagonals are allowed
With eight neighbours one diagonal step covers a row and a column together, so a cell four rows and four columns away is 8 by Manhattan and 4 steps away in truth. The estimate now overshoots by up to double, and an overshooting estimate is exactly what the optimality guarantee forbids. Swap it for Chebyshev distance, max(dx, dy), when a diagonal costs the same as a straight step, or octile distance, (dx + dy) + (sqrt(2) - 2) * min(dx, dy), when it costs sqrt(2).
An overestimating heuristic is sometimes the point
Inflating h does not break the search, it breaks the guarantee: A* still returns a path, just not necessarily the shortest, because an inflated estimate can make the genuinely better route look worse and leave it sitting on the frontier until after the goal has been popped. Weighted A* does this deliberately, multiplying h by something like 1.5 or 2, and expands a small fraction of the cells in return. A route 10 percent longer found ten times faster is a good trade for a game character and a bad one for a delivery van, so this is a dial to set rather than a bug to avoid.
Read more
- A* search algorithmWikipedia
- Introduction to the A* algorithmRed Blob Games
- Heuristics for grid maps, including tie-breakingAmit Patel, Stanford · theory.stanford.edu
- Jump point searchWikipedia
- Lee algorithmWikipedia
Next up
- Bellman-FordRelax every edge V-1 times; a further improvement means a negative cycle.
- Floyd-WarshallAdmit one stopover vertex per round and relax every pair through it; the matrix converges in n rounds.
- 0-1 BFSA deque replaces the heap when weights are 0 or 1: a 0 edge pushes to the front, a 1 edge to the back.