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.

3 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!

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