Why does pathfinding lag when there is no path?

When a goal is unreachable, A* expands 52,286 nodes on a 256x256 grid, which is 99.7% of the roughly 52,428 walkable cells on the map. A successful search on the same map expands 10,920. The failed search takes 7.57 ms against 1.66 ms, and it is not a constant factor you can tune away. It is the algorithm doing exactly what it must: proving a negative requires looking everywhere.

The short answer

• A* returns "no path" only after its open set empties, which means every reachable cell has been visited and closed.
• The heuristic prunes nothing in the failure case. There is no partial progress toward an unreachable goal to prefer.
• Cost scales with the size of the reachable region, not with the distance to the goal. A unit sealed in a small closet fails instantly. A unit on the open side of a sealed door searches the whole open side.
• On a 256x256 grid the failure case is 4.6x slower and expands 4.8x more nodes than the success case.
• The gap widens with map size. A successful search touches 34% of a 64x64 map but only 21% of a 256x256 one, while a failed search touches 99.7% of both.
• This is why a game stutters exactly when a player walls something off, and never during normal play.

What the numbers look like

Node 23.5.0, Apple M3. Grids are 20% random walls, 4-way movement, Manhattan heuristic, binary heap open set. Start is the top-left corner, goal is the bottom-right. In the failure runs the goal's three neighbours are walled in, so it is provably unreachable. Each figure is the median of 5 runs of the script below, each of which itself reports the median of 9 searches.

The last row is the one to look at. A 256x256 grid holds 65,536 cells, and at 20% walls roughly 52,428 are walkable. The failed search expanded 52,286 of them. It did not approximately search the map. It searched the map.

Why doesn't the heuristic help?

A* orders its open set by f = g + h, where h estimates the remaining distance to the goal. When a path exists, that estimate pulls the search into a narrow corridor aimed at the target, and most of the grid is never touched. The 64x64 success case expanded 1,113 cells out of roughly 3,276 walkable, so it ignored 66% of the map. At 256x256 it ignored 79%.

When the goal is unreachable, h still produces numbers, and they are still smallest near the goal. But no amount of ordering changes the termination condition. A* stops when it pops the goal, or when the open set is empty. The goal never gets popped. So the loop runs until every reachable cell has been closed, and the heuristic has only decided the order in which they were closed, not how many.

This is the part that surprises people: a better heuristic makes successful searches faster and does nothing at all for failed ones.

Why does it feel like a random stutter?

Because the trigger is a change in map topology, not a change in unit count. Consider a tower defence game where the player is allowed to wall off a lane. Every frame that lane is open, each unit's path search expands a few hundred nodes. The frame the lane closes, every unit that wanted to go through it runs a full-map search.

Fifty units on the 256x256 grid above is 50 x 7.57 ms, or 379 ms in one frame. That is a visible freeze, and it happens on exactly the frame where the player did something, which makes it look like the placement logic is slow rather than the pathfinder.

What to do about it

Three fixes, in the order they are worth doing.

Precompute connectivity. Run a flood fill and label each connected region with an id. Before searching, compare the start and goal region ids. If they differ, return "no path" immediately, without touching A* at all. Recompute the labels when the map changes, which is once per wall placement rather than once per unit per frame. This turns the entire failure case into an integer comparison.

// One flood fill after any map edit; O(cells) once, not O(cells) per unit.
function labelRegions(grid, W, H) {
  const region = new Int32Array(W * H).fill(-1)
  let next = 0
  for (let i = 0; i < W * H; i++) {
    if (grid[i] || region[i] !== -1) continue
    const stack = [i]; region[i] = next
    while (stack.length) {
      const c = stack.pop(), cx = c % W, cy = (c / W) | 0
      for (const [dx, dy] of [[1,0],[-1,0],[0,1],[0,-1]]) {
        const nx = cx + dx, ny = cy + dy
        if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue
        const ni = ny * W + nx
        if (grid[ni] || region[ni] !== -1) continue
        region[ni] = next; stack.push(ni)
      }
    }
    next++
  }
  return region
}

// Then, per unit:
if (region[startIdx] !== region[goalIdx]) return null   // no A* at all

Cap the node budget. Give each search a maximum expansion count and abandon it past the cap, treating the result as "no path for now". A unit that gives up for one frame and retries next frame is far better than a frame that takes 379 ms. Pick the cap from your measured success case: if real paths expand 10,920 nodes, a cap of 20,000 costs you nothing and bounds the worst case.

Spread searches across frames. Queue path requests and serve a fixed number per frame. This does not make any single search faster, but it converts a spike into a constant cost, which is what a frame budget actually needs.

Does this apply to Dijkstra and BFS too?

Yes, and more so. Both lack a goal heuristic entirely, so their successful searches already explore most of the reachable region. Their failure case costs roughly the same as their success case, which means the failure is less surprising but the baseline is worse. A* is the algorithm where the gap between the good case and the bad case is widest, and therefore the one where an unexpected failure hurts most.

Check it yourself

Save as astar-bench.cjs and run node astar-bench.cjs. It takes about 10 seconds and prints the table above.

class MinHeap {
  constructor(){ this.a = [] }
  push(n){ const a=this.a; a.push(n); let i=a.length-1
    while(i>0){ const p=(i-1)>>1; if(a[p].f<=a[i].f) break; [a[p],a[i]]=[a[i],a[p]]; i=p } }
  pop(){ const a=this.a, top=a[0], last=a.pop()
    if(a.length){ a[0]=last; let i=0
      for(;;){ const l=2*i+1, r=l+1; let m=i
        if(l<a.length && a[l].f<a[m].f) m=l
        if(r<a.length && a[r].f<a[m].f) m=r
        if(m===i) break; [a[m],a[i]]=[a[i],a[m]]; i=m } }
    return top }
  get size(){ return this.a.length }
}

function astar(grid, W, H, sx, sy, gx, gy) {
  const g = new Float64Array(W*H).fill(Infinity), closed = new Uint8Array(W*H)
  const h = (x,y) => Math.abs(x-gx) + Math.abs(y-gy)
  const open = new MinHeap(); let expanded = 0
  g[sy*W+sx] = 0; open.push({x:sx, y:sy, f:h(sx,sy)})
  while (open.size) {
    const c = open.pop(), ci = c.y*W + c.x
    if (closed[ci]) continue
    closed[ci] = 1; expanded++
    if (c.x === gx && c.y === gy) return {found:true, expanded}
    for (const [dx,dy] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const nx = c.x+dx, ny = c.y+dy
      if (nx<0 || ny<0 || nx>=W || ny>=H) continue
      const ni = ny*W + nx
      if (grid[ni] || closed[ni]) continue
      const ng = g[ci] + 1
      if (ng < g[ni]) { g[ni] = ng; open.push({x:nx, y:ny, f:ng + h(nx,ny)}) }
    }
  }
  return {found:false, expanded}
}

function build(W, H, walled) {
  const grid = new Uint8Array(W*H)
  for (let i=0;i<W*H;i++) if (Math.random() < 0.20) grid[i] = 1
  grid[0] = 0; grid[W*H-1] = 0
  if (walled) { const gx=W-1, gy=H-1
    for (const [dx,dy] of [[-1,0],[0,-1],[-1,-1]]) grid[(gy+dy)*W + (gx+dx)] = 1 }
  return grid
}

const median = a => { const s=[...a].sort((x,y)=>x-y); return s[s.length>>1] }
for (let w=0; w<40; w++) { const G = build(64,64,false); astar(G,64,64,0,0,63,63) }

for (const S of [64,128,256]) {
  for (const walled of [false,true]) {
    const ts=[], ex=[]
    for (let r=0;r<9;r++) {
      const G = build(S,S,walled)
      const t0 = performance.now()
      const res = astar(G,S,S,0,0,S-1,S-1)
      ts.push(performance.now()-t0); ex.push(res.expanded)
      if (walled && res.found) throw new Error("goal should be unreachable")
    }
    console.log(`${S}x${S}\t${walled?"NO path":"path   "}\t${median(ts).toFixed(2)} ms\t${median(ex)} nodes`)
  }
}

The throw in the failure branch is worth keeping. Sealing a corner with three walls is easy to get wrong by one index, and a "failure" benchmark that quietly found a path would report the success numbers twice and look perfectly reasonable.

Region labelling and a per-frame search budget are both built into the navigation layer of our game engine, for exactly the tower-defence case above.