A* Search, explained.
A* prioritises search states using the cost already incurred plus an estimate of the remaining cost to a goal.
Why it happens
An eight-by-six grid has unit-cost orthogonal moves. Priority is g + w times Manhattan distance. Weight zero gives uniform-cost search; weight one is admissible and consistent here, while weight three gives up the same optimality guarantee.
A* prioritises search states using the cost already incurred plus an estimate of the remaining cost to a goal.
Read the result
Read path length and expanded cells as separate outcomes. Changing walls or heuristic restarts the search so comparisons remain interpretable.
A worked example
Guide a route through an editable maze
Find a route with weight zero and record expanded cells and the returned path length.
Restart using weight one, whose Manhattan estimate never overstates remaining cost on this orthogonal unit grid.
Try weight three or edit walls, comparing actual results without assuming weighted search always returns the same shortest path.
OPTIONAL DEEPER DETAILGo deeper: inside the model
Inside this model
An eight-by-six grid has unit-cost orthogonal moves. Priority is g + w times Manhattan distance. Weight zero gives uniform-cost search; weight one is admissible and consistent here, while weight three gives up the same optimality guarantee.
Where this idea is useful
A practical use
Compare route length and expanded states separately when evaluating a heuristic’s speed and solution quality.
A common misconception
“A stronger heuristic weight always gives an equally good path faster.”
Overweighting the estimate can reduce exploration but sacrifices the admissibility guarantee. Some maps return the same route, others need not.
What this explanation leaves out
- Orthogonal unit-cost grid movement is assumed. Weight three is weighted heuristic search and may return a suboptimal path.
What happens if walls isolate the goal?
The open set is exhausted and the board reports no route; it does not draw a path through walls or invent a distance.
Which solution-quality guarantee are you willing to exchange for less search?
Associated thinkers
Associations marked provisional are awaiting source review.
Further reading
Explore the original research or the teaching reference behind this experiment.