A* search

Deep dive

How it works

In: weighted graph (non-negative costs), start, goal, a heuristic h that never overestimates · Out: cheapest path and its cost, or none · State: none between calls; per call a cost and parent per generated node plus the open set · Cost: O(E log V) worst case, far fewer expansions with a tight h

1. g[start] = 0. Open = {(h(start), start)}.
2. Pop the node with minimum f. Skip it if stale (its g got better after the push). If it is the goal, reconstruct the path and return.
3. For each neighbour v: ng = g[u] + w(u,v). If ng < g[v], set g[v] = ng and parent[v] = u, and push (ng + h(v), v).
4. Tie-break equal f toward larger g (deeper nodes). On open grids, huge plateaus of equal f otherwise get expanded breadth-first.

S . . . . . . G        Dijkstra: a disc around S
. . # # # # . .        A*: an ellipse-like band from S toward G,
. . . . . . . .        bulging only where walls force detours

Code

8-connected grid, integer costs (10 straight, 14 diagonal), octile heuristic, no corner cutting:

use std::cmp::Reverse;
use std::collections::BinaryHeap;

pub struct Grid { pub w: usize, pub h: usize, pub blocked: Vec<bool> } // row-major

const STRAIGHT: u32 = 10;
const DIAG: u32 = 14; // ≈ 10·√2; integers avoid float ties and NaN

fn octile(a: (usize, usize), b: (usize, usize)) -> u32 { // exact on an empty grid → admissible
    let (dx, dy) = (a.0.abs_diff(b.0) as u32, a.1.abs_diff(b.1) as u32);
    STRAIGHT * dx.max(dy) + (DIAG - STRAIGHT) * dx.min(dy)
}

pub fn astar(g: &Grid, start: (usize, usize), goal: (usize, usize)) -> Option<(u32, Vec<(usize, usize)>)> {
    let idx = |(x, y): (usize, usize)| y * g.w + x;
    let mut cost = vec![u32::MAX; g.w * g.h];
    let mut parent = vec![usize::MAX; g.w * g.h];
    let mut open = BinaryHeap::new(); // min-heap on f, then max on g (prefer deeper nodes)
    cost[idx(start)] = 0;
    open.push(Reverse((octile(start, goal), Reverse(0u32), idx(start))));
    while let Some(Reverse((_, Reverse(gu), u))) = open.pop() {
        if gu > cost[u] { continue; } // stale entry
        let (ux, uy) = (u % g.w, u / g.w);
        if (ux, uy) == goal {
            let (mut path, mut v) = (vec![goal], u);
            while parent[v] != usize::MAX { v = parent[v]; path.push((v % g.w, v / g.w)); }
            path.reverse();
            return Some((gu, path));
        }
        for (dx, dy) in [(-1i64, -1i64), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)] {
            let (nx, ny) = (ux as i64 + dx, uy as i64 + dy);
            if nx < 0 || ny < 0 || nx >= g.w as i64 || ny >= g.h as i64 { continue; }
            let (nx, ny) = (nx as usize, ny as usize);
            if g.blocked[idx((nx, ny))] { continue; }
            let diag = dx != 0 && dy != 0;
            if diag && (g.blocked[idx((nx, uy))] || g.blocked[idx((ux, ny))]) { continue; } // no corner cutting
            let ng = gu + if diag { DIAG } else { STRAIGHT };
            let v = idx((nx, ny));
            if ng < cost[v] {
                cost[v] = ng;
                parent[v] = u;
                open.push(Reverse((ng + octile((nx, ny), goal), Reverse(ng), v)));
            }
        }
    }
    None // goal unreachable: the whole reachable region was explored
}

Complexity and constants

• Worst case equals Dijkstra: an uninformative h, or a goal behind a long wall (the classic "U-shaped trap"), expands the whole region.
• Per expansion: one heap pop (log of the open-set size) plus 8 neighbour checks on a grid. Order of 50-200 ns on small maps.
• Memory: cost 4 B + parent 8 B per cell here. Storing a 3-bit direction instead of parent brings a 1000 × 1000 grid to about 5 MB.

Efficiency

• Cost: measured with the code above on an Apple M4 Pro, one thread, 1000 × 1000 grid with 10 % random walls, corner to corner (both searches return cost 14826): octile heuristic 24.7 ms and 162,696 expansions (152 ns each); h = 0 (Dijkstra) 57.6 ms and 900,483 expansions (64 ns each). Memory 12 B per cell here. Bound: heap work and cache misses per expansion.
• Levers:
  • tight admissible heuristic — 5.5× fewer expansions, 2.3× less time (measured above; each expansion costs more) — any goal-directed query
  • Jump Point Search — often an order of magnitude over plain A* (Harabor, Grastien 2011; Key facts) — uniform-cost grids
  • navmesh or hierarchical abstraction (HPA*) — orders of magnitude fewer nodes than a grid (Implementation notes; Botea et al. 2004) — large static maps
  • weighted A* (w > 1) — fewer expansions for a path at most w× optimal — when near-optimal is enough
  • generation counter per cell — O(1) reset instead of clearing O(cells) — many searches on one map
• Naive → standard → state of the art:
  • Dijkstra, h = 0 · 57.6 ms, 900,483 expansions (grid above)
  • A* with octile heuristic (code above) · 24.7 ms, 162,696 expansions
  • JPS on uniform grids, navmesh or HPA* on large maps · order of 10× fewer expansions (JPS), orders of magnitude fewer nodes (navmesh)

Implementation notes

• No hash maps on grids: flat arrays indexed by cell, reset in O(1) per search with a generation counter stored next to each cell.
• Budgeted search: games cap expansions per frame (time slicing) and continue next frame, or return the best partial path (lowest h).
• Hierarchical: HPA* clusters the map, plans on an abstract graph of cluster entrances, then refines locally. Navmeshes (polygons) cut node counts by orders of magnitude versus grids, then smooth the path with the funnel algorithm.
• Reachability first: label connected regions with union-find or flood fill. Unreachable goals then fail in O(1) instead of exploring the whole map.
• Many agents, same goal: one reverse Dijkstra from the goal gives a flow field every agent follows.
• Dynamic obstacles: D* Lite repairs the previous search instead of replanning from scratch (robots, RTS).

Pitfalls

• Inadmissible heuristic: Manhattan distance on an 8-connected grid overestimates diagonals, so paths are suboptimal. A heuristic in different units than the costs (meters vs. seconds) has the same effect.
• Float costs with √2: ties and rounding produce zig-zag paths and extra expansions. Use scaled integers.
• Diagonal corner cutting through walls: check both orthogonal neighbours.
• Marking a node closed when it is pushed instead of when it is popped breaks optimality.
• Recomputing full paths for hundreds of units every frame. Cache paths, share flow fields, and stagger requests across frames.

Variants and alternatives

In production

Navigation: Recast & Detour navmesh pathfinding (its README names Unity, Unreal, Godot and O3DE as users), Unity NavMesh, ROS 2 Nav2 (SmacPlanner2D grid A*, SmacPlannerHybrid Hybrid-A*). Planning and puzzles: the Fast Downward planner offers A* among its search algorithms (Helmert 2006); IDA* solves the 15-puzzle (Korf 1985). Language: A* parsing returns the exact best parse (Klein, Manning 2003). Bioinformatics: APA aligns sequences globally with A and seed heuristics (Groot Koerkamp, Ivanov 2024). ROS global planners also use A* and Dijkstra.

Implementations

Sources

• P. Hart, N. Nilsson, B. Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics, 1968. paper
• R. Korf, Depth-First Iterative-Deepening: An Optimal Admissible Tree Search, Artificial Intelligence, 1985. paper
• D. Harabor, A. Grastien, Online Graph Pruning for Pathfinding on Grid Maps (JPS), AAAI, 2011. paper
• S. Koenig, M. Likhachev, D Lite*, AAAI, 2002. paper
• A. Botea, M. Müller, J. Schaeffer, Near Optimal Hierarchical Path-Finding, Journal of Game Development, 2004.
• M. Helmert, The Fast Downward Planning System, Journal of Artificial Intelligence Research 26, 2006. paper
• D. Klein, C. Manning, A* Parsing: Fast Exact Viterbi Parse Selection, NAACL-HLT 2003. paper