Coupled Cellular Automata

Origins

Back in 2007 I was trying to figure out the algorithms behind Jonathan McCabe’s cellular automata pictures. I was never able to determine the algorithm to get the same results and coloring as Jonathan, but this is an explanation of my own Coupled Cellular Automata that arose from trying.

Algorithms

The principal of this method is to have 3 CAs with different settings running mostly independently of each other, but have their values interact with each other to create a new interesting result.

Coupled Cellular Automata settings

To start with you need 3 arrays to keep track of the 3 separate CAs. I used a 3D array to store them, ie c[0,x,y] c[1,x,y] and c[2,x,y].

Each cell is updated using a kernel which is very similar to an image processing kernel. For example, this kernel

Coupled Cellular Automata kernel

is like a weighted blur image processing kernel.

Initialise a value to 0. The current cell value is multiplied by 4 and added to the total. The north, south, east and west neighbour cell values are mutlipled by 2 and added to the total. The corner cell values are mutliplied by 1 and added to the total.

Depending on which of the 3 CA layers is being processed, the value is updated by

case level of
0:value:=value div k1total-(c[2,x,y] mod k1mod+1);
1:value:=value div k2total-(c[0,x,y] mod k2mod+1);
2:value:=value div k3total-(c[1,x,y] mod k3mod+1);
end;

k1total, k2total and k3total are the total of all the kernel values. For the above kernel the total value is 16 (4+2+2+2+2+1+1+1+1).

k1mod, k2mod and k3mod are the 3 “Mod value” settings that can be customised.

The value is also modified by using the cell value in another layer. This gets the CAs feeding through each other and causes the multiple layered look of the CA.

Once you have the new value for the cell, it is then kept within the range of 0 to 255 by the Wrap Method. The 3 wrap methods (Mod, Inverse and Clamp) make the following changes to the value

case wrapmethod of
0:value:=value mod 255;
1:if value > 255 then value:=-255 else if value < -255 then value:=255;
2:if value > 255 then value:=255 else if value < -255 then value:=-255;
end;

At this stage you now have a new value for the cell. Put this cell into a temp array and then swap the temp array into the cell array once all cells are processed (like any other CA you want to update all the cells simultaneously).

Repeat the above steps as long as you need to.

Display Methods

You now have the 3 CA layers updated with their new values. I use 3 different methods to display the CA.

1. Color Palette. Index a 256 color palette with abs(c[0,x,y]+c[1,x,y]+c[2,x,y] div 3) mod 255;

2. RGB. Convert the layer values to a color by using RGB(abs(c[0,x,y]),abs(c[1,x,y]),abs(c[2,x,y]));

3. YUV. Pass the layer values as YUV into a YUV to RGB converter routine YUVtoRGB(abs(c[0,x,y]),abs(c[1,x,y])-128,abs(c[2,x,y]-128),r1,g1,b1);

Results

Here are some more example kernels and the resulting images. The settings dialog screen captures also show off the new skinning theme support that Visions Of Chaos now includes.

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Of course like any CA these need to be seen dynamically changing and updating. To see the above samples and others in motion download Visions Of Chaos.

If you are a coder who experiments with the above algorithms and has any other ideas or enhancements let me know.

Jason.

Ant Automata

Langton’s Ant

Langton’s Ant was invented by Christopher Langton in 1986.

Here are the simple steps to generate Langton’s Ant.

1. Start with a blank 2D grid of white cells/pixels.
2. Place a virtual ant in the middle cell.
3. If the ant is on a white cell it turns the pixel black, turns 90 degrees right and then moves one cell forward.
4. If the ant is on a black cell it turns the pixel white, turns 90 degrees left and then moves one cell forward.
5. Step 3 and 4 are repeated for as long as required.

Here is a nice GIF file courtesy of Wikipedia that shows how the first 200 steps of Langton’s Ant evolve.

At first the ant travels around in a roughly blob shaped random pattern, but after a while (around 10,000 steps) the ant starts to build a structured pathway as in the following GIF animation.

Langton's Ant

Structures like that are referred to as highways. The above highway would continue to grow forever on a large enough grid.

Rule strings for a wider variety of Ants

Langton’s Ant can be represented by the rule “RL” which is the direction the ant turns depending on the underlying cell color. R for a black cell and L for a blue cell (as in the above animation).

An extension to Langton’s Ant is to allow more than 2 characters. For example, if you try RRLL as a rule it gives the following cardioid like structure over time (click for a larger detailed image).

Ant Automaton

With more characters in the rule string you use more colors. In the above cardioid example the first R character is black and then the other 3 colors are shaded between a light and dark blue.

A simple way of referring to the different rules is to use a rule number. To get a rule number, you follow these steps;

1. Convert the rule string into a binary string. RRLL -> 1100.
2. Convert that binary string into a decimal number. 1100 = 12.

Here are some other examples with their rule numbers showing the variety of patterns that can emerge from these very simple rules. Click on each of the images to see the higher resolution originals.

Rule 9
Ant Automaton

Rule 262 – Diagonal scaffolding like structures
Ant Automaton

Rule 908 – Builds a rougher jagged highway
Ant Automaton

Rule 1080 – Spiral
Ant Automaton

Rule 8383 – Build Sierpinski Triangle patterns as it grows
Ant Automaton

There are more examples in my Ant Automaton Gallery.

3D Ant Automata

The next logical step was to extend into 3D space. I was trying to work out how to handle and program an ant turning in 3 dimensions when I came across Dr Heiko Hamann‘s page on 3D Langton’s Ants. He generously provides some source code here that has the required matrix manipulation required to get the ant turning in 3D space. Have a look if you are interested in implementing your own 3D version of Langton’s Ant.

Once I got the code working I ran a brute force search over the first 20,000 rule numbers. It is harder to see structures within the blobs of random that tend to emerge, but a few interesting results did occur. One thing you get is a lot of very basic highways, so the same emergence of highways in 2D does carry over to 3D.

Here are a few examples I found so far and their corresponding rule numbers. Click to see the larger original images.

Rule 318 – An example of one of the many highways
Ant Automaton

Rule 1042 – Creates more cubic structures and then builds a vertical highway
Ant Automaton

Rule 4514 – Slowly builds a complex vertical highway
Ant Automaton

Rule 6046 – Builds a vertical sprouting highway from a virtual seed
Ant Automaton

Rule 6738 – Corkscrew highway
Ant Automaton

Rule 9513 – Zigzag highway
Ant Automaton

Rule 10952 – After a long time building a seemingly random blob it starts generating a triangle shaped highway
Ant Automaton

Rule 17416 – Generates plate like interlocking 3D puzzle pieces and then a complex highway
Ant Automaton

OBJ Export

Visions Of Chaos also supports exporting the 3D Ant Automata to OBJ files. Here are some examples of 3D Ants exported to OBJ files and imported into and rendered in Blender. I really am a total amateur with Blender but these images show some potential with nice ambient occlusion.

3D Ant Automaton

3D Ant Automaton

3D Ant Automaton

Experiment with Ant Automata

If you want to see any of these automata being built or want to experiment with other rules, download Visions Of Chaos.

If you find any new interesting rules let me know.

Jason.

Yin Yang Fire

Yin Yang Fire

Back around 1999 Jack Ruijs discovered a cellular automaton he named Yin Yang Fire. See here for his explanation. Unfortunately he decided to keep the formula a secret after being ignored by “several universities/persons that are working on the field of self organizing system / computer-algorithms etc” so he has never shared the methods that create his Yin Yang Fire images.

Yin Yang Fire

Yin Yang Fire

I remembered Yin Yang Fire again when I stumbled across this forum post by MackTuesday that has some code he discovered to generate the Yin Yang Fire. Ignoring the name calling and insults, here is the snippet of source code he provides.


// The number of states is 64. In memory they take the values 0-63.
int me = cellsBuffer[x][y];
int result = me;
// cellSum is the sum of the states of the 8 neighbors plus the central cell
// numStates = 64
if (me * 9 + 2 >= cellSum) {
result = result - 1;
if (result < 0) {
result = numStates - 1;
}
}
else {
result = me + 1;
}
return result;

For those of you who have played with cellular automata in the past then this method will be fairly familiar. Update each cell using its value and the total of its 8 neighbours. What is new is the update rule


if (me * 9 + 2 >= cellSum) {
result = result - 1;
if (result < 0) {
result = numStates - 1;
}
}
else {
result = me + 1;
}

If you run the rule as is you get a lot of color cycling and flashing as the cell states decrease to 0 and then wrap around to numstates again. This is shown in the following GIF aniumation.

Yin Yang Fire

To avoid the pulsating/strobing updates you can update the display every n calculated frames. A good formula I found is to use numstates*1.5 steps between display. So for example the default of 64 states should be shown on screen every 64*1.5 or 96 steps. This gives a smoother (but faster) output as shown in the following GIF.

Yin Yang Fire

There is a Long term state vector diagram on this page that shows a variation dropoff around 50000 steps. None of my tests could replicate this, but Thorsten Ewert has been able to confirm that the same drop off does occur using the algorithms shown above.

Yin Yang Fire

Alternate neighbourhoods can also be used. This next one used a Von Nuemann (N S E W neighbours only)

Yin Yang Fire

If you are an enthusiast of cellular automata reading this, do experiment and let me know about any further discoveries here (without keeping it a secret for 15 years!)

Yin Yang Fire

The latest version of Visions Of Chaos now supports YIn Yang Fire cellular automata and I also hacked together a quick online GLSL shader version here that you can run in your browser. It seems to run best under Chrome.

Since writing this post I was contacted by Thorsten Ewert who has done more investigations into the Yin Yang Fire CA. See his page here for more information. Thanks Thorsten.

Jason.

JavaScript Cellular Automata

Over the last few days I have started learning JavaScript. Creating a simple 2D cellular automata seemed like a good start.

The cells in an outer totalistic CAs get updated based on their 8 immediate neighbouring cells surrounding them. The most famous example would be John Conway‘s Game Of Life.

To see the results of the Outer Totalistic Cellular Automata click here. A bit of CSS to pretty things up and there it is. There is a drop down list of preset rules to show the sorts of emergent behavior that can arise from cellular automata.

If you are interested, the source code is available here.

So far JavaScript has been a relatively pleasant experience. Most of my time was spent on the “how to do” rather than the “what to do”. Once you know the basics of programming any new language mostly comes down to syntax.

Jason.

Multiphase Smoothed-Particle Hydrodynamics

Smoothed-Particle Hydrodynamics (SPH) is a method of simulating fluid flow. It is based on representing a fluid by a large number of discreet (individual) particles. Each particle has properties like position, pressure, density, mass, etc. The particles are fed through a bunch of equations that make them move in a fluid like flow.

If you are a maths nerd then one of the better and recommended papers for SPH fluids is Particle-based Viscoelastic Fluid Simulation.

Multiphase SPH is when you have 2 or more fluids with different densities etc (think oil and water) that flow around each other and clump together.

I have always had a fascination with simulating fluids. Over the years I have tried to understand SPH and have had many failed attempts at writing programs to do it (the basic formulas seem relatively simple, but getting the code to run stable without explosions and crashes is far from simple). Then I found this blog post by Tom Madams that had sample source code. With that I was finally able to get SPH working. It can still be fiddly to find a nice set of parameters to make a nice looking movie, but Tom’s code seems to be a great start. Thanks Tom!!

Multiphase SPH is now available in Visions Of Chaos.

A future release will include 3D support.

Jason.

Cyclic Cellular Automata

Cyclic Cellular Automata were first developed by David Griffeath at the University of Wisconson.

The rules are relatively simple;

1. Take a 2D grid of cells.
2. Select a maximum number of states each cell can have.
3. Select a threshold value.
4. Fill the cells with random state values between 0 and (maximum states-1).
5. At each step of the simulation every cell follows these rules;
a) Count how many neighbouring cells (Moore or Von Neumann neighborhoods) surrond the cell with a value of the current cell’s state + 1
b) If the count is greater or equal to the threshold value then the cell state is incremented by 1
6. Repeat this process as long as you want to.

By following those steps you can get emergent behaviour of spirals and other patterns. Here are a few examples (click the title to watch it in HD format on YouTube);

The different rules (every 10 seconds) in the above video are;
313 (David Griffeath)=1/3/3/M
Amoeba (Jason Rampe)=3/10/2/N
Black vs White (Jason Rampe)=5/23/2/N
Black vs White 2 (Jason Rampe)=2/5/2/N
Boiling (Jason Rampe)=2/2/6/N
Bootstrap (David Griffeath)=2/11/3/M
CCA (David Griffeath)=1/1/14/N
Cubism (Jason Rampe)=2/5/3/N
Cyclic Spirals (David Griffeath)=3/5/8/M
Diamond Spirals (Jason Rampe)=1/1/15/N
Fossil Debris (David Griffeath)=2/9/4/M
Fuzz (Jason Rampe)=4/4/7/N
Lava Lamp (Jason Rampe)=3/15/3/M
Lava Lamp 2 (Jason Rampe)=2/10/3/M
Maps (Mirek Wojtowicz)=2/3/5/N
Perfect Spirals (David Griffeath)=1/3/4/M
Stripes (Mirek Wojtowicz)=3/4/5/N
Turbulent Phase (David Griffeath)=2/5/8/M
The 2/5/8/M refers to Range/Threshold/States/Neighborhood.

The same principle works in 3D too. You just need to expand the neighborhood checks to cover 3D space.

2D and 3D CCA are now included in the latest version of Visions Of Chaos.

Jason.