Home/Pathfinding/A*
Search algorithmsCTRL K

A*

· best-first search · Manhattan heuristic
/pathfinding/a-star
EXPANDED
0
closed cells
OPEN SET
1
candidates in the heap
PUSHES
0
relaxations that improved g
PATH
—
length once the goal is reached
WALLS
28%
of 880 cells blocked
closedopencurrentpathstart / goal
44×20 · 28% walls · seed 7 · 567 steps
step 0 / 566
Walls28
a_star.ts
1
function aStar(grid: Grid, start: Cell, goal: Cell) {
2
  const open = new MinHeap<Cell>([start]);
3
  const distance = new Map([[start, 0]]), parent = new Map();
4
  while (open.size > 0) {
5
    const current = open.pop(); // lowest score = distance + heuristic
6
    if (current === goal) return rebuild(parent, current);
7
    for (const neighbor of neighbors(grid, current)) {
8
      const newDistance = distance.get(current)! + 1;
9
      if (newDistance < (distance.get(neighbor) ?? Infinity)) {
10
        distance.set(neighbor, newDistance); parent.set(neighbor, current);
11
        open.push(neighbor, newDistance + heuristic(neighbor, goal));
12
      }
13
    }
14
  }
15
}
CURRENT STEP
line 2

Start at (12, 1), goal at (5, 42). The open set holds only the start.

// how it works

Understanding A*

A* · f = g + h · why it beats Dijkstra on a map
01

The idea

A* keeps an open set of cells to explore and always expands the one with the lowest f = g + h, where g is the cost from the start so far and h is an estimate of the cost still to go. With h = 0 it is Dijkstra; with a good h it heads straight for the goal and expands far fewer cells.

On a grid with 4-way movement the Manhattan distance is the natural heuristic. It never overestimates, so A* is guaranteed to return a shortest path; the closed cells you see are the price of that guarantee.

02

The four stages

1
popopen cell with lowest g + h
2
checkis it the goal? then rebuild
3
relaxcheaper neighbours get new g
4
pathfollow parents back to start
03

Complexity

best
O(d)heuristic is exact, straight line to goal
average
O(E log V)depends on the heuristic quality
worst
O(E log V)h = 0, same as Dijkstra
space
O(V)open and closed sets, parents
04

Versus its siblings

CELLS EXPANDED · 44×20 MAZE
bfs
612
dijkstra
604
greedy
96
a*
188
jps
41
same maze, same start and goal · greedy path was 23% longer
05

Pseudocode

A*(start, goal)
  open ← {start}; dist[start] ← 0
  while open not empty
    current ← node in open with lowest dist + heuristic
    if current = goal: return path via parent
    for each neighbour of current
      if dist[current] + 1 < dist[neighbour]
        dist[neighbour] ← dist[current] + 1; parent[neighbour] ← current; add neighbour to open
06

When to use

Any map with a meaningful distance: game units, robots, GPS routing, puzzle solvers.
When you need the optimal path and can afford to keep an open set in memory.
07

Pitfalls

A heuristic that overestimates breaks optimality. Manhattan for 4-way, octile for 8-way, Euclidean is safe but weak.
Ties in f make A* wander. Break ties toward larger g to stay focused.
Open set as a plain array is O(n) per pop. Use a binary heap.
Dynamic maps: re-running A* every change is wasteful. D* Lite reuses the search.
08

History

Peter Hart, Nils Nilsson and Bertram Raphael published A* in 1968 at Stanford Research Institute, for Shakey, the first mobile robot that could reason about its actions. It generalised Dijkstra’s 1959 algorithm by adding the heuristic term.

Back to Pathfinding