secretGeek logowiki. secretGeek

Cellular Automata

gol al ca grimoire

A cellular automata is a discrete mathematical model whereby a grid of cells is envisaged, where the next state of each cell is determined by a set of rules which use the current state of the cell and its neighbors as input.

Each of the bolded words above can be defined in particular ways to create different cellular automata, with wildly different behaviour and consequences. A particularly famous and interesting CA is known as Conway's Game of Life.

Grid

The grid is traditionally thought of as a two dimensional grid of squares.

But the grid can be composed of any sort of tiling system (hexagonal! triangular! semi-regular! aperiodic! irregular!) in any number of dimensions (1 dimension, 2 dimensions, 3 dimensions, more dimensions... or fractional dimensions). Hence the 'grid' (or lattice) may be a honeycomb (a mathematical term of art, used to refer to a regular tiling in more than 2 dimensions) or any number of other systems.

When working through examples, it helps to imagine it first as a two dimensional grid of squares. And then consider other possibilities.

State

The state of each cells is typically thought of as the binary value of "On" or "Off". While two-state systems are the most commonly studied, three state, four state, N-state, floating-point number states (see: smooth life), complex number states, and complex object states (where a cell is a multi-dimensional object) are all valid cellular automata.

If the CA is a simulation of a real world system, the "state" could refer to anything at all. Is this tree on fire? burnt out? Is this patient infected? immune? healthy but not immune? immuno-compromised? Does this space ship contain alien dna? nuclear material? Does this bank account contain blood-money?

Neighborhood

In a two dimensional grid, the neighborhood may be the cells which are horizontally or vertically adjacent to the current cell. (This is called the 'Moore Neighborhood').

neighborhood_moore.png
The Moore Neighborhood

Or they may include the cells which are diagonally adjacent to the current cell. (Adding these cells to the neighborhood creates a 'Von Neumann Neighborhood').

neighborhood_von_neumann.png
The Von Neumann Neighborhood

These concepts can also be applied to 3 dimensional, or high-dimensioned honeycombs. More distant cells may be considered, and their effect on the rules may be weighted according to their distance (or a function based on their distance).

The Set of Rules

The set of rules, in any Cellular Automata, generally define a function which determines the "next state" of the cell based on the "current state" of the cell and the current state of its "neighborhood".

In a binary CA, the effect of the rules can be broken down into three categories:

  1. When does a live cell remain alive? (Survival)
  2. When does a dead cell become alive? (Generate)

These are logically complete, and from them you can readily deduce the answer to these similar-sounding questions:

  1. When does a live cell die? (death)
  2. When does a dead cell remain dead?

How to make Cellular Automata more interesting

The website Simulating the world (in emoji) is like a case study in making Cellular Automata interesting. Here are some basic rules:

  1. Don't mention Cellular Automata!
  2. Use real world examples
  3. Use color
  4. Allow simple interactions (start, stop, change cell state)
  5. Allow complex interactions (let people change the parameters of the rules)
  6. Allow really complex interactions (let people add/remove parameterized rules)

See Also

 

Game of Life implementation via nomatteus.