A* Pathfinding

Drag to paint walls. Drag the start or goal node to move it. A* expands the lowest-cost frontier first using a Manhattan-distance heuristic. Each evaluated cell shows g (cost so far, top-left), h (heuristic, top-right), and f = g + h (center).

Start Goal Frontier Visited Path Wall
Grid: — Frontier: 0 Visited: 0 Path: —

How A* works

A* finds the shortest path between two cells by always expanding the most promising cell first. For each cell it tracks three numbers:

  • g — the cost of the cheapest path found so far from the start to this cell (here, one per step).
  • h — a heuristic estimate of the remaining cost from this cell to the goal. We use the Manhattan distance (|Δx| + |Δy|), which never overestimates, so A* is guaranteed to find a shortest path.
  • f = g + h — the estimated total cost of a path through this cell. A* always expands the frontier cell with the lowest f.

Each step the algorithm:

  1. Picks the frontier cell with the smallest f and marks it visited.
  2. If that cell is the goal, it walks the recorded parent links backwards to reveal the path.
  3. Otherwise it looks at the four neighbours, and for any that offer a cheaper g, records this cell as their parent and adds them to the frontier.

Because the heuristic guides the search toward the goal, A* explores far fewer cells than a blind flood fill while still guaranteeing the shortest route. If the frontier empties before reaching the goal, no path exists.