Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Pathfinding

A* Search Visualiser

Dijkstra, plus a guess at how far there is still to go.

Drawthen drag on the board
Board

A* is Dijkstra with a hint: each cell is ranked by the cost to reach it plus a guess at the cost still to come, so the search leans towards the end.

Cells expanded
0
In the open list
1
O((cells + edges) log cells), usually far lessextra space O(cells)

There are 303 cells to search on this board. The gap between that and the cells expanded is what a better search order buys you — walls and mud change it, so redraw the board and watch it move.

  • Start
  • End
  • Wall
  • Mud (costs 5)
  • Waiting to be expanded
  • Expanded
  • Route
function aStar(grid, start, end) {
const dist = new Map([[start, 0]]);
const cameFrom = new Map([[start, null]]);
const open = [start];
while (open.length > 0) {
const cell = takeLowest(open, dist, end); // cost + guess
if (cell === end) return path(cameFrom, end);
for (const next of neighbours(grid, cell)) {
const cost = dist.get(cell) + stepCost(grid, next);
if (cost < (dist.get(next) ?? Infinity)) {
dist.set(next, cost);
cameFrom.set(next, cell);
open.push(next);
}
}
}
return null; // the end is walled off
}
// Manhattan distance. It never overestimates,
// which is what keeps the answer optimal.
const guess = (cell, end) =>
Math.abs(cell.row - end.row) +
Math.abs(cell.col - end.col);

The highlighted line is the one that produced the picture on the left.

What A* Search does

Dijkstra treats every direction as equally promising, so it spends most of its time exploring away from the goal. A* ranks each cell by the cost to reach it plus an estimate of the cost still to come. The estimate costs nothing to compute and pulls the search towards the goal, while the real cost keeps the answer honest.

How it works, step by step

  1. Score each waiting cell as cost-so-far plus a guess at the remaining distance.
  2. Expand the cell with the lowest score.
  3. If it is the goal, stop and rebuild the route.
  4. Otherwise update each neighbour's cost-so-far exactly as Dijkstra does, and re-score it.

What to watch for

  • The visited area is a narrow wedge aimed at the goal, rather than Dijkstra's expanding circle, and the cells-expanded counter is far lower for the same answer.
  • The route A* reports costs exactly the same as Dijkstra's. The guess changes the order cells are examined in, never the answer.
  • The guess used here is Manhattan distance: how many steps away the goal would be with nothing in the way. On a four-direction grid it can never overestimate, which is what keeps the answer optimal.
  • Wall the goal off completely and A* degrades to Dijkstra: with nowhere to lean, the hint stops helping.

Cost

TimeO((cells + edges) log cells), usually far less
Extra spaceO(cells)
FindsCheapest route, if the guess never overestimates
Handles costsYes
Waiting listPriority queue on cost + guess

When to reach for it

For point-to-point routing where a sensible estimate of the remaining distance exists — game movement, maps, robot navigation. If you need distances from one start to everywhere, there is nothing to aim at and Dijkstra is the right algorithm.

Read more