A* pathfinding

O(E log V)

A* finds a shortest path like BFS, but it spends its effort wisely. Each candidate cell is scored f = g + h, where g is the actual distance from the start and h is a heuristic estimate of the distance still to go — here the Manhattan distance to the goal. It always expands the open cell with the smallest f, so it pushes toward the goal instead of fanning out blindly. As long as the heuristic never overestimates (Manhattan distance on a unit grid is admissible), A* is guaranteed to find an optimal path — the same length BFS would — while typically visiting a fraction of the cells.

Click a cell to toggle a wall
Grid
Edit the input and press Play

How it works

  1. Score the start with f = g + h and put it in the open set.
  2. Expand the open cell with the lowest f.
  3. For each free neighbour, if this route is cheaper, update its g and re-score it.
  4. When the goal is expanded, follow the parent pointers back — the path is optimal.

Pseudocode

1aStar(grid, start, goal):            # O(E log V)2  g[start] ← 0;  open ← {start}3  while open not empty:4    cell ← node in open with least f  # f = g + h5    if cell = goal: stop6    for nbr in free neighbours(cell):7      if g[cell] + 1 < g[nbr]:8        g[nbr] ← g[cell] + 1; prev[nbr] ← cell9        f[nbr] ← g[nbr] + manhattan(nbr, goal)10        add nbr to open11  walk prev from goal back to start