Percolation

Cellular Automata

Random bonds keep joining neighbouring cells; the cells connected to the top light up, and the wet region spreads until it reaches the bottom — it percolates. Tracking which cells belong to the same cluster is the job of a union-find structure with path compression: every lookup flattens the pointers it walks so the next one is instant. Runs on its own; 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 — the wet region spreads until it percolates, then reseeds.

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

What it is

Union-find answers "are these two things in the same group?" almost instantly, even as groups keep merging. Its find operation walks a chain of parent pointers to a root — and compresses the chain on the way back so it never gets long:

find(x):                         // which cluster is x in?
  r = x; while (parent[r] != r) r = parent[r];   // walk to the root
  while (parent[x] != r) {                       // ...then FLATTEN the path:
    next = parent[x]; parent[x] = r; x = next;   // point every node straight at the root
  }
  return r;

Here it drives percolation: each random bond unions two cells, and cells whose root connects to the top row are "wet". Watch the wet region grow until a single spanning cluster bridges top to bottom. The whole run is deterministic and bit-exact across every codegen mode.

Compiler stress-test

Item	What it exercises
union-find	A disjoint-set structure tracks which cells belong to the same cluster. Each cell points at a "parent"; following parents leads to a representative root. Merging two clusters is just pointing one root at the other.
path compression	The clever part: every time you walk to a root, you re-point all the nodes you passed straight at it, so future lookups are near-instant. That is pointer-chasing with in-place rewrite — a memory-access pattern no earlier demo runs.
percolation	Random bonds keep joining neighbouring cells. Cells connected to the top light up; when the wet region reaches the bottom, the grid has "percolated" — the same phase transition that governs whether coffee brews or a forest fire spreads.
integer-exact	Parents are 16-bit indices, ranks are bytes, and the bond order is a seeded pseudo-random sequence — so the whole evolution is deterministic and bit-exact across default, +mos-a16 and +mos-xy16.

Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg (and MAME where the SPC700 IPL is present). Hit Verify fidelity to reproduce the build gate's WRAM assert (gate CRC 0x025B — a fold of the cluster count, a compressing find after every bond, the percolation verdict and the parent-array checksum) live in this tab. No far pointers — the same source passes every way: host == default == +mos-a16 == +mos-xy16 == bsnes-jg, -verify clean.