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.
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
Ssome 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
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
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.
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.