Grid Search and A*

algorithmintermediateTime O(cells log cells)Space O(cells)

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.

Breadth-first search from the top-left to the bottom-right. Every reached cell gets g, its distance so far. The frontier is expanded first-in first-out, so the search grows in rings of equal distance in every direction, walls permitting.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 21, with their answers.

The frontier is a queue. Which cell is expanded next?
- (1,0) with f 1
- (0,1) with f 1
Answer: (1,0) with f 1. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (0,1) with f 1
- (2,0) with f 2
Answer: (0,1) with f 1. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (2,0) with f 2
- (0,2) with f 2
Answer: (2,0) with f 2. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (0,2) with f 2
- (2,1) with f 3
Answer: (0,2) with f 2. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (2,1) with f 3
- (0,3) with f 3
Answer: (2,1) with f 3. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (0,3) with f 3
- (2,2) with f 4
Answer: (0,3) with f 3. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (2,2) with f 4
- (0,4) with f 4
Answer: (2,2) with f 4. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (0,4) with f 4
- (3,2) with f 5
Answer: (0,4) with f 4. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (3,2) with f 5
- (1,4) with f 5
- (0,5) with f 5
Answer: (3,2) with f 5. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (1,4) with f 5
- (0,5) with f 5
- (4,2) with f 6
Answer: (1,4) with f 5. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (0,5) with f 5
- (4,2) with f 6
- (2,4) with f 6
Answer: (0,5) with f 5. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (4,2) with f 6
- (2,4) with f 6
- (1,5) with f 6
Answer: (4,2) with f 6. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (2,4) with f 6
- (1,5) with f 6
- (4,3) with f 7
Answer: (2,4) with f 6. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (1,5) with f 6
- (4,3) with f 7
- (4,1) with f 7
Answer: (1,5) with f 6. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (4,3) with f 7
- (4,1) with f 7
- (3,4) with f 7
Answer: (4,3) with f 7. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (4,1) with f 7
- (3,4) with f 7
- (2,5) with f 7
Answer: (4,1) with f 7. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (3,4) with f 7
- (2,5) with f 7
- (4,4) with f 8
Answer: (3,4) with f 7. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (2,5) with f 7
- (4,4) with f 8
- (4,0) with f 8
Answer: (2,5) with f 7. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (4,4) with f 8
- (4,0) with f 8
- (3,5) with f 8
Answer: (4,4) with f 8. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (4,0) with f 8
- (3,5) with f 8
- (4,5) with f 9
Answer: (4,0) with f 8. First in, first out: the oldest frontier cell.
The frontier is a queue. Which cell is expanded next?
- (3,5) with f 8
- (4,5) with f 9
Answer: (3,5) with f 8. First in, first out: the oldest frontier cell.

How it runs, step by step

Breadth-first search from the top-left to the bottom-right. Every reached cell gets g, its distance so far. The frontier is expanded first-in first-out, so the search grows in rings of equal distance in every direction, walls permitting.
Breadth-first search on a 5 by 6 grid.
Expand (0,0), g = 0. New neighbours (1,0), (0,1) get g = 1. Frontier: 2.
Expand (0,0), 2 new cells.
Expand (1,0), g = 1. New neighbours (2,0) get g = 2. Frontier: 2.
Expand (1,0), 1 new cells.
Expand (0,1), g = 1. New neighbours (0,2) get g = 2. Frontier: 2.
Expand (0,1), 1 new cells.
Expand (2,0), g = 2. New neighbours (2,1) get g = 3. Frontier: 2.
Expand (2,0), 1 new cells.
Expand (0,2), g = 2. New neighbours (0,3) get g = 3. Frontier: 2.
Expand (0,2), 1 new cells.
Expand (2,1), g = 3. New neighbours (2,2) get g = 4. Frontier: 2.
Expand (2,1), 1 new cells.
Expand (0,3), g = 3. New neighbours (0,4) get g = 4. Frontier: 2.
Expand (0,3), 1 new cells.
Expand (2,2), g = 4. New neighbours (3,2) get g = 5. Frontier: 2.
Expand (2,2), 1 new cells.
Expand (0,4), g = 4. New neighbours (1,4), (0,5) get g = 5. Frontier: 3.
Expand (0,4), 2 new cells.
Expand (3,2), g = 5. New neighbours (4,2) get g = 6. Frontier: 3.
Expand (3,2), 1 new cells.
Expand (1,4), g = 5. New neighbours (2,4), (1,5) get g = 6. Frontier: 4.
Expand (1,4), 2 new cells.
Expand (0,5), g = 5. Every open neighbour was reached already, so nothing joins the frontier.
Expand (0,5), 0 new cells.
Expand (4,2), g = 6. New neighbours (4,3), (4,1) get g = 7. Frontier: 4.
Expand (4,2), 2 new cells.
Expand (2,4), g = 6. New neighbours (3,4), (2,5) get g = 7. Frontier: 5.
Expand (2,4), 2 new cells.
Expand (1,5), g = 6. Every open neighbour was reached already, so nothing joins the frontier.
Expand (1,5), 0 new cells.
Expand (4,3), g = 7. New neighbours (4,4) get g = 8. Frontier: 4.
Expand (4,3), 1 new cells.
Expand (4,1), g = 7. New neighbours (4,0) get g = 8. Frontier: 4.
Expand (4,1), 1 new cells.
Expand (3,4), g = 7. New neighbours (3,5) get g = 8. Frontier: 4.
Expand (3,4), 1 new cells.
Expand (2,5), g = 7. Every open neighbour was reached already, so nothing joins the frontier.
Expand (2,5), 0 new cells.
Expand (4,4), g = 8. New neighbours (4,5) get g = 9. Frontier: 3.
Expand (4,4), 1 new cells.
Expand (4,0), g = 8. Every open neighbour was reached already, so nothing joins the frontier.
Expand (4,0), 0 new cells.
Expand (3,5), g = 8. 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. Every cell at a smaller distance was expanded before it, so this distance is the shortest.
Goal reached at distance 9.
Shortest path of 9 steps after expanding 23 of the 23 open cells. BFS explored in every direction, so it looked at cells no shortest path uses.
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

A* Search

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.

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