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.
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:
- Use Maze preset for a new random labyrinth each click, or paint walls yourself (toggle walls by clicking the same cell twice).
- Move Start and Goal with the edit chips if you like.
- Press Run search and watch open vs closed cells; try Step for one expansion at a time.
- Drag Heuristic weight from 1 (A*) down to 0 (Dijkstra) and run again on the same maze.
Try this:
- 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).
- 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.
- Load Maze preset and repeat at 1.00 vs 0: Dijkstra should expand clearly more cells than A* (often roughly 1.5×).
- 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.