Laboratory 02 · Verified

A* Search

Observe how the heuristic guides frontier expansion toward a minimum-cost path.

Original paper: A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Authors: Peter E. Hart, Nils J. Nilsson, and Bertram Raphael
Published: 1968

Interactive workbench

A* search, one expansion at a time

Edit the board, tune the heuristic, and watch frontier priorities turn local choices into a complete route.

Statusready

Expanded0

Frontier1

Path cost—

Current g —Current h —Current f —Steps 0Discovered 1Peak frontier 1Path length —

9 × 13 orthogonal gridTap to edit · arrows point to predecessors

Start Goal Wall Frontier Expanded Current Final path Predecessor

Priority formulaf(n) = g(n) + 1 × h(n)

Standard A*. With w = 1, path cost and Manhattan distance have their standard A* balance. On this four-way grid, the result is optimal.

Read the search

01
Choose
Take the frontier node with the lowest f score, using a fixed tie-break order.
02
Expand
Close that node and update every reachable four-directional neighbor.
03
Reconstruct
When the goal is reached, follow predecessors back to the start.