The Allegro Wiki is migrating to github at https://github.com/liballeg/allegro_wiki/wiki

Cellular Automata - Game of life and other variants

From Allegro Wiki
Jump to: navigation, search

Cellular Automata theory

An example using the "Day&Night" rules

The Basics

Cellular Automata is based on a strict set of rules that are applied to a set of cells (these can be 1d, 2d or even 3d). Based on the rules and conditions, their birth or survival is determined. Totalistic cellular automata means that the only basis of determining life or death of cells is the number of neighbours they have. One-bit cellular automata means that all cells only have two states: alive or dead. The type of cellular automata I'm discussing is both totalistic and one-bit.

Rules

As said before, cellular automata is based on a set of rules. The rules determine two things:

  • 1. How many neighbours an empty, or "dead" cell needs to have to be born.
  • 2. How many neighbours a live cell needs to survive.

Naming conventions

The naming of totalistic one-bit cellular automata rules is relatively straightforward. The format is
(B)[neighbours needed to give birth to new cell]/(S)[neighbours needed for a live cell to survive]
An example of the most well-known rule, "Game of life": B3/S23. This means that any empty cell with three neighbours will give birth to a new cell, and all live cells need two or three neighbours to survive. Notice that if the cell has over three neighbours, it will die (out of overcrowding).

Variations

There are many other rules than Game of life. Here are a few:

  • Anneal B4678/S35678
  • Day&Night B3678/S34678
  • Diamoeba B35678/S5678
  • High life B36/S23

Cellular automata in practice

Data structure

The most often used structure to represent cells is a 2-dimensional array. This is usually aligned in a square grid, so that each cell has 8 neighbours. Each cell has to have it's state -- 1 or 0 -- stored. Also, to avoid problems, it's a good idea to store the number of neighbours too. An unoptimized cell struct might look something like this:

#define ARRAYSIZE 64
typedef struct cell { unsigned short alive; // 1 or 0, a single bit could be used unsigned short n; // number of neighbours, 0..8 in a square grid }; cell data[ARRAYSIZE][ARRAYSIZE];

Because all cells are calculated based on the data of the previous round, you shouldn't calculate new values for the cell array straight away. Instead, you should mark them to be killed/given birth to. After you've iterated through all the cells, you can check the marked cells and act based on their info. The simplest way to get away with it is to use one or two extra arrays. I chose two because it's the simplest possible way to display the idea.

bool birth[ARRAYSIZE][ARRAYSIZE]; //cells marked to be killed here
bool death[ARRAYSIZE][ARRAYSIZE]; //cells marked to be given birth to here

Putting it to work

The order of actions when using cellular automata is the following:


for each pass
  {
  Fill the cell array with random 1's and 0's  //Only on first pass
  Reset birth and death arrays to false
  for each cell
     {
     Calculate number of neighbours
     If the cell is empty (dead) and it has the right amount of neighbours as defined in the rule used, mark the cell in the birth array.
     If the cell is alive and doesn't have the right amount of neighbours to survive, mark the cell in the death array.
     }
  Apply birth and death arrays to the cell array
  }


The random data will become less and less random with each pass, and many rules either expand or collapse if given enough passes.

Conclusion

I hope this explanation will allow you to employ this powerful tool. It could be very handy at many things, but above all I believe it's very useful for random map creation (see the image above). Have fun!