A* Search

Two distances, one priority

g is the length of the best route found so far from S to a cell. h is the Manhattan estimate to G: |column − goalColumn| + |row − goalRow|, ignoring walls. f = g + h estimates the total route through that cell. The estimate is not a completed route.

Start with g(S)=0 and infinity elsewhere. The purple frontier contains discovered, unselected cells. Select the smallest f from the entire frontier; ties keep first discovery order. Neighbors are inspected north, east, south, west. Selection can switch branches: it does not represent a character walking between the selected cells.

A better route changes the parent

For an open neighbor, try candidate = g(current) + 1. If candidate is smaller than its stored g, replace g and its parent. Add a previously unseen cell to the frontier; an existing frontier cell stays in place with its updated priority. Equal-length alternatives keep the old parent. This update is called relaxation.

Simply replacing h with g+h in a first-discovery-only Greedy implementation is insufficient. A cell may be discovered along a longer route before a shorter one is found. This demo uses a consistent heuristic, so a cell selected for expansion already has its shortest distance and does not need reopening.

Eight steps instead of ten

This is the same 7×4 maze as the Greedy episode. Coordinates (column, row) start at 1. S=(1,3), G=(7,3). The east neighbor has g=1, h=5, f=6; the south neighbor has g=1, h=7, f=8. A* starts east too, eventually encountering the dead end near G.

The upper detour raises the estimate to 10. The lower branch still offers cells with f=8, so A* selects them first. The final route follows row 4 and takes 8 transitions; Greedy's upper route takes 10. The green route is reconstructed from parents, rather than the order of expansion. This example illustrates priority selection; it does not contain every kind of relaxation event.

Why this route is shortest

Here every passage costs one, moves are orthogonal and the maze is finite. Manhattan h is zero at G, never exceeds the remaining route length and is consistent: h(u) ≤ 1 + h(v) for every passage u→v. Removing walls gives the estimate; restoring them cannot shorten the route.

Under these conditions a closed cell needs no reopening. Finish when G is selected with minimum f, not when it is first discovered. A* then returns a shortest route, or reports failure if the frontier empties. With an inconsistent heuristic, a version that never reopens closed cells can lose this guarantee. Diagonal movement, weighted edges and other heuristics require different assumptions and code.

Reading the player

Cell numbers display f; infinity means the cell has not been discovered. S and G keep their labels. The text lists g+h=f for the current cell and each frontier cell. Purple means frontier, the outline marks the current cell, green marks the reconstructed route.

Discovered includes S and every first insertion; selected counts removals, including G. Neighbor checks count open adjacency entries, even already known neighbors; walls and G's neighbors are excluded. Improved routes count decreases of a previously finite g. During reconstruction the path grows backwards; the final snapshot reverses it. Try stepping, seeking and the zero-length start-equals-goal example.

The cost of this version

For V cells and E passages this array-based implementation takes O(V² + E) time and O(V) extra working memory, excluding the graph. Each cell is selected at most once; finding and removing the minimum takes O(V), while relaxation is constant-time per neighbor. A binary heap with decrease-key can give O((V+E) log V) search time; this demo intentionally scans an array.

Replay saves a full O(V) snapshot at each visible event. There are O(V+E) events; for this four-neighbor grid E=O(V), giving O(V²) history memory in addition to the shared maze. Search complexity and saved visualization history are different costs.

JavaScript implementation

The code expects a finite Map of IDs to ordered neighbor arrays, valid endpoints, unit edge costs and a finite nonnegative consistent h with h(goal)=0. IDs cannot be null. Use open grid passages in N/E/S/W order and Manhattan h to reproduce this player. The input is unchanged; null means no route. This implementation does not accept arbitrary weights or reopen closed nodes.

function aStar(adjacency, start, goal, h) {
    const open = [start];
    const closed = new Set();
    const g = new Map([[start, 0]]);
    const parent = new Map([[start, null]]);
    const f = v => g.get(v) + h(v);
    while (open.length) {
        let best = 0;
        for (let i = 1; i < open.length; i++) {
            if (f(open[i]) < f(open[best])) best = i;
        }
        const current = open.splice(best, 1)[0];
        if (current === goal) {
            const path = [];
            for (let v = goal; v !== null; v = parent.get(v)) path.push(v);
            return path.reverse();
        }
        closed.add(current);
        for (const next of adjacency.get(current)) {
            if (closed.has(next)) continue;
            const candidate = g.get(current) + 1;
            if (candidate >= (g.get(next) ?? Infinity)) continue;
            const unseen = !g.has(next);
            g.set(next, candidate);
            parent.set(next, current);
            if (unseen) open.push(next);
        }
    }
    return null;
}