cellular automaton
An elementary (1D) cellular automaton explorer — pick a rule, pick a seed, watch it unfold.
rule
seed
rule 110 — Turing-complete (proved by Matthew Cook, 1998/2004)
Click a tile's output square to flip that bit of the rule.
Conway's Game of Life is also a cellular automaton — just a 2D one, where each cell looks at all 8 neighbors instead of the 2 an elementary rule considers. That extra dimension and neighborhood size is what lets Life support the rich zoo of gliders, guns, and oscillators it's known for. Rule 110 gets to the same destination — Turing-completeness, universal computation — from the opposite direction: one dimension, two states, a neighborhood of three. It's about as minimal as a system can be while still being able to compute anything computable, which is exactly why Matthew Cook's proof of it was such a landmark result.
view source
import { useEffect, useRef, useState } from 'react';
const CELL = 4;
type SeedMode = 'center' | 'random' | 'paint';
const SEED_MODES: SeedMode[] = ['center', 'random', 'paint'];
const PRESETS: { rule: number; caption: string }[] = [
{ rule: 30, caption: "chaotic — was Mathematica's default RNG for years" },
{ rule: 90, caption: 'Sierpinski triangle via XOR' },
{ rule: 110, caption: 'Turing-complete (proved by Matthew Cook, 1998/2004)' },
{ rule: 184, caption: 'traffic flow model' },
];
function nextGen(row: number[], rule: number): number[] {
const w = row.length;
return row.map((_, i) => {
const l = row[(i - 1 + w) % w];
const c = row[i];
const r = row[(i + 1) % w];
const idx = (l << 2) | (c << 1) | r;
return (rule >> idx) & 1;
});
}
function randomRow(width: number): number[] {
return Array.from({ length: width }, () => (Math.random() < 0.5 ? 1 : 0));
}
function centerRow(width: number): number[] {
const row = Array<number>(width).fill(0);
row[Math.floor(width / 2)] = 1;
return row;
}
interface Props {
initialRule?: number;
}
export default function CellularAutomaton({ initialRule = 110 }: Props) {
const canvasRef = useRef<HTMLCanvasElement>(null);
const [rule, setRule] = useState(initialRule);
const [seedMode, setSeedMode] = useState<SeedMode>('center');
const [paintedRow, setPaintedRow] = useState<number[] | null>(null);
const ruleRef = useRef(rule);
const seedModeRef = useRef(seedMode);
const paintedRowRef = useRef(paintedRow);
const colsRef = useRef(0);
const redrawRef = useRef<() => void>(() => {});
useEffect(() => {
ruleRef.current = rule;
redrawRef.current();
}, [rule]);
useEffect(() => {
seedModeRef.current = seedMode;
redrawRef.current();
}, [seedMode]);
useEffect(() => {
paintedRowRef.current = paintedRow;
redrawRef.current();
}, [paintedRow]);
useEffect(() => {
const canvas = canvasRef.current;
if (!canvas) return;
const ctx = canvas.getContext('2d');
if (!ctx) return;
const seedRow = (width: number): number[] => {
const mode = seedModeRef.current;
if (mode === 'paint') {
const painted = paintedRowRef.current;
return painted && painted.length === width
? painted
: Array<number>(width).fill(0);
}
if (mode === 'random') return randomRow(width);
return centerRow(width);
};
const draw = () => {
const rect = canvas.getBoundingClientRect();
const dpr = window.devicePixelRatio || 1;
canvas.width = rect.width * dpr;
canvas.height = rect.height * dpr;
ctx.setTransform(dpr, 0, 0, dpr, 0, 0);
const cols = Math.floor(rect.width / CELL);
const rows = Math.floor(rect.height / CELL);
colsRef.current = cols;
ctx.fillStyle = '#000';
ctx.fillRect(0, 0, rect.width, rect.height);
ctx.fillStyle = '#e6e6e6';
let row = seedRow(cols);
for (let y = 0; y < rows; y++) {
for (let x = 0; x < cols; x++) {
if (row[x]) ctx.fillRect(x * CELL, y * CELL, CELL, CELL);
}
row = nextGen(row, ruleRef.current);
}
};
redrawRef.current = draw;
draw();
let painting = false;
let paintValue = 1;
const columnAt = (clientX: number) => {
const rect = canvas.getBoundingClientRect();
return Math.floor((clientX - rect.left) / CELL);
};
const paintAt = (clientX: number) => {
const col = columnAt(clientX);
const width = colsRef.current;
if (col < 0 || col >= width) return;
const current = paintedRowRef.current;
const base =
current && current.length === width
? [...current]
: Array<number>(width).fill(0);
base[col] = paintValue;
paintedRowRef.current = base;
setPaintedRow(base);
};
const onPointerDown = (e: PointerEvent) => {
const col = columnAt(e.clientX);
const width = colsRef.current;
if (col < 0 || col >= width) return;
if (seedModeRef.current !== 'paint') setSeedMode('paint');
const current = paintedRowRef.current;
const base =
current && current.length === width
? current
: Array<number>(width).fill(0);
paintValue = base[col] ? 0 : 1;
painting = true;
paintAt(e.clientX);
};
const onPointerMove = (e: PointerEvent) => {
if (!painting) return;
paintAt(e.clientX);
};
const stopPainting = () => {
painting = false;
};
canvas.addEventListener('pointerdown', onPointerDown);
window.addEventListener('pointermove', onPointerMove);
window.addEventListener('pointerup', stopPainting);
const onResize = () => draw();
window.addEventListener('resize', onResize);
return () => {
canvas.removeEventListener('pointerdown', onPointerDown);
window.removeEventListener('pointermove', onPointerMove);
window.removeEventListener('pointerup', stopPainting);
window.removeEventListener('resize', onResize);
};
}, []);
const toggleBit = (idx: number) => setRule((r) => r ^ (1 << idx));
const regenerate = () => {
if (seedMode === 'paint') {
setPaintedRow(null);
} else {
redrawRef.current();
}
};
const activeCaption = PRESETS.find((p) => p.rule === rule)?.caption;
return (
<div className="cellular-automaton">
<div className="ca-canvas">
<canvas
ref={canvasRef}
aria-label={`Elementary cellular automaton, rule ${rule}`}
role="img"
/>
</div>
<div className="controls">
<div className="group">
<span className="group-label">rule</span>
{PRESETS.map((p) => (
<button
key={p.rule}
type="button"
className={rule === p.rule ? 'active' : ''}
title={p.caption}
onClick={() => setRule(p.rule)}
>
{p.rule}
</button>
))}
</div>
<div className="group">
<span className="group-label">seed</span>
{SEED_MODES.map((mode) => (
<button
key={mode}
type="button"
className={seedMode === mode ? 'active' : ''}
onClick={() => setSeedMode(mode)}
>
{mode}
</button>
))}
</div>
<button type="button" className="regenerate" onClick={regenerate}>
regenerate
</button>
</div>
<p className="rule-caption">
rule {rule}
{activeCaption ? ` — ${activeCaption}` : ''}
</p>
<div className="rule-table">
<p className="hint">
Click a tile's output square to flip that bit of the rule.
</p>
<div className="tiles">
{[7, 6, 5, 4, 3, 2, 1, 0].map((idx) => (
<div className="tile" key={idx}>
<div className="pattern">
<span className={(idx >> 2) & 1 ? 'on' : ''} />
<span className={(idx >> 1) & 1 ? 'on' : ''} />
<span className={idx & 1 ? 'on' : ''} />
</div>
<button
type="button"
className={`output ${(rule >> idx) & 1 ? 'on' : ''}`}
aria-label={`toggle output for pattern ${idx.toString(2).padStart(3, '0')}`}
onClick={() => toggleBit(idx)}
/>
</div>
))}
</div>
</div>
<style>{`
.cellular-automaton {
border: 1px solid #2a2d31;
background: #0e1113;
}
.ca-canvas {
aspect-ratio: 2 / 1;
border-bottom: 1px solid #2a2d31;
}
.ca-canvas canvas {
display: block;
width: 100%;
height: 100%;
cursor: crosshair;
touch-action: none;
}
.cellular-automaton .controls {
display: flex;
flex-wrap: wrap;
gap: 1.25rem;
padding: 0.75rem 1rem;
}
.cellular-automaton .group {
display: flex;
align-items: center;
gap: 0.4rem;
flex-wrap: wrap;
}
.cellular-automaton .group-label {
color: var(--muted);
font-size: 0.75rem;
text-transform: uppercase;
letter-spacing: 0.04em;
margin-right: 0.15rem;
}
.cellular-automaton .controls button {
font-family: inherit;
font-size: 0.75rem;
color: #8a8f98;
background: rgba(0, 0, 0, 0.4);
border: 1px solid #2a2d31;
padding: 0.25rem 0.6rem;
cursor: pointer;
}
.cellular-automaton .controls button:hover {
color: #e6e6e6;
}
.cellular-automaton .controls button.active {
color: #0b0d0f;
background: var(--accent);
border-color: var(--accent);
}
.cellular-automaton .rule-caption {
color: var(--muted);
font-size: 0.8rem;
margin: 0;
padding: 0 1rem 0.75rem;
}
.cellular-automaton .rule-table {
border-top: 1px solid #2a2d31;
padding: 0.75rem 1rem 1rem;
}
.cellular-automaton .hint {
color: var(--muted);
font-size: 0.75rem;
margin: 0 0 0.6rem;
}
.cellular-automaton .tiles {
display: grid;
grid-template-columns: repeat(4, minmax(0, 1fr));
gap: 0.5rem 0.25rem;
}
@media (min-width: 480px) {
.cellular-automaton .tiles {
grid-template-columns: repeat(8, minmax(0, 1fr));
}
}
.cellular-automaton .tile {
display: flex;
flex-direction: column;
align-items: center;
gap: 0.3rem;
}
.cellular-automaton .pattern {
display: flex;
gap: 2px;
}
.cellular-automaton .pattern span {
width: 12px;
height: 12px;
border: 1px solid #2a2d31;
}
.cellular-automaton .pattern span.on {
background: #e6e6e6;
border-color: #e6e6e6;
}
.cellular-automaton .output {
width: 26px;
height: 26px;
padding: 0;
border: 1px solid #2a2d31;
background: transparent;
cursor: pointer;
}
.cellular-automaton .output:hover {
border-color: #4a4f56;
}
.cellular-automaton .output.on {
background: var(--accent);
border-color: var(--accent);
}
`}</style>
</div>
);
}