A* pathfinding: paint walls, watch the frontier think

Draw a maze on a grid, slide from Dijkstra to A*, and watch the open set chase the goal before the shortest path lights up.

y26w44

Last week a Naive Bayes spam filter counted words and rolled dice. This week the machine does something older and sharper: search. Not learning from data, not chatting; just expanding a frontier of possibilities until a path appears.

A* is the workhorse behind game maps, robotics, and puzzle solvers. You maintain an open set of cells worth revisiting, scored by distance traveled plus a heuristic guess toward the goal. With a perfect underestimate (Manhattan distance on a grid), you still get the shortest path, but you visit far fewer cells than blind breadth-first search. Slide the heuristic to zero and you are running Dijkstra: optimal, patient, and a little wasteful. That is classic symbolic AI: explicit states, explicit costs, a planner that behaves like an agent taking reasoning steps you can see.

How to play:

  1. Use Maze preset for a new random labyrinth each click, or paint walls yourself (toggle walls by clicking the same cell twice).
  2. Move Start and Goal with the edit chips if you like.
  3. Press Run search and watch open vs closed cells; try Step for one expansion at a time.
  4. Drag Heuristic weight from 1 (A*) down to 0 (Dijkstra) and run again on the same maze.

Try this:

  1. On the default map (start in the middle, goal top-right), run with heuristic 1.00: the frontier should lean toward the goal; note Nodes expanded (often on the order of 40).
  2. Without moving walls, set heuristic to 0 and run again: the wave fills more of the open grid; Nodes expanded should jump (often 100+) while Path steps stays the same.
  3. Load Maze preset and repeat at 1.00 vs 0: Dijkstra should expand clearly more cells than A* (often roughly 1.5×).
  4. Box the goal with walls so no path exists: the gadget should admit defeat honestly.

Why this matters

Deep Blue won chess by searching millions of positions per second; expert systems encoded planners in rules before neural nets were fashionable. Modern AlphaGo mixes learning with search (Monte Carlo tree search), but the intuition starts here: represent the world as a graph, score moves, expand what looks promising. A* is the polite version that refuses to waste work when a compass toward the goal is available.

Missed the earlier editions? Train a perceptron, watch a Markov chain babble, lose to unbeatable tic-tac-toe, teach a filter to see edges, watch an agent learn from reward, see how a model reads text in tokens, watch one roll downhill to learn, let a machine find groups on its own, see a line learn to bend, watch words decide who to listen to, explore vs exploit on slot machines, chat with ELIZA, scribble Hopfield memory, or count words for spam.

Nodes expanded: 0 Path steps: -
1.00
Edit:
Start Goal Wall Open set Closed Path
A* keeps a priority queue of cells ordered by cost-so-far plus a guess toward the goal (Manhattan distance here). Slide Heuristic to 0 and you get Dijkstra: still optimal, but the wave expands in all directions until it accidentally hits the goal.