Part A · Search
A* Lab
Paint tiles, move the start and goal, and watch our original A* search expand the board. The port keeps the original priority queue and tie-breaking, so paths and node counts match the Python program exactly.
Reference study
980 paired boards: fewer expansions, at a price
10 random boards for every size from 2 × 2 to 99 × 99 from the notebook's generator (seed 2022), each searched with both heuristics and solved by breadth-first search. Generated by web/scripts/generate-reference-studies.ts with the A* port that reproduces the original paths and node counts exactly.
- The report's direction holds, and is now measured. Manhattan expanded 110.3 fewer nodes per board on average (paired 95% CI 95.8 to 125.8 fewer); fewer on 617 boards, more on 135.
- But it finds a shortest path less often. Manhattan returned an optimal path on 74.3% of solvable boards, Euclidean on 85.6%: 11.3 points fewer for Manhattan on the same boards (paired 95% CI 9.1 to 13.3). Where only one heuristic was optimal, it was Manhattan on 1 boards and Euclidean on 106 (exact McNemar p < 0.001).
- Why: neither heuristic is admissible here. On this hex grid a step like (1, −1) costs 1, but Manhattan scores it 2 and Euclidean √2. Overestimating makes the search greedier: fewer expansions, longer paths. The two sample inputs happen to be solved optimally (8 and 13 cells, confirmed by BFS).
Node expansions (paired, 980 boards)
- Mean difference, Manhattan − Euclidean
- −110.3
- 95% paired bootstrap CI [−125.8, −95.8]; median −12.5
- Mean expansions per board
- 259.8 vs 370.1
- Manhattan vs Euclidean, the notebook's counter
- Wilcoxon signed-rank (two-sided)
- p < 0.001
- n = 752 non-zero pairs (228 ties dropped), W = 26,435.0, z = −19.32
- Effect size
- r = −0.81
- matched-pairs rank-biserial; Cohen's d_z = −0.46
Manhattan expanded fewer nodes on 617 boards, Euclidean on 135, with 228 ties. Negative differences favour Manhattan.
Did A* find a shortest path? (931 boards with a path)
| Heuristic | Interval | Rate (95% CI) | Extra cells |
|---|---|---|---|
| Manhattanshortest path found | 74.3% [71.4, 77.0] | +0.69 | |
| Euclideanshortest path found | 85.6% [83.2, 87.7] | +0.19 | |
| Both the same lengthagreement rate | 81.5% [78.9, 83.9] |
- Paired difference, Manhattan − Euclidean
- −11.3 pp
- 95% paired bootstrap CI [−13.3, −9.1] pp; resamples boards, 2000 reps, seed 2023
- Exact McNemar test (two-sided)
- p < 0.001
- 107 discordant boards: optimal for Manhattan only on 1, Euclidean only on 106
The two rates come from the same boards, so the paired difference and McNemar's test (which uses only the boards where the heuristics disagree) are the comparison; the separate intervals above describe each heuristic on its own. Extra cells: mean path length beyond the shortest, over boards with a path (largest seen: 14). Neither heuristic is admissible on this grid: both overestimate the true distance for 40.9% of start/goal pairs on an empty 10 × 10 board.
Heuristic study
Manhattan vs Euclidean, revisited
Our report compared node expansions on random boards from the notebook's generator (random barriers, random start and goal) and found the two heuristics similar on small boards, with Manhattan expanding slightly fewer nodes as boards grew. Re-run the experiment here: random boards for every size from 2 × 2 to 99 × 99, counted the way the notebook counted them. One board per size is the notebook's protocol; more boards per size give tighter intervals.
The comparison is now paired: both heuristics search the same boards, so the analysis works on the per-board difference (paired bootstrap interval, Wilcoxon signed-rank test, effect sizes). Each board is also solved by breadth-first search to check whether A* returned a shortest path.