← All SNES demos

Maze Generate + Solve

Algorithms & Data

A 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:

ItemWhat it exercises
Genuine recursionThe 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 ceilingA 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 heapA* 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 libcallsDeliberately multiply/divide-free (grid indexing is shift/mask) — a different shape from the __mulsi3 / __udivmodsi4 demos. The gate object contains none
rep/sepNative 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.