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).

loading core…

Self-running demo — carve, solve, repeat.

Click the screen to focus, then watch. Tab away and it pauses.

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.