A bit about cellular automata

On a habr already many - many - many times wrote about the game "Life". More recently, there was an amazing article Life on the Lobachevsky plane . But the game "Life" is a special case of the so-called. cellular automata . There are many other cellular automata that are completely different from the Life game, but nonetheless very interesting. I’d like to talk about some of them here.

To begin with, we consider a series of cells in which, in addition to one, there are zeros:

... 0 1 0 0 0 0 0 0 ...

Consider the following rule, replace the number in the cell with the sum of this number and the neighbor on the left. We get the following series of states:

... 0 1 0 0 0 0 0 0 ...
... 0 1 1 0 0 0 0 0 ...
... 0 1 2 1 0 0 0 0 ...
... 0 1 3 3 1 0 0 0 ...
... 0 1 4 6 4 1 0 0 ...
... 0 1 5 10 10 5 1 0 ...
... 0 1 6 15 20 15 6 1 ...

It is not difficult to see that this is Pascal's triangle. And now, instead of the usual addition, we will use addition modulo two. It is known (and even recently described in the habrastatia the Sierpinski Triangle and the Pascal Triangle ) that a discrete analogue of the Sierpinski triangle is obtained:

... 0 1 0 0 0 0 0 0 ...
... 0 1 1 0 0 0 0 0 ...
... 0 1 0 1 0 0 0 0 ...
... 0 1 1 1 1 0 0 0 ...
... 0 1 0 0 0 1 0 0 ...
... 0 1 1 0 0 1 1 0 ...
... 0 1 0 1 0 1 0 1 ...

Interesting? Read on!


It makes no sense to give an exact definition of a cellular automaton, but it is useful to note the following properties of cellular automata: parallelism , locality , and homogeneity . Parallelism means that updates of all cells occur independently of each other. Locality means that the new state of the cell depends only on the old state of the cell and its surroundings. And finally, uniformity means that all cells are updated according to the same rules.

In order not to mess with infinite grids, we consider cellular automata on a finite quadrangular grid, and so that there are no problems with boundaries, we wrap the grid in a torus. Two neighborhoods of the cell are named for:Moore 's neighborhood - all eight surrounding cells are neighbors, and von Neumann 's neighborhood - only the nearest cells on the left, right, top and bottom are neighbors. To avoid ambiguities, in addition to the verbal description of the rule for transforming the state of the cell, the implementation of the function will also be given

int transformCell(
    int northWestCell, int northCell, int northEastCell,
    int westCell, int centerCell, int eastCell,
    int southWestCell, int southCell, int southEastCell);

Limited and unlimited growth

So, let the cells can be in two states: 0 - dead, and 1 - living.
Consider the following rule: a cell becomes alive if at least one of its neighbors is alive; once a cell has become alive, it always remains alive. In the case of the Moore neighborhood, the body of the function transformCell()will be as follows:

int sum = northWestCell + northCell + northEastCell + 
    westCell + eastCell + 
    southWestCell + southCell + southEastCell;
if (sum > 0) {
    return 1;
} else {
    return centerCell;
}

If the field is initially filled with zeros, then living cells will not appear, but if one of the cells is made alive, then a growing square of living cells will arise from this “germ”, which will eventually fill the field. At the same time, the region of living cells increases at the highest possible speed - the speed of light.


We slightly change the rule above: instead of the condition “at least one of the neighbors is alive”, we consider the condition “exactly one of the neighbors is alive”.

int sum = northWestCell + northCell + northEastCell + 
    westCell + eastCell + 
    southWestCell + southCell + southEastCell;
if (sum == 1) {
    return 1;
} else {
    return centerCell;
}

The structure obtained from one cell will be, firstly, much rarefied, and, secondly, it will have an explicit fractal character.


Instead of the Moore neighborhood, we can consider the von Neumann neighborhood:

int sum = northCell + westCell + eastCell + southCell;
if (sum == 1) {
    return 1;
} else {
    return centerCell;
}

Cyclic cellular automata

Cyclic cellular automata were invented by David Griffith. A cell can be in n states, which we will number by numbers 0, 1, ..., n - 1. We say that state m is next to state k if m + 1 = k (mod n ). A cell from state m passes to the next state k only if one of the neighboring cells has state k . For example, in the case of a von Neumann neighborhood, the transformation is written as follows:

int nextState = (centerCell + 1) % statesNumber;
if (northCell == nextState ||
        westCell == nextState ||
        eastCell == nextState ||
        southCell == nextState) {
    return nextState;
} else {
    return centerCell;
}

Moreover, if you start with a randomly filled field, three different stages can be observed. The first stage is a random field. Then colored areas begin to appear that will absorb areas filled randomly. These blocks will "wave" to change their color. Then there are spirals, which are also called demons . And finally, in the third stage, the field will be consumed by demons.





You can also consider a one-dimensional cyclic cellular automaton:

int transformCell(int leftCell, int centerCell, int rightCell) {
    int nextState = (centerCell + 1) % statesNumber;
    if (nextState == leftCell || nextState == rightCell) {
        return nextState;
    } else {
        return centerCell;
    }
}

If you are interested in learning more details, I recommend starting with the Wikipedia Cyclic cellular automaton .

Hashman

Let the cell again be in the states 0, 1, ..., n - 1.
Consider a rule consisting of three parts.

Health . If a cell is in state 0 (i.e., healthy), then it becomes ill if several of its neighbors are sick (i.e., are in a non-zero state).

Recovery . If the cell is in state n - 1, then it self-heals and goes into state 0.

Disease . Otherwise, the state of the cell is calculated as the average of the states of neighboring cells plus some constant. (If the resulting number is greater than n - 1, then the new state will be n - 1.)

int sum = northWestCell + northCell + northEastCell +
        westCell + eastCell +
        southWestCell + southCell + southEastCell;
if (centerCell == 0) {
    if (sum < 5) {
        return 0;
    } else if (sum < 100) {
        return 2;
    } else {
        return 3;
    }
} else if (centerCell == statesNumber - 1) {
    return 0;
} else {
    return Math.min(sum / 8 + 5, statesNumber - 1);
}

It is noted that the wave-like processes obtained in this way resemble the reaction of Belousov-Zhabotinsky .

Surface of venus

This rule (as well as the previous one) I found in Cellab Manual . Each cell is in the state 0, 1, 2 or 4. The rule has the form:

if (centerCell == 0) {
    return 2 * ((northWestCell % 2) ^ (northEastCell % 2)) + northCell % 2;
} else if (centerCell == 1) {
    return 2 * ((northWestCell % 2) ^ (southWestCell % 2)) + westCell % 2;
} else if (centerCell == 2) {
    return 2 * ((southWestCell % 2) ^ (southEastCell % 2)) + southCell % 2;
} else {
    return 2 * ((southEastCell % 2) ^ (northEastCell % 2)) + eastCell % 2;
}

If you start with a randomly filled field, then two “flows” crashing into each other are formed: vertical and horizontal. After some time, one of the “flows” begins to prevail. And in the end, only one remains.





This is a small part of cellular automata that I wanted to talk about, but I have to stop so that the article does not become too large. For those interested, I’ll give a few references:

(1) T. Toffoli, N. Margolus, Machine of cellular automata , M., Mir, 1991.

(2) M. Schroeder, Fractals, chaos, power laws. Miniatures from the Endless Paradise , Izhevsk, RHD, 2001, pp. 469--490.

(3) R. Rucker, J. Walker Cellab Manual .