Cyclic Cellular Automata

2D 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.

2D OpenGLSL Shader Code

Getting a GLSL version of CCA working was a real pain. See the comments for past attempts.

Finally I did manage to get the shader code working for all possible rules.

The current version of the code is in Visions of Chaos and also runnable in your browser here.

3D Cyclic Cellular Automata

The same principles work in 3D too. You just need to expand the neighborhood checks to cover 3D XYZ space.

Here is one of my earliest 3D CCA movies.

This next one still uses the cubic 3D space for the cellular automata, but hides the cells outside a sphere shape.

That movie is better, but there are still problems with it.

Firstly, I used software OpenGL rendering which does not support shadows. I am hiding state 0 cells (as well as the cells outside the sphere) but without proper lighting it is hard to see within the cavities. The fix for this is to use a better rendeing engine. I use and recommend Mitsuba Renderer. Mitsuba gives the awesome ambient occlusion shading that really allows you to see the 3D structures. Mitsuba is much slower than software OpenGL (depending on the number of little spheres being rendered some of the frames can take a few minutes each), but the results are so much nicer.

The next fix came from a Twitter idea from Nathaniel Virgo

These are the methods I tried to hide further cells inside the displayed array to see the inner structures better;

1. If any cell state has a different state neighbor (moore or von neumann neighborhoods) then it can be hidden. This hides the “seams” between cell states.

2. If any cell state is greater than 1 difference from any neighbor then it is shown, otherwise hidden. For example if the current cell is state 5 then if the surrounding cells are between states 4 and 6 then it is hidden, otherwise it is shown. This method is even better. It cuts down each CCA area into thin “stripes” that really see their shapes and structures more clearly.

The CCA itself still runs the same, you are just hiding certain cells at the display stage. If you use the second trim method with a 3 state array (states 0, 1 and 2) you will only get a plot of state 2 cells as the difference between state 1 and states 0 and 2 can never be greater than 1.

So after a good week or so of rendering, I had the parts of a movie ready to combine and upload to YouTube.

This leads to the next problem of frame rate. These 3D CCAs tend to visually run very fast with the spiral structures rapidly changing. If you wantch the above two sample 3D CCA movies you will notice the movement is a bit too fast to appreciate the structures evolving as the CA runs.

You can use the YouTube playback speed setting and set it to 0.5 (or I could set the movie to 15 fps), but this results in a very jerky playback rate.

Then I tried Butterflow. Instructions here. This smoothly interpolates frames and halves the speed. More than just adding a blended frame between each frame, Butterflow uses motion interpolation that blends the movement within the frames.
butterflow -o output.mp4 -r 2x input.mp4
The resulting output results in smoother flow that gives you time to peer within the CA. I added a quick soundtrack composed in FL Studio and the movie was ready to upload.

Note that this movie is the same CCA rules as the last 2 above, just using the more optiomal ways of displaying what’s going on inside.

Trimming the visible cells within the CA structure before display is a great idea that I have not used before. I will have to experiment using it with the other 3D and 4D cellular automata in Visions of Chaos.

4D Cyclic Cellular Automata

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

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

Jason.

5 responses to “Cyclic Cellular Automata

  1. Hi, I am trying to implement cyclic CA in GLSL, but I keep having trouble with how to initialize and choose from a set of colors. Any tips for implementation? Thanks!

    • This is surprisingly difficult to implement. I have been hacking away for a few hours trying all sorts of variations and cannot get a reliable result. Did you have any luck in the end?
      See here for my latest attempt
      https://softology.com.au/CCAShader.glsl
      If you put the mouse to the left side of the shader it clears the screen and then dragging the mouse puts a random path down that does kind of follow a CCA development, but the pattern is all wrong. Maybe something with all the int to float handling. If you get anywhere, let me know. If I work it out I will update this with a new reply.

      • Hi,

        Thanks for the reply. I think I got something working. I’m not super familiar with GLSL, but it seems to follow the correct behavior for some of the rules, but not others. For example, R2T9C4Moore does not look correct. Below is the GLSL code:

        uniform vec2 u_resolution;
        // uniform vec3 u_mouse;
        uniform sampler2D u_currentTexture;
        uniform int u_frameCount;
        // uniform float u_mouseSize;
        uniform int u_paused;
        uniform float u_time;
        uniform int u_t; // threshold
        uniform int u_r; // range
        uniform int u_c; // number of states
        uniform bool u_moore; // moore on

        highp float rand(vec2 co)
        {
        // random function
        highp float a = 12.9898;
        highp float b = 78.233;
        highp float c = 43758.5453;
        highp float dt= dot(co.xy ,vec2(a,b));
        highp float sn= mod(dt,3.14);
        return fract(sin(sn) * c);
        }

        float v(float xrel, float yrel) {
        // get red value of state relative to (0, 0)
        vec2 xy;
        xy.x = mod(gl_FragCoord.x + xrel, u_resolution.x);
        xy.y = mod(gl_FragCoord.y + yrel, u_resolution.y);
        return texture2D(u_currentTexture, xy/u_resolution).r;
        }

        float getNextColor() {
        // get the value of the current color + 1
        for (int i = 0; i < 19; ++i) {
        if (u_c == i) {
        break;
        }
        float d = float(u_c – 1);
        if (abs(v(0.,0.) – float(i) * 1. / d) < .01) {
        float nextColor = float(i) * 1. / d + 1. / d;
        if (abs(nextColor – 1. – 1./d) < 0.01) {
        nextColor = 0.0;
        }
        return nextColor;
        }
        }
        }

        int neighborSum() {
        int count = 0;
        float nextColor = getNextColor();
        if (u_moore) {
        for (int x = 0; x < 22; ++x) {
        if (x == u_r * 2 + 1) {
        return count;
        }
        for (int y = 0; y < 22; ++y) {
        if (y == u_r && x == u_r) {
        continue;
        }
        if (y == u_r * 2 + 1) {
        break;
        }
        if (abs(v(float(x – u_r), float(y – u_r)) – nextColor) < .001) {
        count = count + 1;
        }
        }
        }
        } else {
        if (abs(v(-1., 0.) – nextColor) < .01) {
        count = count + 1;
        }
        if (abs(v(1., 0.) – nextColor) < .01) {
        count = count + 1;
        }
        if (abs(v(0., 1.) – nextColor) < .01) {
        count = count + 1;
        }
        if (abs(v(0., -1.) – nextColor) < .01) {
        count = count + 1;
        }
        }
        return count;
        }

        float mod2(float f) {
        float d = float(u_c – 1);
        float nextColor = float(v(0.,0.)) * 1. / d + 1. / d;
        if (abs(nextColor – 1. – 1./d) < 0.01) {
        nextColor = 0.0;
        }
        return nextColor;
        }

        void main()
        {
        float d = float(u_c – 1);
        float minRes = min(u_resolution.x, u_resolution.y);
        vec2 uv = (gl_FragCoord.xy – 0.5 * u_resolution.xy) / minRes;
        // float inputSize = u_mouseSize / minRes;
        float fate = v(0.,0.);
        // float before = fate;
        if(u_frameCount float(u_t) || abs(sum – float(u_t)) < .01) {
        fate = getNextColor();
        } else {
        fate = v(0.,0.);
        }
        }
        gl_FragColor = vec4(fate, .2, .4, 1.);
        }

        Hopefully this makes sense. I would really like some help figuring out why for most patterns my code doesn't work. It does work for R1T1C14VonNeumann, however. Also, I'm not sure if this was necessary, but in all the if statements where I compare if something is less than .01, this is a replacement for checking equality. I found that sometimes just checking if floats are equal to 0 didn't work for some reason, and this is a solution I found online. I also was not able to use variables to initialize for loops, so I had to find a workaround. If there's any easier method, please let me know. Any suggestions or fixes would be greatly appreciated!

    • I revisited this GLSL code today after many months. I was able to get it working.
      http://glslsandbox.com/e#60621.0
      BUT, like your code rules with a large number of states (in this case >5) do not work?!
      Really odd. The code should allow enough states to be represented as floats between 0 and 1. I use the alpha channel for state storage.
      Anyway, maybe someone will fix it. I am going to update this post asking for any help too.

      Jason.

  2. Pingback: Time in the cellular machine / geek magazine – Developers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s