A* and BFS pathfinding
mediumBFS expands in rings; A* aims at the goal; greedy best-first charges at it and gets the answer wrong. Compare expanded-cell counts on the same maze - the heuristic is the only difference.
O(E) with a perfect heuristicWorst O(E log V)Space O(V)Saved in this browser - no sign-up, nothing sent anywhere.
How a* and bfs pathfinding works
A maze is a graph in disguise: every open cell is a vertex with up to four unit-weight neighbours. This visualizer runs three searches over the same painted maze - BFS, A* and greedy best-first - and they differ in exactly one number: how each scores the next cell to expand.
A* scores a cell as f = g + h: g is the exact cost paid so far, h an estimate of the cost remaining - here Manhattan distance, which on a 4-connected grid never overestimates. That admissibility is the guarantee: A* keeps BFS's optimality while the estimate steers expansion toward the goal, skipping most of the map.
The other two are the same loop with h distorted. BFS sets h to 0 and expands in even rings - optimal, but blind. Greedy best-first keeps only h and drops g: it charges at the goal, dives into any dead end that points the right way, and its path carries no optimality guarantee. A* with h set to 0 is exactly Dijkstra.
Step by step
- Start top-left at (0, 0), goal bottom-right at (8, 11). The starting estimate is h = 8 + 11 = 19, so no path can beat 19 steps.
- Expand the start: its open neighbours get g = 1 and f = 1 + h. The open set orders every discovered cell by f.
- Each round pops the smallest f. Ties between cells resolve toward the goal, because h penalises anything drifting away from it.
- Walls force detours: when the straight route is blocked, g grows until cells set aside earlier become the cheapest frontier again - the fallback greedy best-first lacks.
- The goal comes off the open set and the search stops - with an admissible h, nothing still pending could reach it cheaper.
- Walk the cameFrom pointers backwards from the goal to reconstruct the path, then switch to BFS: same path length, far more cells expanded.
Complexity
| Best case time | O(E) with a perfect heuristic |
|---|---|
| Worst case time | O(E log V) |
| Space | O(V) |
A* with an admissible heuristic is optimal; with h = 0 it is Dijkstra.
Reference implementation
Python
import heapq
def astar(grid, start, goal, use_heuristic=True):
rows, cols = len(grid), len(grid[0])
def h(c):
return abs(c[0] - goal[0]) + abs(c[1] - goal[1]) if use_heuristic else 0
g = {start: 0}
came = {}
pq = [(h(start), 0, start)]
while pq:
_, gu, u = heapq.heappop(pq)
if u == goal:
path = [u]
while u in came:
u = came[u]
path.append(u)
return path[::-1]
if gu > g.get(u, float("inf")):
continue
for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
v = (u[0] + dr, u[1] + dc)
if not (0 <= v[0] < rows and 0 <= v[1] < cols):
continue
if grid[v[0]][v[1]] == 1:
continue
if gu + 1 < g.get(v, float("inf")):
g[v] = gu + 1
came[v] = u
heapq.heappush(pq, (g[v] + h(v), g[v], v))
return NoneJavaScript
function astar(grid, start, goal, useHeuristic = true) {
const R = grid.length, C = grid[0].length;
const h = ([r, c]) =>
useHeuristic ? Math.abs(r - goal[0]) + Math.abs(c - goal[1]) : 0;
const key = ([r, c]) => r * C + c;
const g = new Map([[key(start), 0]]);
const came = new Map();
const open = [[h(start), 0, start]];
while (open.length) {
open.sort((a, b) => a[0] - b[0]);
const [, gu, u] = open.shift();
if (u[0] === goal[0] && u[1] === goal[1]) return came;
for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
const v = [u[0] + dr, u[1] + dc];
if (v[0] < 0 || v[0] >= R || v[1] < 0 || v[1] >= C) continue;
if (grid[v[0]][v[1]] === 1) continue;
if (gu + 1 < (g.get(key(v)) ?? Infinity)) {
g.set(key(v), gu + 1);
came.set(key(v), u);
open.push([gu + 1 + h(v), gu + 1, v]);
}
}
}
return null;
}Worth noticing
The heuristic is the only difference
Switch between BFS and A* on the same maze and compare the expanded-cell counts. Both find a shortest path; A* looks at far fewer cells because the heuristic biases it towards the goal.
Admissible means never overestimating
Manhattan distance on a 4-connected grid can never exceed the true remaining cost, which is what guarantees A* still finds an optimal path. Overestimate - as greedy best-first effectively does by ignoring g - and optimality is lost.
Greedy best-first is fast and wrong
Run it against a maze with a dead end pointing at the goal. It charges straight in, because it only asks 'how close does this look?' and never accounts for the distance already travelled. A* adds g back in and stays honest.
A* with h = 0 is exactly Dijkstra
The f = g + h formula degrades gracefully. No heuristic means no guidance, so it expands uniformly in all directions - which is Dijkstra, and on a uniform-cost grid, BFS.
Common pitfalls
- Using an inadmissible heuristic. Manhattan distance is only valid without diagonal moves; allow diagonals and it overestimates, quietly costing A* its shortest-path guarantee.
- Trusting greedy best-first's output. It optimises the appearance of progress - h alone - and happily returns a much longer path after diving into a plausible-looking dead end.
- Skipping the closed set. Expanded cells are final on a grid like this; re-expanding them multiplies work without ever changing the answer.
- Stopping when the goal is first discovered rather than when it is popped from the open set. A cheaper route may still be pending; the pop is the proof.
- Inflating h to speed things up and forgetting the cost: weighted A* expands fewer cells but only bounds, rather than guarantees, path quality.
Where it is used
- Game AI: unit movement on tile maps is A* with tuned heuristics almost universally.
- Robotics and warehouse automation, planning collision-free routes over occupancy grids.
- Turn-by-turn navigation, where Dijkstra-family searches run under heuristics and heavy preprocessing.
- Puzzle solvers - 8-puzzle, Sokoban - where A* over state graphs with admissible heuristics is standard.
Frequently asked questions
What is the time and space complexity of A* pathfinding?
Worst case O(E log V), the same as Dijkstra - with a useless heuristic it degenerates into exactly that. Best case O(E) with a perfect heuristic, when only the true path is expanded. Space is O(V) for the open set, closed set and cameFrom map.
What makes a heuristic admissible?
It must never overestimate the true remaining cost. Manhattan distance qualifies on a 4-connected grid because every move changes it by at most 1. Admissible heuristics keep A* optimal; the closer they hug the true cost without crossing it, the fewer cells get expanded.
Why not just use greedy best-first search if it is faster?
Because it ignores costs already paid. Scoring by h alone, it dives into any dead end that points at the goal and returns whatever path it stumbled through - fast, but with no optimality guarantee. Paint a pocket facing the goal in this visualizer and watch it commit.
Is A* better than BFS on grids?
Same worst case, same path length - on a unit-cost grid both are optimal. The difference is expansions: BFS explores rings in every direction while A*'s heuristic focuses effort toward the goal. Compare the expanded counts here on the same maze; the gap is the entire argument for heuristics.