Maze Generate + Solve
Algorithms & DataA maze carved by recursive
division — a function that calls itself — then solved by
A* with an indexed binary-heap
priority queue. Watch the search explore (dim cells) and the shortest path light up (yellow), then
it builds a fresh maze and does it again. Runs automatically; no joypad needed. Written in C and
compiled with the llvm-mos-based 65816 toolchain
(+mos-a16, 16-bit accumulator mode).
Self-running demo — carve, solve, repeat.
Source maze.cmaze.h in wbniv/llvm-mos-65816
What it is
Two classic algorithms, back to back. Recursive division starts from an open room and
recursively splits each sub-rectangle with a wall that has one random gap — every split keeps the
maze fully connected. Then A* finds the shortest path from the top-left to the bottom-right
cell, expanding the most promising frontier cell first (lowest g + Manhattan heuristic)
using a binary min-heap:
divide(x, y, w, h): // genuine recursion
if w <= 1 or h <= 1: return
add a wall across the longer side, with one gap
divide(left half) ; divide(right half)
solve: push start into a binary min-heap keyed by g + h
pop the best cell ; relax its 4 neighbours (decrease-key)
stop when the goal is popped ; walk came[] back for the path
On screen: cyan walls, the A* frontier dimming cells as it explores, and the recovered shortest
path lit bright. The bottom HUD counts cells EXPLORED and the final PATH
length.
Compiler stress-test #18 — recursion + a data structure
Most demos in this gallery lean on the 32-bit math libcalls. This one is the recursion + heap member: no multiply, no divide — instead it stresses the soft-stack frame ABI (a self-recursive call) and a real priority-queue data structure (the binary heap's array indexing). And it surfaced a genuine platform limit:
| Item | What it exercises |
|---|---|
| Genuine recursion | The carve is a recursive-division function that calls itself — the soft-stack frame ABI + JSR/RTS codegen under test. The disasm gate asserts a real self-call (a JSR whose target is maze_divide) |
| 256-byte stack ceiling | A recursive-backtracker DFS is infeasible here: 65816 return addresses live on the 256-byte hardware stack, and ~6 bytes/level means a DFS’s O(N) depth (≈190 for a 16×15 grid) overflows it. Recursive division is ~log depth, so it fits |
| Indexed binary heap | A* uses a binary min-heap priority queue with decrease-key via an hpos[] position map — the sift-up/down array indexing (i≫1 / i≪1, parallel arrays, pos-map write-back) is the data-structure stress |
| No 32-bit libcalls | Deliberately multiply/divide-free (grid indexing is shift/mask) — a different shape from the __mulsi3 / __udivmodsi4 demos. The gate object contains none |
| rep/sep | Native 16-bit accumulator brackets under +mos-a16; 227 occurrences across the carve, the heap, and the A* relaxation (the values route through the Imag16 zero-page pair as int16) |
The maze logic is a portable C header (examples/65816/maze.h) linked into the SNES ROM
and a host oracle alike. The gate asserts corpus_result — a 16-bit rotate-XOR CRC over
the carved walls, the A* path, and the heap operation counts — is identical on host and target.
Written in C with the llvm-mos 65816 toolchain. Hit Verify fidelity to
reproduce the build gate's WRAM assert (gate CRC 0x0749) live in this tab — the same
hash the host oracle and the cycle-accurate bsnes-jg core agree on, across the default 8-bit, the
+mos-a16, and the +mos-xy16 builds.