block KA, vicinity of Margolusa

Short description

The article discusses the block KA configuration, which involves dividing a grid into predetermined sections or blocks with transition instructions. The article provides examples of rules and animations, such as the Billiard Ball Machine and Diffusion Limited Aggregation, that demonstrate how the configuration works. The article also highlights the importance of considering the non-cyclic mesh and the dependence on the starting state in some of the models. The article concludes by showcasing different figures that can be created from the block KA configuration.

block KA, vicinity of Margolusa

👾, Habre!

Today we will again deviate a little from the classic model and build the configuration from the very beginning, fortunately, there are no difficulties in this. Today’s configuration – block KA – assumes that our grid is divided into some sections, actually blocks, for which transition instructions are predetermined. No variations – one transition template for one location template. Sounds like we’re going to get a bunch of messy oscillators, right? But the configuration has a second condition: at each step, the division grid is shifted, due to which the cells are treated with a new block at each subsequent iteration. Better, of course, by example.

The most popular model for building block-based spacecraft is the division into 2×2 blocks with a shift of 1 diagonal cell per iteration. This model bears the name of its first and main researcher, the pioneer of the study of space vehicles – Norman Margolus. Although the appearance itself is called the neighborhood of Margolus, it is somewhat different logically from those neighborhoods that we examined earlier. Namely: this neighborhood reflects both possible states at once, and it is not tied to any specific cell. There are different representations in the image. One of them:

Blocks are formed on even iterations with blue lines, blocks are formed on odd iterations with red dashed lines

As with the alternative neighborhoods, this section of the KA is also very sparsely explored (this statement will only become more relevant the further we move away from the standard model), and the Margolus neighborhood is almost the only one recognized in the entire configuration. However, this does not mean that we will not find something to look at.

Introductory

In general, each type rule contains several transition instructions in a one-dimensional representation, such as

0, 0, 0, 0: 1, 1, 1, 1

(=A block with all empty cells becomes completely filled).

In addition to the set of instructions, it is also specified whether rotations of the instructions and their display horizontally and vertically are required. This allows you to shorten the descriptions, for example, by making them equivalent 1, 0, 0, 0: 0, 1, 0, 0 and 0, 1, 0, 0: 1, 0, 0, 0 horizontal display.

Also, to reduce the number of described instructions, individual cell values ​​can be replaced by variables, that is, take any value.

Example: 0, 0, 0, 0: 0, 0, 1, 1 and 1, 0, 0, 0: 1, 0, 1, 1 are replaced by a, 0, 0, 0: a, 0, 1, 1

It is worth mentioning that block KAs are reversible, that is, knowing the current state of the field and the transition instructions, we can restore the previous states step by step.

1. Billiards

Let’s start with a not the simplest example, but it will give us a good understanding of this configuration.

Billiard Ball Machine

.

The rule is defined by two transitions with rotational symmetry and, like most configuration rules, requires a specific starting state.

Симметрия: поворот

1, 0, 0, 0: 0, 0, 0, 1

1, 0, 0, 1: 0, 1, 1, 0


18s., speed 3, 112×112

You may have a question – Why do “bullets” ricochet correctly? After all, we do not set any direction, only the current state is known.” The secret is in the second instruction and the fact that our “balls” consist of two cells. Let’s slow down the animation a little:


10s, speed 0.2, 112×112

Let’s break the starting state: move the outer ball one cell higher, remove one cell from the first inner ball, and move the cells closer to each other for the second ball.


12 p., 112×112

Everything seems to be broken. Perhaps you have a new question – “OK, why do individual cells bounce back in the same direction from which they came?”.

Here the essence is in the configuration itself – a cell that has changed due to transition 1, 0, 0, 0: 0, 0, 0, 1 cannot be in another block in the second or third positions, it will always be in positions 1 and 4, and will follow transitions along this diagonal. And vice versa – the cell in positions 2 and 3 from this transition (Симметрия: поворот) will always be on them.

A large number of lines in the image of the neighborhood can hide from you this counterintuitive feature, which is extremely important in the implementation of the algorithm and the construction of figures. Look at the image again (duplicated below, under spoiler). Due to the fact that with each iteration we move diagonally, blocks with starting cells at positions x+1 or y+1 simply does not exist. In other words, there are those blocks that have the sum of positions on both axes in the starting cells even.

Well, it can be considered that we have figured out the configuration. Now we can enjoy other examples.

2. Sand

One of the most popular configuration rules models the behavior of sandstone cells, albeit with some assumptions.

Симметрия: отражение по горизонтали

1, 1, 0, 0: 0, 0, 1, 1

1, a, 0, b: 0, a, 1, b

1, 0, a, 0: 0, 0, a, 1

3, a, 0, b: 3, a, 1, b

This rule assumes 4 states: 0 – an empty cell; 1 – grain of sand; 2 – fixed cells with which we can create surfaces for sand; 3 – endless source of sand.


40s., speed 1.5, 112×112

Here you can see the bulk of the assumptions, but even with them the model is very close to its prototype.

With a large amount of sand, you can find another interesting feature, when the cells gather in a line when they fall.


28s., speed 1.5, 224×224; Random Fill (20%)

3. Diffusion Limited Aggregation

Симметрия: отражения + поворот

1, 0, 0, 0: 0, 0, 0, 1

1, 1, 0, 0: 1, 1, 0, 0

0, 1, 1, 0: 1, 0, 0, 1

1, 1, 1, 0: 1, 1, 0, 1

1, 0, 2, 0: 2, 0, 2, 0

1, 0, 2, 2: 2, 0, 2, 2

State transitions 1 may resemble a billiard rule with a couple of modifications:


13 p., 112×112; Random Fill (5%)

But the main interest in the rule is caused by cells in the second state, thanks to which growth occurs, similar to many natural processes:


32 p., 112×112; Random fill (60%) + center cell in second state

4. Toothpick sequence

One of the simplest rules, with a single transition: in each block, with a single filled cell, the adjacent ones are also filled.

Симметрия: поворот

1, 0, 0, 0: 1, 1, 1, 0


15 p., 224×224; Two starting cells diagonally

672×672

5. Throne

Classic configuration rule. The transition instructions are even simpler “toothpick” – all empty blocks are filled, and vice versa. No symmetries, of course, will be needed.

The rule is very flickery, so every second frame is removed from the animations. We will leave the original look under the spoiler.


15 p., 112×112; The central block is filled 27×27


57 p., 224×224; 6×6, 2×2 and 2×2 blocks are filled

Flicker

If you’ve come here, let me immediately show you a completely random distribution (3%)


17 p., 224×224

Well, now the original animations above the spoiler:


27 p., 112×112



55 p., 224×224

The behavior seen at the boundaries of the example is caused by the non-cyclic mesh. If you link the borders, the appearance will change significantly:


25 p., 224×224

Flicker

40 p., 224×224

6. Criteria

Development of instructions

Tron

But it led to the emergence of a rule

Critters

interested in his gliders.

Симметрия: поворот

0, 0, 0, 0: 1, 1, 1, 1

0, 0, 0, 1: 1, 1, 1, 0

0, 1, 1, 1: 1, 0, 0, 0

1, 1, 1, 1: 0, 0, 0, 0

Gliders in this rule are very stable. They can pass through each other without damage, with different elimination, change the direction of flight, and if they are damaged, they can recover from the next collision. Because the rules are the basis TronYes, the animation flickers again, and is halved again.


56 p., 224×224, 50×40%

Flicker

56 p., 224×224, 50×60%

7. Rotations

Another simple rule that generates travelers.

Симметрия: поворот

1, 0, 0, 0: 0, 1, 0, 0


59 p., 112×112

8. M0,2,8,12,1,10,9,11,4,6,5,14,3,7,13,15

Finally, let’s get acquainted with another version of the description of transitions.

For two-state block CAs, the locations can be represented as binary numbers and in this case the simplified notation can be used M0,1,2,…,14,15, where the subscript denotes the starting location and the subscript value is the location pattern after the transition. Example M15,1,2,…,14,15 will correspond to the rule with a single instruction “all empty – all filled”, without a reverse transition.

This option is quite compact, but, unfortunately, not universal.

Let’s go back to the rule. M0,2,8,12,1,10,9,11,4,6,5,14,3,7,13,15. As you can see, only two values ​​remained in their positions and the rest changed. In explicit notation with symmetry reduction, it would look like this:

Симметрия: поворот

1, 0, 0, 0: 0, 1, 0, 0

1, 1, 0, 0: 0, 0, 1, 1

0, 1, 1, 0: 1, 0, 0, 1

1, 1, 1, 0: 1, 1, 0, 1

There are many different interesting figures to be found in this rule.


17s., speed 5, 112×112


12s., speed 3, 224×224

9. M0,14,13,0,11,0,0,0,7,0,0,0,0,0,0,0

An interesting rule, both in appearance and transitions: we keep transitions for only four locations with one filled cell, inverting the state of the block, and reset all other locations to empty blocks. Well, as a result, we get ornamental-fractal types with a great dependence on the starting state.


33 p., 672×672


30 p., 672×672


27 p., 672×672

10. M0,1,2,3,4,10,6,11,8,9,5,13,12,14,7,15

And let’s finish today’s review with an interesting oscillating rule.


35 p., 112×112

Other figures, of course, are also possible.


21 p., 112×112


And that’s all today. See you in a week!

Read also

← Previous part

|

Next part (TBA) →

Related posts