A* Pathfinding on a Grid

Start from brute force

The obvious approach is breadth-first search from start: expand cells in rings of 1, 2, 3 … steps and return the ring number when goal appears. When every step costs 1 it is correct, because BFS reaches each cell first by a route with the fewest steps. It costs O(R·C) time and O(R·C) space for the queue and the visited set. It is not wrong, just blind: it expands every cell nearer the start than the goal is, in every direction, including the half of the map behind the start. Trying every route with DFS is far worse, because the number of simple paths grows exponentially with the grid.

The approach

A* expands cells in order of f = g + h, where g is the steps taken so far and h is the Manhattan distance to the goal. On a 4-direction grid with unit steps, one move changes Manhattan distance by exactly 1, so it never overestimates (it is admissible) and never drops faster than the cost paid (it is consistent). That gives the invariant: when a cell is popped with its current best g, that g is final, so the first time the goal is popped, its g is the answer.

In the reference, frontier is a heapq of (f, g, cell) tuples and best_g holds the cheapest g found per cell. A neighbor is pushed only when ng beats best_g. Because heapq has no decrease-key, an improved cell is pushed again, and a popped entry whose g exceeds best_g[cur] is a stale copy and is skipped. If the heap empties first, the function returns -1.

Walk through an example

On the first example the direct route down is walled off, so f climbs from 2 to 6 as the search is pushed around the wall, then holds at 6, the answer.

Complexity

With a consistent heuristic each open cell is expanded at most once and pushed at most four times, so A* costs O(R·C·log(R·C)) time for heap operations and O(R·C) space for best_g and frontier. BFS is O(R·C) time and space. A* does not beat that worst-case bound; it cuts how many cells are expanded when the heuristic points the right way.

Edge cases to test

• Start equals goal: astar([[0,0],[0,0]], [0,0], [0,0]) returns 0, because the start is the first cell popped.
• No route, including a goal one diagonal step away: astar([[0,1],[1,0]], [0,0], [1,1]) returns -1. The loop must end when the frontier is empty, not only when the goal is found.
• The goal is a wall: astar([[0,1]], [0,0], [0,1]) returns -1, since walls are never pushed. The reference does not check the start cell, so a start on a wall still walks out (astar([[1,0]], [0,0], [0,1]) returns 1); if your inputs allow that, decide the rule and test it.
• A non-square grid: astar([[0,0,0,0]], [0,0], [0,3]) returns 3. Bounds checks must use the row count R and column count C separately.

Common mistakes

• A non-admissible heuristic (it overestimates) — A* then returns a non-optimal path.
• Wrong heuristic for the movement model: Manhattan for 4-directional, Chebyshev or Euclidean for 8-directional.
• Not tracking g separately from f, so re-relaxation uses the wrong cost.

Follow-ups an interviewer asks next

What changes if diagonal moves are allowed?

Add the four diagonal offsets and change the heuristic, because Manhattan now overestimates. If a diagonal costs 1, use Chebyshev distance, max(|dr|, |dc|). If it costs √2, use octile distance, max + (√2 − 1)·min. Many games also forbid cutting a corner between two walls; that is a rule in neighbor generation, not in the heuristic.

Cells have different costs (road, mud). Does A* still work?

Yes. Replace ng = g + 1 with g + cost(next), and keep the heuristic a lower bound by scaling Manhattan by the cheapest possible step: if a road step costs 0.5, use 0.5·(|dr| + |dc|). Cells get improved more often, so the stale-entry check does more work.

Can you return the path, not just its length?

Keep a parent map: whenever best_g[next] improves, set parent[next] = cur. When the goal pops, follow parents back to the start and reverse the list. It costs O(R·C) extra space and does not change which cells are expanded.

The map is large and many queries hit it. What next?

Spend preprocessing to save search. Landmark heuristics (ALT) store distances to a few landmarks and use the triangle inequality for a tighter admissible bound. Hierarchical planners search coarse clusters first and refine. On uniform-cost grids, Jump Point Search skips symmetric paths without preprocessing. Bidirectional search from both ends also shrinks the explored area.

Where this shows up

A* is the workhorse of game pathfinding and robotics motion planning. The general idea — guide a search with a cheap admissible lower-bound estimate — makes it the go-to whenever Dijkstra is too slow but you can estimate distance-to-goal.

Reference solution

import heapq

def astar(grid, start, goal):
    R, C = len(grid), len(grid[0])
    start, goal = tuple(start), tuple(goal)

    def h(p):
        return abs(p[0] - goal[0]) + abs(p[1] - goal[1])   # Manhattan

    best_g = {start: 0}
    frontier = [(h(start), 0, start)]                       # (f, g, cell)
    while frontier:
        f, g, cur = heapq.heappop(frontier)
        if cur == goal:
            return g
        if g > best_g.get(cur, 1 << 30):
            continue                                        # stale entry
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = cur[0] + dr, cur[1] + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 0:
                ng = g + 1
                if ng < best_g.get((nr, nc), 1 << 30):
                    best_g[(nr, nc)] = ng
                    heapq.heappush(frontier, (ng + h((nr, nc)), ng, (nr, nc)))
    return -1


print(astar([[0,0,0],[1,1,0],[0,0,0]], [0,0], [2,0]))  # -> 6
print(astar([[0,1],[1,0]], [0,0], [1,1]))              # -> -1

function astar(grid: number[][], start: number[], goal: number[]): number {
  const R = grid.length, C = grid[0].length;
  const key = (r: number, c: number) => r * C + c;
  const h = (r: number, c: number) => Math.abs(r - goal[0]) + Math.abs(c - goal[1]);

  const bestG = new Map<number, number>([[key(start[0], start[1]), 0]]);
  // frontier: array of [f, g, r, c]; pop the minimum f by scan (fine for grids)
  const frontier: number[][] = [[h(start[0], start[1]), 0, start[0], start[1]]];
  while (frontier.length) {
    let bi = 0;
    for (let i = 1; i < frontier.length; i++) if (frontier[i][0] < frontier[bi][0]) bi = i;
    const [f, g, r, c] = frontier.splice(bi, 1)[0];
    if (r === goal[0] && c === goal[1]) return g;
    if (g > (bestG.get(key(r, c)) ?? Infinity)) continue;
    for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === 0) {
        const ng = g + 1;
        if (ng < (bestG.get(key(nr, nc)) ?? Infinity)) {
          bestG.set(key(nr, nc), ng);
          frontier.push([ng + h(nr, nc), ng, nr, nc]);
        }
      }
    }
  }
  return -1;
}

console.log(astar([[0,0,0],[1,1,0],[0,0,0]], [0,0], [2,0])); // -> 6
console.log(astar([[0,1],[1,0]], [0,0], [1,1]));            // -> -1