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

# Cellular Automata - Game of life and other variants

## Contents

## Cellular Automata theory

### 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!