As a “Hello World” project to get acquainted with the capabilities of processing.js, a JavaScript port of the Processing visualization language, we’ve developed an interactive cellular automata explorer. Before diving into the specifics of how the imagery is generated, we’ll present a little more background on cellular automata.
What Are Cellular Automata?
To start, a definition may be in order. From Wikipedia:
“In mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states (labeled 0 and 1) and the rule to determine the state of a cell in the next generation depends only on the current state of the cell and its two immediate neighbors. As such, it is one of the simplest possible models of computation.”
A Brief History of Cellular Automata: The Contributions of Von Neumann, Conway, & Wolfram
The first system of cellular automata was developed in the 1940s by John von Neumann as an exercise to understand the problem of building self-replicating robots. As the Terminator franchise did not exist in von Neumann’s time, this was generally accepted as being a Good Idea.
In essence, what he created was a two-dimensional grid of finite-state machines (FSM), each of which may be in only one state at a time, with the ability to transition to another state via a triggering event—kind of like a really big game of Whac-A-Mole. But unlike Whac-A-Mole, each FSM in this system (referred to as a “cell”) is able to effect change on other cells in its “neighborhood.” Informed by transition rules, a change in any given cell will cascade through its neighbors, which will do the same to their neighbors, etc. Imagine that the moles don’t just randomly pop their little heads up, but that the act of whacking one will cause some of its friends to peek out and say “Hey, what’s the fuss all about?” This, in turn, causes their neighbors to either hide or take a look for themselves. In this way, any small, localized state change may have far-reaching consequences; a single cell transition may have a cascading effect across the grid.
The ‘Hacker Emblem’, representing a glider from Conway’s ‘Game of Life’
John Conway’s “Game of Life” brought Neumann’s ideas to a wider audience in the October 1970 issue of Scientific American. Conway’s model allowed for a neighborhood of 8 neighboring cells (including diagonals), as opposed to the 4 in Neumann’s model. The eye-opening results of running the simulation demonstrated that emergent complexity and self-organization could arise in the absence of explicit design.
In the early ’80s, Stephen Wolfram, of Mathematica and Wolfram Alpha fame, presented the Wolfram code, a naming system for a special class of cellular automata known as elementary cellular automata (ECM). ECM, unlike the two-dimensional “Game of Life,” are implemented in one-dimensional space. From 1992 to 2002, he explored simple computational systems, including ECM. He concluded from his studies that the universe is digital in nature and that even the most complex systems are governed by fundamental laws that can be described as simple programs. He does, however, temper this statement with the theory of computational irreducibility, which implies that the computational processes comprising our free will are sufficiently complex enough to be unpredictable.
Implementation
An ECM system may be visualized as a series of rows, with each row comprised of a number of cells. Each subsequent row is generated by applying a transition rule to every cell in the prior row. Each of the cells comprising a row can exist in one of two states, 0 and 1, and has a neighborhood of only 2 adjacent cells. The initial state may randomly assign each cell in the first row to either a 0 or 1; one method (used in our case) assigns only a single cell to have a state of 1, the rest having a state of 0. For visualization purposes, a cell in state 0 will be white; a state 1 cell is black. Given that a cell has 2 possible states (0 or 1) and 2 neighbors, any cell will find itself in one of 8 possible configurations (2^3=8).
A rule defining state transitions
In the first state of the image above: (1 1 1), the cell itself is 1, and its neighbors are 1. The new state for the cell will have to be 0 or 1; this is defined by the transition rule in place. Given 1 of 2 outcomes for each of 8 configurations, there are 256 possible transition rules. Each rule defines the new state for a cell, given its current state and that of its neighbors.
Holding the patterns constant: 111 110 101 100 011 010 001 000, each transition rule can be seen as an 8-digit binary number. The place of each bit corresponds to one of the 8 patterns, and the value of each bit (0 or 1) gives the new state for a cell. For example, if the transition rule is: 0 0 0 0 0 0 0 1, then only a cell having the pattern 000 will be black in the next row. Using the rule: 0 0 0 0 0 0 1 1, cells in the pattern 001 and 000 will be black, and so on.
Our interactive visualization allows for exploration of the output of each transition rule, from 0-255. The rule number may be input via a jQuery slider or text input. This number is then converted to its binary equivalent and is front-padded with 0s if necessary to create an 8-digit binary number. Visual rendering is done using the processing.js library, which is drawn within a canvas element on the page. The first step in rendering each view is to place a single black cell in the middle of the top row. To create each subsequent row, moving down the page, the state of each cell (and its neighbors) in the prior row is used to generate a new cell value of 0 or 1, depending on the transition rule selected. If the value is 0, nothing is drawn; for a cell value of 1, a black square is drawn. Cell size may be changed by selecting a different radio button; smaller cells will increase processing time but give a more detailed rendering.
By applying the various rule sets, some very interesting images are produced. Here are a few examples:
Rule #: 30, 45, 57, 60, 73, 86, 105, 110, 124, 126, 135, 165, 181, 210, 225
Hopefully we’ve piqued your interest in the wonderful world of cellular automata. Happy rendering!
My brain hurts just a little bit!
I love this! So very interesting. Love going to Wolfram’s Demo Project and playing with Rule 30 and beyond.