Skip to content

Cellular Automata

A cellular automaton is a model of a system of "cell" objects with the following characteristics:

  1. The cells live on a grid.
  2. Each cell has a state.
  3. Each cell has a neighborhood, which affects the cell's state.

Elementary Cellular Automata

This is a 1-dimensional cellular automaton where the grid is a simple array, the state is either 1 or 0, and the neighborhood is the cell itself plus the cells to its left and right.

  • Three neighbors, each with two states, means we can represent the neighborhood state in binary from 0b000 to 0b111. There are 8 possibilities in total.
  • To find the new state for a cell based on its neighborhood's state, we need to map each neighborhood state to a new state. We can do this with a set of 8 bits, like 0b11111111. Since 8 bits can represent numbers from 0 to 255, the rulesets for elementary cellular automata are usually represented by a number.

How to deal with edges?

Usually three ways:

  1. Edges remain constant. In my implementation, everything outside the bounds is constant.
  2. Edges wrap around. This effectively simulates an infinite grid.
  3. Edges have different neighborhoods and rules.

Classification

  1. Class 1: Uniformity. Every cell becomes black. Rule: 222
  2. Class 2: Repetition. Cells oscillate in regular patterns. Rule: 190
  3. Class 3: Random. Chaotic and random patterns. (Can be used for random number generation!). Rule: 30
  4. Class 4: Complexity. A mixture of class 2 and 3. Rules: 110

Game of Life

Rules

  1. Death
    • Overpopulation: A living cell with four or more live neighbors dies.
    • Loneliness: A living cell with one or fewer live neighbors dies.
  2. Birth: A dead cell with exactly three live neighbors becomes a live cell.
  3. Stasis:
    • Staying alive: A living cell with two or three live neighbors stays alive.
    • Staying dead: A dead cell with any number of neighbors other than three stays dead.

Variations

  1. Non-rectangular grids. Hexagonal grids, for example.
  2. Probabilistic. What if both death and birth only occur with a certain probability?
  3. Continuous. What if a cell's state is no longer binary, but a floating-point number?
  4. Image Processing. Some image processing algorithms, like blurring or simulating ink dispersion and water ripples, can be achieved with CA rules.
  5. Historical. What if a cell's behavior is affected by its duration of life? This relates to a "complex adaptive system".
  6. Moving cells. What if cells could move?
  7. Nesting. A complex system nested in another complex system? Sounds fun. Countries of cities of neighborhoods of families of individuals.

References