A* Pathfinding: Dijkstra With a Sense of Direction

Dijkstra explores everywhere. A* has a hunch.

Dijkstra's algorithm finds the shortest path from a start node by growing a frontier outward in order of distance: it always expands the unvisited node with the smallest cost-so-far. It is correct and it is complete, but it is blind — it expands nodes behind you, beside you and in front of you with equal enthusiasm, because it has no idea where the goal is. On an open grid it explores a disc.

A* (Hart, Nilsson and Raphael, 1968) changes exactly one thing. Every node is scored not by the cost to reach it, but by the estimated cost of a whole path through it:

f(n) = g(n) + h(n)

g(n) = the exact cost of the best path found so far from start to n
h(n) = a HEURISTIC estimate of the remaining cost from n to the goal

Expand the node with the smallest f, not the smallest g. That single substitution stretches the search toward the goal: on an open grid, Dijkstra's disc becomes a narrow ellipse pointing at the target. Set h = 0 and A* degenerates exactly into Dijkstra; make h large and it turns into a greedy best-first search that dives at the goal and finds bad paths quickly.

Admissible, consistent, and the difference that bites you

A* returns the optimal path if the heuristic is admissible: it never overestimates the true remaining cost. An admissible heuristic is optimistic — it may promise a shortcut that does not exist, but it never warns you off a road that is actually cheap. Overestimate anywhere on the optimal path and A* can settle for something worse.

A stronger property is consistency (the triangle inequality, sometimes called monotonicity):

h(n) ≤ cost(n, n') + h(n')     for every edge n → n'
h(goal) = 0

A consistent heuristic is automatically admissible, and it buys you something valuable: f never decreases along a path, so the first time A* pops a node from the queue it already has that node's optimal g. You can therefore close a node permanently and never reopen it. With a merely-admissible-but-inconsistent heuristic you must be prepared to reopen closed nodes when a cheaper route to them appears later, or you will silently return sub-optimal paths. Nearly every heuristic in this section is consistent, which is why most implementations quietly skip the reopening branch and still work.

Choosing the heuristic for your grid

The heuristic must match the movement rules exactly. This is the single most common source of subtly wrong paths and wildly slow searches:

4-way movement (N/E/S/W)
    h = D * (|dx| + |dy|)                       // Manhattan

8-way movement (diagonals cost D2 ≈ 1.414·D)
    h = D * (|dx| + |dy|) + (D2 - 2*D) * min(|dx|, |dy|)   // octile

any-angle movement
    h = D * sqrt(dx*dx + dy*dy)                 // Euclidean

Using Manhattan distance on an 8-way grid overestimates — a diagonal step covers one unit of dx and one of dy at a cost of 1.414, not 2 — so the heuristic is inadmissible and the path can come out wrong. Using Euclidean distance on a 4-way grid is admissible but weak: it always under-promises, so A* explores far more nodes than it needs to. The rule is: the heuristic should be the cost of the cheapest path ignoring all obstacles, under the movement rules you actually allow.

A related nuisance is ties. On an obstacle-free grid a huge number of paths have identical f, and A* wanders through all of them, exploring a fat diamond instead of a line. The standard cure is to break ties toward the straight line — nudge h upward by a factor of about (1 + 1/expected_path_length), or add a tiny cross-product term against the start–goal vector. The path stays optimal in practice and the explored region collapses dramatically.

The implementation, and where the time actually goes

open = priority queue (binary heap), keyed by f
g[start] = 0; push(start, h(start))

while (open not empty):
  current = pop_min(open)                 // O(log n)
  if current is goal: return reconstruct(cameFrom, current)
  closed.add(current)
  for each neighbour nb of current:
    if nb in closed: continue
    tentative = g[current] + cost(current, nb)
    if (tentative < g[nb]):               // a better route to nb
      cameFrom[nb] = current
      g[nb] = tentative
      push_or_decrease_key(open, nb, tentative + h(nb))

The open set must be a priority queue. A linear scan for the minimum turns every pop into O(n) and is the reason so many hand-written A* implementations crawl. A binary heap gives O(log n) pops and pushes and is enough for any grid you can draw. Two more practical points: store g and the parent in flat typed arrays indexed by y*w + x rather than in a hash map keyed by objects, and if your heap has no decrease-key operation, simply push the node again with the better f and discard stale entries when they pop (check whether the popped f matches the current g + h). It wastes a little memory and is faster than maintaining an index.

The variants worth knowing

Weighted A*    f = g + w·h, with w > 1. Inadmissible, but the
               path is guaranteed within a factor w of optimal and
               the search is dramatically faster. w ≈ 1.2–2 is common.

Jump Point     On uniform-cost grids, skips over whole corridors of
Search (JPS)   symmetric nodes without expanding them. Same optimal
               path, often an order of magnitude fewer expansions.

Theta*         Allows any-angle paths by letting a node's parent be
               any ancestor with line-of-sight, removing the ugly
               45° staircase that grid A* produces.

D* Lite        Repairs the previous search when the map changes
               instead of replanning from scratch — the standard
               choice for a robot discovering obstacles as it moves.

HPA*           Hierarchical: plan on a coarse graph of clusters,
               refine inside each cluster. Scales to huge maps.

One last note on the path A* returns on a grid: it is optimal on the graph you gave it, which is not the same as optimal in the plane. A grid path is a staircase, and a unit's motion looks robotic unless you post-process it — a line-of-sight string-pull (remove any waypoint whose neighbours can see each other) is cheap and fixes most of it. Theta* solves the same problem inside the search instead.

Frequently asked questions

Try it live

Everything above runs in your browser — open A* Pathfinding and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.