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.

3D Cellular Automata

Cellular Automata (or CA as they are often abbreviated to) have insterested me for many years (at least as long as I had an interest in fractals or maybe longer). I can still remember writing my first serious code in Turbo Pascal and being amazed at the patterns that arose from John Conway’s Game Of Life. Cellular Automata are a great example of complexity and emergence arising from simple rules.

3D CA have been implemeted in Visions Of Chaos for years, but only in a 2 state version (ie each cell is either dead or alive). Here is an older low resolution example of some of the 2 state rules I found (this used to be “high resolution” on YouTube).

I revisited the 3D CA code when testing the new JPS support in Visions Of Chaos. The most obvious progression was to allow more than 2 states per cell. This leads to more interesting results (but also a much larger possible search space to try and find good rules within).

Here are a few of the multi-state 3D Cellular Automata rules I found while testing the new 3D CA code. They are all based on the surrounding Moore neighborhood 26 cells.


4 4 5
Survival 4
Birth 4
Number Of States 5
This rule can be difficult to get started and develop (as this movie shows), but once past the initial deadness it develops many gliders and other shapes.


Amoeba 3
Survival 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26
Birth 5,6,7,12,13,15
Number Of States 5
This one has slow growth using bulbous pulsating arms to grow. Rarely it will sprout a thin diagonal growing arm from the main body that will continue to spread until it hits a wall or other active cell(s).


Coral
Survival 4,5,6,7
Birth 6,7,8,20
Number Of States 4
Trying to get coral like growth. I have tweaked this one for hours and cannot seem to get a nice realistic coral result.


Jason’s Brain
Survival 4
Birth 4,8
Number Of States 5
Very similar to 4 4 5. Found when I was trying to find a 3D version of Brian’s Brain (hence the name).


Pyroclastic
Survival 4,5,6,7
Birth 6,7,8
Number Of States 10
Expanding rule. Reminded me of footage of pyroclastic flows from volcanos.

Finding good or interesting rules is not easy, so if you have any new rules let me know. Just comment on this post and give the details.

Finding ways to display 3D Cellular Automata can be difficult. The main issue faced is if the rule causes a dense cluster of particles you only get to see the outside and the inside of the structure(s) remian hidden. Some options I experimented with are only rendering state 1 (ie cells that have just been born) cells, and rendering the display with a chunk of cells cut out of it to see inside.

A quick side tip for other programmers. If you are rendering a large grid of 3D cubes in OpenGL you can work out which sides of each cube touch another cube and then skip passing these faces to OpenGL. The overhead of coding the face checks gives a huge speedup when there are a large amount of cubes on screen.

Jason.