Cellular Automata Explained – Part 1

My attempt at explaining cellular automata. Aimed at someone who has no real knowledge of how CAs work.

If you look at some online definitions of CAs you will see explanations like this and this. You can try and understand them, but probably be still left confused.

1D Cellular Automata

OK, let’s start at the simplest form of cellular automata, the one dimensional cellular automata.

A one dimensional CA consists of a line of row of cells. Each cell can be alive (on) or dead (off).

The first row of the image above is how this cellular automaton begins. It has 1 single centered alive (black) cell surrounded by dead (white) cells.

1D CA Rules

Cellular automata change states and evolve based on simple rules. The rules apply to every cell in the CA at the same time each step.

For the above image, the rules are as follows;

This shows the 8 possible rules for this CA. Each new cell state depends on itself and it’s 2 neighbors in the previous state.

The first rule (with the 3 black squares above a single white square) means that if the current cell and its two neighbors are black that cell will become a white cell the next step of the CA.

The second rule means that if a cell and its left neighbor are black but its right neighbor is white, the cell will be white in the next step.

The rest of the 6 rules are the same principal and cover all possible combinations of white and black cells.

You apply these rules to every cell in the CA each step. Here is a nice animation courtesy of Wikipedia showing how the rules are applied to a row of cells and the next step of the CA resulting from the rules.

Once the rules have been applied to all the cells, that step is completed. For 1D CA the easiest way to display them is to show each of the steps under the last in a 2D grid. The first 15 steps are shown in the grid above.

1D CA Rule Numbers

Looking again at the rule for this CA

you will notice that there are a series of 1’s and 0’s under the rules. 0 for if the rule creates a dead (white) cell and 1 if the rule creates an alive (black) cell. This series of 1’s and 0’s can be converted into a binary string that can then be converted into a number. For 8 digit binary numbers the numbers will range from 0 (for 00000000) to 255 (for 11111111).

These 1D CA’s have 256 possible combinations of rules. Rule 30 (shown above) is the conversion of 00011110 binary into digital 30. Being able to refer to each rule as a single number makes it easier to state which rule you are talking about.

More steps

If you follow the above rule repeatedly for more steps it evolves like this

From such simple rules some interesting structures arise within in. This specific rule has been used to generate random numbers (you can keep track of the center pixel going down the image and use it to create random numbers). You can see more info about Rule 30 here.

So what about the other 255 1D CA rules?

You can see the results of all 256 rules here.

An interesting result is rule 22.

Rule 22 results in a structure of triangles within triangles. This is a famous fractal pattern called the Sierpinski Triangle and it tends to pop up all over the place in cellular automata and fractals.

The End – for now

Hopefully by now you have a basic understanding of cellular automata. The main points to know are;

1. CAs are based on a grid of cells that are alive or dead.
2. The CA runs/updates/steps by running a set of rules on all the cells at the same time.
3. The same rules are then applied to the new cells and the process repeats itself.

The one dimensional cellular automata are kind of bland and once you seen the possible 256 rules there isn’t much excitement, but understanding 1D first makes the transition into higher dimensions and more complex rules easier to grasp.

If you want to experiment with these 1D CAs yourself, you can download Visions of Chaos. Open the 1D CA mode dialog and suddenly the options should be more clear to you now.

There is even an option that takes the CA steps and maps them into music. You can also print a catalog of all the 256 rules with more details.

If any of the above is not clear, please comment and let me know.

Jason.

Extended Neighborhood 1D Cellular Automata

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.

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.

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

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.

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

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.

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.

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

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.

More explorations with Multiple Neighborhoods Cellular Automata

Since my last post explaining Multiple Neighborhoods Cellular Automata (MNCA) /u/slackermanz released his source code to hundreds of his shaders based on the same principals. Some using different neighborhoods, but all based on the same idea of multiple neighborhoods with rules for each neighborhood working together each step of the CA.

In the past you may have seen Kellie Evans’ Larger Than Life CA variations that use larger circular neighborhoods to make unique bug shaped gliders. In my opinion /u/slackermanz MNCA varieties are vastly more interesting with much more complex results compared to the bugs in Larger Than Life. Seeing new results like this not come from the depths of academia is also refreshing.

Some of these results are simply fascinating. Shapes and structures including blobs, amoeba like creatures with cell walls, cells that undergo mitosis and split into 2 smaller cells, worms, snakes, multi cellular worms that travel across the grid, circular cells that behave like they are hunting other cells, blobs grow and split, fluid like ripples and chains of cells that resemble algae. I have stared at some of these like they were a virtual lava lamp.

MNCA are a superb example of complexity from simple rules. The way some of the results seem to have almost intelligence in their behavior. Of course this is all a side effect of how the CA rules work and no real AI, intelligence or otherwise is involved. But, as with all CAs the emergence of interesting patterns from the simplest of rules occurs.

I have trimmed his original set of 470 shaders down to 92 which are now included with Visions of Chaos. If you are in any way interested in cellular automata I encourage you to download Visions of Chaos or /u/slackermanz’s source code and have a play with the MNCA shaders yourself.

Here is a 4K movie with some examples of how the MNCA work.

My next idea was to try extending MNCA to 3D. Rather than the 2D circular neighborhoods, use 3D shells like the following. The shells have 1/8th cut away to show the concentric rings.

7824 neighbor cells to count.

3337 neighbor cells to count.

2718 neighbor cells to count.

6188 neighbor cells to count.

So far I haven’t found any interesting 3D results worth posting, but some interesting structures.

MNCA need to be run on larger sized grids to allow their larger neighborhoods room to grow and evolve. That means in 3D you need to use large dimensions 3D grids. Using a large sized grid, and having to count all those thousands of neighbor cells for every 3D location really takes its toll on calculation times. I have now added 3D MNCA to the latest version of Visions of Chaos so if you have a grunty machine and patience you can try finding some 3D MNCA rules yourself. If you find any interesting results please send the M3D paramter file(s) to me.

See this post for the more recent results from MNCA.

Jason.

Rock Paper Scissors Cellular Automata

Rock Paper Scissors Origins

Rock paper scissors is a simple game that dates back to around 200 BC.

The game is played between two or more players who make a rock, paper or scissors shape with their hand at the same time. Rock breaks scissors, scissors cut paper and paper wraps rock. See this Wikipedia article for loads of info on the game.

Rock Paper Scissors Cellular Automata

Converting the game principals to a cellular automaton is simple enough. This is how I implemented it;

Every pixel color is calculated by playing a virtual 9 player game of rock paper scissors. The current cell vs its immediate 8 moore neighbors. If the neighbor count is greater than a threshold value in the result that beats the current cell then the current cell becomes the winner (what a terrible sentence). For example, if the current cell is scissors, the threshold is 3, and there are 4 rocks surrounding it, then it becomes a rock.

Using the above algorithm leads to very stable exact spiral shapes. The initial grid in this case was the screen divided into 3 “pie wedges”. One for each of the 3 states.

Adding some randomness helps break up the exactness of the spirals. Rather than checking if the winning neighbor count is greater than a specified threshold, check if it is greater than a threshold + a small random amount. This gives more variety in the spirals. This next image used a threshold of 3 and between 0 and 2 added randomly.

Rock Paper Scissors Lizard Spock Cellular Automata

I first saw this variation on The Big Bang Theory.

It was invented by Sam Kass. Lizard and Spock are added in as 2 more possible moves. This results in the play logic..

Scissors cuts Paper, Paper covers Rock, Rock crushes Lizard, Lizard poisons Spock, Spock smashes Scissors, Scissors decapitates Lizard, Lizard eats Paper, Paper disproves Spock, Spock vaporizes Rock, Rock crushes Scissors.

For the cellular automata you add 2 more cell states for Lizard and Spock. Otherwise the rest of the CA uses the same logic as the 3 state Rock Paper Scissors version.

It is interesting that the 5 states do not fully intermingle. Island blobs with 3 of the 5 states seem to form. In the above image there are clearly areas with only red, yellow and orange cells, and then other areas with only red, green and blue cells.

The following is an animated GIF of 45,000 steps (updated 1,000 steps per frame) that shows how these blobs fight for dominance and in this case RGB wins in the end.

RPS 15

RPS 15 includes Rock Gun Fire Lightning Devil Scissors Dragon Snake Water Human Tree Air Wolf Paper Sponge.

Threshold 2

Threshold 2 Random 2

Threshold 3

Threshold 3 Random 3

RPS 25

RPS 25 pushes it to 25 possible moves.

Threshold 2

Threshold 2 Random 8

Threshold 3

Threshold 1 Random 4

RPS 101

There is even the insane RPS 101. See the RPS 101 moves here.

I didn’t code RPS 101 as yet.

Image Based RPS

This idea came from NoSocks on YouTube. To use an image as RPS;

Find which of the RGB values is highest for the current pixel. Choose a neighbor at random and find which of its RGB values is higher. R is Rock, G is Paper and B is Scissors. So if the current pixel has the highest G value from its RGB values and the neighbor has the highest B value from its RGB values then the neighbor cell color is copied into the current cell (because B=Scissors beats G=Paper).

You can also use the smallest RGB values.

Here is an example animated GIF of Van Gogh’s Starry Night put through the process (click to open). Source RPS is determined by largest RGB. Opponent RPS determined by smallest RGB value.

3D Rock Paper Scissors

The same RPS technique can be applied to 3D too. Just check the 26 neighbors around each cell in 3D rather than 8 cells in 2D. The following movie has 1/8th of the 3D grid cut out to show the inner workings better.

4D Rock Paper Scissors

Extending into the 4th dimension was the next step. Rather than using a 3D array of [X,Y,Z] components you add a 4th dimension (usually denoted as W) and now use 4 loops over the [X,Y,Z,W] array dimensions.

The main issue is how to display the 4 dimensional array in the 3 dimensions we can see. For the following example movie I scale the 4th dimension density into a color palette index.

Some basic pseudo-code is;

for loopx:=0 to gridsize do
begin
   for loopy:=0 to gridsize do
   begin
      for loopz:=0 to gridsize do
      begin
         count:=0;
         for loopw:=0 to gridsize do if array[loopx,loopy,loopz,loopw]>0 then inc(count);
         if count>0 then cell_color:=palette[count/gridsize*255];
      end;
   end;
end;

To also show more of the interior of the CA structure I also hide cells when the above count value is above or below a threshold value. The threshold is calculated by the gridsize div 10. So if the gridsize is 100 then cells with a count less than 10 or greater than 90 are hidden and not rendered.

Availability

Rock Paper Scissors CA and the above variations are now included in the latest version of Visions of Chaos

Jason.

Multiple Neighborhoods Cellular Automata

Just a quick note at the start of this post. This was the initial version of MNCA. For the latest code and examples make sure you check out this post and this post too.

This one comes from the code here from u/slackermanz. He didn’t have a name for them at the time so I coined the term “Multiple Neighborhood Cellular Automata“.

For this CA there are 4 different large size neighborhoods used each step.

Each cell uses the above neighborhood patterns to tally the live cells into 4 sum values. sum_0 is the live cell count in neighborhood 1, sum_1 is the live cell count in neighborhood 2, sum_2 is the live cell count in neighborhood 3, and sum_3 is the live cell count in neighborhood 4.

The sums are used to determine life or death for the cells by using the following formulas.

If sum_0 is between 0 and 17 then the cell dies.
If sum_0 is between 40 and 42 then the cell lives.
If sum_1 is between 10 and 13 then the cell lives.
If sum_2 is between 9 and 21 then the cell dies.
If sum_3 is between 78 and 89 then the cell dies.
If sum_3 is greater than 108 then the cell dies.

Put all that into an options form to allow easy config changes.

Here is a quick sample movie with a few of the interesting rules I found so far.

Multiple Neighborhoods Cellular Automata are now included in the latest version of Visions of Chaos.

See here and here for more explorations into the world of Multiple Neighborhood Cellular Automata.

Jason.

Stacked Generations Display For 2D Cellular Automata

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

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.

These examples are of History Dependent Cellular Automata.

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.

History Dependent Cellular Automata

I have been exploring a variety of cellular automata lately and here is another one.

This is from another idea I had. Andrew Adamatzky let me know there has been work done using previous states before referred to as “Cellular Automata with Memory”. See these papers by Ramon Alonso-Sanz for other examples of 1D and 2D CAs using memory from previous generations.

This is a totalistic CA that uses the usual 8 immediate neighbor cells as well as the last step’s current cell and 8 neighbors. This gives a total of 17 neighbor cells that can influence the birth and survival of the cells.

I call them “History Dependent Cellular Automata” because they depend on the previous cycles’ neighbor cells as well as the usual 8 immediate neighbor cells.

Here are a few animated GIFS showing some early results. The GIF thumbnails are messy, so click them to see the clear GIFs.

Amoebas 01

Amoebas 03

Sample 01

Space Ships

I also experimented with extending the history back another step.

This gives a much larger search space to find interesting rules within and the majority of rules are random chaos, but here are a few interesting results I stumbled on through random searches. Again, the GIF thumbnails are a mess, so click them to see the clear definition GIF animations.

Feeding Walkers

Space Ships

Surviving Clumps

I also experimented with extending these CA into 3D space. Same principal as 2D but with more neighbors in 3D. Here is an example movie.

These CAs are now included with Visions of Chaos if you want to have a play with them.

Jason.

Alternating Neighborhoods Cellular Automata

This was a quick experiment with an idea I had.

Update a cellular automata using different neighborhoods and rules every second step. Green is the current cell. Red are the cells checked each step. The first step uses the 4 neighbor cells north, south, east and west. The second step uses the 4 diagonal neighbors. Then they alternate each step of the CA. Each neighborhood has its own set of rules for birth and survival.

There are a total of 2^20 or 1,048,576 possible rules using this method. 9*2^20 (9,437,184) if you take into account a maximum state value of between 2 and 10 for each cell.

Click the following to open a short GIF animation of each of the rules. The thumbnails are a mess.

Amoebas

Fireworks

Gliders

Life-ish

Traffic

Walkers and Spinners

Extending the possible maximum states of each cell up to 10 shows potential with some more interesting structures.

Expanding Ships

Fireballs

Spirals

Stick Growth

My next idea was to extend the neighborhoods as follows

The settings are extended to handle the larger neighborhood.

This gives 2^52 or 4 quadrillion (4,503,599,627,370,496 to be exact) possible rules (and that is only for 2 state rules). A maximum cell state of 10 gives 9*2^52 or 40 quadrillion (40,532,396,646,334,464) possible rules. Finding those sweet spots of interest between dying out and total chaos becomes even more daunting.

I wasn’t confident that those neighborhoods would give any interesting results beyond chaotic noise, but they are showing potential so far from random searches and mutations of rules.

Amoeba

BZ-ish

Fire Ships

Pulsating

Thick Ripples

The Alternating Neighborhood Cellular Automata are now available as part of the latest version of Visions of Chaos.

Jason.