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.

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

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.

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.

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).

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

Rule 262 – Diagonal scaffolding like structures

Rule 908 – Builds a rougher jagged highway

Rule 1080 – Spiral

Rule 8383 – Build Sierpinski Triangle patterns as it grows

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

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

Rule 4514 – Slowly builds a complex vertical highway

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

Rule 6738 – Corkscrew highway

Rule 9513 – Zigzag highway

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

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

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.

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.