Cellular Automata at Dart
The implementation of the classic cellular automaton - the Conuevian "Life" - is the same task for a novice programmer as it is for a radio technician to solder a simple radio receiver. For those who do not know what “Life” is, read this article: Wikipedia: Life (game) .
Let me remind you the rules: the action takes place on the cell field. Each cell has 8 neighbors - cells adjacent to it by sides or corners. At the beginning of the game, some cells are filled, forming the initial organism, the rest are empty. Evolution occurs as follows: in the next generation, all filled cells with less than 2 or more than 3 neighbors are cleaned and empty cells with exactly 3 neighbors are filled.
After playing with interesting configurations, it gets a little boring. In fact, for 40 years, everything that can be described has been chewed on hundreds of pages of various articles and books. Finding something new and interesting is difficult. Then there is a desire to change the rules - what if new organisms behave in a completely different way?
Here you can immediately see the demo.
For starters, you can change the number of cells at which old die and new ones appear. Only 2 8 options (does a cell appear at N = 1..8 neighbors?) For the birth of cells and 2 9 for death, total we have 2 17 , a good amount. However, most of these configurations are not of interest (they quickly die out or spread indefinitely). John Conway himself wrote that he experimented with the rules, choosing the values so that the evolution was interesting: poorly predictable, relatively long, leaving behind various isolated configurations, and also so that there were no simple unlimitedly growing configurations. And in the end I came to the only one that now has the greatest popularity.
Now let's try to generalize the rules. We have a cell that can be filled or empty, as well as a group of cells - neighbors. Total 2 groups - from one cell and from 8 cells.
We need a list of pairs of increments of coordinates that determine the position of the cells of the group relative to the processed one. For the first group (central cell) this will be the only pair (+0, +0). For the second (neighboring cells) - eight pairs (-1, -1), (-1, +0), ..., (+1, +0), (+1, +1).
To set the rules, we use a two-dimensional array of Boolean type. The dimension is determined by the number of possible states of the groups: for the first - two (the cell in the center is empty or filled), for the second - nine (from 0 neighbors to the maximum number - 8).
The array element index determines the number of filled cells in each group, and the element value determines the state of the cell after processing: empty (false) or filled (true). Thus, in order to find out what to do with a filled cell with 4 neighbors, we need to turn to the element with the index (1, 4). If the value is false, we clear the cell; if true, we leave it unchanged. And the contents of the array will be like this: elements with indices (0, 3), (1, 2) and (1, 3) are true, the rest are false.
To summarize the rules for N groups: the coordinate array will contain N lists of pairs of integer values, and the set of rules will be represented by an N-dimensional array, the nth dimension of which will be 1 + the number of lists of increment pairs for the nth group.
With this structure of rules, the number of options is limited only by imagination, although there is still the possibility of expanding the rules. Now about the nuances of implementation.
There is no array implementation with a programmable number of dimensions in all languages I know, so you have to write your own. We do this through a one-dimensional array as follows: let's create an n-dimensional array e [Q 1 , Q 2 , ..., Q n ] with a range of indices [0 ... Q n - 1] for the n-th dimension. Create a one-dimensional array e 'with dimension Q 1 * Q 2 * ... * Q n and associate with each element e [i 1 , i 2 , ..., i n] element e '[i 1 * k 1 + i 2 * k 2 + ... + i n * k n ], where k m = 1 * Q 1 * Q 2 * ... * Q m - 1 . That is, k 1 = 1, k 2 = Q 1 , k 3 = Q 1 * Q 2 , etc. This is a one-to-one correspondence, in other words, different elements of the array e will correspond to different elements of the array e '.
For speed and simplicity, I will implement a limited looped field. The loop algorithm for the integer X coordinate in the range [0 ... K - 1] is as follows: if, when the coordinate changes, it leaves this range, then we will increase or decrease it by K units (depending on whether it is on the left or right of our range) until the coordinate returns to the set limits. Then, when the coordinate “leaves” the right border of the range, it will “enter” through the left border and vice versa.
The algorithm is implemented by the formula X = X - floor (X / K) * K, but if K is a power of two, then it is better to use the faster and simpler formula X = X & K.
The field, therefore, will be a two-dimensional array of N x N cells, which can be represented as one-dimensional using the familiar correspondence e (X, Y) => e '(X + Y * N).
Now a little about optimization:
You should not redraw the entire field at each step of evolution. Of course, in the beginning you will have to draw all the cells of the initial configuration, but then for each generation it is enough to redraw only the changed cells.
Instead of processing all filled cells and neighboring unfilled cells with checking the number of neighbors for each cell, it’s better to process only the change in the cell’s occupancy, storing the number of its neighbors in each cell: when the cell is full, it “scatters” units over the cells of which it is a neighbor , increasing the value of the number of neighbors for these cells. And vice versa, when the cell is purified, it “takes” these units.
Since we have several groups, it turns out that for each cell we must keep a list of the number of neighbors for each group. But it will be faster to use instead of this list the corresponding integer according to the correspondence principle similar to address translation during the transition from a multidimensional array to a one-dimensional one, which we examined earlier: [K 1 , K2 , ..., K n ] => [K 1 + Q 1 * K 2 + Q 1 * Q 2 * K 3 + ... + Q 1 * ... * Q n-1 * K n ].
Thus, the generation cycle will look like this:
I wrote the program in the Google Dart language, you can see it here . You can run the program compiled in Javascript here .
Now about the interesting sets of rules that I managed to find:
This version of the rules is characterized by an evolution similar to quicksand. A randomly filled field stabilizes after several hundred generations. In this case, many stable configurations are formed, such as blocks and diagonal stripes, and the simplest pulsating configurations with a period of 2 generations - a diagonal row of 2 cells and a vertical of 3 cells. A pulsating cross with a period of 3 generations is also often found. There are also “shockers" - stable configurations with several pulsating cells, as well as "butterflies" - pulsating configurations with a long period, similar to insect flapping wings. I have not seen moving configurations.
The rules are similar to the previous ones, only instead of birth with 1 neighbor diagonally and 2 vertically / horizontally, the birth rule is used with 2 neighbors diagonally and 1 vertically / horizontally.
Also quicksand, but they stabilize faster - after 100-200 generations, and other configurations arise. There are almost no stable configurations (mainly 2x2 blocks), but pulsating ones - a whole zoo. You can note the popular configuration “bracket”, squares with flashing edges, a cross from the previous rules, “candy”, pulsating garbage and a rather complex and large “bat” with a large period of pulsation. Sometimes a configuration produces vertical / horizontal fighter jets.
The random configuration under these rules quickly assumes a diamond-like shape. She is extremely not inclined to divide into several pulsating areas and likes to pick up the left stable and pulsating blocks. Extremely reluctantly grows and shrinks, but with small sizes it often disappears, leaving behind a small stable or pulsating configuration.
These rules lead to the fact that configurations tend to rectangular-diagonal shapes, similar to the tracks of the printed circuit board. After about a thousand generations, pulsating rectangular configurations usually remain on the field.
The configuration quickly takes the form of “boiling water with steam” in triangular “glasses”. It usually “calms down” after several thousand generations, after which there remains a system of these “glasses” with pulsating “water” in them.
The cell array, which exists initially, begins to grow rapidly left and right, which is ensured by the rapid formation of “locomotives,” that is, moving configurations that leave a pulsating trail. Since the field is looped, the “armada of ships” collide, as a result of which its parts can either be destroyed or transformed into ships flying in the opposite direction, and also leave pulsating configurations behind them. Of the notable configurations, the minimum moving unit is a scout (reminiscent of the Shofixti ship from Star Control), there are also slightly larger “sailboats” that generate “scouts” a “bomber” that multiplies exponentially “disk” as well as stable “slash” configurations , “Applause” and “jumping arc”,
This configuration tends to recede and attack in jerks, slowly expanding at the end and leaving diagonal “wire” pieces bent at right angles. Also often there is a “vital” stone and a beehive, a rotating “colon”. Among the pulsating configurations, one can distinguish “four points”, a “crumpler” of two stones, and a “smile” with a long pulsation period. Often, as a result of the development of a small separate configuration, a stable “rhombus” is formed.
Here, instead of “wire” pieces, stable heaps of “stones” and “curls” of various complexity are formed. There is one common diagonally moving “spot” configuration.
With these rules, even the smallest configurations often turn into intricate “steam locomotives”. We can distinguish a vertical “snake” with the possible generation of an array of bicellular “dies”, a growing striped triangle, a growing diagonal row, generating pulsating garbage. Also, some configurations can transmit unicellular “signals” along the resulting diagonal row, which can be suppressed by other configurations. There is a simple vertically moving configuration - a “trolley”, which can leave behind a vanishing “smoke”, as well as a pulsating “spider”, which is often a stabilizer of the diagonal row.
In the program you will also find codes of rules, each of which has an interesting feature.
Let me remind you the rules: the action takes place on the cell field. Each cell has 8 neighbors - cells adjacent to it by sides or corners. At the beginning of the game, some cells are filled, forming the initial organism, the rest are empty. Evolution occurs as follows: in the next generation, all filled cells with less than 2 or more than 3 neighbors are cleaned and empty cells with exactly 3 neighbors are filled.
After playing with interesting configurations, it gets a little boring. In fact, for 40 years, everything that can be described has been chewed on hundreds of pages of various articles and books. Finding something new and interesting is difficult. Then there is a desire to change the rules - what if new organisms behave in a completely different way?
Here you can immediately see the demo.
For starters, you can change the number of cells at which old die and new ones appear. Only 2 8 options (does a cell appear at N = 1..8 neighbors?) For the birth of cells and 2 9 for death, total we have 2 17 , a good amount. However, most of these configurations are not of interest (they quickly die out or spread indefinitely). John Conway himself wrote that he experimented with the rules, choosing the values so that the evolution was interesting: poorly predictable, relatively long, leaving behind various isolated configurations, and also so that there were no simple unlimitedly growing configurations. And in the end I came to the only one that now has the greatest popularity.
Now let's try to generalize the rules. We have a cell that can be filled or empty, as well as a group of cells - neighbors. Total 2 groups - from one cell and from 8 cells.
We need a list of pairs of increments of coordinates that determine the position of the cells of the group relative to the processed one. For the first group (central cell) this will be the only pair (+0, +0). For the second (neighboring cells) - eight pairs (-1, -1), (-1, +0), ..., (+1, +0), (+1, +1).
To set the rules, we use a two-dimensional array of Boolean type. The dimension is determined by the number of possible states of the groups: for the first - two (the cell in the center is empty or filled), for the second - nine (from 0 neighbors to the maximum number - 8).
The array element index determines the number of filled cells in each group, and the element value determines the state of the cell after processing: empty (false) or filled (true). Thus, in order to find out what to do with a filled cell with 4 neighbors, we need to turn to the element with the index (1, 4). If the value is false, we clear the cell; if true, we leave it unchanged. And the contents of the array will be like this: elements with indices (0, 3), (1, 2) and (1, 3) are true, the rest are false.
To summarize the rules for N groups: the coordinate array will contain N lists of pairs of integer values, and the set of rules will be represented by an N-dimensional array, the nth dimension of which will be 1 + the number of lists of increment pairs for the nth group.
With this structure of rules, the number of options is limited only by imagination, although there is still the possibility of expanding the rules. Now about the nuances of implementation.
There is no array implementation with a programmable number of dimensions in all languages I know, so you have to write your own. We do this through a one-dimensional array as follows: let's create an n-dimensional array e [Q 1 , Q 2 , ..., Q n ] with a range of indices [0 ... Q n - 1] for the n-th dimension. Create a one-dimensional array e 'with dimension Q 1 * Q 2 * ... * Q n and associate with each element e [i 1 , i 2 , ..., i n] element e '[i 1 * k 1 + i 2 * k 2 + ... + i n * k n ], where k m = 1 * Q 1 * Q 2 * ... * Q m - 1 . That is, k 1 = 1, k 2 = Q 1 , k 3 = Q 1 * Q 2 , etc. This is a one-to-one correspondence, in other words, different elements of the array e will correspond to different elements of the array e '.
For speed and simplicity, I will implement a limited looped field. The loop algorithm for the integer X coordinate in the range [0 ... K - 1] is as follows: if, when the coordinate changes, it leaves this range, then we will increase or decrease it by K units (depending on whether it is on the left or right of our range) until the coordinate returns to the set limits. Then, when the coordinate “leaves” the right border of the range, it will “enter” through the left border and vice versa.
The algorithm is implemented by the formula X = X - floor (X / K) * K, but if K is a power of two, then it is better to use the faster and simpler formula X = X & K.
The field, therefore, will be a two-dimensional array of N x N cells, which can be represented as one-dimensional using the familiar correspondence e (X, Y) => e '(X + Y * N).
Now a little about optimization:
You should not redraw the entire field at each step of evolution. Of course, in the beginning you will have to draw all the cells of the initial configuration, but then for each generation it is enough to redraw only the changed cells.
Instead of processing all filled cells and neighboring unfilled cells with checking the number of neighbors for each cell, it’s better to process only the change in the cell’s occupancy, storing the number of its neighbors in each cell: when the cell is full, it “scatters” units over the cells of which it is a neighbor , increasing the value of the number of neighbors for these cells. And vice versa, when the cell is purified, it “takes” these units.
Since we have several groups, it turns out that for each cell we must keep a list of the number of neighbors for each group. But it will be faster to use instead of this list the corresponding integer according to the correspondence principle similar to address translation during the transition from a multidimensional array to a one-dimensional one, which we examined earlier: [K 1 , K2 , ..., K n ] => [K 1 + Q 1 * K 2 + Q 1 * Q 2 * K 3 + ... + Q 1 * ... * Q n-1 * K n ].
Thus, the generation cycle will look like this:
- Before the first cycle, all cells of the initial configuration are processed. They and those cells whose neighbors they are are entered into the list of processed cells.
- All cells from cells are checked for change (that is, if their state and the state from the code of rules corresponding to the number of their neighbors at the moment are not equal). If, according to the rules, the state should change, this cell is entered in the list of changed togglingCells cells.
- The list of cells is cleared.
- All cells from togglingCells change their state by “scattering” or “taking” their neighborhood from the cells of which they are neighbors. All cells with a changed number of neighbors are entered into cells.
- TogglingCells cells are drawn.
- togglingCells is cleared.
I wrote the program in the Google Dart language, you can see it here . You can run the program compiled in Javascript here .
Now about the interesting sets of rules that I managed to find:
Horizontal-vertical-diagonal breakdown
Sandy GV (SandyLifeHV)
- Survival
- 1 or 2 diagonally + 1 or 2 vertically / horizontally
- Birth
- 2 diagonally + 0 vertically / horizontally
- 0 diagonally + 2 vertically / horizontally
- 1 diagonally + 2 vertically / horizontally
This version of the rules is characterized by an evolution similar to quicksand. A randomly filled field stabilizes after several hundred generations. In this case, many stable configurations are formed, such as blocks and diagonal stripes, and the simplest pulsating configurations with a period of 2 generations - a diagonal row of 2 cells and a vertical of 3 cells. A pulsating cross with a period of 3 generations is also often found. There are also “shockers" - stable configurations with several pulsating cells, as well as "butterflies" - pulsating configurations with a long period, similar to insect flapping wings. I have not seen moving configurations.
SandyD (SandyLifeD)
The rules are similar to the previous ones, only instead of birth with 1 neighbor diagonally and 2 vertically / horizontally, the birth rule is used with 2 neighbors diagonally and 1 vertically / horizontally.
Also quicksand, but they stabilize faster - after 100-200 generations, and other configurations arise. There are almost no stable configurations (mainly 2x2 blocks), but pulsating ones - a whole zoo. You can note the popular configuration “bracket”, squares with flashing edges, a cross from the previous rules, “candy”, pulsating garbage and a rather complex and large “bat” with a large period of pulsation. Sometimes a configuration produces vertical / horizontal fighter jets.
Amoeba (AmoebaLife)
- Survival
- 2 diagonally + 0-2 vertically / horizontally
- 0-2 diagonally + 2 vertically / horizontally
- Birth
- 2 diagonally + 0-2 vertically / horizontally
The random configuration under these rules quickly assumes a diamond-like shape. She is extremely not inclined to divide into several pulsating areas and likes to pick up the left stable and pulsating blocks. Extremely reluctantly grows and shrinks, but with small sizes it often disappears, leaving behind a small stable or pulsating configuration.
Electronics (ElectronicLife)
- Survival
- 2-3 diagonally + 2 vertically / horizontally
- 0-1 diagonally + 2-3 vertically / horizontally
- Birth
- 1-2 diagonally + 1-2 vertically / horizontally
These rules lead to the fact that configurations tend to rectangular-diagonal shapes, similar to the tracks of the printed circuit board. After about a thousand generations, pulsating rectangular configurations usually remain on the field.
Puff breakdown
Liquid (LiquidLife)
- Cell emergence / survival
- 0-1 upper + 1-3 central + 2-3 lower
- 1-2 upper + 2-3 central + 0-1 lower
- 2-3 upper + 1-3 central + 1-2 lower
The configuration quickly takes the form of “boiling water with steam” in triangular “glasses”. It usually “calms down” after several thousand generations, after which there remains a system of these “glasses” with pulsating “water” in them.
Armada (ArmadaLife)
- Cell emergence / survival
- 0-1 upper + 1-2 central + 2-3 lower
- 1-3 upper + 1-2 central + 1-3 lower
- 2-3 upper + 1-2 central + 0-1 lower
The cell array, which exists initially, begins to grow rapidly left and right, which is ensured by the rapid formation of “locomotives,” that is, moving configurations that leave a pulsating trail. Since the field is looped, the “armada of ships” collide, as a result of which its parts can either be destroyed or transformed into ships flying in the opposite direction, and also leave pulsating configurations behind them. Of the notable configurations, the minimum moving unit is a scout (reminiscent of the Shofixti ship from Star Control), there are also slightly larger “sailboats” that generate “scouts” a “bomber” that multiplies exponentially “disk” as well as stable “slash” configurations , “Applause” and “jumping arc”,
Side breakdown
Wire (WireLife)
- Survival
- 1-3 horizontal + 1-2 vertical
- Birth
- 2 horizontal + 2-3 vertical
This configuration tends to recede and attack in jerks, slowly expanding at the end and leaving diagonal “wire” pieces bent at right angles. Also often there is a “vital” stone and a beehive, a rotating “colon”. Among the pulsating configurations, one can distinguish “four points”, a “crumpler” of two stones, and a “smile” with a long pulsation period. Often, as a result of the development of a small separate configuration, a stable “rhombus” is formed.
Curls (TwirlLife)
- Survival
- 1-3 horizontal + 1-3 vertical
- Birth
- 2 horizontal + 2 vertical
Here, instead of “wire” pieces, stable heaps of “stones” and “curls” of various complexity are formed. There is one common diagonally moving “spot” configuration.
Bracket Breakdown
Snakes
- Survival
- 2-3 cells in one of the brackets, 0 in the other
- Birth
- 1-2 cells in each of the staples
With these rules, even the smallest configurations often turn into intricate “steam locomotives”. We can distinguish a vertical “snake” with the possible generation of an array of bicellular “dies”, a growing striped triangle, a growing diagonal row, generating pulsating garbage. Also, some configurations can transmit unicellular “signals” along the resulting diagonal row, which can be suppressed by other configurations. There is a simple vertically moving configuration - a “trolley”, which can leave behind a vanishing “smoke”, as well as a pulsating “spider”, which is often a stabilizer of the diagonal row.
In the program you will also find codes of rules, each of which has an interesting feature.