← Blog
SimulationAlgorithmCanvas APITypeScript

The World of Cellular Automata — From Game of Life to Wave Function Collapse

10 min read

Go deeper on this topic

Creative Coding

Mathematical simulations, nature visualization, and generative art in the browser

Article 1 of 12 in this series.

View topic page

Next reads

Fluid Simulation in the Browser — Real-Time Computation on a 100x60 Grid

Running a real-time fluid simulation by simplifying the Navier-Stokes equations on a 100x60 grid. Implementation details of diffusion, advection, and pressure solver.

Drawing Fractal Mathematics in the Browser — From Mandelbrot Set to Barnsley Fern

Rendering fractals in the browser using complex number iteration, escape time algorithm, IFS (iterated function systems), and recursive drawing.

Generating Natural Terrain with Perlin Noise — Why Randomness Can Be Beautiful

Step-by-step implementation of natural terrain generation with Perlin noise, from the mathematics of gradient noise to octave composition and 3D mesh rendering on Canvas.

Use the topic hub as a map, then continue to the next article in the series. New here? Start at the home hub →

Common Structure of Cellular Automata

GameOfLife, SandFall, and WaveFunctionCollapse look completely different, but they share common design patterns implemented on Canvas API:

  1. Grid: Store each cell's state in a 2D array
  2. Neighbor rules: Determine the next state by referencing adjacent cells
  3. Bulk update: Calculate the next state for all cells, then write them all at once

GameOfLife — The Rules of Life

Conway's Game of Life exhibits surprisingly complex behavior from just four rules:

const W = 200
const H = 150
let grid = new Uint8Array(W * H)
let nextGrid = new Uint8Array(W * H)

function stepLife() {
  for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
      let neighbors = 0

      for (let dy = -1; dy <= 1; dy++) {
        for (let dx = -1; dx <= 1; dx++) {
          if (dx === 0 && dy === 0) continue
          const nx = (x + dx + W) % W
          const ny = (y + dy + H) % H
          neighbors += grid[ny * W + nx]
        }
      }

      const idx = y * W + x
      const alive = grid[idx]

      if (alive) {
        nextGrid[idx] = neighbors === 2 || neighbors === 3 ? 1 : 0
      } else {
        nextGrid[idx] = neighbors === 3 ? 1 : 0
      }
    }
  }

  // Buffer swap (no copy)
  const temp = grid
  grid = nextGrid
  nextGrid = temp
}

There are two reasons for using Uint8Array: memory efficiency (1 byte per cell) and the JIT compiler can optimize integer operations more easily. (x + dx + W) % W implements a torus boundary (right edge wraps to left edge).

The Importance of Buffer Swapping

Overwriting grid in place causes updated cells to affect the neighbor calculations of not-yet-updated cells. Double buffering solves this. The code above swaps references rather than copying, so the cost is zero.

SandFall — Falling Simulation

SandFall is an automaton where particles fall according to gravity. The rules are simple:

type Material = 0 | 1 | 2 // 0: air, 1: sand, 2: water

function stepSand(grid: Uint8Array, w: number, h: number) {
  // Scan from bottom to top (processing order in gravity direction matters)
  for (let y = h - 2; y >= 0; y--) {
    for (let x = 0; x < w; x++) {
      const idx = y * w + x
      if (grid[idx] !== 1) continue

      const below = (y + 1) * w + x
      const belowLeft = (y + 1) * w + (x - 1)
      const belowRight = (y + 1) * w + (x + 1)

      if (grid[below] === 0) {
        // Empty below → fall
        grid[below] = 1
        grid[idx] = 0
      } else if (x > 0 && grid[belowLeft] === 0) {
        // Empty below-left → diagonal fall
        grid[belowLeft] = 1
        grid[idx] = 0
      } else if (x < w - 1 && grid[belowRight] === 0) {
        // Empty below-right → diagonal fall
        grid[belowRight] = 1
        grid[idx] = 0
      }
    }
  }
}

Scanning from bottom to top is critical. Scanning top-down causes particles to fall multiple cells in a single step.

For water, add rules allowing lateral flow. Just a few extra lines express the difference between "liquid" and "solid" behavior.

WaveFunctionCollapse — Constraint Propagation

WFC (Wave Function Collapse) is a procedural generation algorithm. Each cell holds a "set of possible states" and alternates between observation and constraint propagation:

type Cell = {
  collapsed: boolean
  options: Set<number>
}

function findLowestEntropy(cells: Cell[][]): [number, number] | null {
  let minEntropy = Infinity
  let candidates: [number, number][] = []

  for (let y = 0; y < cells.length; y++) {
    for (let x = 0; x < cells[y].length; x++) {
      if (cells[y][x].collapsed) continue
      const entropy = cells[y][x].options.size
      if (entropy < minEntropy) {
        minEntropy = entropy
        candidates = [[x, y]]
      } else if (entropy === minEntropy) {
        candidates.push([x, y])
      }
    }
  }

  if (candidates.length === 0) return null
  return candidates[Math.floor(Math.random() * candidates.length)]
}

function collapse(cells: Cell[][], x: number, y: number) {
  const options = Array.from(cells[y][x].options)
  const chosen = options[Math.floor(Math.random() * options.length)]
  cells[y][x].options = new Set([chosen])
  cells[y][x].collapsed = true
}

function propagate(cells: Cell[][], rules: Map<number, Set<number>[]>) {
  const stack: [number, number][] = []
  // ... Propagate constraints to neighbors
  // Reduce adjacent cell options using compatibility rules
}

The key point of WFC is collapsing the lowest-entropy cell first. Deciding cells with fewer options first suppresses contradiction occurrence.

High-Speed Rendering with ImageData

Rendering 30,000 cells (200x150) every frame requires direct ImageData manipulation rather than fillRect:

function renderGrid(ctx: CanvasRenderingContext2D, grid: Uint8Array, w: number, h: number) {
  const imageData = ctx.createImageData(w, h)
  const data = imageData.data

  for (let i = 0; i < w * h; i++) {
    const px = i * 4
    const cell = grid[i]

    if (cell === 1) {       // Sand
      data[px] = 194
      data[px + 1] = 178
      data[px + 2] = 128
    } else if (cell === 2) { // Water
      data[px] = 64
      data[px + 1] = 164
      data[px + 2] = 223
    }
    data[px + 3] = 255
  }

  ctx.putImageData(imageData, 0, 0)
}

putImageData updates all pixels in a single GPU transfer. This is orders of magnitude faster than calling fillRect per cell.

Summary: Tools for Cellular Automata Implementation

To deeply understand the relationship between cellular automata and complex systems, the books on the tool shelf are ideal. The mechanism by which complex behavior emerges from simple rules applies broadly to programming design philosophy in general.

Follow @sakimyto