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.
Softology's Blog 
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.
Pingback: Time in the cellular machine / geek magazine – Developers
Hi, I am trying to implement a Cyclic Spirals (David Griffeath) cellular automaton. But I am unable to get the spirals. For each cycle, I create a new grid (temporary), copy each cell’s state into the temporary grid. But for the ones which has neighbours with state = currentState + 1, I copy the next state. Then I copy the temporary grid to the original grid. Is there any other rules that I’m not considering. I don’t understand what the 3 in 3/5/8/M means. I read that it’s the range. But I don’t quite get it.
See the initial steps in the post. You count all neighbors with a value of currentState+1 and then check if that count is greater than a threshold value. If the count is greater than threshold you increment the current cell, otherwise it remains the same state.
The 2/5/8/M refers to Range/Threshold/States/Neighborhood.
Range is how far the neighborhood extends from the current state. For the immediate 8 neighbor cells this is a “Moore neighborhood” range 1. If you extended the range out another cell then it would be the 24 surrounding cells that are counted. Von Neumann is a more diamond shape neighborhood. See the links in the blog post for the difference between Moore and Von Neumann.
https://ibb.co/0ZD8yhh
Hi Thank you for the reply.
This is the pattern that I’m getting. Have you some across this? I am using exact same rules.
Maybe your neighborhood area is wrong. If you post a snippet of your inner cell processing code I may be able to spot the problem.
Hi, I have sent it as e-mail. I am unable to post the code here.
hi, I read your article after I made similar experiments here:https://www.shadertoy.com/view/wlsBWB
in my case the CA is applied on the surface of the sphere; here I also used the values as altitude:https://www.shadertoy.com/view/ws3yzXhttps://www.shadertoy.com/view/WsdyDS