Barnes-Hut Galaxy

Physics & Simulation

An 8-body gravity simulation on a Super Nintendo using the Barnes-Hut algorithm: each step rebuilds a quadtree over the stars and walks it recursively to approximate gravitational forces. The tree lives in a node pool, chased through runtime child[] indices — the first demo in the battery to exercise pointer-chasing dynamic trees. Watch the amber stars draw cyan trails as the galaxy collapses. Compiled with the llvm-mos-based 65816 toolchain (+mos-a16).

loading core…

Self-running — the galaxy collapses slowly (≈1 step per 25 frames; trails build up over ~30 s). (Boot holds while the gate CRC computes.)

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

What it is

Each frame: rebuild the quadtree by inserting all 8 stars (recursive descent into the correct quadrant), then for each star walk the tree to sum gravitational forces (recursive, with the Barnes-Hut centre-of-mass shortcut for distant nodes), then integrate position and velocity. The stars trace trails as they fall toward their common centre of mass.

// recursive force walk — pointer-chasing through the node pool:
void bh_force(uint8_t node, int16_t px, int16_t py, int32_t *fx, int32_t *fy) {
    BhNode *n = &bh_pool[node];          // ZP-indexed pool access
    uint32_t dist2 = dx*dx + dy*dy + SOFT;   // __mulsi3
    if (!n->has_child || n->cw*n->cw < dist2) {
        *fx += G * n->mass * dx / dist2;  // __mulsi3 + __divsi3
    } else {
        for (uint8_t q = 0; q < 4; q++)
            bh_force(n->child[q], px, py, fx, fy);  // JSR via child index
    }
}

Compiler stress-test #31 — pointer-chasing dynamic trees

A Round 2 demo opening the last data-structure corner: a linked tree built and walked at runtime, distinct from the flat arrays of #13 (N-body) and #18 (heap). The recursive call graph is tree-shaped (not linear), and every node access chases a runtime index through the pool.

Corner	What it exercises
Pointer-chasing tree walk	Each step rebuilds a pooled-node quadtree (bh_insert, recursive) then walks it per particle to approximate forces (bh_force, recursive). Both follow bh_pool[node->child[q]] where child[q] is a runtime uint8_t index — generating ZP-indexed indirect loads and a tree-shaped recursive call graph (JSR to self). This is distinct from the flat-array N-body (#13) and the linear/log recursion of the sort-race (#17) and maze (#18). The disasm gate confirmed bh_force self-references and rep/sep=160.
Barnes-Hut approximation	The force walk uses the centre-of-mass shortcut: if a tree node is far enough away (its width² < distance²), the whole node contributes via its aggregate COM rather than recursing into children. This is the O(N log N) algorithm that makes large N-body simulations tractable — and the conditional recursion is exactly what stresses the tree-shaped call graph.
Gravity kernel: mul + div	Each force evaluation computes dist² = dx² + dy² (__mulsi3), then F = G·mass·d / dist² (__mulsi3 + __divsi3). The centre-of-mass is sum_x / mass (__divsi3). The gate confirmed __mulsi3=5, __divsi3=4 — fusing the multiply-divide corner with the pointer-chasing corner in one demo.
Deliberate heavy grind	Eight particles each do a full recursive tree walk with divides every frame — about one simulation step per 25 emulated frames. The galaxy collapse unfolds slowly (watch the amber stars draw cyan trails as they fall together). This pacing IS the stress test: the recursive call graph and divide path run continuously. Gate CRC 0xEF0B; bit-exact host == +mos-a16 == +mos-xy16.

Written in C with the llvm-mos 65816 toolchain. Hit Verify fidelity to reproduce the build gate's WRAM assert (gate CRC 0xEF0B) live in this tab. Disasm gate: __mulsi3=5, __divsi3=4, recursive bh_force, rep/sep=160. No compiler bug found — recursive tree-walk codegen correct across all modes.