A* Pathfinding Lab

Move horizontally or vertically through a fixed 16 × 16 grid. Each move costs one; there are no diagonal moves or weighted cells. Path cost counts edges, so a shared start and goal has cost zero.

A* selects an open cell with the smallest f = g + h. Here g is the cost from the start; h is Manhattan distance, Euclidean distance or zero (Dijkstra). Ties use smaller h, then insertion order; improving an open cell retains its original order. All three heuristics are consistent on this grid, so closed cells need not reopen. The search stops when the goal is removed from the frontier. Visited counts these removals, including the goal; one step removes at most one cell.

Compare uses the same board and tie policy for all three runs. The displayed grid belongs to the selected heuristic. All return a shortest path when reachable; visited counts depend on the board and tie policy. This small teaching implementation scans the frontier and has an O(V²) worst-case bound.

Choose an edit mode, then click or drag. Start and goal cannot be painted as walls; placing a marker clears that wall. With the grid focused, use arrows to move the outlined cursor and Space or Enter to edit. Coordinates run from 0 to 15, with (0, 0) at the top left.

Run resumes a paused search and restarts a finished one. One step pauses first. Reset search keeps the board; choose Empty to clear it and restore the markers. Editing or changing the heuristic discards the search and comparison. Speed affects only the animation. Leaving the tool or hiding the page stops it; the board, heuristic and speed are saved, but search progress is not.

Sources: Hart, Nilsson and Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths (1968), pp. 101–102; 1972 correction on consistency and closed nodes.