Voxel Automata Terrain

Voxel Automata Terrain

Brent Werness aka @R4_Unit tweeted about an algorithm he calls “Voxel Automata Terrain” that creates interesting 3D structures. He also provides some processing source code I was able to translate so I had to have a go at creating some of these myself.

Voxel Automata Terrain

These structures are created using a process similar to the diamond-square algorithm but in 3D. A 3D cube is repeatedly iterated and divided to leave these structures behind. I don’t really understand it beyond that so I cannot give a better explanation at this time.

Voxel Automata Terrain

The code for dividing the cube up is the first parts of Brent’s code. Mostly everything after the evaledges routine is display related.

Voxel Automata Terrain

For my images I use the states array to render solid cubes using the Mitsuba renderer. State 1 and state 2 cells can be shown or hidden and displayed using different colors.

Voxel Automata Terrain

I also setup a flickr gallery with more example images.

Voxel Automata Terrain

Voxel Automata Terrain

If you start the process without a random side and fill the initial base side with all state 1 or state 2 cells you get symmetric structures as a result.

Voxel Automata Terrain

Voxel Automata Terrain

Voxel Automata Terrain

I also tried extending the maximum possible cell states to 4. The rule arrays need to be changed to three dimensional. From some initial quick searches (a few hundred of the possible 4 billion rules) did not lead to any new unique structures, but it does add another color to the mix.

Voxel Automata Terrain

Voxel Automata Terrain

Voxel Automata Terrain

Here is a movie showing some samples with ncreasing levels of detail/recursion.

Voxel Automata Terrain are now available as part of the latest version of Visions of Chaos.

Jason.

The Belousov-Zhabotinsky Reaction and The Hodgepodge Machine

Inspiration for this post

The other day I saw this YouTube video of a Belousov-Zhabotinsky Cellular Automaton (BZ CA) by John BitSavage

After a while of running in an oscillating state it begins to grow cell like structures. I had never seen this in BZ CAs before. I have seen similar cell like growths in Digital Inkblot CAs and in the Yin Yang Fire CA. Seeing John’s results different to the usual BZ CA was what got me back into researching BZ in more depth.

The Belousov-Zhabotinsky Reaction

Belousov-Zhabotinsky Reactions (see here for more info) are examples of a chemical reactions that can oscillate between two different states and form intetesting patterns when performed in shallow petri dishes.

Here are some sample high res images of real BZ reaction by Stephen Morris. Click for full size.

Belousov-Zhabotinsky Reaction

Belousov-Zhabotinsky Reaction

Belousov-Zhabotinsky Reaction

and some other images from around the Internet

Belousov-Zhabotinsky Reaction

Belousov-Zhabotinsky Reaction

Belousov-Zhabotinsky Reaction

Belousov-Zhabotinsky Reaction

and some sample movies I found on YouTube

The Hodgepodge Machine Cellular Automaton

Back in August 1988, Scientific American‘s Computer Recreations section had an article by A. K. Dewdney named “The hodgepodge machine makes waves”. After a fair bit of hunting around I could not find any copies of the article online so I ended up paying $8 USD to get the issue in PDF format. The PDF is a high quality version of the issue, but $8 is still a rip off.

In the article Dewdney describes the “hodgepodge machine” cellular automaton designed by Martin Gerhardt and Heike Schuster of the University of Bielefeld in West Germany. A copy of their original paper can be seen here.

How the Hodgepodge Machine works

The inidividual cells/pixels in the hodgepodge automaton have n+1 states (between 0 and n). Cells at state 0 are considered “healthy” and cells at the maximum state n are said to be “ill”. All cells with states inbetween 0 and n are “infected” with the larger the state representing the greater level of infection.

Each cycle of the cellular automaton a series of rules are applied to each cell depending on its state.

(a) If the cell is healthy (i.e., in state 0) then its new state is [a/k1] + [b/k2], where a is the number of infected cells among its eight neighbors, b is the number of ill cells among its neighbors, and k1 and k2 are constants. Here “[]” means the integer part of the number enclosed, so that, for example, [7/3] = [2+1/3] = 2.

(b) If the cell is ill (i.e., in state n) then it miraculously becomes healthy (i.e., its state becomes 0).

(c) If the cell is infected (i.e., in a state other than 0 and n) then its new state is [s/(a+b+1)] + g, where a and b are as above, s is the sum of the states of the cell and of its neighbors and g is a constant.

The parameters given for these CA are usual q (for max states), k1 and k2 (the above constants) and g (which is a constant for how quickly the infection tends to spread).

My previous limited history experimenting with BZ

Years ago I implemented BZ CA in Visions of Chaos (I have now correctly renamed the mode Hodgepodge Machine) and got the following result. This resolution used to be considered the norm for YouTube and looked OK on lower resolution screens. How times have changed.

The above run used these parameters
q=200
k1=3
k2=3
g=28

Replicating Gerhardt and Miner’s results

Gerhadt and Miner used fixed values of k1=2 and k2=3. The majority of their experiments used a grid size of q=20 (ie only 20×20 cells) without a wraparound toroidal world. This leaves the single infection spreading g variable to play with. Their paper states they used values of g between 1 and 10, but I get no spirals with g in that range.

Here are a few samples which are 512×512 sized grids with wraparound edges and many thousands of generations to be sure they had finally settled down. Each cell is 2×2 pixels in size so they are 1024×1024 images.

Hodgepodge Machine

q=100, k1=2, k2=3, g=5

Hodgepodge Machine

q=100, k1=2, k2=3, g=20

Hodgepodge Machine

q=100, k1=2, k2=3, g=25

Hodgepodge Machine

q=100, k1=2, k2=3, g=30

Results from other parameters

Hodgepodge Machine

q=100, k1=3, k2=3, g=10

Hodgepodge Machine

q=100, k1=3, k2=3, g=15

Hodgepodge Machine

q=100, k1=3, k2=3, g=20

Extending into 3D

The next logical step was extending it into three dimensions. This blog post from Rudy Rucker shows a 3D BZ CA from Harry Fu back in 2004 for his Master’s degree writing project. I must be a nerd as I whipped up my 3D version over two afternoons. Surprisingly there are no other references to experiments with 3D Hodgepodge that I can find.

The algorithms are almost identical to their 2D counterparts. The Moore neighborhood is extended into three dimensions (so 26 neighbors rather than 8 in the 2D version). It is difficult to see the internal structures as they are hidden from view. Methods I have used to try and see more of the internals are to slice out 1/8th of the cubes and to render only some of the states.

Clicking these sample images will show them in 4K resolution.

3D Hodgepodge Machine

q=100, k1=1, k2=18, g=43 (150x150x150 grid)

3D Hodgepodge Machine

q=100, k1=1, k2=18, g=43 (150x150x150 grid – same as previous with a 1/8th slice out to see the same patterns are extending through the 3D structure)

3D Hodgepodge Machine

q=100, k1=1, k2=18, g=43 (150x150x150 grid – same rules again, but this time with only state 0 to state 50 cells being shown)

3D Hodgepodge Machine

q=100, k1=2, k2=3, g=15 (150x150x150 grid)

3D Hodgepodge Machine

q=100, k1=3, k2=6, g=31 (150x150x150 grid)

3D Hodgepodge Machine

q=100, k1=4, k2=6, g=10 (150x150x150 grid)

3D Hodgepodge Machine

q=100, k1=4, k2=6, g=10 (150x150x150 grid – same rules as the previous image – without the 1/8th slice – with only states 70 to 100 visible)

3D Hodgepodge Machine

q=100, k1=3, k2=31, g=43 (250x250x250 sized grid – 15,625,000 total cells)

3D Hodgepodge Machine

q=100, k1=4, k2=12, g=34 (350x350x350 sized grid – 42,875,000 total cells)

3D Hodgepodge Machine

q=100, k1=1, k2=9, g=36 (400x400x400 sized grid – 64,000,000 total cells)

Download Visions of Chaos if you would like to experiment with both 2D and 3D Hodgepodge Machine cellular automata. If you find any interesting rules please let know in the comments or via email.

More experiments with Coupled Cellular Automata

Make sure you click the images in this post to see them in full 4K resolution. The thumbnails do not do them justice and hide a lot of the multi-scaled structures within them.

Coupled Cellular Automaton

After my original attempt to replicate Jonathan McCabe‘s Coupled Cellular Automata results I was contacted by Ian McDonald with some questions about how my original algorithms worked and that inspired both of us to make another attempt at getting McCabe like results.

Coupled Cellular Automaton

With some back and forth and some hints from Jonathan we were able to get a little further towards replicating his images.

Coupled Cellular Automaton

How the McCabe algorithms work

Jonathan has provided some hints to how his Coupled CA work in the past.

Firstly from here;

Each pixel represents the state of the 4 cells of 4 cellular automata, which are cross coupled and have their individual state transition tables. There is a “history” or “memory” of the previous states which is used as an offset into the state transition tables, resulting in update rules which depend on what has happened at that pixel in previous generations. Different regions end up in a particular state or cycle of states, and act very much like immiscible liquids with surface tension.

Coupled Cellular Automaton

and secondly from here;

The generative system involves four linked cellular automata – think of them as layers. “Linked” because at each time step, a cell’s state depends both on its neighbours in that layer, and on the states of the corresponding cells in the other three layers. Something like a three-dimensional CA, but not quite; the four layers influence each other through a weighted network of sixteen connections (a bit like a neural net). The pixels in the output image use three of the four CA layers for their red, green and blue values.

As in a conventional CA, each cell looks to its neighbours to determine its future state. This is a “totalistic” CA, which means each simply sums the values of its neighbours, then changes its state based on a table of transition rules. Now for the really good part: each cell also uses its recent history as an “offset” into that transition table. In other words, the past states of a cell transform the rules that cell is using. The result is a riot of feedback cycles operating between state sequences and rulesets; stable or periodically oscillating regions form, bounded by membrane-like surfaces where these feedback cycles compete. Structures even form inside the membranes – rule/state networks that can only exist between other zones.

Coupled Cellular Automaton

After emailing him he did provide a few more more clues to how his Coupled CA work which did help me get to the point I am at now.

How the “inner loop” behaves and how the 4 (or more) CA layers are actually processed and combined is still a mystery, but this is a hint;

“Cross-Coupled” is a matrix multiply to give 4 numbers from 4 numbers. If the matrix was “1.0” diagnally and “0.0” elsewhere you have zero coupling. If the zeros are replaced with other values you get cross-coupling of various amounts. If the cross coupling is very low you have 4 independant systems, if it is very high you get effectively one system, I think there is a sweet spot in between where they influence each other but don’t disappear into the mix.

And regarding the history;

The history or memory is an average of previous states at that cell. You can do it a few ways, say as a decaying average, adding the current state and multiplying by 0.99 or some number, so the memory fades. The memory is added to the index to look up the table, so you actually need a bigger table than 9*256.

Coupled Cellular Automaton

How my version works

Here are the basic steps to how I created the images within this post. Note that this is not how the McCabe CA works, but does show some similarities visually to his.

The CA is based on a series of CA layers. Each layer/array constains byte values (0-255) and is initialised with random noise. You need a minimum of 4 layers, but any number of layers can be used.

You also need a set of lookup tables for each layer. The lookup tables are 1D arrays containing byte values (0-255). They each have 256*10 entries. The arrays are filled using multiple sine waves combining different frequencies and amplitudes which are then normalised into the 0-255 range. You want to have smallish changes between the lookup table entries.

256*10 entries in the lookup table is because in the McCabe CA the current cell, its 8 neighbours and the history of that cell are used to index the lookup table. That gives 10 possible values between 0 and 255 which are totalled to index the lookup table. For the method I discuss in this blog post, you really only need a lookup table with 256 entries as the index maths never goes betyond 0 to 255. BUT I still use the larger sized array to stretch the sine waves further/more smoothly across the tables. Note you can also change the “*10” size to a larger number to help smooth out the resulting CA displays even more. Experiment with different values.

Coupled Cellular Automaton

Now for the main loop.

1. Blur each layer array. Gaussian blur can be used but tends to be slow. Using a faster 2 pass blur as described here works just as well for this purpose. Make sure the blur radius has a decent amount of difference between layers, for example 1, 10, 50, 100. These large differences in blur amounts is what leads to the resulting images having their detail at many scales appearance.

Coupled Cellular Automaton

2. Process the layers. This is the secret step that Jonathan has not yet released. I tried all sorts of random combinations and equations until I found the following. This is what I use in the images for this post.

for i:=0 to numlayers-1 do t[i,x,y]:=c[i,x,y]+lookuptable[i,trunc(abs(h[(i+1) mod numlayers,x,y]-c[(i+2) mod numlayers,x,y]))];

That allows for any number of layers, but to show the combinations simpler, here it is unrolled for 4 layers


t[0,x,y]:=c[0,x,y]+lookuptable[0,trunc(abs(h[1,x,y]-c[2,x,y]))];
t[1,x,y]:=c[1,x,y]+lookuptable[1,trunc(abs(h[2,x,y]-c[3,x,y]))];
t[2,x,y]:=c[2,x,y]+lookuptable[2,trunc(abs(h[3,x,y]-c[0,x,y]))];
t[3,x,y]:=c[3,x,y]+lookuptable[3,trunc(abs(h[0,x,y]-c[1,x,y]))];

t is a temp array. Like all CAs you put the results into a temp array until the whole grid is processed and then you copy t back to c
c is the current CA layers array
lookuptable is the array created earlier with the combined sine waves
h is the history array, ie what the c array was last cycle/step

An important step here is to blur the arrays again once they have been processed. Using just a radius 1 gaussian is enough. This helps cut down the noise and speckled nature of the output.

Coupled Cellular Automaton

3. Display. So now you have 4 byte vlaues (one for each layer) for each pixel. How can you convert these into a color to display? So far I have used these methods;

Color palette – Average the 4 values and use them as an index into a 256 color palette.

RGB – Use the first 3 layers as RGB components.

YUV – Use the first 3 layers as YUV components and then convert into RGB.

Matrix coloring – This deserves a larger section below.

Coupled Cellular Automaton

Matrix coloring

If you use just RGB or YUV conversions the colors tend to be a bit bland and unexciting. When I asked Jonathan how he got the amazing colors in his images he explained that the layers can be multiplied by a matrix. Now, in the past I had never really needed to use matrices except in some OpenGL code (and even then OpenGL handles most of it for you) but a quick read of some online tutorials and I was good to go.

You take the current cell values for 3 layers and multiply them by a 3×3 matrix


              [m2 m2 m2]
[m1 m1 m1]  x [m2 m2 m2] = [m3 m3 m3]
              [m2 m2 m2]

or 4 layers multiplied by a 4×4 matrix


                 [m2 m2 m2 m2]
                 [m2 m2 m2 m2]
[m1 m1 m1 m1]  x [m2 m2 m2 m2] = [m3 m3 m3 m3]
                 [m2 m2 m2 m2]

In both cases the m1 array variables are the CA layer values for each of the X and Y pixel locations. I use the first 3 layers, last 3 layers or first layer and last 2 layers. If you use a 4×4 matrix use the first 4 etc. Multiply them by the m2 matrix and get the m3 results.

You can use the m3 results as RGB components to color the pixels (after multiplication the RGB values will be outside the normal 0 to 255 range so they will need to be normalised/scaled back into the 0 to 255 range). For the 4×4 matrix you can use the 4th returned value for something too. I use it for a contrast setting but it doesn’t make that much of a difference.

If the matrix you are multiplying is the identity matrix (ie all 0s with diagonal 1s) the m3 result is the same as the m1 input. If you change the 0s slightly you get a slight change. For the images in this post I have used random matrix values anywhere from -10 to +10 (with and without a forced diagonal of 1s).

Using matrix multiplication to get the wider range of colors is really awesome. I had never seen this method used before and am so grateful of the hint from Jonathan. I am sure it will come in handy in many other areas when I need to convert a set of values to colors.

Another great tip from Jonathan is to do histogram equalisation on the bitmap before display. This acts like an auto-contrast in Photoshop and can really make blander images pop.

Another thing to try is hue shifting the image. Convert each pixel’s RGB values to HSL, shift the H component and then convert back to RGB.

Coupled Cellular Automaton

Once you put all those options together you get might get a dialog with a bunch of settings that looks like the following screen shot.

Coupled Cellular Automaton Dialog

Problem

There is one major issue with this method though. You cannot create a nice smooth evolving animation this way. The cell values fluctuate way too much between steps causing the movie to flicker wildly. To help reduce flicker you can render only every second frame, but the movie still has wild areas. Jonathtan confirmed his method also has the same display results. Coupled Cellular Automata using the method described in this post are best used for single frame images and not movies.

Coupled Cellular Automaton

Help me

If you are a fellow cellular automata enthuisast and have a play with this method, let me know of any advancements you make. Specifically, the main area that can be tweaked is the inner loop algorithm of how the layers are combined and processed. I am really interested in any variations that people come up with.

Coupled Cellular Automaton

Explore it yourself

If you are not a coder and want to experiment with Coupled Cellular Automata they are now included in Visions of Chaos.

To see my complete gallery of Coupled Cellular Automata images click here.

Jason.

Visions Of Chaos for Android updated

Visions Of Chaos for Android

It took a lot longer than I wanted, but the new Visions Of Chaos for Android v1.0 is now available for download. It is 100% free and ad free.

Visions Of Chaos for Android

The main new feature is support for running OpenGL ES shaders on your Android device. There are over 1000 sample shaders included with the app.

Visions Of Chaos for Android

Visions Of Chaos for Android

So, if you own one of the 85% market share Android devices download the app from the Visions Of Chaos for Android web page or directly from Google Play now.

Jason.

Coupled Cellular Automata

Origins

Back in 2007 I was trying to figure out the algorithms behind Jonathan McCabe’s cellular automata pictures. I was never able to determine the algorithm to get the same results and coloring as Jonathan, but this is an explanation of my own Coupled Cellular Automata that arose from trying.

Algorithms

The principal of this method is to have 3 CAs with different settings running mostly independently of each other, but have their values interact with each other to create a new interesting result.

Coupled Cellular Automata settings

To start with you need 3 arrays to keep track of the 3 separate CAs. I used a 3D array to store them, ie c[0,x,y] c[1,x,y] and c[2,x,y].

Each cell is updated using a kernel which is very similar to an image processing kernel. For example, this kernel

Coupled Cellular Automata kernel

is like a weighted blur image processing kernel.

Initialise a value to 0. The current cell value is multiplied by 4 and added to the total. The north, south, east and west neighbour cell values are mutlipled by 2 and added to the total. The corner cell values are mutliplied by 1 and added to the total.

Depending on which of the 3 CA layers is being processed, the value is updated by

case level of
0:value:=value div k1total-(c[2,x,y] mod k1mod+1);
1:value:=value div k2total-(c[0,x,y] mod k2mod+1);
2:value:=value div k3total-(c[1,x,y] mod k3mod+1);
end;

k1total, k2total and k3total are the total of all the kernel values. For the above kernel the total value is 16 (4+2+2+2+2+1+1+1+1).

k1mod, k2mod and k3mod are the 3 “Mod value” settings that can be customised.

The value is also modified by using the cell value in another layer. This gets the CAs feeding through each other and causes the multiple layered look of the CA.

Once you have the new value for the cell, it is then kept within the range of 0 to 255 by the Wrap Method. The 3 wrap methods (Mod, Inverse and Clamp) make the following changes to the value

case wrapmethod of
0:value:=value mod 255;
1:if value > 255 then value:=-255 else if value < -255 then value:=255;
2:if value > 255 then value:=255 else if value < -255 then value:=-255;
end;

At this stage you now have a new value for the cell. Put this cell into a temp array and then swap the temp array into the cell array once all cells are processed (like any other CA you want to update all the cells simultaneously).

Repeat the above steps as long as you need to.

Display Methods

You now have the 3 CA layers updated with their new values. I use 3 different methods to display the CA.

1. Color Palette. Index a 256 color palette with abs(c[0,x,y]+c[1,x,y]+c[2,x,y] div 3) mod 255;

2. RGB. Convert the layer values to a color by using RGB(abs(c[0,x,y]),abs(c[1,x,y]),abs(c[2,x,y]));

3. YUV. Pass the layer values as YUV into a YUV to RGB converter routine YUVtoRGB(abs(c[0,x,y]),abs(c[1,x,y])-128,abs(c[2,x,y]-128),r1,g1,b1);

Results

Here are some more example kernels and the resulting images. The settings dialog screen captures also show off the new skinning theme support that Visions Of Chaos now includes.

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Coupled Cellular Automaton

Of course like any CA these need to be seen dynamically changing and updating. To see the above samples and others in motion download Visions Of Chaos.

If you are a coder who experiments with the above algorithms and has any other ideas or enhancements let me know.

Jason.

Ant Automata

Langton’s Ant

Langton’s Ant was invented by Christopher Langton in 1986.

Here are the simple steps to generate Langton’s Ant.

1. Start with a blank 2D grid of white cells/pixels.
2. Place a virtual ant in the middle cell.
3. If the ant is on a white cell it turns the pixel black, turns 90 degrees right and then moves one cell forward.
4. If the ant is on a black cell it turns the pixel white, turns 90 degrees left and then moves one cell forward.
5. Step 3 and 4 are repeated for as long as required.

Here is a nice GIF file courtesy of Wikipedia that shows how the first 200 steps of Langton’s Ant evolve.

At first the ant travels around in a roughly blob shaped random pattern, but after a while (around 10,000 steps) the ant starts to build a structured pathway as in the following GIF animation.

Langton's Ant

Structures like that are referred to as highways. The above highway would continue to grow forever on a large enough grid.

Rule strings for a wider variety of Ants

Langton’s Ant can be represented by the rule “RL” which is the direction the ant turns depending on the underlying cell color. R for a black cell and L for a blue cell (as in the above animation).

An extension to Langton’s Ant is to allow more than 2 characters. For example, if you try RRLL as a rule it gives the following cardioid like structure over time (click for a larger detailed image).

Ant Automaton

With more characters in the rule string you use more colors. In the above cardioid example the first R character is black and then the other 3 colors are shaded between a light and dark blue.

A simple way of referring to the different rules is to use a rule number. To get a rule number, you follow these steps;

1. Convert the rule string into a binary string. RRLL -> 1100.
2. Convert that binary string into a decimal number. 1100 = 12.

Here are some other examples with their rule numbers showing the variety of patterns that can emerge from these very simple rules. Click on each of the images to see the higher resolution originals.

Rule 9
Ant Automaton

Rule 262 – Diagonal scaffolding like structures
Ant Automaton

Rule 908 – Builds a rougher jagged highway
Ant Automaton

Rule 1080 – Spiral
Ant Automaton

Rule 8383 – Build Sierpinski Triangle patterns as it grows
Ant Automaton

There are more examples in my Ant Automaton Gallery.

3D Ant Automata

The next logical step was to extend into 3D space. I was trying to work out how to handle and program an ant turning in 3 dimensions when I came across Dr Heiko Hamann‘s page on 3D Langton’s Ants. He generously provides some source code here that has the required matrix manipulation required to get the ant turning in 3D space. Have a look if you are interested in implementing your own 3D version of Langton’s Ant.

Once I got the code working I ran a brute force search over the first 20,000 rule numbers. It is harder to see structures within the blobs of random that tend to emerge, but a few interesting results did occur. One thing you get is a lot of very basic highways, so the same emergence of highways in 2D does carry over to 3D.

Here are a few examples I found so far and their corresponding rule numbers. Click to see the larger original images.

Rule 318 – An example of one of the many highways
Ant Automaton

Rule 1042 – Creates more cubic structures and then builds a vertical highway
Ant Automaton

Rule 4514 – Slowly builds a complex vertical highway
Ant Automaton

Rule 6046 – Builds a vertical sprouting highway from a virtual seed
Ant Automaton

Rule 6738 – Corkscrew highway
Ant Automaton

Rule 9513 – Zigzag highway
Ant Automaton

Rule 10952 – After a long time building a seemingly random blob it starts generating a triangle shaped highway
Ant Automaton

Rule 17416 – Generates plate like interlocking 3D puzzle pieces and then a complex highway
Ant Automaton

OBJ Export

Visions Of Chaos also supports exporting the 3D Ant Automata to OBJ files. Here are some examples of 3D Ants exported to OBJ files and imported into and rendered in Blender. I really am a total amateur with Blender but these images show some potential with nice ambient occlusion.

3D Ant Automaton

3D Ant Automaton

3D Ant Automaton

Experiment with Ant Automata

If you want to see any of these automata being built or want to experiment with other rules, download Visions Of Chaos.

If you find any new interesting rules let me know.

Jason.

Yin Yang Fire

Yin Yang Fire

Back around 1999 Jack Ruijs discovered a cellular automaton he named Yin Yang Fire. See here for his explanation. Unfortunately he decided to keep the formula a secret after being ignored by “several universities/persons that are working on the field of self organizing system / computer-algorithms etc” so he has never shared the methods that create his Yin Yang Fire images.

Yin Yang Fire

Yin Yang Fire

I remembered Yin Yang Fire again when I stumbled across this forum post by MackTuesday that has some code he discovered to generate the Yin Yang Fire. Ignoring the name calling and insults, here is the snippet of source code he provides.


// The number of states is 64. In memory they take the values 0-63.
int me = cellsBuffer[x][y];
int result = me;
// cellSum is the sum of the states of the 8 neighbors plus the central cell
// numStates = 64
if (me * 9 + 2 >= cellSum) {
result = result - 1;
if (result < 0) {
result = numStates - 1;
}
}
else {
result = me + 1;
}
return result;

For those of you who have played with cellular automata in the past then this method will be fairly familiar. Update each cell using its value and the total of its 8 neighbours. What is new is the update rule


if (me * 9 + 2 >= cellSum) {
result = result - 1;
if (result < 0) {
result = numStates - 1;
}
}
else {
result = me + 1;
}

If you run the rule as is you get a lot of color cycling and flashing as the cell states decrease to 0 and then wrap around to numstates again. This is shown in the following GIF aniumation.

Yin Yang Fire

To avoid the pulsating/strobing updates you can update the display every n calculated frames. A good formula I found is to use numstates*1.5 steps between display. So for example the default of 64 states should be shown on screen every 64*1.5 or 96 steps. This gives a smoother (but faster) output as shown in the following GIF.

Yin Yang Fire

Yin Yang Fire

Alternate neighbourhoods can also be used. This next one used a Von Nuemann (N S E W neighbours only)

Yin Yang Fire

If you are an enthusiast of cellular automata reading this, do experiment and let me know about any further discoveries here (without keeping it a secret for 15 years!)

Yin Yang Fire

Since writing this post I was contacted by Thorsten Ewert who has done more investigations into the Yin Yang Fire CA. See his page here for more information. For example, there is a Long term state vector diagram on this page that shows a variation drop off around 50000 steps. None of my tests could replicate this, but Thorsten has been able to confirm that the same drop off does occur using the algorithms shown above. Thanks Thorsten.

The latest version of Visions Of Chaos now supports Yin Yang Fire cellular automata and I also hacked together a quick online GLSL shader version here that you can run in your browser. It seems to run best under Chrome.

If you have an Android phone or tablet you can download Visions Of Chaos for Android which also has the Yin Yang Fire shader included.

Jason.