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 principle works in 3D too. You just need to expand the neighborhood checks to cover 3D space.

The following movie hides cells outside a sphere shape. The CA grid is 300x300x300 cells in size.

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.

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

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