AlgoScope

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.

The player

A star search on a 5 by 6 grid.012345012340

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.

  1. Frontier by f: (1,0) f 9, (0,1) f 9. Which is expanded next?

    • (1,0) with f 9
    • (0,1) with f 9

    Answer: (1,0) with f 9. The smallest f wins. Ties go to the cell added first.

  2. Frontier by f: (0,1) f 9, (2,0) f 9. Which is expanded next?

    • (0,1) with f 9
    • (2,0) with f 9

    Answer: (0,1) with f 9. The smallest f wins. Ties go to the cell added first.

  3. Frontier by f: (2,0) f 9, (0,2) f 9. Which is expanded next?

    • (2,0) with f 9
    • (0,2) with f 9

    Answer: (2,0) with f 9. The smallest f wins. Ties go to the cell added first.

  4. Frontier by f: (0,2) f 9, (2,1) f 9. Which is expanded next?

    • (0,2) with f 9
    • (2,1) with f 9

    Answer: (0,2) with f 9. The smallest f wins. Ties go to the cell added first.

  5. Frontier by f: (2,1) f 9, (0,3) f 9. Which is expanded next?

    • (2,1) with f 9
    • (0,3) with f 9

    Answer: (2,1) with f 9. The smallest f wins. Ties go to the cell added first.

  6. Frontier by f: (0,3) f 9, (2,2) f 9. Which is expanded next?

    • (0,3) with f 9
    • (2,2) with f 9

    Answer: (0,3) with f 9. The smallest f wins. Ties go to the cell added first.

  7. Frontier by f: (2,2) f 9, (0,4) f 9. Which is expanded next?

    • (2,2) with f 9
    • (0,4) with f 9

    Answer: (2,2) with f 9. The smallest f wins. Ties go to the cell added first.

  8. Frontier by f: (0,4) f 9, (3,2) f 9. Which is expanded next?

    • (0,4) with f 9
    • (3,2) with f 9

    Answer: (0,4) with f 9. The smallest f wins. Ties go to the cell added first.

  9. Frontier by f: (3,2) f 9, (1,4) f 9, (0,5) f 9. Which is expanded next?

    • (3,2) with f 9
    • (1,4) with f 9
    • (0,5) with f 9

    Answer: (3,2) with f 9. The smallest f wins. Ties go to the cell added first.

  10. Frontier by f: (1,4) f 9, (0,5) f 9, (4,2) f 9. Which is expanded next?

    • (1,4) with f 9
    • (0,5) with f 9
    • (4,2) with f 9

    Answer: (1,4) with f 9. The smallest f wins. Ties go to the cell added first.

  11. Frontier by f: (0,5) f 9, (4,2) f 9, (2,4) f 9. Which is expanded next?

    • (0,5) with f 9
    • (4,2) with f 9
    • (2,4) with f 9

    Answer: (0,5) with f 9. The smallest f wins. Ties go to the cell added first.

  12. Frontier by f: (4,2) f 9, (2,4) f 9, (1,5) f 9. Which is expanded next?

    • (4,2) with f 9
    • (2,4) with f 9
    • (1,5) with f 9

    Answer: (4,2) with f 9. The smallest f wins. Ties go to the cell added first.

  13. Frontier by f: (2,4) f 9, (1,5) f 9, (4,3) f 9. Which is expanded next?

    • (2,4) with f 9
    • (1,5) with f 9
    • (4,3) with f 9

    Answer: (2,4) with f 9. The smallest f wins. Ties go to the cell added first.

  14. Frontier by f: (1,5) f 9, (4,3) f 9, (3,4) f 9. Which is expanded next?

    • (1,5) with f 9
    • (4,3) with f 9
    • (3,4) with f 9

    Answer: (1,5) with f 9. The smallest f wins. Ties go to the cell added first.

  15. Frontier by f: (4,3) f 9, (3,4) f 9, (2,5) f 9. Which is expanded next?

    • (4,3) with f 9
    • (3,4) with f 9
    • (2,5) with f 9

    Answer: (4,3) with f 9. The smallest f wins. Ties go to the cell added first.

  16. Frontier by f: (3,4) f 9, (2,5) f 9, (4,4) f 9. Which is expanded next?

    • (3,4) with f 9
    • (2,5) with f 9
    • (4,4) with f 9

    Answer: (3,4) with f 9. The smallest f wins. Ties go to the cell added first.

  17. Frontier by f: (2,5) f 9, (4,4) f 9, (3,5) f 9. Which is expanded next?

    • (2,5) with f 9
    • (4,4) with f 9
    • (3,5) with f 9

    Answer: (2,5) with f 9. The smallest f wins. Ties go to the cell added first.

  18. Frontier by f: (4,4) f 9, (3,5) f 9, (4,1) f 11. Which is expanded next?

    • (4,4) with f 9
    • (3,5) with f 9
    • (4,1) with f 11

    Answer: (4,4) with f 9. The smallest f wins. Ties go to the cell added first.

  19. Frontier by f: (3,5) f 9, (4,5) f 9, (4,1) f 11. Which is expanded next?

    • (3,5) with f 9
    • (4,5) with f 9
    • (4,1) with f 11

    Answer: (3,5) with f 9. The smallest f wins. Ties go to the cell added first.

  20. Frontier by f: (4,5) f 9, (4,1) f 11. Which is expanded next?

    • (4,5) with f 9
    • (4,1) with f 11

    Answer: (4,5) with f 9. The smallest f wins. Ties go to the cell added first.

How it runs, step by step

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. 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.

  10. 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.

  11. 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.

  12. 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.

  13. Expand (0,5), g = 5, f = 9. Every open neighbour was reached already, so nothing joins the frontier.

    Expand (0,5), 0 new cells.

  14. 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.

  15. 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.

  16. Expand (1,5), g = 6, f = 9. Every open neighbour was reached already, so nothing joins the frontier.

    Expand (1,5), 0 new cells.

  17. 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.

  18. 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.

  19. Expand (2,5), g = 7, f = 9. Every open neighbour was reached already, so nothing joins the frontier.

    Expand (2,5), 0 new cells.

  20. 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.

  21. Expand (3,5), g = 8, f = 9. Every open neighbour was reached already, so nothing joins the frontier.

    Expand (3,5), 0 new cells.

  22. 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.

  23. 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.

The code

Grid Search and A*, in Python

def shortest_path(open, use_heuristic):
    rows, cols = len(open), len(open[0])
    goal = (rows - 1, cols - 1)
    def h(p):                                               # Manhattan estimate, 0 for plain BFS
        return abs(goal[0] - p[0]) + abs(goal[1] - p[1]) if use_heuristic else 0
    g = {(0, 0): 0}
    frontier = [(0, 0)]                                     # BFS: a queue; A*: a priority queue on f
    while frontier:
        cur = min(frontier, key=lambda it: g[it] + h(it))   # smallest f; all equal for BFS
        frontier.remove(cur)
        if cur == goal:
            return g[cur]                                   # first time the goal comes off: done
        for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            next = (cur[0] + dr, cur[1] + dc)
            if not (0 <= next[0] < rows) or not (0 <= next[1] < cols):
                continue
            if not open[next[0]][next[1]]:                  # wall
                continue
            if next not in g:                               # first visit is the shortest
                g[next] = g[cur] + 1
                frontier.append(next)
    return -1                                               # no path

Grid Search and A*, in JavaScript

function shortestPath(open, useHeuristic) {
  const rows = open.length, cols = open[0].length;
  const goal = [rows - 1, cols - 1];
  const key = ([r, c]) => `${r},${c}`;                       // arrays compare by reference, so key cells by string
  const h = (p) =>                                           // Manhattan estimate, 0 for plain BFS
    useHeuristic ? Math.abs(goal[0] - p[0]) + Math.abs(goal[1] - p[1]) : 0;
  const g = new Map([[key([0, 0]), 0]]);
  const frontier = [[0, 0]];                                 // BFS: a queue; A*: a priority queue on f
  while (frontier.length > 0) {
    const f = (it) => g.get(key(it)) + h(it);                // smallest f; all equal for BFS
    const cur = frontier.reduce((best, it) => (f(it) < f(best) ? it : best));
    frontier.splice(frontier.indexOf(cur), 1);
    if (key(cur) === key(goal)) return g.get(key(cur));      // first time the goal comes off: done
    for (const [dr, dc] of [[1, 0], [0, 1], [-1, 0], [0, -1]]) {
      const next = [cur[0] + dr, cur[1] + dc];
      if (next[0] < 0 || next[0] >= rows || next[1] < 0 || next[1] >= cols) continue;
      if (!open[next[0]][next[1]]) continue;                 // wall
      if (!g.has(key(next))) {                               // first visit is the shortest
        g.set(key(next), g.get(key(cur)) + 1);
        frontier.push(next);
      }
    }
  }
  return -1;                                                 // no path
}

Grid Search and A*, in Kotlin

fun shortestPath(open: Array<BooleanArray>, useHeuristic: Boolean): Int {
    val rows = open.size; val cols = open[0].size
    val goal = (rows - 1) to (cols - 1)
    fun h(p: Pair<Int, Int>) =                                   // Manhattan estimate, 0 for plain BFS
        if (useHeuristic) abs(goal.first - p.first) + abs(goal.second - p.second) else 0
    val g = mutableMapOf((0 to 0) to 0)
    val frontier = mutableListOf(0 to 0)                 // BFS: a queue; A*: a priority queue on f
    while (frontier.isNotEmpty()) {
        val cur = frontier.minByOrNull { g[it]!! + h(it) }!!   // smallest f; all equal for BFS
        frontier.remove(cur)
        if (cur == goal) return g[cur]!!                         // first time the goal comes off: done
        for ((dr, dc) in listOf(1 to 0, 0 to 1, -1 to 0, 0 to -1)) {
            val next = (cur.first + dr) to (cur.second + dc)
            if (next.first !in 0 until rows || next.second !in 0 until cols) continue
            if (!open[next.first][next.second]) continue          // wall
            if (next !in g) { g[next] = g[cur]!! + 1; frontier += next }   // first visit is the shortest
        }
    }
    return -1                                                    // no path
}

This lesson has no write-it-yourself editor. It is free, like every lesson, and nothing here is locked.

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.

Where this is used

Robot navigation stacksRobotics

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.

Game agent pathfindingGames

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.

Maze routing on boards and chipsElectronics design

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.

Warehouse floor robotsLogistics

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

Next up