Cellular automaton: binary life

Cellular automaton (CA) is a discrete system consisting of separate cells. Those cells are located close to each other on a grid. Every cell can be in one of the defined states, and the number of states must be finite. The state of each cell is updated according to a rule which says how the new state depends on the actual state of the cell and states of cells in the neighborhood. Neighborhood may be defined in many ways, but usually the Moore neighborhood or the Neumann neighborhood is used. States of all cells are updated synchronously.

Moore (8) i Neumann (4) neighborhoods. State of the red cell depends on states of green cells.

Those surnames are surnames of pioneers of cellular automata theory – John von Neumann and Edward F. Moore. Of course, one can design many rules for the automaton, many states, neighborhood types and configurations. The choice of the automaton setup depends on its application. You will need different setups for image processing and restoration, for simulation of tumor cells, and for simulation of forest fire.

The program

Users can change the size of a board, the rules of automaton, and the neighborhood type. There are 11 predefined setups of the cellular automaton. Left mouse button cycles through possible states of a cell (it is possible to drag the cursor to change state of multiple cells), while right mouse button sets the state to zero. The Reset button sets the zero'th state for all cells. Step performs one step, Start button starts simulation with given speed Speed can of simulation can be controlled using speed list (higher the number, faster the simulation).

Every parameter such automata rules, type of neighborhood, board size or type can be changed during simulation, however be cautious when changing board size as resizing to small size will destroy outer cells. It is possible to save the automata state and parameters using save button - the data is stored locally as long as browser local storage is not purged.

To run the program, choose your language:

Available automata

The program implements few definitions of automatons: Original Conway Game of Life, March, Invasion, HighLife, Seeds, Amoeba and Replicator.

The The Game of Life automaton was created by John Horton Conway in 1970. It is considered by its exceptionality. The definition is very simple; it is based only on two states and three rules, but the behavior is extremely complex. The Game of Life is often compared with the automaton defined by von Neumann. Neumann's automaton is also able to simulate any function using only logical rules, but is founded on 29 states of a cell. The set of cell states includes only two elements "1" and "0". "1" means that a cell is alive (black), "0" cell is dead.

Rules of the automaton:

1. A dead cell with exactly three live neighbors becomes a live cell.
2. A live cell with two or three live neighbors stays alive.
3. In all other cases, a cell dies or remains dead.

Note that EACH cell follows THE SAME rules in EACH simulation step!

The predefined simple objects found in the simulation grid have their own names:

Blinker	Block	Clock	Glider
Gliders by the Dozen	Light-weight spaceship	Pi Heptomino	R Pentomino
Thunderbird	Toad	Tub

The automata Invasion and March were placed in program for their interesting visual effects.

For March automaton the cell can be in one of two states: active (black) and dormant (white). Rules of the automaton:

1. If active cell has at least four activated neighbors, it changes state to dormant.
2. If a cell is dormant and has two activated neighbors, it changes state to active.
3. If a cell has three activated neighbor, it changes state to active.
4. In all other cases, a cell is dormant.

For the Invasion (see picture below), there are three states: dormant (white), active (gray), sub-active (dark). Rules of the automaton:

1. If a cell is active and has at least three activated or sub-activated neighbors, it changes state to sub-active.
2. If a cell is dormant and has at least three activated or sub-activated neighbors, it changes state to active.
3. If a cell is active and has one or two activated or sub-activated neighbors, the cell is still active.
4. In all other cases, a cell is dormant.

HighLife, Seeds, Amoeba and Replicator are similar to Life automaton. Cells in all of them can be in one of two states - active (black) or dormant (white), however different rules for spawning and survival are applied.

In HighLife automaton cell survives (remains active) when it has 2 or 3 active neighbors, the new cell is spawned (becomes active) when it has 3 or 6 active neighbors otherwise the cell is dormant.

In Seeds automaton cell is spawned when it has exactly 2 active neighbors otherwise it stays dormant. It is worth noticing that every active cell becomes dormant in next generation.

In Amoeba automaton cell survives when it has 1, 3, 5 or 8 active neighbors, the new cell is spawned when it has 3, 5 or 7 active neighbors, otherwise cell is dormant.

A very interesting and eye-catching automaton is Replicator. In this automaton a cell survives or is spawned when it has 1, 3, 5 or 7 active neighbors. Given such simple rules - every drawn pattern using this automaton is a replicator - it will draw multiple copies of itself assuming enough space is available.

Program and Text: Magdalena Ławrynowicz, Amadeusz Juskowiak

Mentor: Maciej Komosinski