Cellular automata
A cellular automaton is a grid of cells where each cell changes over time based on a set of rules and the states of its neighbors. Simple rules can lead to complex patterns and behaviors.
One-dimensional cellular automata
The world is a 1D row of cells. We can see the evolution of the world over time by adding new generations to the top or bottom of a grid. If we do this repeatedly, we'll see a pattern scrolling vertically.
Elementary cellular automata
The simplest automata are known as elementary cellular automata (ECA). Each cell has 2 possible states: 0 or 1. The state of each cell in the next generation depends only on 3 values: its current state and the state of its two immediate neighbors. There are 23 = 8 orientations of these values.
Since there are 2 possible states for a cell, there are 28 = 256 rules for determining the new state of a cell in the next generation of the world.
One way to view the behavior of a rule is to initialize the first generation with a single 1 in the middle. Some rules such as rule 30 will lead to chaotic and aperiodic patterns.
Other rules such as rule 90 will lead to symmetric and periodic patterns. When starting with one middle cell, a fractal pattern called a Sierpinkski triangle appears.
Rules may behave differently when cells are initialized with random states. Rule 106 starting with a single cell leads to only a diagonal line. However, initial cells with random states leads to chaotic behavior.
Rule numbering and behavior classes
The 256 elementary rules are numbered by the Wolfram code. The eight neighborhoods are ordered by reading the three cells (left, center, right) as a 3-bit binary number: 111, 110, 101, 100, 011, 010, 001, 000. For each neighborhood, the rule says whether the center cell becomes 0 or 1 in the next generation. Those eight output bits, in the same order, form an 8-bit binary number: the rule number. For example, rule 30 in binary is 00011110. Neighborhoods 100, 011, 010, and 001 yield 1, while the rest yield 0.
Wolfram grouped the 256 rules into four behavior classes. Class I rules quickly drive almost all cells to the same value. Class II rules produce simple periodic or striped patterns. Class III rules behave chaotically, with no obvious repetition. Class IV rules show a mix: localized structures that move and interact in complex ways. Rule 110 is in this class and has been proved Turing complete, meaning it can in principle perform any computation. Below are examples from each class.
Class I — quickly homogeneous
In rule 0, every neighborhood maps to 0, so after one generation the entire row is zero. From a random start you see a single row of structure, then nothing. Class I rules suppress complexity and converge to a uniform state.
Class II — periodic patterns
Rule 250 acts like a shift: a cell is 1 if its left neighbor was 1. From a single live cell you get a clean diagonal line. The pattern is periodic in time and space. Many Class II rules produce stripes, checkerboards, or simple repeating patterns.
Rule 184 is another Class II rule, often used to model traffic. Cells can be thought of as cars moving along a lane. From a random start you see jams and flowing regions that evolve in a periodic, predictable way.
Class III — chaotic
Rule 30 behaves chaotically. There is no obvious repetition or simple structure, and small changes in the initial row lead to very different outcomes. The pattern looks random even though the rule is deterministic. Rule 30 is sometimes used as a simple pseudorandom number source.
Rule 126 produces aperiodic, chaotic-looking patterns from most initial conditions. Like rule 30, it has no simple repeating structure. It's another example of how many of the 256 rules fall into the chaotic class.
Class IV — complex, localized structures
Class IV rules sit between order and chaos. They produce persistent, particle-like structures that move across the grid and interact in complicated ways. Rule 110 is the best-known example.
Rule 54 also shows persistent moving structures and particle-like collisions rather than uniform chaos or simple periodicity. Only a small fraction of the 256 elementary rules exhibit this kind of complex behavior.
Two-dimensional cellular automata
The world is a 2D grid of cells. We can see how it changes over time by updating the cells on the grid with new states from each generation.
Conway's Game of Life
Created by mathematician John Conway in 1970, this is perhaps the most well-known cellular automata.
Cells have 2 possible states: live or dead. In new generations of the world, the state of each cell depends on its 8 immediate neighboring cells.
New worlds are generated based on these rules:
- A dead cell with 3 neighbors becomes live
- A live cell with 2 or 3 neighbors stays live
- All other live cells become dead
Oscillators
Oscillators are patterns that always return to their initial state.
Glider guns are oscillators that continuously generate gliders. Gliders are small patterns that travel across space. They can be used to transmit information.
Many glider guns can be arranged together to create logic gates. Logic gates can be used to create computers. Fun fact: The Game of Life and other Life-like automata can be implemented in the Game of Life using a construct called an OTCA metapixel.
Life-like cellular automata
Cellular automata are considered Life-like if they're similar to the Game of Life: 2D, cells have 2 possible states and change based on their 8 immediate neighbors. A common notation for the rules by which cells change is a string in the format of Bx/Sy, where:
- B = Birth - dead cells with these numbers of neighbors become live
- S = Survival - live cells with these numbers of neighbors stay live
- x and y are strings of digits from 1 to 8
The rulestring of the Game of Life can be written as: B3/S23
Some examples of how changing the rules affects the world:
- Day and Night - behaves the same after inverting the world
- Maze - expands outwards and generates maze-like paths
- Mazectric - similar to Maze, with shimmering edges and straigher corridors
- Anneal - the world converges towards the state of the majority
- Diamoeba - diamond amoeba-like shapes with moving edges
- HighLife - similar to Life but with a small self-replicating pattern
- 34 Life - a Life variant with many small oscillators and spaceships
Day and Night
In Day and Night, each cell has two possible states: on or off. The on and off states in the world are symmetric. If the state of all cells in the world are inverted, the future world is the inverted version of the original.
Since this follows similar rules as the Game of Life, it's considered a Life-like cellular automata.
New generations of Day and Night worlds follow these rules:
- An off cell with 3, 6, 7, or 8 neighbors becomes on
- An on cell with 3, 4, 6, 7, or 8 neighbors becomes off
- All other on cells become off
The rulestring is: B3678/S34678
Maze
This is an example of a maze generation algorithm. When initialized with random values in the center, cells will expand outwards towards the edges until a steady state is reached.
In some cases, oscillator patterns will appear, where 2x2 cells will continuously switch between on and off states.
The rulestring is: B3/S12345
Mazectric
This is similar to Maze. The edges of the expanding maze will have transient oscillators and appear to shimmer. Stable oscillators are more common and corridors will tend to be straighter compared to Maze.
The rulestring is: B3/S1234
Anneal
When starting with random values, blobs will quickly group together. As time passes, a single blob may form or the world will fade towards nothingness. This is a variant of the Vichniac majority voting rule. As blobs fade away, their edges approximate the curve-shortening flow or geometric heat flow.
The rulestring is: B4678/S35678
Diamoeba
When starting with random values, amoeba-like shapes with moving edges will group together. As time passes, they'll hint towards diamond shapes.
The rulestring is: B35678/S5678
HighLife
HighLife uses the rulestring B36/S23, which is very close to the Game of Life but with an extra birth condition when a cell has 6 neighbors.
That one change is enough to support a tiny self-replicating pattern, along with oscillators and gliders similar to those in the Game of Life.
34 Life
The 34 Life rule B34/S34 changes the balance between birth and survival from the Game of Life, while still using the same 8-cell neighborhood.
It has many small oscillators and spaceships, but larger random patterns often break apart or explode, giving it a different feel from classic Life.
Cyclic cellular automata
These are multi-state systems where the state of a cell changes if enough neighboring cells are in a state that win over it. Systems with 3 states are also known as "Rock, paper, scissors". For example, if a scissors cell is surrounded by enough rock cells, then the scissors cell becomes a rock in the next generation.
When initialized with random values, this system can reach a steady state of spiral waves.
Emergence
A central idea in cellular automata is emergence - complex, global behavior arises from simple, local rules with no central plan and no cell knowing the big picture. Each cell only looks at its neighbors and applies the same rule, yet over time the grid as a whole can form waves, spirals, gliders, and computation.
That contrast is what makes cellular automata interesting. The rules are easy to write down (ie. birth if 3 neighbors, survive if 2 or 3). Nobody programs the spiral in cyclic automata or the glider in the Game of Life. Those patterns emerge from many cells following the same tiny rule. This kind of bottom-up order is studied in physics, biology, and complexity science, and cellular automata are a clean playground for it.
Visual effects
These animations combine or expand upon the above ideas just for fun.
Trails in 2D
If we instead slowly transition cells from live to dead over many generations, patterns moving around in the world will leave trails behind them as they fade.
This concept can be used to visualize the speed at which patterns travel.
Bubbling lava
The bottom half of the world is a chaotic elementary cellular automaton. The top half of the world starts off empty and is the Game of Life with 2D trails.
As each generation of the ECA reaches the middle, it provides live cells to the top half of the world, which then starts spawning new life.
Order and chaos
The top of and bottom of the world are generated with 2 different ECAs. The middle of the world follows the rules of the Game of Life.
Since the top ECA generates symmetric patterns, it starts off also creating symmetric patterns in the middle. The bottom ECA generates chaotic patterns. As the two colors collide, they form a third color.
About this page
This page is a work in progress. Animations are written in plain javascript and use the canvas API for rendering. All source code is available here.