A* Pathfinding Simulator, expanding toward the goal.

Why a heuristic changes the search

Dijkstra fans out blindly; A* leans in.

Dijkstra explores cells in order of their distance from the start. Without any information about where the goal is, it has no reason to prefer one direction over another, so it expands like a circular wave. On a 14×22 grid, that wave reaches every cell roughly equidistant from the start before it ever reaches the goal — even if the goal is straight ahead.

A* uses a heuristic: a guess about how far the goal is from each cell. The search prioritises cells that have low f = g + h, where g is the known cost from the start and h is the estimated cost to the goal. Cells closer to the goal get expanded first. The wave becomes a directed beam.

This is the same correctness as Dijkstra (when the heuristic is admissible — never overestimates) with usually 5-100× fewer cells expanded. The penalty: if the heuristic is misleading or the goal is unreachable, A* can perform worse than Dijkstra because it commits to bad directions first.

Which heuristic to use

The one that's tightest while staying honest.

Where A* actually ships

Game pathfinding. Unity, Unreal, almost every 2D/3D game with NPCs uses A* on a navmesh. Pre-baked navigation meshes turn the world into a graph of triangles; A* runs over the triangle adjacency.

GPS and routing. Real navigation systems use heavily-modified A* variants — Contraction Hierarchies, Customizable Route Planning. The base algorithm is A*; the optimisations make it run on continental graphs in milliseconds.

Robotics. Mobile robots plan paths in occupancy grids. ROS's navigation stack uses A* with a grid heuristic; D* and D* Lite are A* variants for replanning when obstacles change.

Puzzle solving. 15-puzzle, Rubik's Cube, sliding-tile games. The heuristic becomes domain-specific (number of misplaced tiles, Manhattan-distance sum). A* with a good heuristic finds the optimal solution to a 15-puzzle in seconds.

Bidirectional A*. Run A* from both start and goal until the two frontiers meet. Roughly halves the search space.

The algorithm, line by line

Six structural parts. Each one matters.

A* is built from six pieces. Drop any one of them and the algorithm degrades to something else — Dijkstra, greedy best-first, or wrong.

function astar(start, goal):
    open      = MinHeap()                # 1. priority queue keyed by f
    open.push((0, start))
    came_from = {}                       # 2. parent map for path reconstruction
    g_score   = {start: 0}               # 3. cost from start
    f_score   = {start: h(start, goal)}  # 4. estimated total cost

    while open is not empty:
        current = open.pop()             # 5. pick smallest f
        if current == goal:
            return reconstruct(came_from, current)

        for neighbor in neighbors(current):
            tentative_g = g_score[current] + cost(current, neighbor)
            if tentative_g < g_score.get(neighbor, infinity):
                came_from[neighbor] = current
                g_score[neighbor]   = tentative_g
                f_score[neighbor]   = tentative_g + h(neighbor, goal)  # 6. relax
                open.push((f_score[neighbor], neighbor))

    return failure

1. Priority queue. A binary heap is the standard implementation. Insertion and extract-min are O(log n). Pairing heap or Fibonacci heap give better theoretical bounds for decrease-key but rarely beat a binary heap in practice because of constant factors. Pythonic implementations use heapq; JS implementations usually roll their own (the language has no built-in heap).

2. Parent map. Without it, you get the cost of the shortest path but not the path itself. Reconstruction walks from goal to start via parent pointers, then reverses the list.

3. g_score. The known shortest distance from start to a given node, computed so far. Starts as {start: 0}. Updated whenever a cheaper route to a node is discovered.

4. f_score. The estimated total path cost from start through this node to goal. f = g + h. The open set is sorted by f, so the cheapest possibly-optimal frontier node is always picked next.

5. Pop and goal check. If the popped node is the goal, the path is final — A* guarantees the first time you pop the goal, the path is optimal (assuming admissible heuristic). This early termination is what makes A* finish quickly on goal-directed problems.

6. Relaxation. For each neighbor, check whether the path through current is cheaper than any known path. If yes, update g, recompute f, set the parent, push to the open set. The same neighbor can be pushed multiple times with different f scores — the lazy approach is to keep them all and skip stale entries on pop (cheap with a heap, hard with a sorted array).

Reference implementations

The same algorithm in three languages.

Useful as a translation reference and as a starting point for adaptation. The Python version is the canonical readable form; Go and TypeScript versions show the same algorithm with different language idioms.

Python (production-quality)

import heapq
from typing import Callable, Hashable, Iterable, Optional

def astar(
    start: Hashable,
    goal: Hashable,
    neighbors: Callable[[Hashable], Iterable[tuple[Hashable, float]]],
    h: Callable[[Hashable, Hashable], float],
) -> Optional[list[Hashable]]:
    """
    Returns the shortest path from start to goal as a list of nodes, or None
    if unreachable. neighbors(n) yields (next_node, edge_cost) tuples.
    h(a, b) returns an admissible heuristic estimate of cost from a to b.
    """
    open_heap: list[tuple[float, int, Hashable]] = []
    counter = 0  # tiebreaker for equal f-scores; avoids comparing nodes
    heapq.heappush(open_heap, (h(start, goal), counter, start))

    came_from: dict[Hashable, Hashable] = {}
    g_score: dict[Hashable, float] = {start: 0.0}

    closed: set[Hashable] = set()

    while open_heap:
        _, _, current = heapq.heappop(open_heap)
        if current in closed:
            continue
        if current == goal:
            return _reconstruct(came_from, current)
        closed.add(current)

        for neighbor, edge_cost in neighbors(current):
            if neighbor in closed:
                continue
            tentative_g = g_score[current] + edge_cost
            if tentative_g < g_score.get(neighbor, float("inf")):
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f = tentative_g + h(neighbor, goal)
                counter += 1
                heapq.heappush(open_heap, (f, counter, neighbor))

    return None

def _reconstruct(came_from, current):
    path = [current]
    while current in came_from:
        current = came_from[current]
        path.append(current)
    return list(reversed(path))

Go (typed, idiomatic)

package astar

import "container/heap"

type Node interface{ comparable }

type item[N Node] struct {
    node     N
    priority float64
    index    int
}
type pq[N Node] []*item[N]

func (p pq[N]) Len() int            { return len(p) }
func (p pq[N]) Less(i, j int) bool  { return p[i].priority < p[j].priority }
func (p pq[N]) Swap(i, j int)       { p[i], p[j] = p[j], p[i]; p[i].index, p[j].index = i, j }
func (p *pq[N]) Push(x interface{}) { *p = append(*p, x.(*item[N])) }
func (p *pq[N]) Pop() interface{}   { old := *p; n := len(old); x := old[n-1]; *p = old[:n-1]; return x }

func AStar[N Node](
    start, goal N,
    neighbors func(N) []struct{ Node N; Cost float64 },
    h func(a, b N) float64,
) ([]N, bool) {
    open := &pq[N]{}
    heap.Init(open)
    heap.Push(open, &item[N]{node: start, priority: h(start, goal)})

    cameFrom := map[N]N{}
    gScore := map[N]float64{start: 0}
    closed := map[N]bool{}

    for open.Len() > 0 {
        cur := heap.Pop(open).(*item[N]).node
        if closed[cur] {
            continue
        }
        if cur == goal {
            return reconstruct(cameFrom, cur), true
        }
        closed[cur] = true

        for _, n := range neighbors(cur) {
            if closed[n.Node] {
                continue
            }
            tentative := gScore[cur] + n.Cost
            if g, ok := gScore[n.Node]; !ok || tentative < g {
                cameFrom[n.Node] = cur
                gScore[n.Node] = tentative
                heap.Push(open, &item[N]{node: n.Node, priority: tentative + h(n.Node, goal)})
            }
        }
    }
    return nil, false
}

func reconstruct[N Node](cameFrom map[N]N, current N) []N {
    path := []N{current}
    for {
        prev, ok := cameFrom[current]
        if !ok {
            break
        }
        current = prev
        path = append([]N{current}, path...)
    }
    return path
}

TypeScript (browser-friendly)

type Node = string;
type Heuristic = (a: Node, b: Node) => number;
type Neighbors = (n: Node) => { node: Node; cost: number }[];

class MinHeap<T> {
    private heap: { p: number; v: T }[] = [];
    push(p: number, v: T) {
        this.heap.push({ p, v });
        this.siftUp(this.heap.length - 1);
    }
    pop(): T | undefined {
        if (this.heap.length === 0) return undefined;
        const top = this.heap[0].v;
        const last = this.heap.pop()!;
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.siftDown(0);
        }
        return top;
    }
    get size() { return this.heap.length; }
    private siftUp(i: number) {
        while (i > 0) {
            const parent = (i - 1) >> 1;
            if (this.heap[parent].p <= this.heap[i].p) break;
            [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
            i = parent;
        }
    }
    private siftDown(i: number) {
        const n = this.heap.length;
        while (true) {
            let smallest = i;
            const l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && this.heap[l].p < this.heap[smallest].p) smallest = l;
            if (r < n && this.heap[r].p < this.heap[smallest].p) smallest = r;
            if (smallest === i) break;
            [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
            i = smallest;
        }
    }
}

export function astar(
    start: Node, goal: Node,
    neighbors: Neighbors, h: Heuristic
): Node[] | null {
    const open = new MinHeap<Node>();
    open.push(h(start, goal), start);

    const cameFrom = new Map<Node, Node>();
    const gScore = new Map<Node, number>([[start, 0]]);
    const closed = new Set<Node>();

    while (open.size > 0) {
        const current = open.pop()!;
        if (closed.has(current)) continue;
        if (current === goal) return reconstruct(cameFrom, current);
        closed.add(current);

        for (const { node, cost } of neighbors(current)) {
            if (closed.has(node)) continue;
            const tentative = gScore.get(current)! + cost;
            if (tentative < (gScore.get(node) ?? Infinity)) {
                cameFrom.set(node, current);
                gScore.set(node, tentative);
                open.push(tentative + h(node, goal), node);
            }
        }
    }
    return null;
}

function reconstruct(cameFrom: Map<Node, Node>, current: Node): Node[] {
    const path = [current];
    while (cameFrom.has(current)) {
        current = cameFrom.get(current)!;
        path.unshift(current);
    }
    return path;
}

The three versions are structurally identical. Differences come from language ergonomics — Python's heapq wants tuples for priority and uses a counter as a tiebreaker; Go's container/heap wants you to implement the interface; TypeScript wants you to write the heap yourself.

Cost analysis, in concrete numbers

The bounds and the practical numbers.

The worst-case complexity of A* is the same as Dijkstra: O((V + E) log V) with a binary heap, where V is the number of nodes and E the number of edges. The heuristic doesn't change the asymptotic worst case — only the average performance.

In the best case (perfect heuristic, single-step path) A* runs in O(d) where d is the depth of the goal. In the worst case (zero heuristic or adversarial layout) it expands every node like Dijkstra. Practical performance lives between those two extremes and depends almost entirely on how informative the heuristic is.

The gap between Manhattan and linear-conflict on the 15-puzzle is the prototypical "better heuristic dominates" result. Linear-conflict adds 2 to Manhattan's estimate whenever two tiles in the same row are out of order — a small tightening that prunes the search by orders of magnitude.

The memory cost is O(V) in the worst case — open set + closed set + parent map all scale with the number of distinct nodes visited. On grid pathfinding this is manageable; on huge graphs (continental road networks) the memory is the bottleneck and you reach for hierarchical approaches like Contraction Hierarchies that pre-compute shortcuts.

Variants worth knowing

When base A* isn't quite the right shape.

Bidirectional A*

Run A* from both start and goal at once, expanding the cheaper of the two frontiers each step, until they meet. The expanded area is roughly two cones meeting in the middle rather than one big cone — half the search space. The trick is detecting when to stop: the path found at the meeting point isn't necessarily optimal until you verify the open-set tops on both sides are heavier than the candidate path cost.

IDA* (Iterative Deepening A*)

A* with constant memory. Instead of an open set, do depth-first search bounded by a threshold on f. If the goal is found, return; otherwise increase the threshold to the smallest f that exceeded the bound and re-run. Memory is O(depth) instead of O(V) but the same nodes are visited repeatedly. Used in 15-puzzle and Rubik's Cube solvers where the graph is enormous but memory is constrained.

Jump-Point Search (JPS)

Specialised for grid pathfinding. JPS recognises that on uniform grids, most cells are uninteresting — you only need to consider "jump points" where a forced choice must be made. JPS prunes the search by orders of magnitude on open grids without changing optimality. Used in many real-time strategy games. Penalty: only works on uniform-cost grids, fails on graphs with varying edge costs.

D* and D* Lite

A* for replanning when the world changes. The robot is partway through a path and discovers a new obstacle; instead of replanning from scratch, D* Lite reuses the previous search's results and updates only the affected portion. Used in ROS's navigation stack and other robotics frameworks. The book-keeping is complex; the prize is real-time replanning at video frame rates.

Weighted A* and Anytime A*

Multiply h by a constant ε > 1 — A* expands fewer nodes but the path may be up to ε times longer than optimal. Anytime A* runs Weighted A* with progressively shrinking ε, returning a series of paths that approach optimality as time permits. Used when an approximate fast answer beats an optimal slow one — many game AIs use ε = 2 because the player can't tell the difference and the game feels snappier.

Contraction Hierarchies

Not a variant of A* exactly, but the technique that powers production routing engines (OpenStreetMap's OSRM, GraphHopper, modern Google Maps). Precompute "shortcuts" between important nodes; A* (or bidirectional Dijkstra) then runs over a much smaller graph. Continental routing in milliseconds — what makes Google Maps feel instant.

How to design a heuristic

Tight, consistent, fast — pick any two.

The art of A* is the heuristic. Three properties define a good one:

Admissibility. h(n) ≤ true cost from n to goal. Required for A* to find the optimal path. Manhattan distance is admissible on a 4-directional grid; straight-line distance is admissible in Euclidean space; the minimum spanning tree of remaining cities is admissible for TSP.

Consistency (monotonicity). h(n) ≤ cost(n, m) + h(m) for any neighbor m. Stronger than admissibility. Consistent heuristics guarantee that a node never needs to be re-expanded — once closed, always closed. All consistent heuristics are admissible; not all admissible heuristics are consistent. Most natural heuristics (Manhattan, Euclidean) are consistent.

Informativeness. The tighter h is to the true cost without exceeding it, the fewer nodes A* expands. A heuristic that always returns 0 is admissible but useless — A* becomes Dijkstra. A heuristic that perfectly equals the true cost expands only the optimal path.

Designing a heuristic for a new problem is mostly relaxation: take the actual problem, drop some constraints, solve the easier version. The cost of the relaxed solution is admissible. Manhattan distance is what you get when you relax "wall" constraints from grid pathfinding — count the moves needed if walls didn't exist. Linear-conflict on the 15-puzzle is what you get when you relax further but capture in-row conflicts. The pattern is general.

Where A* actually ships in real systems

Game pathfinding

Almost every 2D and 3D game with NPCs uses A* on a navmesh (Unity NavMesh, Unreal Navigation System, Recast Navigation library). The world is decomposed into a graph of triangles; A* runs over the triangle adjacency with Euclidean distance as the heuristic. Game-specific extensions handle dynamic obstacles, group movement, and multi-agent crowding.

RTS games (StarCraft, Age of Empires) use simpler grid A* with Jump-Point Search for speed. The challenge isn't A* itself but coordinating thousands of units without each one pathfinding from scratch — flow fields and shared paths are the production optimisations.

GPS and routing

Google Maps, Apple Maps, OSRM, Waze, GraphHopper — all use heavily-modified A* variants. The base algorithm is A*; the optimisations are what make continental routing run in milliseconds: Contraction Hierarchies, Customizable Route Planning, Hub Labels, Multi-Level Dijkstra. The 2010 Geisberger et al. CH paper is the canonical reference.

Real-time route updates (recompute when traffic changes) use D* Lite or similar incremental algorithms — too expensive to replan from scratch every few seconds.

Robotics

The ROS navigation stack uses A* (or its variants — RRT*, Hybrid A*) for global planning, followed by a local planner (DWA, TEB) for short-horizon control. Self-driving cars use Hybrid A* (kinematically constrained A* over a state space that includes orientation, not just position) for low-speed maneuvering like parking.

Puzzle and game-solving

The 15-puzzle, 24-puzzle, Rubik's Cube, sliding-tile games all yield to A* with the right heuristic. Korf's 1985 paper "Depth-first iterative deepening" (IDA*) became the standard approach. Cube solvers run IDA* with pattern databases as the heuristic.

Network protocols and infrastructure

Some routing protocols (link-state algorithms in OSPF and IS-IS) use Dijkstra rather than A* because there's no single goal — they compute shortest paths to all destinations. But layer-3 networks at very large scale sometimes use A*-like heuristics to route packets across regions before the precise per-router Dijkstra kicks in.

Bugs every A* implementer writes once

Read this list before you debug yours.

Inadmissible heuristic. The classic mistake is using Euclidean distance on a 4-directional grid where the actual minimum cost is Manhattan. Euclidean h is always ≤ Manhattan true cost, so it's admissible — but on a graph where edges cost 1 and only N/S/E/W moves are allowed, the true cost is Manhattan distance, not Euclidean. Euclidean underestimates more than necessary, slowing A* down. Using Manhattan is admissible and tighter.

The opposite mistake — using Chebyshev distance on a 4-directional grid — is non-admissible. Chebyshev counts max(dx, dy), assuming diagonals cost 1 (king moves). On a 4-directional grid, you can't move diagonally, so Chebyshev underestimates the true distance, breaking the optimality guarantee.

Re-expanding closed nodes. With a consistent heuristic, A* never needs to re-expand a closed node. With an inconsistent (but admissible) heuristic, it might. Implementations that ignore this and use a "closed set never reopens" rule with an inconsistent heuristic produce sub-optimal paths. Either ensure your heuristic is consistent or be willing to reopen.

Tiebreaking on equal f. When two nodes have the same f, which one to expand first matters. Tiebreaking by larger g (deeper exploration first) tends to make A* feel faster because it pushes toward the goal. The Python heapq module doesn't tiebreak — you have to add a counter or g-score in the priority tuple to control it. Many tutorials omit this and end up with non-deterministic tie behavior.

Off-by-one in the reconstruct. Walking parent pointers from goal to start, you collect [goal, parent(goal), parent(parent(goal)), ..., start]. The reverse gives you start → goal. Forgetting to include the start in the walk (because cameFrom doesn't contain start) is a one-off-shorter path. Forgetting to reverse gives you a goal-to-start path.

Heap with mutable priorities. Standard binary heaps don't support decrease-key in O(log n). The common (wrong) fix is to remove and re-insert; the right fix is lazy deletion: insert a new entry with the new priority and skip stale entries on pop. Tutorials often hand-wave this; libraries that get it wrong cause subtle performance bugs.

Infinite loops on disconnected components. If goal is unreachable, A* exhausts the open set and should return failure. Implementations that don't check open-set emptiness loop forever. The classic test case: start in one room, goal in another, walls fully separating them.

Forgetting the goal check on neighbors. Some implementations check "current == goal" but never get there because they always pop a different node first. The check must be on pop, not on neighbor expansion.

Negative edge costs. A* assumes non-negative edges. With negative edges, the heuristic can't be admissible (or the algorithm loops). For negative edges, use Bellman-Ford or, if no negative cycles, Johnson's algorithm.

A* in an interview

Three questions you should be ready for if A* comes up:

"How is A* different from Dijkstra?" A* uses a heuristic to focus the search toward the goal; Dijkstra explores uniformly outward. Both find optimal paths; A* typically expands far fewer nodes. Set the heuristic to 0 and A* degenerates to Dijkstra. Setting it to something inadmissible turns A* into a greedy best-first search that might find sub-optimal paths.

"What makes a heuristic admissible? What if it's not?" Admissible means h(n) never overestimates the true cost. If your heuristic overestimates, A* may return a sub-optimal path because it can pass over the true optimal path's expansion in favor of one that looks cheaper but isn't. Admissibility is the cost you pay for optimality.

"Walk me through finding the path from A to B on this graph." The interviewer will draw a small graph (5-8 nodes), give you edge weights and h values for each node, and ask you to trace A*. The expected answer is a table: round-by-round open set contents, current node, g/h/f values for each. The trap is failing to update a node's g when a cheaper path is found mid-search.

Common deeper questions:

"What's the complexity?" — O((V + E) log V) with a binary heap.

"What if I have multiple goals?" — Run A* with a heuristic = minimum estimate to any goal, or run multiple A*s in parallel.

"How do you handle dynamic obstacles?" — D* Lite or Anytime A*; cheaper than replanning from scratch.

"Can A* handle infinite or very large graphs?" — Yes, as long as the heuristic guides the search away from infinity. IDA* gives you constant memory.

Where A* came from

A* was published in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at SRI International, in the paper "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". The motivating application was Shakey the Robot, the first general-purpose mobile robot capable of reasoning about its own actions. Shakey needed to plan paths through a 7-room laboratory; Dijkstra worked but was slower than necessary because it explored uniformly.

The key idea — combine known cost (g) with estimated remaining cost (h) — was already known in operations research and AI under various names. Hart-Nilsson-Raphael's contribution was the precise formalisation: when the heuristic is admissible, the algorithm is both complete (finds a path if one exists) and optimal (the path is shortest). The proof is short and worth reading once.

The name is a small joke: in the original paper, the optimal algorithm in this family was called A* (A-star), because earlier candidate algorithms had been named A1, A2 etc., and A* was the "best" of the family. Nilsson chose the asterisk to denote optimality, the same way mathematical analysis uses x* for an optimal solution.

A* is now over 55 years old and remains the dominant pathfinding algorithm in production. Newer variants (D*, IDA*, JPS, contraction hierarchies, machine-learned heuristics) refine specific aspects but the core algorithm — priority queue + heuristic-informed expansion — is unchanged. It is one of the longest-lived algorithms in the field.

A* on a tiny graph, by hand

Six nodes. Trace every expansion.

The smallest example that exercises every part of the algorithm:

Nodes:    S, A, B, C, D, G
Edges:    S-A: 1,  S-B: 4
          A-C: 2,  A-D: 5
          B-D: 1
          C-G: 3
          D-G: 2

Heuristic h to goal G (admissible, e.g. straight-line):
  h(S)=7,  h(A)=6,  h(B)=2,  h(C)=3,  h(D)=2,  h(G)=0

Step-by-step trace:

Initialise: open = [(7, S)],  g(S)=0,  others=∞

Iter 1:  Pop (7, S).  Expand neighbors:
   A: g=0+1=1,  f=1+6=7,  parent=S    → push (7, A)
   B: g=0+4=4,  f=4+2=6,  parent=S    → push (6, B)
   Open: [(6, B), (7, A)]

Iter 2:  Pop (6, B).  Expand neighbors:
   D: g=4+1=5,  f=5+2=7,  parent=B    → push (7, D)
   Open: [(7, A), (7, D)]

Iter 3:  Pop (7, A).  Expand neighbors:
   C: g=1+2=3,  f=3+3=6,  parent=A    → push (6, C)
   D: g=1+5=6 > existing 5;  skip
   Open: [(6, C), (7, D)]

Iter 4:  Pop (6, C).  Expand neighbors:
   G: g=3+3=6,  f=6+0=6,  parent=C    → push (6, G)
   Open: [(6, G), (7, D)]

Iter 5:  Pop (6, G).  Goal reached!
   Reconstruct: G ← C ← A ← S
   Path: S → A → C → G, cost = 6

Note that node D was reached twice with different g-scores; A* kept the lower one (g=5 via B, not g=6 via A) but in this example D was never expanded because G was popped first. The path through D would have been S → B → D → G with cost 4+1+2 = 7, longer than the chosen path.

The heuristic guided the search to expand B before A (because f(B)=6 < f(A)=7), but then the actual optimal path went through A. That's normal — A* is willing to explore a few sub-optimal-looking branches as long as f values warrant it; the optimal path is guaranteed because A* doesn't terminate until it pops the goal.

Further reading

The original 1968 paper, Hart-Nilsson-Raphael's "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" in IEEE Transactions on Systems Science and Cybernetics, is short and worth reading once. The proof of optimality is two pages.

Amit Patel's "Introduction to A*" (theory.stanford.edu/~amitp/GameProgramming/) is the canonical web tutorial — Red Blob Games quality, with interactive demos. The companion pages on heuristics, grid pathfinding, and navigation meshes are the best practitioner's reference on the web.

Russell and Norvig's Artificial Intelligence: A Modern Approach covers A* in Chapter 3, with formal correctness proofs and the connection to other informed search algorithms. The textbook treatment if you want the academic angle.

For game pathfinding specifically, Steve Rabin's Game AI Pro series has chapters on JPS, hierarchical pathfinding, and crowd navigation that go beyond textbook A*. The Recast Navigation library (recastnav.com) is the open-source reference implementation used by Unity and Unreal.

For continental-scale routing, the Geisberger-Sanders-Schultes-Vetter "Contraction Hierarchies" paper (Algorithmics 2008) is the seminal work. OSRM's documentation (project-osrm.org/docs/) covers the production engineering.

For robotics, Sebastian Thrun's Probabilistic Robotics covers Hybrid A* and the connection to motion planning. The ROS navigation stack documentation has practical patterns for replanning, dynamic obstacles, and multi-agent coordination.

A* in the family of search algorithms

One framework, many points on the spectrum.

The informed-search family is parametrised by what each node's priority is:

The lesson: A* is a single point on a wider spectrum of trade-offs between informedness, memory, optimality, and admissibility. Picking the right algorithm for a problem means knowing where on the spectrum the constraints actually sit.

Most practical pathfinding lives in the A* / Weighted A* / Hierarchical A* region. Pure Dijkstra is rare in production because almost every interesting problem has a usable heuristic. Pure greedy is even rarer because the cost of sub-optimal paths usually exceeds the cost of guidance.

Five gotchas that show up at scale

1. The graph doesn't fit in memory. A 14×22 grid is 308 nodes. A continental road network is 30M nodes; even the parent map and g-score table together exceed 4 GB at 64-bit pointers. Production routing engines never materialise the full graph in A*'s memory — they stream nodes from disk-based stores (LMDB, RocksDB) or use Contraction Hierarchies that pre-compute over a smaller core graph.

2. Heuristic computation dominates. If your heuristic is expensive (e.g., querying an external service or computing a learned model per call), A* spends more time computing h than walking the graph. The fix is cache aggressively — memoize h per node, or use a lookup table for grid-like problems where h is a pure function of coordinates.

3. Floating-point comparison. When f-scores are floats and two paths happen to produce f values within machine epsilon, the tiebreaker behavior becomes undefined. Symptoms: same input produces different paths on different runs. Fix: scale costs to integers when possible, or use explicit epsilon comparison plus a deterministic tiebreaker (lexicographic on node id).

4. Heuristic mismatched to cost units. Cost units are meters; heuristic returns kilometers. Divide by 1000 somewhere wrong and the heuristic becomes inadmissibly large. Result: A* finds sub-optimal paths quickly. Always unit-test the heuristic against the actual edge-cost function: for a known optimal path, sum the edge costs and confirm h(start) ≤ true cost.

5. Dynamic obstacles invalidate the search mid-walk. Robot starts walking the computed path; new obstacle appears; the path is now invalid. A* gives you a snapshot; what you need is replanning. D* Lite is the textbook answer; in practice many systems just rerun A* periodically from the robot's current position, since the cost of frequent re-runs is bounded.

Practice the pattern

Five exercises to make it stick.

1. Implement A* with Manhattan heuristic. Take the algorithm in Part 04, code it from scratch in your favorite language, test against the simulator. Confirm same number of expansions for the same start/end on the same grid.

2. Implement Greedy Best-First Search. Same code, but pop by h(n) instead of f(n). Run on a grid with walls. Confirm the path is found faster but not always optimal — particularly when walls force a detour.

3. Implement Bidirectional Dijkstra. Two searches, one from start, one from goal. Stop when frontiers meet. Confirm node count roughly halves on a uniform graph.

4. Build a tie-breaker that prefers paths closer to the straight line. Add a small bonus to f for nodes closer to the start-goal line; the path becomes visibly less zigzaggy. Confirm optimality is preserved (the bonus must be small enough to not break the admissibility bound).

5. Solve a 15-puzzle with A*. Encode the puzzle state, define Manhattan distance heuristic (sum of |row_diff| + |col_diff| for each tile from its goal position), run A*. Time the search vs IDA* for a depth-30 puzzle. Notice how memory dominates A* but not IDA*.

By the time you finish these five, A* and its variants are part of your toolkit forever.

Bonus: heuristic design exercises

6. Sliding-tile pattern database. For the 8-puzzle (smaller cousin of 15-puzzle), precompute the optimal cost to solve just three specific tiles. Use this as h. Confirm A* expands fewer nodes than with Manhattan alone.

7. Maze with weighted terrain. Modify the grid so different cell types have different costs (road = 1, grass = 2, swamp = 5). Confirm A* with Manhattan h still finds optimal paths, but h is now further from the true cost so it expands more nodes than on uniform-cost grids.

8. Multi-goal A*. Goal is any of three target cells. Heuristic = min over the three Manhattan distances. Confirm A* finds the path to the nearest goal, not necessarily the first one listed.

9. Constrained A*. Path must avoid certain cells entirely (forbidden zones). Encoding via edge cost = infinity is sufficient; A* naturally routes around. Compare expansion count with and without the constraint.

10. Anytime A*. Run weighted A* with ε = 3, return path; rerun with ε = 2, return better path; rerun with ε = 1 (regular A*), return optimal. Plot path-quality-vs-time. The curve is the anytime property in action.

Terminology cheat sheet

g(n) — known cost from start to node n.

h(n) — heuristic estimate of cost from n to goal.

f(n) = g(n) + h(n) — estimated total path cost through n.

Open set — nodes discovered but not yet expanded; priority queue keyed by f.

Closed set — nodes already expanded; should not be reopened with a consistent heuristic.

Admissible — h never overestimates true cost. Required for optimality.

Consistent (monotonic) — h(n) ≤ cost(n,m) + h(m). Stronger than admissibility; guarantees no re-expansion.

Relaxation — updating a node's g and parent when a cheaper path is found.

Expansion — popping a node from the open set and generating its neighbors.

Frontier — informal name for the open set; the "wavefront" of unexpanded discovery.

Reconstruction — walking the parent map from goal back to start to produce the path.

Tiebreaker — rule for choosing among nodes with equal f. Often: prefer larger g (deeper).

IDA* — iterative-deepening A*; constant memory at the cost of repeated work.

JPS — Jump-Point Search; grid-specific pruning that skips uninteresting cells.

Contraction Hierarchies — preprocessing that adds shortcut edges so A* runs on a smaller graph at query time.

Pattern database — precomputed admissible heuristic for a subset of the problem's state.

Hybrid A* — A* over a state space including continuous variables like orientation; used for self-driving car parking.

D* / D* Lite — incremental A* variants for replanning when the environment changes.

Weighted A* — A* with f = g + ε·h, ε > 1. Faster but up to ε-suboptimal.

Anytime A* — runs Weighted A* with shrinking ε; returns progressively better paths over time.

Navmesh — navigation mesh; the world decomposed into triangles for game pathfinding.

RRT* — Rapidly-exploring Random Tree; samples random states instead of expanding nodes; used in robotics where the state space is continuous.

Manhattan distance — |x1-x2| + |y1-y2|; admissible on 4-directional grids.

Euclidean distance — √((x1-x2)² + (y1-y2)²); admissible in continuous Euclidean space.

Chebyshev distance — max(|x1-x2|, |y1-y2|); admissible on 8-directional grids (king moves).