Flag of the United Kingdom
Andreas Rejbrands webbplats

Aktuellt

Nedan visas de artiklar vars titel innehåller frasen "cellular automat", så när som på valet mellan versaler och gemener.


A second coloured extended-range cellular automaton, part 2

A new view of the automaton from yesterday:

A second coloured extended-range cellular automaton

A second example of a simple coloured extended-range cellular automaton:

A simple coloured extended-range cellular automaton

I have experimented a bit with coloured (RGB) extended-range cellular automata. Mathematically, these are ordinary N-state extended-range automata in which N = 2563, the values are interpreted as RGB colour codes and the rendering procedure uses the colour of the cell directly, instead of applying some arbitrary colour scheme. Below is a simple example I produced yesterday:

A simple extended-range cellular automaton

Today I give my first example of an extended-range cellular automaton. It is an N-state range-r automaton defined by the following rule: the new value of the cell is equal to the average of the values in the range-r Moore neighbourhood (including the cell itself) plus a constant increment. Typically I use N = 10, r = 32 or 36, and an increment of 10. Starting from random noise, this produces a small number of discrete circles (enclosed by squares) that evolve and expand until the entire region is filled with a chaotic mess. The most interesting images are obtained in the middle of this process. The following images shows generation 43:

Generation 43

Another example (different simulation, same generation):

Generation 43

A bit later, the circles get rough boundaries:

Generation 52

Another example:

Generation probably 52 or thereabout

Numbers of cellular automata

All cellular automata I have considered this far have used the standard Moore neighbourhood, a 3×3 square with the current cell in the middle and eight neighbours. Yesterday I extended my program to support larger neighbourhoods. Now it supports neighbourhoods of arbitrary range. If the range is r, the neighbourhood consists of all cells you can reach in no more than r steps from the current cell, each step being horizontal, vertical, or diagonal. Hence, the range-r Moore neighbourhood is a square consisting of (2r + 1)2 cells, with the current cell in the middle. r = 1 yields the standard eight-cell Moore neighbourhood.

The number of possible extended-range cellular automata is nearly ungraspable. Let us do some simple math.

“Floor plan”, a cellular automaton

Recall “Rain” and “Inferno”, two cellular automata almost defined by the same rule; they only differ in the choice of the parameter θ, which is θ = N/24 for “Rain” and θ = N/12 for “Inferno”. If we let θ = −N/12, we obtain a new cellular automaton, which I call “Floor plan”. In general, this rule creates period-18 “floor plans”. A single such floor plan (for N = 24) is shown below:

The “Floor plan” cellular automaton.

Although the image appears to be two-colour, it actually isn’t. By posterizing it to two colours, however, a true maze is obtained. And as far as mazes are concerned, this is a pretty nice one. Below a larger maze is shown and its main connected component is highlighted:

The “Floor plan” cellular automaton: a large maze (posterized)

The “Floor plan” cellular automaton: a large maze that has been posterized and flood filled in its largest connected component.

“Camouflage”, a cellular automaton

Today I present a particularly simple N-state cellular automaton. It is defined by the following rule: if a cell has two (or more) Moore neighbours with the same value as the cell itself, then the value of the cell is increased by one (mod N); otherwise, it is left unchanged. In this case, it is easy to see what kind of pattern is created simply by thinking about the rule. To confirm, here is a computer simulation showing a still image from the final stage (N = 96):

The final state of the “Camouflage” cellular automaton: the grid consists of a number of irregularly shaped constant-colour regions.

It is also easy to figure out what happens if N is changed; I leave this as an exercise to the reader.

“Rain”, a cellular automaton

Today we give another simple but visually pleasing example of an N-state CA: if the value of the cell is greater than the average of the von Neumann neighbours minus θ, decrease the value of the cell by one (mod N); otherwise, set it to the successor (mod N) of this average. N = 24 and θ = N/24 gives “Rain”, preferably rendered in shades of blue:

The “Rain” cellular automaton.

If instead θ = N/12, we obtain “Inferno”, preferably rendered in shades of red (or not at all).

“Fluorescence”, a cellular automaton

Both “Fuzz with dust” and “Dunes” contain the following rule as “subrules”: replace a cell’s value by the successor (mod N) of the average of the values of the von Neumann neighbours. How does this rule look on its own?

The answer is that it produces growing fluorescent cells on a folder-containing background:

The “Fluorescence” cellular automaton.

The fluorescence becomes apparent when the background darkens, as it does cyclically:

The “Fluorescence” cellular automaton.

A less zoomed-in picture (with a different colour scheme):

The “Fluorescence” cellular automaton.

With the “Rainbow” colour scheme, the illusion of fluorescence disappears, but the images are still very pleasant:

The “Fluorescence” cellular automaton.

“Dunes”, a cellular automaton

A few weeks ago, I considered the following N-state cellular automaton rule: if the top-left neighbour of a cell has a value greater than N/2, then the value of the cell is increased by one (mod N); otherwise, the value is set to the successor of the average of the values of the von Neumann neighbours (mod N). The result looks like this (for N = 24):

The “Dunes” cellular automaton.

Superficially, the image looks like dunes, but if you look more carefully, it might actually bear a stronger resemblance to a network of anastomosing capillaries. Experiments performed on small(er) grids (strongly) suggest that, in most cases, the grid eventually becomes filled with non-anastomosing, parallel vessels with periodically animated colours, the period being at least as big as the smallest dimension of the grid (often with equality, but sometimes equal to the other dimension, or much, much larger than any of those).

“Fuzz with dust”, a cellular automaton

Multi-state cellular automata can be used to create intriguing visual effects. Today and the next few days I will give examples of such visuals. I start with an automaton I discovered yesterday, defined by the following rule: if the top-left neighbour has a value greater than the bottom-right neighbour, decrease the value of the cell (mod N); otherwise, set the cell’s value to the successor (mod N) of the average of the values of the von Neumann neighbours. This produces the following result (with N = 24):

The “Fuzz with dust” cellular automaton.

I call it “Fuzz with dust”.

A rose-producing cyclic cellular automaton

In addition to the generalisations to the standard cyclic cellular automaton we saw yesterday, it is natural to investigate what happens if you increase a cell’s value not by one, but by two, three, or more every time it should be updated (not altering the condition). It turns out, at least for N = 24 states and the standard threshold (1), that you obtain rounded square spirals if you increase by two instead of by one:

The final state of the cyclic cellular automaton with increment two.

If you increase the increment to three, you make roses:

An intermediate step of the cyclic cellular automaton with increment three, showing roses.

Eventually the roses cover the entire region:

Roses

More cyclic cellular automata

It is possible to alter the parameters of the cyclic cellular automaton. Obviously, the number of states N per cell can be varied. But it is also possible to change the “threshold”, defined as the number of neighbours with value n + 1 (mod N) needed for a cell to advance from n to n + 1 (mod N). Some of these variants have specific names, and two particularly neat ones are “313” (three states, threshold 3) and “Perfect” (four states, threshold 3), shown below.

The “313” rule creates a pattern of “moustaches”:

The 313 cyclic automaton in shades of green.

The “Perfect” rule creates octagonal spirals:

The Perfect cyclic automaton in shades of red.

Tomorrow I will make a different kind of adjustment to the cyclic CA.

The cyclic cellular automaton

A well-known (non-life-like) cellular automaton is the cyclic automaton. In this system, each cell in a rectangular grid with toroidal topology is assigned any of N discrete values, ranging from 0 to N − 1. In each step, a cell with value n is assigned value n + 1 (mod N) if any (Moore) neighbour has this value; if no neighbour has value n + 1 (mod N), the cell is left unchanged.

I ran the simulation with N = 24 from an initial soup (in which every cell was randomly assigned any of the N values with equal probability). After about 400 generations, a period-24 stage is reached, where the entire plane consists of animated square spirals:

The cyclic cellular automaton.

You may also have a look at the transformation from the initial soup to the final state. (Warning: somewhat awesome.)

According to both Wikipedia and mirekw.com, the cyclic ceullar automaton and its variants were first described by David Griffeath.

A non-life-like cellular automaton

Today I give a first example of a non-life-like cellular automaton. It is a very similar beast, though: it still uses a rectangular grid with the toroidal topology, two possible states per cell, and the Moore neighbourhood, and the new state of a cell still is a function of the current states of the cell and its neighbours. However, in this automaton, it is not sufficient to know only the number of living neighbours to determine the new state of a cell.

To be specific, this automaton is very similar to B2/S23, but a dead cell comes to life iff it has precisely two live von Neumann neighbours; the survival condition still uses the Moore neighbourhood. Hence, in a sense, this automaton mixes the von Neumann and Moore neighbourhoods. Technically, though, it uses the entire Moore neighbourhood, but the birth condition cares about which neighbours are alive.

Below the ashes of this automaton (formed from a 50% random soup) is shown. It does produce a number of neat period-2, period-3, and period-4 oscillators.

Tomorrow I will give a much more interesting example of a non-life-like automaton.

The Day and Night cellular automaton

Although I could probably spend a few more years discussing the properties of life-like cellular automaton rules, I feel it is time to end the introductory series. I do so by giving an example of a shrinking black blob in the Day and Night automaton (B3678/S34678).

The Day and Night cellular automaton.

However, you need not panic: by putting the life-like cellular automata aside for now, I can spend time investigating other types of automata.

Final patterns of cellular automata, part 3

Today we consider the final patterns (or ash) created by Game of Life itself (B3/S23). After trying a few times, I managed to produce a random initial 50% soup creating an ash containing instances of all of the three most common oscillators:

Ashes of Game of Life including blinkers, toads, and a beacon.

The final stage contains 71 blinkers (including ten traffic lights), two toads, and one beacon; these are the most common oscillators found in B3/S23 ash, in this order. As still lifes are concerned, we obtained 78 blocks, 47 beehives (including three honey farms), 17 loafs (but no bakery), seven boats, one tub, two ponds, and two ships (but no fleet).

After trying many more initial soups, I also managed to find one producing a pulsar in the end. The pulsar is the fourth most common oscillator.

Ash of Game of Life containing a pulsar.

This ash contains 96 blinkers (including eight traffic lights), one toad, no beacons, and one pulsar. The still lifes obtained were 98 blocks, 45 beehives (including one honey farm), 15 loafs (but no bakery), 13 boats, two tubs, three ponds, no ships (so obviously no fleet), and one barge.

Final patterns of cellular automata, part 2

Today, we continue to investigate the final or near-final stages of various life-like cellular automata. We begin with B5678/S023456 which represents a “class” of rules creating patterns that resemble lung tissue:

Black thin curves divide the white bitmap background into many densely-packed round spaces, like small airways and alveoli. Some smaller spaces are partly red (like capillaries).

Many rules create ashes consisting of small black (stationary) objects. One example, B578/S024567, creates (microscopic) “worms” and debris:

B568/S4567 creates other kinds of microscopic creatures, but no debris:

B4567/S567 creates opsonized bacteria:

B378/S01235678 creates small islands of maze-like structures on a black background:

Finally, B278/S1456780 creates white lakes with red fish on a black background:

Final patterns of cellular automata

There are many life-like cellular automaton rules. To be specific, there are 262 144 of them. I have studied the rules that do not contain B0 or B1 in some detail. For each of these rules, I created an 80×80 torus with an initial 50% random soup and computed the 500th generation. In the obtained bitmap image, live cells were coloured according to their age (1: red; 2: a bit darker red; ...; 10 and beyond: black). Then I studied these 65536 images one screen (198 bitmaps) at a time, investigating many of them further.

A screenshot of a part of a Windows 7 Explorer folder list view containing 5×8 of the described bitmaps.

Not surprisingly, these 65536 bitmaps can very roughly be classified into a reasonably small number of “classes” according to the large-scale patterns they display. Two of these classes, the black and the red mazes, have already been described. Today we give a few other examples. Before doing so, however, three important points regarding the experiment should be made. First, some of the bitmaps didn’t represent the final stage of the simulation. Second, I did not obtain any information about the behaviour of the rules prior to the 500th generation (and sometimes the journey is more interesting than the final outcome). Third, many features of life-like rules cannot at all be discovered by an experiment like this. For instance, there are other seeds than the 50% random soup (like 2×2 squares and benzene rings) and spaceships aren’t detected. Still, the experiment gave me a better understanding of the life-like CA “zoo”.

A huge number of bitmaps display ongoing, chaotic activity with no “interesting” patterns; these bitmaps look rather similar to the initial soup (and the animations to noise), but with a slightly different distribution of live cells. In some cases, however, you clearly see some “interaction” between cells (B234/S023):

Bright red pixels form an intricate pattern of clusters and thin strings connecting them, all on a white background. Maybe it looks a bit like red paint.

A very common type of pattern consists of red, black, and white pixels that form distinct patterns, typically with white rectangles with black borders surrounded by white and red areas. Below three such rules are shown:

B234567/S0234567:

A huge number of white squares with black borders are scattered across the bitmap; they tend to form horizontal and vertical stripes. Surrounding these are larg(er) red and white regions, seperated by black lines, each region a union of orthogonal rectangles.

B234678/S01234567:

A huge number of slightly larger white squares with black borders are scattered across the bitmap; they tend to form horizontal and vertical stripes. Surrounding these are small red and white areas.

B2345678/S01234567:

On a white background (that you don't see very much of), red regions with black borders are seen. These regions are mainly rectangular, or unions of rectangles. Outside these, there are occasional irregular red regions (without black borders), sometimes with white holes.

The last image doesn’t represent the final stage, which consists of only the red rectangle-like regions:

On a white background (that you don't see very much of), red regions with black borders are seen. These regions are mainly rectangular, or unions of rectangles.

B234678/S7 belongs to a completely different “class”, in which two red “brush patterns” coexist on a white background:

A huge number of rules create mainly (or, sometimes, entirely) black patterns, that is, stationary patterns, sometimes with oscillators, ranging from a number of small black objects on a white background to a bitmap almost entirely black. In between, sometimes large, irregular regions of (mainly) black and (mainly) white cells form; often boundaries between such regions oscillate in some way. A nice, (almost entirely) non-oscillating pattern with a black/white ratio close to 0.5 is formed quickly by B5678/S145678:

Tomorrow I will give six more examples (unless Linköping University contacts me, in which case I might suffer a breakdown).

More cellular automaton mazes

The last two days we have become familiar with some of the CA maze-generating rules: “Maze” (B3/S12345), “Mazectric” (B3/S1234) and the B2(7)(8)/S(0)123(5)(6)(7)(8) family of very nice mazes. As noted, however, there are many more maze-generating rules, producing mazes with a number of different qualities. Today we will show a few more examples.

Some mazes are composed mainly (or even exclusively) of horizontal and vertical walls without corners, often found clustered together. For example, this is B2/S124, which consists of a single connected component:

B2/S124

The following maze (B3/S012358) is almost as simple, but also contains a few corners. As the reader can check for herself (e.g., using Win+R, pbrush, Enter), this one consists of one huge connected component and a few smaller components:

B3/S012358

At the other extreme, this maze (B25/S23457) consists of a large number of (mostly either horizontal or vertical) small corridors not connected to each other:

B25/S23457

Occasionally, you find a rule that forms voids (white-coloured areas) or rocks (black-coloured areas) in a maze (B278/S0124567):

B278/S0124567

There are also rules that produce mazes with very short walls, like B26/S012357:

B26/S012357

Some mazes have additional features, like “force fields” (B23/S234):

B23S234

A well-known example is “Maze with Mice” (B37/S12345):

Maze with Mice

Try also B2378/S1234.

All mazes we have considered thus far have been almost stationary patterns (with the occasional oscillating corner, “force field”, or “mouse”), but there are also rules that form mazes that alternate between generations. Typically, a maze is replaced by its inverse in the next generation. I use the term “red mazes” to denote these, since they are shown in red in my software (because the walls consist of newly born cells in each generation). Below is B24567/S, one of these “red maze” rules:

B24567/S

In this article and the previous ones, we have only seen a small number of the many maze-forming rules. However, most of the remaining rules are close variants of the ones we have seen.

Cellular automaton maze generation, part 2

Let us continue yesterday’s discussion on maze-generating rules by considering some larger examples. By giving each connected component of “Maze” (B3/S12345) a unique colour, it is easy to see just how disconnected the maze is:

Maze

Applying the same processing to “Mazectric” (B3/S1234) we see that this maze is marginally better, but it is still highly disconnected:

Mazectric

As noted yesterday, we get a significant improvement by considering the inverse colouring of “Maze” (that is, by interpreting the white cells as walls and the black cells as corridors):

Maze (inverse interpretation)

This makes the connected components a lot larger, but there is still quite a few of them. My proposed B2/S123, however, consists of one huge connected component and a fairly small number of very small or tiny components:

B2/S123

That’s what I call a maze!

Cellular automaton maze generation

Among the 262144 possible life-like cellular automaton rules, quite a few generate mazes of various kinds. Among these, two are particularly well-known and are even named: “Maze” (B3/S12345) and “Mazectric” (B3/S1234). From an initial soup, these quickly make stationary mazes with the occasional oscillating corner (not shown below):

Maze:

Maze

Mazectric:

Mazectric

I do not know why these two have been selected from the large number of maze-generating rules. In fact, I do not even consider them to be good examples of such rules, because the corridors they make are highly disconnected. This can be seen by trying a few flood-filling operations on the bitmaps:

Maze:

Maze

Mazectric:

Mazectric

Clearly, given two arbitrary points A and B in such a maze, it is highly unlikely that there is a path from A to B. (It appears like the situation gets better in the B3/S12345 (“Maze”) case if you reinterpret the white cells as the walls, but not very much.)

There are life-like maze-generating rules that create much better mazes in this regard, such as the B2(7)(8)/S(0)123(5)(6)(7)(8) rules. Below B2/S123 is shown:

B2/S123:

B2/S123

Trying a single flood-fill operation shows that this maze is much nicer (unless you are unlucky):

B2/S123:

B2/S123

A “burning” cellular automaton

Yesterday, we used the “Diamoeba” cellular automaton to give an example of CA dynamics. In that example, the boundary between a “diamond” of live cells and the surrounding dead cells fluctuated chaotically. A different boundary behaviour is exemplified by the rule B356/S014678, in which a random soup quickly will produce a large (possibly disconnected) region of mostly living cells surrounded by mostly dead cells (and a large number of small still-lifes and the occasional oscillator). The boundary of the large region is “burning”, and the total size of the region varies slowly with time:

A picture of generation 917.

A video is available (MP4, 36.3 MB) showing the first 3800 generations. If this particular simulation is allowed to proceed, the living pixels will win the battle. Indeed, just before generation 15000, the entire space consists of the region of living cells.

The “Diamoeba” cellular automaton

The “Diamoeba” cellular automaton (B35678/S5678) is a well-known life-like cellular automaton. Perhaps its most intriguing feature is the boundary fluctuation found on the “diamonds” formed by the automaton:

A diamond-shaped region of live cells has a chaotically fluctuating boundary.

More cellular automaton rugs

A few days ago we saw some of the patterns obtained from a 2×2 square using the “Persian rugs” (or “Serviettes”) cellular automaton (B234/S). Today we give a few other examples of “rugs” obtained using other rules.

Generation 135 of B234567/S124567:

A rug

Generation 146 of B234678/S8:

A rug

Generation 114 of B235678/S1234567:

A rug

Generation 101 of B2345678/S0238:

A rug

The B268/S04567 cellular automaton

Yesterday, I investigated the life-like cellular automaton B268/S04567. This is an automaton in which most patterns explode, although a few still-lifes and oscillators exist. A random soup will, after a large number of generations, produce a black (stationary) pattern of small, irregular cells with common boundaries that fill the entire space. Some of these cells oscillate. This rule also supports a simple four-cell period-1 orthogonal spaceship travelling at the speed of light. Below two such ships collide, creating an explosion:

A collision between two spaceships in B268/S04567.

Somewhere at generation 2500, a periodic state, as described above, is reached. This state has period 1260, and looks roughly like this:

A steady state in B268/S04567.

The “Persian rugs” cellular automaton

The life-like cellular automaton B234/S is known as “Persian rugs” or “Serviettes” because of the beautiful patterns it creates when the initial seed is a small, symmetric figure. Below, this automaton is run for 99 generations on a 200×200 grid with a central 2×2 square as the initial state. A family of lovely carpets of increasing size is obtained.

An animation showing 99 square patterns of increasing size.

Among these patterns, some personal favourites are the following:

Generation 70:

A picture of generation 70.

Generation 73:

A picture of generation 73.

Generation 80:

A picture of generation 80.

Generation 97:

A picture of generation 97.

The “coagulations” cellular automaton

The life-like cellular automaton B378/S235678 is known as “Coagulations”. This automaton creates rather visually pleasing patterns. Below the simulation has been run for a few hundred generations on a 800×500 square grid with the torus topology and a 50 % soup as the initial state. The live cells are coloured according to their age (the number of generations they have been alive), from yellow (new live cell) to black (a few hundred generations old):

A patterned formed by the “Coagulations” cellular automaton.

If the initial soup is symmetric, the state will be symmetric for all future generations:

A patterned formed by the “Coagulations” cellular automaton.

To get a feeling for the dynamics of this CA, you may want to view an animation of the simulation from an initial soup or an initial small, central pattern. In these animations, only the first ten generations of a live cell are coloured.

The “life without death” cellular automaton

Since Conway’s original Game of Life is the rule B3/S23, it is only appropriate that B3/S012345678 is named “Life without Death”. The following is a simulation of this cellular automaton on a 400×400 square grid with the topology of the plane (not torus) and an initial, small, random mass of pixels as the centre.

A simulation of the “Life without Death” cellular automaton.

Besides the main, irregular, growth, a number of thin, regular, purely horizontal or vertical growth patterns are seen; these are known as “ladders”.

The “replicator” cellular automaton

An interesting life-like cellular automaton is B1357/S1357. Nicknamed “Replicator”, this automaton will produce an infinite number of copies of any small initial figure. Below, this rule is applied to a rasterised version of the capital Latin letter “A”:

The “Replicator” cellular automaton applied to the letter A.

The simulation is run for 96 iterations. At each multiple of 16, the state consists of a number of perfect copies of the initial letter. (At the remaining multiples of 8, the state consists of a mixture of perfect and distorted copies.) To confirm that this is indeed a general phenomenon (and not something that requires the precise shape of the letter “A”), let us redo the experiment using a (rasterisation of a) benzene ring as the initial figure:

The “Replicator” cellular automaton applied to a benzene ring.

(Of course, the “chemical formulae” formed, consisting of adjoined benzene rings, are not valid.)

A cellular automata simulator

I have used some of my recently overwhelming spare time to program a simple cellular automata simulator. It is a native Win32 application able to run simulations on a finite rectangular grid with the topology of the plane or a torus. The computation is run in its own thread, different from the GUI thread, and the application supports binary, multi-state, and RGB automata with the Moore neighbourhood. All life-like cellular automata are supported (and are entered in the GUI using strings like “B3/S23”), and it is easy to hard-code other CAs. The application comes with a library of life-like CAs as well as number of interesting cyclic multi-state cellular automata.

Cellular Automata Simulator screenshot

Below is a small Game of Life (B3/S23) simulation, starting from a random distribution of pixels on a 60×60 square grid with the torus topology. After 855 generations, a period-2 state is reached, containing a number of still lifes as well as eight blinkers (including one traffic light) and a toad.

A game of Conway's Game of Life


Visa alla tidigare notiser.

Visa enbart de senaste notiserna.