A* Pathfinding, in depth: admissible and consistent heuristics, grid heuristics, tie-breaking, weighted A* and when to move beyond it

From Dijkstra to A* in one line

Every node n on the frontier has g(n), the cheapest cost found so far from the start to n. Dijkstra pops the node with the smallest g. A* pops the node with the smallest f(n) = g(n) + h(n), where h(n) estimates the cheapest cost from n to the goal. That is the only change. With h = 0 everywhere, A* is Dijkstra.

The intuition: f(n) estimates the length of the best complete path that passes through n. Popping the smallest f means always extending the path that currently looks shortest overall. Nodes behind the start, which have small g but large h, get large f and wait. If the goal is reached before they come up, they are never expanded at all, and that is where the speed comes from.

A* needs a way to estimate the remaining cost, which means it needs a goal known in advance and some geometry or structure that relates nodes to it. If you need distances to every node, or the goal is "any node satisfying a predicate" with no usable estimate, you want Dijkstra or BFS instead.

A correct implementation

The version below runs on an 8-connected grid where diagonal steps cost the square root of two and may not cut the corner of a wall. It uses Python's heapq, which has no decrease-key operation, so when a node's g improves we push a new entry and leave the old one in the heap. When a stale entry is popped later, the closed-set check discards it. This lazy deletion is simpler and usually faster than an indexed heap; the cost is a heap that can hold several entries per node. The indexed binary heap article shows the alternative when memory matters.

import heapq, math, random

def neighbors8(grid, node):
    """8-connected moves on a 0/1 grid (1 = wall), with no cutting of wall corners."""
    r, c = node
    rows, cols = len(grid), len(grid[0])
    for dr in (-1, 0, 1):
        for dc in (-1, 0, 1):
            if dr == dc == 0:
                continue
            nr, nc = r + dr, c + dc
            if not (0 <= nr < rows and 0 <= nc < cols) or grid[nr][nc]:
                continue
            if dr and dc and (grid[r][nc] or grid[nr][c]):
                continue
            yield (nr, nc), (math.sqrt(2) if dr and dc else 1.0)

def octile(a, b):
    dx, dy = abs(a[0] - b[0]), abs(a[1] - b[1])
    return (dx + dy) + (math.sqrt(2) - 2) * min(dx, dy)

def astar(grid, start, goal, h, w=1.0):
    g = {start: 0.0}
    parent = {start: None}
    open_heap = [(w * h(start, goal), 0.0, start)]   # (f, -g, node): ties prefer deeper nodes
    closed = set()
    expanded = 0
    while open_heap:
        f, neg_g, node = heapq.heappop(open_heap)
        if node in closed:
            continue                      # stale duplicate entry (lazy deletion)
        closed.add(node)
        expanded += 1
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1], g[goal], expanded
        for nxt, cost in neighbors8(grid, node):
            ng = g[node] + cost
            if ng < g.get(nxt, math.inf):
                g[nxt] = ng
                parent[nxt] = node
                heapq.heappush(open_heap, (ng + w * h(nxt, goal), -ng, nxt))
    return None, math.inf, expanded

Three details carry the correctness. First, the goal test happens when the goal is popped, not when it is first pushed: the first push may come via a worse path, and only the pop guarantees no cheaper path remains. Second, g is updated only on strict improvement, so equal-cost alternatives do not churn the heap. Third, the closed-set skip is valid only if the heuristic is consistent, which the next section explains.

Admissible and consistent: what each guarantees

A heuristic is admissible if it never overestimates: h(n) <= h*(n) for every node, where h* is the true remaining cost. Admissibility is what makes A* optimal. Sketch of the argument: suppose the goal is popped with a suboptimal cost C > C*. Some node m on an optimal path must still be on the frontier with its optimal g, so f(m) = g*(m) + h(m) <= g*(m) + h*(m) = C*. The heap would have popped m before the goal, which has f = C. Contradiction.

A heuristic is consistent (or monotone) if for every edge from n to n' with cost c, h(n) <= c + h(n'), and h(goal) = 0. This is the triangle inequality applied to the estimate. Consistency implies admissibility, and it buys one extra guarantee: f never decreases along any path, so the first time a node is popped its g is already optimal. That is exactly the property the closed-set skip relies on.

With an admissible but inconsistent heuristic, a node can be popped and closed, then reached again later through a cheaper path. The algorithm above would ignore that cheaper path and could return a suboptimal answer. The fix is to reopen: when a closed node's g improves, remove it from the closed set and push it again. That restores optimality, but a node may then be expanded many times. In practice, almost every heuristic built from a geometric distance is consistent, and if you combine consistent heuristics with max the result stays consistent. Inconsistency usually comes from hand-tuned or learned heuristics, and those deserve a test.

Choosing a heuristic

The best heuristic is the largest one that stays admissible, because a larger h pushes more nodes past the goal's f and so they are never expanded. For grids and maps, the right choice follows from the movement rules, not from taste:

Two traps recur. Manhattan distance on an 8-connected grid overestimates every diagonal move (it charges 2 for a step that costs about 1.41), so it is inadmissible and returns longer paths; the worked example measures this. And a heuristic in the wrong units is silently wrong: if edges carry travel time in seconds and h returns metres, the search is effectively weighted by an arbitrary factor. Convert h into the edge cost unit with the most optimistic conversion factor.

Worked example: measuring the heuristic

Here is a 200 by 200 grid with a quarter of the cells randomly blocked, plus a long vertical wall the path has to go around. The same astar function runs five times with different heuristics and weights, and reports the path cost and the number of node expansions.

random.seed(7)
N = 200
grid = [[1 if random.random() < 0.25 else 0 for _ in range(N)] for _ in range(N)]
for r in range(20, 180):
    grid[r][100] = 1                      # a long wall with gaps at both ends
start, goal = (10, 10), (190, 190)
grid[10][10] = grid[190][190] = 0
manhattan = lambda a, b: abs(a[0] - b[0]) + abs(a[1] - b[1])
for name, h, w in [("dijkstra", lambda a, b: 0.0, 1.0), ("manhattan", manhattan, 1.0),
                   ("octile", octile, 1.0), ("octile w=1.5", octile, 1.5), ("octile w=3", octile, 3.0)]:
    path, cost, expanded = astar(grid, start, goal, h, w)
    print(f"{name:14s} cost={cost:.2f} expanded={expanded} pathlen={len(path)}")

Running it prints:

dijkstra       cost=332.11 expanded=29537 pathlen=295
manhattan      cost=355.34 expanded=8373 pathlen=316
octile         cost=332.11 expanded=17526 pathlen=295
octile w=1.5   cost=362.07 expanded=5769 pathlen=326
octile w=3     cost=402.01 expanded=1395 pathlen=358

Read it row by row. Dijkstra and octile A* find the same optimal cost, 332.11, but octile A* expands 17,526 nodes against 29,537, about 41 percent fewer. Manhattan expands only 8,373 nodes but returns a path costing 355.34, seven percent too long, because it overestimates diagonals. This is the classic signature of an inadmissible heuristic: fewer expansions, worse answers, no error message.

The two weighted runs are deliberate trades. With w = 1.5 the search expands 5,769 nodes and the cost is 362.07, 9 percent above optimal. With w = 3 it expands 1,395 nodes, 21 times fewer than Dijkstra, at 21 percent above optimal. Both stay well inside the theoretical bound described next.

Tie-breaking and other details that change performance

On grids, many nodes share the same f. With octile distance on an open map, every node on the optimal diagonal band has the same f, and the order among them decides whether A* walks straight to the goal or floods the band. Breaking ties toward larger g (smaller h) prefers nodes closer to the goal, which is why the heap entry is (f, -g, node). It does not affect optimality, only the number of expansions.

• Floating point: diagonal costs of the square root of two accumulate rounding error, so two equal paths can compare unequal. If you test for optimality, compare costs with a tolerance, or scale costs to integers (10 and 14 is a common approximation, but it changes the metric slightly).
• Node identity: the key for g, parent and closed must include every piece of state that affects future moves. If movement depends on heading or remaining fuel, the node is (cell, heading) and the heuristic must be a lower bound for every heading.

Weighted A* and the cost bound

Weighted A* uses f = g + w * h with w > 1. If h is admissible, the returned cost is at most w times the optimal cost. The worked example agrees: 362.07 is 1.09 times optimal for w = 1.5, and 402.01 is 1.21 times optimal for w = 3. The bound is a worst case; real overshoot is usually far below it. With a consistent heuristic the bound holds even without reopening closed nodes, which keeps the simple implementation above usable.

When A* is not enough

A* stores every generated node, so memory, not time, is usually the first limit. The standard escapes trade time, optimality or preprocessing for memory and speed:

Failure modes

• Inadmissible heuristic: Manhattan on 8-connected grids, or the wrong units, returns longer paths with no error. Test against Dijkstra.
• Closed set with an inconsistent heuristic: nodes are finalised too early and better paths are discarded.
• Goal test on push: returns the first path that reaches the goal rather than the cheapest one.
• Missing state in the node key: two different situations share one g entry and the search prunes valid paths.
• Memory blow-up: lazy deletion on a huge map with a weak heuristic fills the heap with duplicates.
• Negative edge costs: A* inherits Dijkstra's assumption of non-negative costs; with negative edges its guarantees do not hold.

What to do next

1. Write down your movement model and costs, then derive the heuristic from it: Manhattan, octile, Chebyshev or Euclidean.
2. Check consistency on a sample: for random edges, assert h(n) <= cost + h(n').
3. Add a randomized test that compares A* path costs to Dijkstra on small grids, with a floating-point tolerance.
4. Count expansions per query in production and track the distribution, not only the latency.
5. Add tie-breaking toward larger g and measure expansions before and after.
6. If latency is still too high, decide which guarantee you will give up: optimality (weighted A*, HPA*), generality (JPS) or preprocessing time (ALT, contraction hierarchies).
7. For deeper background on the frontier and heap, read Dijkstra's algorithm and 0-1 BFS for graphs with only two edge weights.