Pathfinding through denoising
A diffusion model that finds shortest paths. It was never taught to search; it was taught what a solved board looks like, and it recovers the route from pure noise. Pick a style of maze, or draw anything at all, then watch the path resolve.
Loading v4
Drag either endpoint to move it. Hold ⇧ or use the right button to invert the brush.
Four generations
Each model is a step in the same project, and the playground can run any of them. The first learned one kind of maze; the newest learned to find a shortest path through anything. Scores are the share of held-out boards solved with a shortest path.
| Model | Classic | Perfect | Imperfect | Freeform |
|---|---|---|---|---|
| 500,000 boards in 13 styles, from perfect mazes to scribbles · Final · 80k training steps | 99.9% | 99.8% | 97.9% | 99.0% |
| v2, then 20,000 more backtracker mazes | 94.4% | 22.8% | 3.9% | 0.0% |
| 20,000 mazes from four generators | 91.2% | 23.3% | 3.3% | 0.0% |
| 20,000 recursive-backtracker mazes | 27.2% | 2.0% | 0.8% | 0.0% |
- Classic.
- The original test: the five perfect maze styles, with both endpoints on cell centres.
- Perfect.
- The same five maze styles, with endpoints on any open pixel.
- Imperfect.
- Braided, rooms, stretched and hand-edited mazes.
- Freeform.
- Floor plans, caves, noise and scribbles: no maze underneath at all.
Specifics
- Architecture
- U-Net, 6,189,441 parameters, attending at 12 × 12 and 6 × 6
- Board
- 23 × 23 pixels, any arrangement of walls
- Training set
- 500,000 boards from 13 styles, perfect mazes through caves and scribbles, each with a shortest path
- Solve rate
- 99.0% of 1,664 held-out boards solved with a shortest path, 99.8% with any path
- Sampling
- DDIM over 32 of the 1,000 trained noise levels; more steps change little
- Inference
- onnxruntime-web, WebGPU with a WebAssembly fallback. Nothing you draw leaves the tab.
- Download
- 10.5 to 12.5 MB a model, float16 weights, fetched the first time it is picked