Cellular Automatics on Dart
The implementation of the classic cellular automaton - Conway's “Life” - is the same task for a novice programmer as for radio engineering - to solder a simple radio receiver. For those who do not know what Life is, read this article: Wikipedia: Life (game) .
Let me remind the rules: the action takes place in the cellular field. Each cell has 8 neighbors - cells adjacent to it with sides or corners. At the beginning of the game, some cells are filled, forming the initial organism, the rest are empty. Evolution happens like this: in the next generation, all filled cells that have less than 2 or more than 3 neighbors are cleaned and empty ones that have exactly 3 neighbors are filled.
After playing with interesting configurations, it gets a bit boring. In fact, for 40 years, everything that can be described is 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 - and suddenly new organisms will behave quite differently?
')
Here you can see the demo right away.
For a start, you can change the number of cells at which old ones 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, in total we have 2 17 , a good amount. However, the majority of such configurations are of no interest (quickly die out or spread indefinitely). John Conway himself wrote that he experimented with the rules, selecting values so that evolution was interesting: poorly predictable, relatively long, leaving behind various isolated configurations, and also not simple unlimitedly growing configurations. And in the end came to the only one that is now most popular.
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, which determines the position of the cells of the group relative to the processed one. For the first group (central cell) it 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 count - 8).
The index of the array element determines the number of filled cells in each of the groups, and the element value determines the state of the cell after processing: empty (false) or filled (true). Thus, to find out what to do with a filled cell with 4 neighbors, we need to refer to the element with the index (1, 4). If the value is false, we clear the cell, if true, 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.
Summarizing the rules for N groups: the coordinate array will contain N lists of pairs of integer values, and the rulebook will be represented by an N-dimensional array, the n-th dimension of which will be equal to 1 + the number of lists of pairs of increments for the n-th group.
With such a structure of rules, the number of options is limited only by fantasy, although the possibility of expanding the rules is still there. Now about the nuances of implementation.
The implementation of the array with the number of measurements programmatically specified in all the languages I know is missing, so I have to write my own. We do this through a one-dimensional array as follows: suppose we need to 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 assign each element e [i 1 , i 2 , ..., i n ] to each 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 array e will correspond to different elements of array e '.
For speed and simplicity, I will implement a limited looped field. The algorithm for looping the whole X coordinate in the range [0 ... K - 1] is as follows: if, when changing the coordinate, it is out of this range, then we will increase or decrease it by K units (depending on whether it is left or right of our range) until the coordinate returns to the specified limits. Then, when the coordinates “exit” beyond the right edge 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 a faster and simpler formula X = X & K.
The field will thus be a two-dimensional array of N x N cells that can be represented as one-dimensional with the help of the already familiar correspondence e (X, Y) => e '(X + Y * N).
Now a little about optimization:
Do 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 the filled cells and neighboring unfilled with checking the number of neighbors for each cell, it is better to process only the change in the cell fill, storing the number of its neighbors in each cell: when the cell is filled, it “scatters” units in the cells whose neighbor it is by increasing the number of neighbors for these cells. Conversely, when cleansing the cell, it “takes” these units.
Since we have several groups, it turns out that for each cell we must store a list of the number of neighbors for each group. But, instead of this list, it will be faster to use the corresponding integer by the correspondence principle, which is similar to the address conversion during the transition from a multidimensional array to a one-dimensional one, which we have considered earlier: 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 language of Google Dart, you can see it here . Run the program compiled into Javascript here .
Now about the interesting sets of rules that I managed to find:
This version of the rules is characterized by the evolution of quicksands. A randomly filled field stabilizes over several hundred generations. At the same time, 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 row of 3 cells. Also often there is a pulsating cross with a period of 3 generations. “Shockers” are also encountered - stable configurations with several pulsating cells, as well as “butterflies” - pulsating configurations with a long period, similar to insects flapping their wings. Moving configurations I have not met.
The rules are similar to the previous ones, but 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 (mostly 2x2 blocks), but the pulsing ones are a whole zoo. The popular “bracket” configuration, squares with flashing edges, a cross from the previous rules, “candy”, pulsating debris and a rather complicated and large “bat” with a long pulse period can be noted. Sometimes, the configuration is launched by fighter jets flying vertically / horizontally.
Random configuration with these rules quickly acquires a rhombus-like shape. She is extremely not inclined to split into several pulsating areas and likes to pick up the stable and pulsating blocks left behind. It is extremely reluctant to grow and shrink, but at small sizes it often disappears, leaving behind small stable or pulsating configurations.
These rules lead to the fact that the configuration of the 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 the system of these “glasses” with pulsating “water” in them remains.
An array of cells that exists initially begins to grow rapidly left and right, which is ensured by the rapid formation of “locomotives”, that is, moving configurations, leaving behind a pulsating wake. Since the field is looped around, the “armada of ships” collide, as a result of which its parts can both be destroyed and transformed into ships flying in the opposite direction, and also leave pulsating configurations behind them. Of noteworthy configurations - the minimum moving unit is a scout (reminiscent of the Shofixti ship from Star Control), there are also some larger “sailboats” that generate “scouts” “bomber”, breeding in a geometric progression “disk”, as well as stable configurations “slash” , “Applause” and “jumping arc”, which in some cases can turn the ships in the opposite direction.
This configuration tends to retreat and advance in jerks, slowly expanding in the end and leaving diagonal “wire” pieces curved at a right angle. Also often remains a “vital” stone and a hive, a rotating “colon”. From the pulsating configurations, one can distinguish “four points”, a “knob” of two stones and a “smile” with a long period of pulsation. Often, as a result of the development of a small separate configuration, a stable “lozenge” is formed.
Here, instead of “wire” pieces, stable heaps of “stones” and “curls” of different complexity are formed. There is one common diagonally moving “spot” configuration.
With such rules, even the smallest configurations often turn into intricate “locomotives”. We can distinguish a vertical “snake” with the possible generation of an array of two-cell “dice”, a growing striped triangle, a growing diagonal row, generating pulsating debris. Also, some configurations can transmit unicellular “signals” along the diagonal row that can be canceled by other configurations. There is a simple vertically moving configuration - the “cart”, which can leave behind a disappearing “smoke”, as well as a pulsating “spider”, which is often the stabilizer of the diagonal row.
In the program you will find more sets of rules, each of which has an interesting feature.
Let me remind the rules: the action takes place in the cellular field. Each cell has 8 neighbors - cells adjacent to it with sides or corners. At the beginning of the game, some cells are filled, forming the initial organism, the rest are empty. Evolution happens like this: in the next generation, all filled cells that have less than 2 or more than 3 neighbors are cleaned and empty ones that have exactly 3 neighbors are filled.
After playing with interesting configurations, it gets a bit boring. In fact, for 40 years, everything that can be described is 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 - and suddenly new organisms will behave quite differently?
')
Here you can see the demo right away.
For a start, you can change the number of cells at which old ones 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, in total we have 2 17 , a good amount. However, the majority of such configurations are of no interest (quickly die out or spread indefinitely). John Conway himself wrote that he experimented with the rules, selecting values so that evolution was interesting: poorly predictable, relatively long, leaving behind various isolated configurations, and also not simple unlimitedly growing configurations. And in the end came to the only one that is now most popular.
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, which determines the position of the cells of the group relative to the processed one. For the first group (central cell) it 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 count - 8).
The index of the array element determines the number of filled cells in each of the groups, and the element value determines the state of the cell after processing: empty (false) or filled (true). Thus, to find out what to do with a filled cell with 4 neighbors, we need to refer to the element with the index (1, 4). If the value is false, we clear the cell, if true, 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.
Summarizing the rules for N groups: the coordinate array will contain N lists of pairs of integer values, and the rulebook will be represented by an N-dimensional array, the n-th dimension of which will be equal to 1 + the number of lists of pairs of increments for the n-th group.
With such a structure of rules, the number of options is limited only by fantasy, although the possibility of expanding the rules is still there. Now about the nuances of implementation.
The implementation of the array with the number of measurements programmatically specified in all the languages I know is missing, so I have to write my own. We do this through a one-dimensional array as follows: suppose we need to 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 assign each element e [i 1 , i 2 , ..., i n ] to each 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 array e will correspond to different elements of array e '.
For speed and simplicity, I will implement a limited looped field. The algorithm for looping the whole X coordinate in the range [0 ... K - 1] is as follows: if, when changing the coordinate, it is out of this range, then we will increase or decrease it by K units (depending on whether it is left or right of our range) until the coordinate returns to the specified limits. Then, when the coordinates “exit” beyond the right edge 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 a faster and simpler formula X = X & K.
The field will thus be a two-dimensional array of N x N cells that can be represented as one-dimensional with the help of the already familiar correspondence e (X, Y) => e '(X + Y * N).
Now a little about optimization:
Do 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 the filled cells and neighboring unfilled with checking the number of neighbors for each cell, it is better to process only the change in the cell fill, storing the number of its neighbors in each cell: when the cell is filled, it “scatters” units in the cells whose neighbor it is by increasing the number of neighbors for these cells. Conversely, when cleansing the cell, it “takes” these units.
Since we have several groups, it turns out that for each cell we must store a list of the number of neighbors for each group. But, instead of this list, it will be faster to use the corresponding integer by the correspondence principle, which is similar to the address conversion during the transition from a multidimensional array to a one-dimensional one, which we have considered earlier: 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. In the list of cells to be processed, they are entered and those cells whose neighbors they are.
- All cells from cells are checked for change (that is, if their state and state from the rulebook, 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 cells togglingCells.
- 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 the changed number of neighbors are entered into the cells.
- The togglingCells are rendered.
- togglingCells cleared.
I wrote the program in the language of Google Dart, you can see it here . Run the program compiled into Javascript here .
Now about the interesting sets of rules that I managed to find:
Horizontal-Vertical-Diagonal Breakdown
SandGV (SandyLifeHV)
- Survival
- 1 or 2 diagonal + 1 or 2 vertical / horizontal
- Birth
- 2 diagonal + 0 vertical / horizontal
- 0 diagonal + 2 vertical / horizontal
- 1 diagonally + 2 vertical / horizontal
This version of the rules is characterized by the evolution of quicksands. A randomly filled field stabilizes over several hundred generations. At the same time, 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 row of 3 cells. Also often there is a pulsating cross with a period of 3 generations. “Shockers” are also encountered - stable configurations with several pulsating cells, as well as “butterflies” - pulsating configurations with a long period, similar to insects flapping their wings. Moving configurations I have not met.
Sandy D (SandyLifeD)
The rules are similar to the previous ones, but 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 (mostly 2x2 blocks), but the pulsing ones are a whole zoo. The popular “bracket” configuration, squares with flashing edges, a cross from the previous rules, “candy”, pulsating debris and a rather complicated and large “bat” with a long pulse period can be noted. Sometimes, the configuration is launched by fighter jets flying vertically / horizontally.
Amoeba (AmoebaLife)
- Survival
- 2 diagonal + 0-2 vertical / horizontal
- 0-2 diagonal + 2 vertical / horizontal
- Birth
- 2 diagonal + 0-2 vertical / horizontal
Random configuration with these rules quickly acquires a rhombus-like shape. She is extremely not inclined to split into several pulsating areas and likes to pick up the stable and pulsating blocks left behind. It is extremely reluctant to grow and shrink, but at small sizes it often disappears, leaving behind small stable or pulsating configurations.
Electronics (ElectronicLife)
- Survival
- 2-3 diagonal + 2 vertical / horizontal
- 0-1 diagonally + 2-3 vertically / horizontally
- Birth
- 1-2 diagonally + 1-2 vertically / horizontally
These rules lead to the fact that the configuration of the 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.
Puffed up breakdown
Liquid (LiquidLife)
- Cell appearance / 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 the system of these “glasses” with pulsating “water” in them remains.
Armada (ArmadaLife)
- Cell appearance / 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
An array of cells that exists initially begins to grow rapidly left and right, which is ensured by the rapid formation of “locomotives”, that is, moving configurations, leaving behind a pulsating wake. Since the field is looped around, the “armada of ships” collide, as a result of which its parts can both be destroyed and transformed into ships flying in the opposite direction, and also leave pulsating configurations behind them. Of noteworthy configurations - the minimum moving unit is a scout (reminiscent of the Shofixti ship from Star Control), there are also some larger “sailboats” that generate “scouts” “bomber”, breeding in a geometric progression “disk”, as well as stable configurations “slash” , “Applause” and “jumping arc”, which in some cases can turn the ships in the opposite direction.
Side breakdown
Wire (WireLife)
- Survival
- 1-3 horizontal + 1-2 vertical
- Birth
- 2 horizontal + 2-3 vertical
This configuration tends to retreat and advance in jerks, slowly expanding in the end and leaving diagonal “wire” pieces curved at a right angle. Also often remains a “vital” stone and a hive, a rotating “colon”. From the pulsating configurations, one can distinguish “four points”, a “knob” of two stones and a “smile” with a long period of pulsation. Often, as a result of the development of a small separate configuration, a stable “lozenge” is formed.
Twirls (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 different complexity are formed. There is one common diagonally moving “spot” configuration.
Staple breakdown
Snakes
- Survival
- 2-3 cells in one of the brackets, 0 in the other
- Birth
- 1-2 cells in each of the brackets
With such rules, even the smallest configurations often turn into intricate “locomotives”. We can distinguish a vertical “snake” with the possible generation of an array of two-cell “dice”, a growing striped triangle, a growing diagonal row, generating pulsating debris. Also, some configurations can transmit unicellular “signals” along the diagonal row that can be canceled by other configurations. There is a simple vertically moving configuration - the “cart”, which can leave behind a disappearing “smoke”, as well as a pulsating “spider”, which is often the stabilizer of the diagonal row.
In the program you will find more sets of rules, each of which has an interesting feature.
Source: https://habr.com/ru/post/207830/
All Articles