A* search

August 4, 2026

A planner searching a grid has to decide which cell to look at next. Dijkstra’s algorithm always takes the cheapest cell reached so far. That is correct, and it spreads outward in every direction, including directly away from the goal.

A* adds one thing: an estimate of the distance still to go.

Click anywhere below to move the goal.

Shaded cells were examined. The path is the same path Dijkstra would find. The difference is how much of the map had to be looked at to find it.

The ordering rule

Both algorithms keep a frontier of cells waiting to be examined and always take the best one. They differ only in what counts as best.

Dijkstra orders by cost so far:

A* orders by cost so far plus estimated cost remaining:

Set the heuristic to None and the tool becomes Dijkstra exactly, because $h(n) = 0$ makes $f(n) = g(n)$. That is the whole relationship between the two algorithms.

What the estimate has to satisfy

$h$ must never overestimate the true remaining cost. A heuristic with that property is admissible, and it is what makes the path optimal.

The argument is short. A* stops when it takes the goal off the frontier. If some other route were cheaper, one of its cells would still be waiting with

and a smaller $f$ would have been taken first. So no cheaper route can be outstanding when the goal is reached.

Overestimating breaks that. The search becomes confident about a direction it has no right to be confident about, and it can commit to a worse route.

A stronger condition, consistency, requires

for every step from $n$ to $n'$. Consistency implies admissibility and adds a guarantee: $f$ never decreases along the search, so once a cell is examined its cost is final and it never needs revisiting.

Choosing $h$ for the grid

The right heuristic depends on which moves are legal, and getting this wrong is the most common way to break A* by accident.

With four-way movement, the true distance ignoring obstacles is the Manhattan distance:

With eight-way movement, a diagonal covers one row and one column at a cost of $\sqrt{2}$ instead of $2$. The exact obstacle-free distance is the octile distance:

Turn diagonals on and switch to Manhattan. It now counts a diagonal as $2$ when it costs $\sqrt{2}$, so it overestimates, and the path is no longer guaranteed optimal. The readout compares against the true cost whenever that happens.

Euclidean distance is always admissible, but on a grid it underestimates badly, because no vehicle restricted to eight directions can travel the hypotenuse. Underestimating is safe and slow: more cells get examined for the same answer.

Weighting the estimate

The weight slider multiplies $h$:

At $w = 1$ this is ordinary A*. Above that it is weighted A*, which examines dramatically fewer cells and gives up the optimality guarantee in a bounded way. The path it returns costs at most $w$ times the best one.

Push the weight up and watch the shaded region collapse toward a narrow corridor running at the goal, while the path cost creeps above the optimum. That is the trade in its clearest form: a planner that is sure looks at less.

Real planners use this deliberately. When a robot must replan every control cycle, a route five percent long that arrives in time beats an optimal one that misses the deadline.

What the shape of the search tells you

Set the heuristic to None. The examined region is a disc: Dijkstra has no idea where the goal is, so it grows evenly.

Switch to Octile. The disc collapses into an ellipse elongated toward the goal.

Now draw a wall between start and goal. The search spills along the barrier and pools against it, because every cell near the wall looks good to the heuristic and is expensive to actually reach. Straight-line estimates cannot see walls, and that gap between the estimate and reality is exactly where the extra work goes.

That failure is why planners in cluttered spaces often precompute better estimates than a straight line.

Where this leaves you

A* is optimal, complete, and optimally efficient: no algorithm using the same heuristic can examine fewer cells and still guarantee the best path. That is about as strong as guarantees get.

The cost is that it searches a discrete graph. A grid fine enough to plan smooth motion has enormous numbers of cells, and a robot arm’s configuration space has one dimension per joint. Sampling-based planners exist for that case, and they give up completeness in exchange for not enumerating the space at all.

Between the two sits the question this tool is really about: how much does your estimate know, and how much work does that knowledge save?