Have you seen this animation before? It’s called the Game of Life.
In 1970, John Horton Conway created the Game of Life (or Conway’s Game of Life), a cellular automaton that simulates the evolution of a grid of cells based on a few simple rules. Despite its simplicity, the Game of Life exhibits complex behaviors, such as gliders, oscillators, and even Turing-complete machines.
In this article, we’ll explore how simple rules can give rise to complex phenomena and how they can be used to model real-world systems.
The Game of Life
The universe of the Game of Life is a two-dimensional grid of cells, each of which can be alive or dead. The state of each cell evolves over time according to the following rules:
- Any live cell with fewer than two live neighbors dies, as if by underpopulation.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by overpopulation.
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Or in other words:
- If the sum of all nine fields in a given neighborhood is three, the inner field state for the next generation will be life.
- If the all-field sum is four, the inner field retains its current state, and every other sum sets the inner field to death.
And that’s it! We can implement these simple rules in code and simulate the evolution of the grid over time. The animation at the beginning of this article shows the Game of Life in action.
Various patterns emerge in the Game of Life, each categorized based on its behavior. Some common types include:
Still lifes, which do not change from one generation to the next.
 |  |  |  |  |
| Block | Beehive | Loaf | Boat | Tub |
Oscillators, which return to their initial state after a finite number of generations.
 |  |  |  |  |
| Blinker | Toad | Beacon | Pulsar | Penta-decathlon |
Spaceships, which translate themselves across the grid.
 |  |  |  |
| Glider | Light-weight spaceship (LWSS) | Middle-weight spaceship (MWSS) | Heavy-weight spaceship (HWSS) |
So cool, right?
We can even run the Game of Life in the Game of Life! It’s been proven that the Game of Life is Turing complete, meaning that it can simulate any algorithm that a computer can run.
If you are interested and want to know more about Turing completeness in the Game of Life, I recommend watching this video by Alan Zucconi.
I learned about the Game of Life from The Coding Train about six years ago. Since then, I’ve fallen in love with these concepts and started exploring them further.
Wave Function Collapse Algorithm
In 2022, I found a game called Townscaper—a game that lets you build a town by just clicking. It’s a simple game, but the concept behind it is really interesting.
As you can see in the video, the game generates a town just by clicking on a grid. But how does it work? How can a simple click generate a complex town?
How does the game know what tile to place and what tile should change so it doesn’t break the town?
Turns out, the game is using an algorithm called the Wave Function Collapse algorithm (WFC)—a greedy, computational algorithm that generates a grid of tiles based on a set of constraints. Developed by Maxim Gumin based on work by Paul Merrell.
The algorithm is based on the idea of quantum mechanics, where a particle is in a superposition until it is observed. This means a particle can be in any possible state until it is observed.
For example, place a cat in a box with poison that will be released if a radioactive atom decays. The cat is in a superposition of being alive and dead until the box is opened and the cat is observed. At that point, the cat is either alive or dead. This is called the Schrödinger’s cat thought experiment.
In WFC, the process starts with a grid where each cell can be any possible tile from a given set. The algorithm then searches for the cell with the lowest entropy—essentially, the one with the most uncertainty. Once found, this cell is observed, meaning it collapses into a specific tile based on predefined constraints.
You can see the visualization below by Wave by Oskar Stålberg.
In summary, the rule in Wave Function Collapse is simple: for a given tile, we have a set of possible neighbors that can be placed next to it. Then we try to fill the empty grid by replacing each cell with the tile that matches its neighbors.
Here are some more examples from Maxim Gumin’s Wave Function Collapse repository:
This kind of programming is fascinating to me. It’s like magic!
The concept is very similar to Constraint programming – a programming paradigm where relations between variables are stated in the form of constraints – that I was researching in my article Cracking the Scheduling Code in Hay Day last year.