GDnD Wiki

GDnD Wiki

This site is for Ulster University students and staff. Enter the class access password to continue.

Cellular Automata

9 min read

Summary

A cellular automaton (CA) is a discrete computational model in which a grid of cells, each holding a simple state (typically on/off), updates in parallel according to fixed neighbourhood rules. The profound result is that extraordinarily complex patterns, including patterns that resemble biological growth, fluid dynamics, and computation itself, emerge from rules that fit in a single paragraph. CAs are used in procedural generation, simulation, and as a conceptual model for emergent systems.

(Shiffman, The Nature of Code, Ch. 7, see source-nature-of-code)

JavaScript to Unity/C# bridge

Nature of Code presents cellular automata in JavaScript, where each generation is often drawn straight to the canvas. In Unity, the cleanest translation is usually:

  • a 1D or 2D array storing the current state
  • a second array for the next state
  • a fixed-rate step in Update() or a coroutine
  • a visual layer such as Texture2D, Tilemap, or instanced sprites

So the real bridge is from “draw pixels directly” to “update data, then render that data through Unity”.

Elementary cellular automata (1D)

The simplest form is a one-dimensional row of cells, each binary (0 or 1), updated by looking at itself and its left and right neighbours. With three cells each having two possible states, there are 2³ = 8 possible neighbourhood configurations. Each configuration maps to a 0 or 1 output. Since there are 8 binary outputs, there are 2⁸ = 256 possible rulesets, named Rule 0 through Rule 255 by Stephen Wolfram.

Rule numbering

Express the rule’s eight outputs as a binary number, read right to left (neighbourhood 111 to 000):

Neighbourhood111110101100011010001000
Rule 30 output00011110

Rule 30 in binary = 00011110 = 30 in decimal. Used by Wolfram’s Mathematica as a pseudorandom number generator.

Rule 90 generates the Sierpiński triangle, a fractal, from a single active cell.

Implementation

// Two arrays — current state and next state
int[] current = new int[width];
int[] next    = new int[width];
 
int[] ruleset = { 0, 1, 1, 1, 1, 0, 0, 0 };   // Rule 30
 
void Step()
{
    for (int i = 1; i < current.Length - 1; i++)
    {
        int left   = current[i - 1];
        int center = current[i];
        int right  = current[i + 1];
        next[i] = ruleset[7 - (left * 4 + center * 2 + right)];
    }
    System.Array.Copy(next, current, current.Length);
}

The critical detail: compute all new states into next before copying back. Updating in-place corrupts the neighbourhood data for cells further along the scan.

Wolfram’s four classes

ClassBehaviourExample
1Uniformity: all cells converge to one stateRule 0
2Repetition: stable or oscillating patternsRule 4
3Chaos: complex, apparently random patternsRule 30
4Complexity: localised structures, long-range orderRule 110

Class 4 is the most interesting: it is Turing-complete (Rule 110 was proven so). It sits at the boundary between order and chaos, the same zone where interesting computation and life-like behaviour emerge.

Conway’s Game of Life (2D)

John Conway (1970) designed a 2D CA with the fewest rules that produce non-trivial, unpredictable emergent behaviour. The rules apply simultaneously to every cell:

ConditionResult
Living cell, < 2 live neighboursDies (underpopulation)
Living cell, 2 or 3 live neighboursSurvives
Living cell, > 3 live neighboursDies (overpopulation)
Dead cell, exactly 3 live neighboursBecomes alive (reproduction)

Neighbourhood = the 8 cells surrounding a given cell (Moore neighbourhood).

Implementation

int[,] grid;
int[,] next;
int cols, rows;
 
void Step()
{
    for (int i = 0; i < cols; i++)
    for (int j = 0; j < rows; j++)
    {
        int neighbours = CountNeighbours(i, j);
        bool alive = grid[i, j] == 1;
        next[i, j] = alive
            ? (neighbours == 2 || neighbours == 3 ? 1 : 0)
            : (neighbours == 3 ? 1 : 0);
    }
    // Swap buffers
    (grid, next) = (next, grid);
}
 
int CountNeighbours(int x, int y)
{
    int sum = 0;
    for (int dx = -1; dx <= 1; dx++)
    for (int dy = -1; dy <= 1; dy++)
    {
        if (dx == 0 && dy == 0) continue;
        int nx = (x + dx + cols) % cols;   // toroidal wrap
        int ny = (y + dy + rows) % rows;
        sum += grid[nx, ny];
    }
    return sum;
}

Toroidal wrapping (mod arithmetic) prevents edge artefacts and creates a seamless grid.

Notable patterns in Game of Life

Pattern typeExampleBehaviour
Still lifeBlock, LoafNever changes
OscillatorBlinker (period 2), PulsarReturns to initial state after N steps
GliderGliderMoves diagonally across the grid indefinitely
SpaceshipLWSSMoves horizontally or vertically
GunGosper Glider GunContinuously emits new gliders

Procedural generation with CAs

Cave generation

A common technique for procedural dungeon generation:

  1. Initialise grid with ~45–55% random cells alive.
  2. Apply a modified GoL-style rule: a cell becomes/stays alive if it has ≥ 5 alive neighbours.
  3. Run 4–6 iterations.
  4. The result is organic cave-like corridors.

This produces natural-looking cavern layouts without hand-authoring.

Terrain textures

Treat pixels as cells. Neighbourhood averaging produces blur-like or erosion effects that can support procedural noise and heightmap smoothing.

Extensions

VariantDescription
Probabilistic rulesOutcomes have random chance, which produces less deterministic and more organic results
Continuous statesCells hold float values (0.0–1.0) instead of binary, which enables gradient-based patterns
Hexagonal gridsSix-neighbour neighbourhood produces different symmetries
Mobile cellsNo fixed grid, with neighbourhood based on proximity radius
Nested CAIndividual cells contain smaller CA systems

In practice (Unity)

In Unity, a CA grid maps naturally to a 2D array updated in a coroutine or fixed-rate loop. For visualisation, either draw with OnDrawGizmos, use a Tilemap, or write to a Texture2D:

Texture2D tex = new Texture2D(cols, rows);
tex.filterMode = FilterMode.Point;   // no anti-aliasing for pixel-perfect grid
 
for (int x = 0; x < cols; x++)
for (int y = 0; y < rows; y++)
    tex.SetPixel(x, y, grid[x,y] == 1 ? Color.white : Color.black);
 
tex.Apply();
GetComponent<Renderer>().material.mainTexture = tex;

Performance note: SetPixel is slow for large grids. Use SetPixels32 with a pre-allocated Color32[] buffer, or compute via a ComputeShader for real-time large-scale CA.

This is one of the next best candidates for the Unity/C# Nature of Code strand because it fits cleanly into a Texture2D or grid-renderer approach. See overview-unity-nature-of-code-examples for the staged implementation plan.

For a concrete Unity example, see:

Scene setup for the Unity example

Use the Game of Life scripts as a small Unity lab:

  1. Create a new 2D scene.
  2. Create an empty GameObject named GameOfLife.
  3. Add SpriteRenderer to the GameObject.
  4. Add GameOfLifeGrid.
  5. Add GameOfLifeTextureRenderer.
  6. Set width and height to a small value first, such as 64.
  7. Set aliveChance around 0.45.
  8. Set stepInterval around 0.1.
  9. Use an orthographic camera and frame the generated sprite.
  10. Press Play and check that the black and white grid changes over time.

The scripts are designed to sit on the same GameObject. GameOfLifeTextureRenderer uses RequireComponent attributes for GameOfLifeGrid and SpriteRenderer, but students should still learn to recognise those dependencies in the Inspector.

Code walkthrough

GameOfLifeGrid owns the simulation. In Awake(), it creates two bool[,] arrays: current for the generation being read and next for the generation being written. Randomise() fills current using aliveChance, which gives the simulation a different starting pattern.

Step() is the main algorithm. It visits every cell, counts live neighbours, applies the Game of Life rules, writes the result into next, then swaps current and next. That final swap is the double-buffering step. It prevents early updates in the scan from changing the neighbour counts for cells that have not been processed yet.

CountNeighbours() checks the eight surrounding cells. The modulo arithmetic wraps the grid edges, so the left edge connects to the right edge and the top connects to the bottom. This is called toroidal wrapping.

GameOfLifeTextureRenderer owns the display. In Awake(), it creates a Texture2D, sets point filtering so cells stay crisp, creates a sprite from that texture, and assigns it to the SpriteRenderer. In Update(), it waits until stepInterval has elapsed, calls grid.Step(), then redraws the texture.

Draw() copies the grid into a pre-allocated Color32[] buffer, then calls SetPixels32() and Apply(). This is faster and cleaner than calling SetPixel() once per cell every frame.

What to change first

ChangeFileExpected effect
width and heightGameOfLifeGridlarger grids show richer structures but cost more to update
aliveChanceGameOfLifeGridlow values produce sparse patterns, high values often die out quickly
stepIntervalGameOfLifeTextureRendererlower values animate faster, higher values make rules easier to observe
neighbour wrappingGameOfLifeGridremoving wrap makes edges behave like borders instead of a continuous surface
cell coloursGameOfLifeTextureRendererchanges readability without changing the simulation

Debugging checklist

  • If the grid is blank, check that the camera frames the generated sprite.
  • If the grid appears but never changes, check that Play mode is active and stepInterval is not too high.
  • If Unity reports a missing component, check that GameOfLifeGrid, GameOfLifeTextureRenderer, and SpriteRenderer are on the same GameObject.
  • If the pattern looks blurred, check that the texture filter mode is FilterMode.Point.
  • If large grids slow down, reduce width and height before changing the algorithm.

Practice

Create a Game of Life scene and run three experiments:

  1. Set aliveChance to 0.20, run for ten seconds, and describe the density.
  2. Set aliveChance to 0.45, run for ten seconds, and describe the difference.
  3. Set stepInterval to 0.5, run again, and explain why the behaviour is easier or harder to study.

Then answer this design question: how could a cave-generation rule differ from Conway’s original rules if the goal is stable playable space rather than endless emergence?

Self-test

  1. Why does a cellular automaton need a separate next array?
  2. What does toroidal wrapping do?
  3. Which script owns the simulation state in the Unity example?
  4. Which script owns the visual output?
  5. Why is SetPixels32() a better teaching target than repeated SetPixel() calls for this example?

Answers

  1. The separate next array keeps all cells reading from the same generation. Without it, earlier updates would change the data used by later cells.
  2. Toroidal wrapping connects opposite edges of the grid, so edge cells still have neighbours on every side.
  3. GameOfLifeGrid owns the simulation state.
  4. GameOfLifeTextureRenderer owns the visual output.
  5. SetPixels32() lets the renderer prepare all cell colours in one buffer, then send them to the texture in one call. That keeps the display code readable while avoiding the slowest per-cell update pattern.

Key takeaway

The CA insight is powerful: local rules plus parallel update leads to emergent global complexity. This is the same principle behind flocking (steering-behaviours), neural networks (genetic-algorithms), and real biological systems. The CA is the cleanest laboratory for understanding emergence because the rules are so simple they can be enumerated completely.

Graph View

Backlinks