Greedy Best-First Search

An estimate, not a route

The heuristic h is the Manhattan distance: |column − goalColumn| + |row − goalRow|. Moves go north, east, south or west and cost one. The estimate ignores walls: a cell next to the goal can still be a dead end. S marks the start and G the goal.

For this grid h never overestimates the shortest remaining distance. Even this admissible heuristic does not make Greedy optimal: the algorithm compares h alone and ignores the distance already traveled, g.

Choose from the entire frontier

The frontier contains discovered cells that have not yet been selected. Remove a cell with the smallest h; stop if it is the goal. Otherwise inspect its open passages in north/east/south/west order and add unseen neighbors. Equal h values are resolved by discovery order.

Mark cells when adding them and keep their first parent. Every cell enters the frontier at most once. This prevents cycles and makes the search terminate on a finite maze, finding a route if one exists. Selecting a cell does not mean walking there from the previously selected cell: the frontier can jump between branches.

Closer to the goal, farther along the route

Coordinates are (column, row), starting at 1. From S=(1,3), the east neighbor has h=5, while the south neighbor has h=7. Greedy goes east, reaches (6,3) with h=1 and meets a wall. It then returns to the waiting frontier and explores the upper passage.

The resulting route has 10 edges. A lower route through row 4 needs only 8. This maze deliberately contains a cycle, so there are alternative routes to compare. Choosing the smallest estimate does not guarantee the shortest answer. The green cells are reconstructed from parents, not from the order of selection.

What the player counts

Discovered includes S and every cell first added to the frontier. Selected counts removals, including the goal. Neighbor checks counts open adjacency entries, including already discovered neighbors; walls are not included. The goal's neighbors are not inspected.

During reconstruction the green path grows from goal to start; the final path is reversed. Unvisited cells after success are simply unexplored, not necessarily unreachable. Restart and seeking use immutable saved states. The second example has start equal to goal: one selection and a zero-edge path.

The cost of this implementation

This teaching version scans an array for the smallest h and removes that entry with splice. For V cells and E passages its worst-case time is O(V² + E), with O(V) extra working memory, excluding the graph. A binary heap implementation with fixed priorities can reduce search time to O((V + E) log V).

The player saves up to O(V) snapshots, each holding O(V) cell data, so visualization history uses O(V²) space in addition to the shared graph. This cost belongs to replay, not to the search itself. The frontier order is deterministic; this is a tie-breaking rule, not sorting stability.

JavaScript implementation

The code expects a Map from cell IDs to ordered neighbor arrays, valid start and goal IDs, and a finite nonnegative heuristic h. IDs must not be null. Build adjacency from open passages in N/E/S/W order and use Manhattan h to reproduce the demo. The input is not modified; null means no route. The player additionally validates and copies the maze.

function greedyBestFirst(adjacency, start, goal, h) {
    const open = [start];
    const parent = new Map([[start, null]]);
    while (open.length) {
        let best = 0;
        for (let i = 1; i < open.length; i++) {
            if (h(open[i]) < h(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();
        }
        for (const next of adjacency.get(current)) {
            if (parent.has(next)) continue;
            parent.set(next, current);
            open.push(next);
        }
    }
    return null;
}

From Greedy to A*

Greedy prioritizes h. A* prioritizes g+h and updates a parent when it finds a cheaper route. With suitable assumptions on edge costs and the heuristic, A* can guarantee a shortest path. Merely changing the priority expression in this first-discovery implementation is not enough: it also needs relaxation.