✦AI & Machine Learning

A* Pathfinder

Name: A* Pathfinder
Author: Ben Ebsworth

A*, Dijkstra, and greedy best-first search — the heuristic pulling the frontier toward the goal.

The Algorithm

Every variant here is best-first search on a weighted graph. Each cell n carries three numbers:

g(n) = cost of the cheapest path from start to n found so far
h(n) = heuristic estimate of the remaining cost from n to the goal
f(n) = the priority used to order the queue

The loop is always the same:

push start onto a min-priority-queue keyed by f
while queue not empty:
    n ← pop the cell with the smallest f      (now "closed")
    if n is the goal: reconstruct and stop
    for each free neighbour m of n:
        tentative = g(n) + cost(n, m)
        if tentative < g(m):
            parent(m) ← n
            g(m) ← tentative
            f(m)  ← (depends on the algorithm)
            push m

When the goal is popped, you walk the parent pointers backward from goal to start to recover the path. The implementation uses a binary min-heap with lazy deletion — when a cheaper route to a cell is found, a fresh entry is pushed and the stale one is simply skipped when it surfaces.

The three score functions

The visceral difference between the algorithms is entirely in f:

Dijkstra: f = g. The heuristic is ignored. The search expands cells in strict order of distance-from-start, so it explores a roughly circular wavefront. It is guaranteed optimal but does a lot of redundant work — it has no idea where the goal is.
A*: f = g + w·h. It balances "how far I've come" against "how far I think I have to go." With w = 1 and an admissible heuristic (one that never overestimates), A* is provably optimal and expands the fewest cells of any optimal algorithm.
Greedy best-first: f = h. Pure ambition — it always steps toward whichever frontier cell looks closest to the goal, ignoring accumulated cost. It is fast and direct, but not optimal: it happily walks into dead-ends and takes detours that a cost-aware search would avoid.

Heuristics

The heuristic must match the connectivity of the grid to stay admissible:

Manhattan  |Δx| + |Δy|              (4-connected: N, S, E, W)
Chebyshev  max(|Δx|, |Δy|)          (8-connected, uniform diagonal cost)
Euclidean  √(Δx² + Δy²)             (8-connected, straight-line distance)

For a 4-connected grid the Manhattan distance is the exact shortest distance with no walls, which makes it the tightest admissible heuristic — A* with Manhattan is essentially perfect on open grids. On an 8-connected grid (where diagonal moves cost √2), Chebyshev and Euclidean are the natural admissible choices.

What to Look For

Dijkstra vs A*: Set both to Manhattan and flip between them. Dijkstra settles a near-circular disc of cells; A* settles a slim cone aimed at the goal. Compare the expanded: counter in the caption — A* typically explores a small fraction of what Dijkstra does, yet returns the same optimal path length.
The cost gradient: The teal→purple colouring is g, the cost-so-far. In Dijkstra it forms clean concentric rings (iso-cost contours). In greedy search the gradient is jagged because the algorithm doesn't expand in cost order.
Weighted A*: Push weight to 3 or 4. The frontier narrows dramatically and the node count plummets — but on a cluttered maze you'll sometimes catch the path taking a visibly suboptimal kink. That's the speed-for-optimality trade laid bare.
Greedy's mistakes: Greedy best-first often produces a longer path than A* on the same maze. It charges at the goal and only backtracks when it hits a wall, leaving telltale dead-end stubs in the closed set.

Why It Matters

Best-first search is one of the most reused algorithms in computing. A* powers route planning in game AI and GPS navigation, motion planning for robot arms and drones, word-ladder and puzzle solvers, and even network routing. The single insight — order your exploration by a cost-plus-estimate score — generalises far beyond grids to any graph where you can define g and a sensible h. The art is almost entirely in choosing the heuristic: too weak and you waste effort like Dijkstra; inadmissible and you lose the optimality guarantee; just right and you get the optimal answer for the least possible work.

A* Pathfinder

A*, Dijkstra, and greedy best-first search — the heuristic pulling the frontier toward the goal.

The Algorithm

Every variant here is best-first search on a weighted graph. Each cell n carries three numbers:

g(n) = cost of the cheapest path from start to n found so far
h(n) = heuristic estimate of the remaining cost from n to the goal
f(n) = the priority used to order the queue

The loop is always the same:

push start onto a min-priority-queue keyed by f
while queue not empty:
    n ← pop the cell with the smallest f      (now "closed")
    if n is the goal: reconstruct and stop
    for each free neighbour m of n:
        tentative = g(n) + cost(n, m)
        if tentative < g(m):
            parent(m) ← n
            g(m) ← tentative
            f(m)  ← (depends on the algorithm)
            push m

The three score functions

The visceral difference between the algorithms is entirely in f:

Dijkstra: f = g. The heuristic is ignored. The search expands cells in strict order of distance-from-start, so it explores a roughly circular wavefront. It is guaranteed optimal but does a lot of redundant work — it has no idea where the goal is.
A*: f = g + w·h. It balances "how far I've come" against "how far I think I have to go." With w = 1 and an admissible heuristic (one that never overestimates), A* is provably optimal and expands the fewest cells of any optimal algorithm.
Greedy best-first: f = h. Pure ambition — it always steps toward whichever frontier cell looks closest to the goal, ignoring accumulated cost. It is fast and direct, but not optimal: it happily walks into dead-ends and takes detours that a cost-aware search would avoid.

Heuristics

The heuristic must match the connectivity of the grid to stay admissible:

Manhattan  |Δx| + |Δy|              (4-connected: N, S, E, W)
Chebyshev  max(|Δx|, |Δy|)          (8-connected, uniform diagonal cost)
Euclidean  √(Δx² + Δy²)             (8-connected, straight-line distance)

What to Look For

Dijkstra vs A*: Set both to Manhattan and flip between them. Dijkstra settles a near-circular disc of cells; A* settles a slim cone aimed at the goal. Compare the expanded: counter in the caption — A* typically explores a small fraction of what Dijkstra does, yet returns the same optimal path length.
The cost gradient: The teal→purple colouring is g, the cost-so-far. In Dijkstra it forms clean concentric rings (iso-cost contours). In greedy search the gradient is jagged because the algorithm doesn't expand in cost order.
Weighted A*: Push weight to 3 or 4. The frontier narrows dramatically and the node count plummets — but on a cluttered maze you'll sometimes catch the path taking a visibly suboptimal kink. That's the speed-for-optimality trade laid bare.
Greedy's mistakes: Greedy best-first often produces a longer path than A* on the same maze. It charges at the goal and only backtracks when it hits a wall, leaving telltale dead-end stubs in the closed set.

A* Pathfinder

The Algorithm

The three score functions

Heuristics

What to Look For

Why It Matters

Further reading

A* Pathfinder

The Algorithm

The three score functions

Heuristics

What to Look For

Why It Matters

Further reading