A simple set of rules can generate complex, emergent behavior. This is the essence of cellular automata, formalized by John von Neumann in 1948 and popularized by John Conway’s Game of Life in 1970.
SmoothLife, a continuous cellular automaton, implemented in WebGPU
Despite being simple to implement, cellular automata demonstrate complex, almost life-like behavior. Their inherently parallel nature makes them especially well-suited to modern GPUs.
This article takes a tour through various cellular automata algorithms, each one more sophisticated than the last:
Conway’s Game of Life — By far, the most famous cellular automaton. Implementing the Game of Life in WebGPU will serve as a basis for the rest of the algorithms presented in this article. Life-like Cellular Automata — What happens when we generalize the rules of Conway’s Game of Life? The answer is cellular automata that exhibit very interesting, self-organizing (and sometimes chaotic) behavior. Von Neumann Neighborhood — We take a small detour and talk about how a small modification to a cell’s neighborhood (i.e., a cell’s search radius) can drastically change the resulting output. Multiple Neighborhood Cellular Automata — Further modifications to a cell’s neighborhood can create very stable, self-organizing behavior that’s very reminiscent of biological cells. Cyclic Cellular Automata — Allowing cells to assume more than just “alive” and “dead” states creates fascinating cyclic structures, evolving past the traditional cell metaphor. Continuous Cellular Automata — Representing cell densities as floating-point numbers generates structures that can move very fluidly, such as the SmoothLife example shown above.
The code for this article can be found here. All examples are implemented in WebGPU. Without further ado, let’s start by looking at how to implement Conway’s Game of Life on a GPU.
Conway’s Game of Life
The most well-known cellular automaton is Conway’s Game of Life, which inspired countless variants and extensions. This classic algorithm will serve as the basis for all other cellular automata discussed in this article.
Animation of Conway’s Game of Life, starting with the R-pentomino as the first generation.
The Game of Life can be conceptualized as a game on a checkerboard, where each position on the board has two potential states: it either has a checkerboard piece, or it does not. In a metaphor to biological systems, each position on the board can be thought of as a cell. If a checkerboard piece is placed on a position, it is said to be alive; otherwise, it is dead.
... continue reading