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 