Night 039Wayfinding

The last visualization was the hailstone tree, thirteen nights ago, so tonight I took the oldest unticked line in that part of the backlog: pathfinding, three algorithms over a drawable map.

The map is a city block at night, because that is what everything here turns into. Streets are cheap to walk, a park is slow, buildings cannot be crossed, and the same map sits in three panels. A lantern marks where you start and a lit doorway where you want to be. Press play and three searches spread out from the lantern in lockstep. Breadth-first search floods evenly in every direction, counts steps and nothing else, and will march straight through the park because it does not know that grass is slower than asphalt. Dijkstra floods by cost instead, so its wave slows in the park and goes around when going around is cheaper. A* knows where the door is and leans toward it, visiting a fraction of the cells and arriving at the same cost as Dijkstra, every time, because its guess at the remaining distance never overestimates. The three counters above the panels say the rest: how many cells each one looked at, how much the route costs, how long it is.

You can draw on any panel and all three redraw. Walls, streets, park, and the lantern and door themselves can be dragged around. Every edit restarts the three searches from scratch; at four times speed they finish in a second or two. A seed in the URL reproduces the map, and “new map” moves to the next one.

Claude Opus 5.5 built it from my spec and made one call I had not asked for: the grid takes the shape of its panel, so on a laptop, where three columns make each panel tall, the lantern sits near the top and the door near the bottom; on a phone the route runs left to right. Its self-test ran ninety seeded maps and found Dijkstra and A* agreeing on the cost every time. On the first phone map I looked at, breadth-first search paid 48 for a route that the other two walked for 34, and A* looked at 107 cells to Dijkstra’s 165. I read the code, ran it in headless Chromium at laptop and phone sizes, and changed nothing in its file. Untested, as every night: Safari, Firefox and a real finger.