1-D Cellular Automaton
Cellular Automata
Rule 90 draws the Sierpinski triangle. Rule 110 is Turing-complete chaos.
Both run live on a Super Nintendo — one pixel row generated per frame, scrolling down so
the entire screen is the computation's history. Written in C and compiled to a real
.sfc ROM with the
llvm-mos-based 65816 toolchain
(+mos-a16, 16-bit accumulator mode). Press X to flip between rules.
X toggle rule · Enter reset
Click the screen to focus, then play. Tab away and it pauses.
Controls
| Key | Action |
|---|---|
| X | Toggle Rule 90 ↔ Rule 110 |
| Enter | Reset (restart from seed) |
What it is
A 1-D elementary cellular automaton (Wolfram, 1983) has 256 cells in a ring. Each generation, every cell looks at its left neighbour, itself, and its right neighbour — a 3-bit pattern — and maps that pattern to a new value via an 8-bit lookup table called the rule number. The SNES renders each generation as one pixel row scrolling downward, so the entire visible screen is the last 224 generations of history.
Rule 90 (binary 01011010) ignores the center cell: new = left XOR right.
Starting from a single live center cell, it produces the Sierpinski triangle — a
perfect fractal that fills the screen as generations accumulate.
Rule 110 (binary 01101110) is one of the simplest known
Turing-complete systems. Its patterns are aperiodic and provably capable of universal
computation via colliding gliders. It starts from the same center-cell seed and immediately
diverges into complex, non-repeating stripes.
Display architecture
The SNES BG3 layer is set up as a 32×32 tile ring in 2bpp mode (256 px tall). Each
CA generation writes its 256 cells — bitpacked into 32 bytes — into the current pixel row
of the current tile-row in VRAM. Every 8 generations a 512-byte DMA fires during v-blank,
flushing the completed tile-row. BG3VOFS is updated each frame so the newest
row always sits at the bottom of the 224-pixel visible window — the ring scrolls seamlessly
with no tilemap rewrites, ever.
Compiler stress-test
| Item | What it exercises |
|---|---|
| Bit-packed CA | 256 cells stored as uint8_t[32] (1 bit/cell); each generation unpacks 3-bit neighbourhoods via shifts+masks, looks up the rule bit, and repacks — pure shift+boolean with no multiply or divide |
| Sliding window | Inner loop uses win >>= 1 / mask <<= 1 (constant-1 shifts only) — eliminates variable-shift loops that cost 20–40 cycles each on the 65816 barrel-shifter-free architecture |
| No mul/div | ca_step contains zero __mulsi3 / __divsi3 calls; the disasm gate asserts shifts ≥ 1, booleans ≥ 1, bad_mul = 0, bad_div = 0 |
| 5-way gate | host == default@MAME == +mos-a16@MAME == +mos-xy16@MAME == +mos-a16@bsnes-jg (gate CRC 0xAB2C, 32 Rule-90 + 32 Rule-110 gens) |
The CA kernel (examples/65816/ca1d.h) is a portable C99 header included by the
SNES ROM, a host oracle, and the corpus slice. The gate runs 32 Rule-90 + 32 Rule-110
generations from a single-cell seed and folds every output row into a CRC-16; the assert
is corpus_result == 0xAB2C on all five build variants — five-way differential.
Written in C with the llvm-mos 65816 toolchain and verified against two
emulators (MAME + bsnes-jg). The player above is that exact cycle-accurate core — hit
Verify fidelity to reproduce the build gate's WRAM assert (gate CRC
0xAB2C) live in this tab. No far pointers → five-way bar:
host == default == +mos-a16 == +mos-xy16 == bsnes-jg.