Extended Neighborhood 1D Cellular Automata

Extended Neighborhood Cellular Automaton

When I first saw this type of cellular automata described by Gugubo on Reddit I was sure I must have implemented it and included it in Visions of Chaos before, but a quick check showed it wasn’t a CA I had covered. There is enough info in the Reddit thread for me to code it up and put it into Visions of Chaos.

Extended Neighborhood Cellular Automaton

This is a 1D Cellular Automaton that uses 5 cells from the previous generation (2 either side and the central cell) to update the new cell state. The larger neighborhood with 2 cells either side is why I called these “Extended Neighborhood” in Visions of Chaos.

Extended Neighborhood Cellular Automaton

There are 4,294,967,296 (2^32) possible “rules” or types in this CA. Each of the rule numbers can be converted into a 32 digit binary number. For example, rule 260 becomes;
00000000000000000000000100000100

Extended Neighborhood Cellular Automaton

To update a cell, use the following steps;
1. Convert the previous step’s left 2 cells, current cell, and right 2 cells into a binary value.
i.e LLCRR may have states 11010 which can be converted into decimal 26
2. Counting from right to left on the binary representation of the rule above, the 26th digit is a 0, so the new cell state is a 0.

Extended Neighborhood Cellular Automaton

The process is repeated for all cells and then repeated for all rows as long as the CA runs.

Extended Neighborhood Cellular Automaton

I also added the option for more than 2 states (alive or dead) per cell. This way, when a cell dies it does not turn instantly into a dead cell, but has a delayed dying period. If there are 4 states per cell then a living cell (state 1) that dies will first go to state 2, then state 3, then finally die (state 0). Only newly born state 1 cells are used in the rule. All other non state 1 cells are considered state 0 when updating the cell based on the binary string rule.

Extended Neighborhood Cellular Automaton

Jason.

Multiple Rules Cellular Automata

Another new CA to experiment with.

The idea for these came from a comment Tsui Kagura left on one of my YouTube videos.

Can you make a CA that is 4D ( or 5D etc ) in a sense, that you use 2 (or more) different regular CA rules, run them in the same space (same coordinates), same time (same steps), but then, based on some kind of rule also have them interact with each other?As if they were neighborhoods from another dimension. I assume we could only be ‘seeing’ one of them, the rest would be in a hidden dimension, but affecting the one we’re looking at. If there are more than one hidden dimensions, they could affect each other too, maybe using a different rule between them…

Using multiple rules on the same CA is something I have not experimented with before, so I had to give it a go.

To start off I used the simplest 2 state 2D CAs. The extension from a usual 2D CA is simple enough. You run 2 rules over the same grid. Store the results of each rule (either 0 or 1 for dead or alive) and then you use the results of the rules to set the new cell state.

How the 2 rule results are converted into a new cell state is the tricky part.

For two 2D CA rules there are 4 possible outcomes (dead dead, dead alive, alive dead, alive alive). So depending on the result states I have 4 options for alive or dead. This gives the following options.

Multiple Rules Cellular Automaton

Here are a few sample results after trying hundreds of random rules.

Multiple Rules Cellular Automaton

Multiple Rules Cellular Automaton

Multiple Rules Cellular Automaton

Multiple Rules Cellular Automaton

I will update this post if I find any more interesting results. There are many more extensions to try like 3D, 4D, 5D, larger neighborhoods, more than 2 rules, etc.

I did try the 3D version of multiple rules. Nothing worth posting as yet. I used both the result1 and result2 method above and also tried feeding the result of rule1 into rule2. Neither has given any unique looking results yet.

Jason.

Stochastic Cellular Automata

Stochastic Cellular Automata (also referred to as Probabalistic Cellular Automata or Random Cellular Automata) are cellular automata that introduce some form of randomness.

For example, the usual Game Of Life CA uses the rule 23/3. If a live cell has 2 or 3 neighboring live cells it survives. If a dead cell has exactly 3 live neighbors a new cell is born at that location. This sort of rule is called deterministic as there is no random chance involved. To make the rule stochastic we can introduce a probability for the rules. The 3 for a cell to be born could have a 90% probability applied. Now if an empty cell has 3 living neighbors it will only be born if a random value is less than the 90% probability.

When implementing the interface for stochastic CA, rather than the usual 3D Cellular Automata settings;

the probabilities are added;

Finding interesting stochastic results seems even more difficult than in deterministic CA. For the 2D variation lichen like growths seem common. For 3D I have been able to tweak some amoeba like growth structures. Here is a sample movie of a few 3D rules.

2D and 3D variations of Stochastic Cellular Automata are now included with the latest version of Visions of Chaos.

Seeing as these are new modes there are very little sample files included with them. If you download Visions of Chaos and find any interesting rules, please email them to me for inclusion in future releases.

Jason.

Stacked Generations Display For 2D Cellular Automata

History Dependent Cellular Automaton

This isn’t something new, but a feature that was on my to do list for years after seeing it implemented elsewhere.

History Dependent Cellular Automaton

The idea is simple. You take a 2D CA and rather than render each step/cycle/update as a 2D image, you add the current 2D cell states as a layer of a 3D stack of cubes. Each slice of the cube is another step in the CA generation.

History Dependent Cellular Automaton

These examples are of History Dependent Cellular Automata.

History Dependent Cellular Automaton

Once again I must give a shout out to the most excellent Mitsuba Renderer. I would not be able to render these examples with such nicely shaded cubes without it.

Visions of Chaos now supports generating 2D Cellular Automata, History Dependent Cellular Automata and Indexed Totalistic Cellular Automata as stacked generations.

Jason.

2D Accretor Cellular Automata

After experimenting with the 3D Accretor Cellular Automata I wanted to see how it works in 2D.

The principals in 2D are almost the same as in 3D, but in 2D you only have face and corner neighbors and no “edge” neighbors.

Here are some samples;

2 states – Solid 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2 states – Random 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

3 states – Solid 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

3 states – Random 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

4 states – Solid 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

4 states – Random 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

5 states – Solid 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

5 states – Random 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

Jason.

The Stepping Stone Cellular Automaton

This CA rule was first designed and explored by David Griffeath on his Commodore 64 back in the mid 1980’s.

The basic rule is you fill an image with random colors and set an update probability. For each pixel see if a random value is less than the probability. If it is then change the pixel to the color of one of its neighbor cells (this can be the 4 N,S,E,W Von-Neumann neighbors or all 8 closest cells in the Moore neighborhood). Griffeath’s original uses a 50/50 chance of each cell being changed and uses the Von-Neumann neighborhood.

From a starting random soup of ROYGBIV pixels

Stepping Stone Cellular Automaton

after a while it starts getting islands of the same color

Stepping Stone Cellular Automaton

If you wait long enough one of the colors will always end up dominating the entire grid. “Long enough” is a subjective term. For small grid sizes a single color can win out over the others in a few thousand steps. For larger images it could take days or longer. I had a 4K sized grid running overnight and it looked no closer to a final resolution than the above sample image.

Once I implemented Stepping Stone in Visions of Chaos I added the option to start from 2 or 4 colors. This gets the competition down to a smaller set of fighting colors.

Firstly starting from a black stripe down a white image for a 50/50 fair fight. Moore neighborhood.

Stepping Stone Cellular Automaton

Stepping Stone Cellular Automaton

Stepping Stone Cellular Automaton

And then using red, blue, green and yellow as the quarters of the image. Von-Neumann neighborhood.

Stepping Stone Cellular Automaton

Stepping Stone Cellular Automaton

Stepping Stone Cellular Automaton

David Griffeath originally included an image of Sharon Stone with his CA software to use as a starting point for the Stepping Stone CA. The first image of Sharon Stone that comes to my mind has to be her iconic leg crossing scene in Basic Instinct. The part where Newman was leering at her. So here is my Sharon Stepping Stone gif animation. Click the image to open the GIF in a new window.

Stepping Stone Cellular Automaton

As a side note, I can remember back when Basic Instinct was first released on VHS tape and we went and hired it. When the tape got to the leg uncrossing scene the tape went all static and unwatchable from previous pervs trying to frame by frame that scene and stretching the tape out (not that we were not poised with our finger on the frame by frame button to do the same thing). The good old days of VHS rental.

Visions of Chaos can use any image to run the stepping stone process.

Jason.

More experiments with Coupled Cellular Automata

Make sure you click the images in this post to see them in full 4K resolution. The thumbnails do not do them justice and hide a lot of the multi-scaled structures within them.

Coupled Cellular Automaton

After my original attempt to replicate Jonathan McCabe‘s Coupled Cellular Automata results I was contacted by Ian McDonald with some questions about how my original algorithms worked and that inspired both of us to make another attempt at getting McCabe like results.

Coupled Cellular Automaton

With some back and forth and some hints from Jonathan we were able to get a little further towards replicating his images.

Coupled Cellular Automaton

How the McCabe algorithms work

Jonathan has provided some hints to how his Coupled CA work in the past.

Firstly from here;

Each pixel represents the state of the 4 cells of 4 cellular automata, which are cross coupled and have their individual state transition tables. There is a “history” or “memory” of the previous states which is used as an offset into the state transition tables, resulting in update rules which depend on what has happened at that pixel in previous generations. Different regions end up in a particular state or cycle of states, and act very much like immiscible liquids with surface tension.

Coupled Cellular Automaton

and secondly from here;

The generative system involves four linked cellular automata – think of them as layers. “Linked” because at each time step, a cell’s state depends both on its neighbours in that layer, and on the states of the corresponding cells in the other three layers. Something like a three-dimensional CA, but not quite; the four layers influence each other through a weighted network of sixteen connections (a bit like a neural net). The pixels in the output image use three of the four CA layers for their red, green and blue values.

As in a conventional CA, each cell looks to its neighbours to determine its future state. This is a “totalistic” CA, which means each simply sums the values of its neighbours, then changes its state based on a table of transition rules. Now for the really good part: each cell also uses its recent history as an “offset” into that transition table. In other words, the past states of a cell transform the rules that cell is using. The result is a riot of feedback cycles operating between state sequences and rulesets; stable or periodically oscillating regions form, bounded by membrane-like surfaces where these feedback cycles compete. Structures even form inside the membranes – rule/state networks that can only exist between other zones.

Coupled Cellular Automaton

After emailing him he did provide a few more more clues to how his Coupled CA work which did help me get to the point I am at now.

How the “inner loop” behaves and how the 4 (or more) CA layers are actually processed and combined is still a mystery, but this is a hint;

“Cross-Coupled” is a matrix multiply to give 4 numbers from 4 numbers. If the matrix was “1.0” diagnally and “0.0” elsewhere you have zero coupling. If the zeros are replaced with other values you get cross-coupling of various amounts. If the cross coupling is very low you have 4 independant systems, if it is very high you get effectively one system, I think there is a sweet spot in between where they influence each other but don’t disappear into the mix.

And regarding the history;

The history or memory is an average of previous states at that cell. You can do it a few ways, say as a decaying average, adding the current state and multiplying by 0.99 or some number, so the memory fades. The memory is added to the index to look up the table, so you actually need a bigger table than 9*256.

Coupled Cellular Automaton

How my version works

Here are the basic steps to how I created the images within this post. Note that this is not how the McCabe CA works, but does show some similarities visually to his.

The CA is based on a series of CA layers. Each layer/array constains byte values (0-255) and is initialised with random noise. You need a minimum of 4 layers, but any number of layers can be used.

You also need a set of lookup tables for each layer. The lookup tables are 1D arrays containing byte values (0-255). They each have 256*10 entries. The arrays are filled using multiple sine waves combining different frequencies and amplitudes which are then normalised into the 0-255 range. You want to have smallish changes between the lookup table entries.

256*10 entries in the lookup table is because in the McCabe CA the current cell, its 8 neighbours and the history of that cell are used to index the lookup table. That gives 10 possible values between 0 and 255 which are totalled to index the lookup table. For the method I discuss in this blog post, you really only need a lookup table with 256 entries as the index maths never goes betyond 0 to 255. BUT I still use the larger sized array to stretch the sine waves further/more smoothly across the tables. Note you can also change the “*10” size to a larger number to help smooth out the resulting CA displays even more. Experiment with different values.

Coupled Cellular Automaton

Now for the main loop.

1. Blur each layer array. Gaussian blur can be used but tends to be slow. Using a faster 2 pass blur as described here works just as well for this purpose. Make sure the blur radius has a decent amount of difference between layers, for example 1, 10, 50, 100. These large differences in blur amounts is what leads to the resulting images having their detail at many scales appearance.

Coupled Cellular Automaton

2. Process the layers. This is the secret step that Jonathan has not yet released. I tried all sorts of random combinations and equations until I found the following. This is what I use in the images for this post.

for i:=0 to numlayers-1 do t[i,x,y]:=c[i,x,y]+lookuptable[i,trunc(abs(h[(i+1) mod numlayers,x,y]-c[(i+2) mod numlayers,x,y]))];

That allows for any number of layers, but to show the combinations simpler, here it is unrolled for 4 layers


t[0,x,y]:=c[0,x,y]+lookuptable[0,trunc(abs(h[1,x,y]-c[2,x,y]))];
t[1,x,y]:=c[1,x,y]+lookuptable[1,trunc(abs(h[2,x,y]-c[3,x,y]))];
t[2,x,y]:=c[2,x,y]+lookuptable[2,trunc(abs(h[3,x,y]-c[0,x,y]))];
t[3,x,y]:=c[3,x,y]+lookuptable[3,trunc(abs(h[0,x,y]-c[1,x,y]))];

t is a temp array. Like all CAs you put the results into a temp array until the whole grid is processed and then you copy t back to c
c is the current CA layers array
lookuptable is the array created earlier with the combined sine waves
h is the history array, ie what the c array was last cycle/step

An important step here is to blur the arrays again once they have been processed. Using just a radius 1 gaussian is enough. This helps cut down the noise and speckled nature of the output.

To make it a little more clear here is the main loop code that does the processing of the arrays.


//blur each layer
for i:=0 to numlayers-1 do QuickBlurArray(c,i,strtoint(CoupledCA2Options.grid.Cells[1,i+1]));

//process the layers
for y:=0 to imageheight-1 do
begin
     for x:=0 to imagewidth-1 do
     begin
          for i:=0 to numlayers-1 do t[i,x,y]:=c[i,x,y]+lookuptable[i,trunc(abs(h[(i+1) mod numlayers,x,y]-c[(i+2) mod numlayers,x,y]))];
     end;
end;

//update main arrays from temp arrays
for y:=0 to imageheight-1 do
	for x:=0 to imagewidth-1 do
		for i:=0 to numlayers-1 do
			c[i,x,y]:=t[i,x,y];

//quick blur each of the CA layers
for i:=0 to numlayers-1 do QuickBlurArray(c,i,1);

//save current state into history array
for y:=0 to imageheight-1 do
    for x:=0 to imagewidth-1 do
        for i:=0 to numlayers-1 do
            h[i,x,y]:=c[i,x,y];

Hope that helps clarify.

Coupled Cellular Automaton

3. Display. So now you have 4 byte vlaues (one for each layer) for each pixel. How can you convert these into a color to display? So far I have used these methods;

Color palette – Average the 4 values and use them as an index into a 256 color palette.

RGB – Use the first 3 layers as RGB components.

YUV – Use the first 3 layers as YUV components and then convert into RGB.

Matrix coloring – This deserves a larger section below.

Coupled Cellular Automaton

Matrix coloring

If you use just RGB or YUV conversions the colors tend to be a bit bland and unexciting. When I asked Jonathan how he got the amazing colors in his images he explained that the layers can be multiplied by a matrix. Now, in the past I had never really needed to use matrices except in some OpenGL code (and even then OpenGL handles most of it for you) but a quick read of some online tutorials and I was good to go.

You take the current cell values for 3 layers and multiply them by a 3×3 matrix


              [m2 m2 m2]
[m1 m1 m1]  x [m2 m2 m2] = [m3 m3 m3]
              [m2 m2 m2]

or 4 layers multiplied by a 4×4 matrix


                 [m2 m2 m2 m2]
                 [m2 m2 m2 m2]
[m1 m1 m1 m1]  x [m2 m2 m2 m2] = [m3 m3 m3 m3]
                 [m2 m2 m2 m2]

In both cases the m1 array variables are the CA layer values for each of the X and Y pixel locations. I use the first 3 layers, last 3 layers or first layer and last 2 layers. If you use a 4×4 matrix use the first 4 etc. Multiply them by the m2 matrix and get the m3 results.

You can use the m3 results as RGB components to color the pixels (after multiplication the RGB values will be outside the normal 0 to 255 range so they will need to be normalised/scaled back into the 0 to 255 range). For the 4×4 matrix you can use the 4th returned value for something too. I use it for a contrast setting but it doesn’t make that much of a difference.

If the matrix you are multiplying is the identity matrix (ie all 0s with diagonal 1s) the m3 result is the same as the m1 input. If you change the 0s slightly you get a slight change. For the images in this post I have used random matrix values anywhere from -10 to +10 (with and without a forced diagonal of 1s).

Using matrix multiplication to get the wider range of colors is really awesome. I had never seen this method used before and am so grateful of the hint from Jonathan. I am sure it will come in handy in many other areas when I need to convert a set of values to colors.

Another great tip from Jonathan is to do histogram equalisation on the bitmap before display. This acts like an auto-contrast in Photoshop and can really make blander images pop.

Another thing to try is hue shifting the image. Convert each pixel’s RGB values to HSL, shift the H component and then convert back to RGB.

Coupled Cellular Automaton

Once you put all those options together you get might get a dialog with a bunch of settings that looks like the following screen shot.

Coupled Cellular Automaton Dialog

Problem

There is one major issue with this method though. You cannot create a nice smooth evolving animation this way. The cell values fluctuate way too much between steps causing the movie to flicker wildly. To help reduce flicker you can render only every second frame, but the movie still has wild areas. Jonathtan confirmed his method also has the same display results. Coupled Cellular Automata using the method described in this post are best used for single frame images and not movies.

Coupled Cellular Automaton

Help me

If you are a fellow cellular automata enthuisast and have a play with this method, let me know of any advancements you make. Specifically, the main area that can be tweaked is the inner loop algorithm of how the layers are combined and processed. I am really interested in any variations that people come up with.

Coupled Cellular Automaton

Explore it yourself

If you are not a coder and want to experiment with Coupled Cellular Automata they are now included in Visions of Chaos.

To see my complete gallery of Coupled Cellular Automata images click here.

Jason.