2D Accretor Cellular Automata

After experimenting with the 3D Accretor Cellular Automata I wanted to see how it works in 2D.

The principals in 2D are almost the same as in 3D, but in 2D you only have face and corner neighbors and no “edge” neighbors.

Here are some samples;

2 states – Solid 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2 states – Random 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

3 states – Solid 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

3 states – Random 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

4 states – Solid 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

4 states – Random 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

5 states – Solid 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

5 states – Random 5×5 pixel seed

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

2D Accretor Cellular Automaton

Jason.

Variations of Ant Automata

I had an idea to extend Langton’s Ant and the generalized Ant Automata by allowing turning of the ant in 45 degree angles rather than just 90 degree angles. I was hoping to get some new unique results.

In the usual ant automaton, when the ant turns right it makes a 90 degree turn (eg from facing west it turns 90 degrees to face north). In my experiment I turn only 45 degrees (so facing west now turns right to face north-west). Otherwise the way the ant behaves is the same for the usual Ant Automaton.

After running a few thousand automated rule numbers the results were nothing spectacular. Mostly blobs without any interesting structures.

Ant Automaton
Rule 95

A few of the rules did produce highways the same as the regular Ant Automaton in 2D and 3D does.

Ant Automaton
Rule 252

Ant Automaton
Rule 87

My next idea was to change the amount the ant turns based on its surrounding 8 neighbors (the left or right turn direction is still based on the rule binary digit as in the usual ant automaton). Each of the 8 neighbors (W,NW,N,NE,E,SE,S,SW) state values are summed and then a turnvalue is found by


turnvalue=neighborcount mod 8+1

This gives a value between 1 and 8 to turn by. 8 means do not turn and keep moving straight ahead. When a turn is made to the left or right, the turn takes that many 45 degree steps. So if the neighbor value comes out to 2, then a right turning ant now turns 90 degrees rather than the usual 45 degrees.

This method did give more interestingly shaped blobs

Ant Automaton
Rule 2327

Ant Automaton
Rule 67

and also produced some complex highways.

Ant Automaton
Rule 71

Ant Automaton
Rule 138

Ant Automaton
Rule 471

Ant Automaton
Rule 2644

The following rule created a symmetric structure before creating a straight highway.

Ant Automaton
Rule 2595

Jason.

Accretor Cellular Automata

Inspiration

Erwin Driessens and Maria Verstappen are collaborative Dutch artists that have worked together since 1990 and have created a wide variety of interesting works.

One of their more fascinating projects is Accretor in which they use cellular automata and 3D printing to create physical objects like the following;

Accretor

Accretor

Accretor

Accretor

They provide some info here which links to this article with more hints of their process but not enough for me to implement the cellular automaton myself. I then emailed Erwin and he was kind enough to clarify the rules he uses. Thanks Erwin.

The rest of this post covers my explanation of and experimentation with the Accretor Cellular Automaton.

Seeding the initial CA array

Start the CA by seeding the middle of an empty 3D grid with a 5x5x5 grid of random cells.

Accretor Cellular Automaton

The original Accretor uses 2 or 3 states per cell, but I have been experimenting with up to 5 states per cell. Expanding to more cells is possible and is something to try in the future.

Using a random cell seed allows the resulting structures to grow in more non-uniform ways.

Accretor Cellular Automaton

Accretor Cellular Automaton

You can also start with a symmetric seed…

Accretor Cellular Automaton

…that leads to symmetric results and structures.

Accretor Cellular Automaton

Accretor Cellular Automaton

The CA rule

The CA rule use a 4 dimensional array of the following dimensions
Rule[0..4,0..6,0..12,0..8]
which corresponds to
[current cell state,face neighbor count,edge neighbor count,corner neighbor count]

Use nested loops to seed the rule array, eg


for stateloop:=0 to (maxstates-1) do
begin
     for faceloop:=0 to 6 do
     begin
          for edgeloop:=0 to 12 do
          begin
               for cornerloop:=0 to 8 do
               begin
                    if random<0.2 then
                    rule[stateloop,faceloop,edgeloop,cornerloop]:=random(maxstates)
                    else
                    rule[stateloop,faceloop,edgeloop,cornerloop]:=0;
               end;
          end;
     end;
end;

The if random<0.2 above gives a 20% chance of the rule array entry being set. This makes the rule array 1/5th the filled “density”. I found that if the rule array is too dense then the resulting structures tend to be too “blobby” and do not have as interesting resulting structures. I ended up testing various probabilities and in the end now allow the user to configure the fill percentage amount.

Accretor Cellular Automaton

Processing the CA

At each step of the CA, empty cells (skip cells that already have an active non state 0 cell) are updated as follows;

1. Count the cell’s neighboring faces, edges and corners.

Rather than count the 26 3D neighbor cells as one group and use that total (as is usually the case with a 3D CA), this method separates the 26 neighbors into 3 groups; faces, edges and corners. See the code below to understand how the faces, edges and corners are counted.

2. If the empty cell does not share at least 1 face with a neighbor stop processing the cell and go onto the next one. A simple if FaceCount<1 then continue check is all that is needed. This ensures the resulting structure is fully connected without cells “joined” at their diagonal corners. It also ensures that the resulting structure can be 3D printed.

3. Use the rule array to update the new cell state (like any CA you use a temp array for the new cell states so all cells are update simultaneously);

4. Repeat as long as necessary. I automatically stop when the CA structure reaches the edge of the 3D array/grid.

Here is some example code that cycles the CA grid each step;


for z:=1 to zcells do
begin
     for y:=1 to ycells do
     begin
          for x:=1 to xcells do
          begin
               cellstate:=c3d[x,y,z];
               t3d[x,y,z]:=cellstate;
               //only process empty cells
               if cellstate=0 then
               begin
                    //count neighboring cells
                    FaceCount:=0;
                    //faces
                    if c3d[x,y,z-1]>0 then inc(facecount);
                    if c3d[x,y,z+1]>0 then inc(facecount);
                    if c3d[x,y-1,z]>0 then inc(facecount);
                    if c3d[x,y+1,z]>0 then inc(facecount);
                    if c3d[x+1,y,z]>0 then inc(facecount);
                    if c3d[x-1,y,z]>0 then inc(facecount);
                    //must have at least 1 face touching
                    if facecount>0 then
                    begin
                         EdgeCount:=0;
                         CornerCount:=0;
                         //edges
                         if c3d[x,y-1,z-1]>0 then inc(edgecount);
                         if c3d[x-1,y,z-1]>0 then inc(edgecount);
                         if c3d[x+1,y,z-1]>0 then inc(edgecount);
                         if c3d[x,y+1,z-1]>0 then inc(edgecount);
                         if c3d[x-1,y-1,z]>0 then inc(edgecount);
                         if c3d[x+1,y-1,z]>0 then inc(edgecount);
                         if c3d[x-1,y+1,z]>0 then inc(edgecount);
                         if c3d[x+1,y+1,z]>0 then inc(edgecount);
                         if c3d[x,y-1,z+1]>0 then inc(edgecount);
                         if c3d[x-1,y,z+1]>0 then inc(edgecount);
                         if c3d[x+1,y,z+1]>0 then inc(edgecount);
                         if c3d[x,y+1,z+1]>0 then inc(edgecount);
                         //corners
                         if c3d[x-1,y-1,z-1]>0 then inc(cornercount);
                         if c3d[x+1,y-1,z-1]>0 then inc(cornercount);
                         if c3d[x-1,y+1,z-1]>0 then inc(cornercount);
                         if c3d[x+1,y+1,z-1]>0 then inc(cornercount);
                         if c3d[x-1,y-1,z+1]>0 then inc(cornercount);
                         if c3d[x+1,y-1,z+1]>0 then inc(cornercount);
                         if c3d[x-1,y+1,z+1]>0 then inc(cornercount);
                         if c3d[x+1,y+1,z+1]>0 then inc(cornercount);
			 //update temp CA array
                         t3d[x,y,z]:=rule[cellstate,facecount,edgecount,cornercount];
                    end;
               end;
          end;
     end;
end;

Accretor Cellular Automaton

Number of possible rules

If my maths is right, using a rule with 3 states (0, 1 and 2), 6 faces, 12 edges and 8 corners works out to 3^2457 (2457=3*7*13*9) possible rules. A hugely vast search space to find interesting rules within. 7 rather than 6 for faces because 0 is also a possible face count, so 0,1,2,3,4,5 and 6 are possible face neighbor counts.

That is approximately 1.9 × 10^1172. If the estimated grains of sand on earth is only 7.5 x 10^18 and the atoms in the human body is 7 x 10^27 then that 10^1172 is ridiculously massive. If written out it is

19360779830108706143158314462932921450873713304210800
53588182939593514138485794005270157932799698822818843
56020894409145212864135998556816842566331095607078650
38555929218194503549932824176875306014690432935132038
89124431912515072526247650091655973630435147327993725
76425212921359895791760004246711770732571379038647670
33203873485407810426459611676843600357049153873089778
17135431812895651701819910615940639410814267993899381
34125993339341535241610822303654061326578587839902022
94773918798722121146213839112691961581285732094802542
94858366701046641821466791051399216256794659987861702
18908742166411834195388405755375661393299315666296665
26580523434609646280665626973739253700248351337869718
98207944219754734206529855353570994892022049504018670
71749069193914930675491887606241533434504857738825465
09009720179663916140828611939274335870602187117477361
04034720794911284806284467706381609467270430744411149
18267733536174551156877346511943390051908666674282501
74400303604461414910970988425320803328355005806525295
80438094328140447700213957276365072583896061394109445
71135838107597919228936011421720714984693698605181870
57525782235384089823045963423979207472317509728149022
1798563

In layman’s terms a veritable crap-tonne.

Accretor Cellular Automaton

Searching for interesting rules

Clicking a random rule button multiple times to see if an interesting result occurs gets real boring real fast. Looking for good rules is like the proverbial needle in a haystack, although in this case the haystack is much much larger than your ordinary haystack.

Searching involves looping through multiple random rules looking for possibly interesting results. There a variety of “categories” that results can be classified as when searching;

1. Stagnated. Rules that lead to the initial small seed not growing at all or only growing a few steps then stopping. These are ignored and not saved.

2. Growth with small straight lines from the starting seed. These are classified as “boring”. Once the growth reaches the edge of the grid, it is simple enough to detect these by checking the active cell count vs the grid size and if less than half a percent consider the rule boring.


if cellcount/(gridsize^3)<0.005 then boring

3. Octahedron shapes. A lot of the resulting structures fill an octahedron shaped area. Before the search begins, generate a rule that is known to create an octahedral shape and remember the active cell count. When generating random rules, if the cell count is within +/- 20% the octahedron count then classify it as an octahedron and put it in a separate folder.

4. Sphere shapes. Another common result. Before the search begins, generate a rule that is known to create a spherical shape and remember the active cell count. When generating random rules, if the cell count is within +/- 20% the sphere count then classify it as an sphere and put it in a separate folder.

5. Slow growth. Erwin has observed that interesting rules tend to be slow growers. A simple way to check for slow growth is to count the steps the CA takes to reach the edge of the grid. If the number of steps is greater than the grid size multiplied by three the rule is considered a slow grower and saved to a separate folder.

6. The rest. If the random rule passes all the above checks then it is considered a possibility. The parameters and a sample image are saved for future checking.

Not all of the above classifiers are bulletproof and 100% reliable, so you will get some incorrectly classified results. Going on active cell count alone is not the most accurate classification method, but it does seem to result in a general weeding out of unwanted results.

After letting the search run for hours or overnight you come back and have a quick scan through the results directories to see if any of the possible good rules are worth further investigation. Once you have a bunch of possible rules that look good they can be rendered at a larger grid size at better quality. I have included the search functionality with Visions of Chaos so you too can hunt for interesting rules if you wish and if you do, let me know if you find any interesting rules.

Accretor Cellular Automaton

Display

Use cubes or spheres to render the grid cells. OpenGL is OK for quick test renders, but the lack of proper shadowing and ambient occlusion can make it difficult to see the actual structures.

As has been the case for a while now, I prefer to use the most excellent Mitsuba Renderer. Pixar’s RenderMan is also supported.

The cube grids can also be exported as a WaveFront OBJ file for importing and rendering in other 3D programs like Blender, Maya, Cinema 4D, etc.

Accretor Cellular Automaton

Results

Here is a 4K sample movie of the resulting CAs using the methods described in this blog post.

Issues with using a rule array and random numbers

Using a rule array means there cannot be a series of check boxes that the user can check/uncheck to manually set the rule. To make a user settable “rule” I use the random number generator seed value as a rule number. For example setting the rule number to 1234 would set the pseudo-random generator seed to 1234 before filling the rule array with random values. This allows the same steps to be repeatable and the same rules to be run again. It does not however allow me to easily share good rules with others. If for example you coded your own version of the Accretor CA (which I encourage anyone into CA to try) chances are your language’s pseudo-random generator would not use the same code as mine does, so you would get different results to mine. You would get your own unique results but we would not be able to share interesting rules. I have the same issue with my implementation of Voxel Automata Terrain.

Another problem with using a random number generator to seed the array is the limited number of random number sequences that can be generated. In my case the pseudo random generator (a linear congruential generator) takes a seed value that is a 32 bit integer value. This means there can only be a total of 4,294,967,296 possible random rules I can generate and check. 4,294,967,296 may seem like a lot, but it is a tiny fraction of the entire possible rule space and statistically you would think that there are some other interesting rules out there that seeding with a random number generator is going to miss.

Accretor Cellular Automaton

Some comments on coding the Accretor CA

Calculate an array that contains each cell’s distance from the center of the grid before starting. This saves costly sqrt calculations during the cycling. I use the distance array for working out what the farthest cell is from the center of the grid which allows a % done stat during generation.

When a new cell becomes active use it’s location to update min/max x,y and z variables. Something like;


maxx:=max(maxx,x+1);
minx:=min(minx,x-1);
maxy:=max(maxy,y+1);
miny:=min(miny,y-1);
maxz:=max(maxz,z+1);
minz:=min(minz,z-1);

Then when cycling the 3D grid each step you only need to loop from zmin to zmax, ymin to ymax, and xmin to xmax. This helps speed things up when the initial growth structure is small. No point looping through the rest of the empty grid when there is no chance of a new cell being born there.

Accretor Cellular Automaton

Future Ideas

Extend the neighborhood beyond the immediate 26 neighbor cells. See if more complicated structures appear.

Accretor Cellular Automaton

2D Version

See this blog post for some results from experimenting with a 2D version of the Accretor Cellular Automata.

Availability

Accretor Cellular Automata is now a mode in Visions of Chaos.

Accretor Cellular Automaton

Jason.

The Stepping Stone Cellular Automaton

This CA rule was first designed and explored by David Griffeath on his Commodore 64 back in the mid 1980’s.

The basic rule is you fill an image with random colors and set an update probability. For each pixel see if a random value is less than the probability. If it is then change the pixel to the color of one of its neighbor cells (this can be the 4 N,S,E,W Von-Neumann neighbors or all 8 closest cells in the Moore neighborhood). Griffeath’s original uses a 50/50 chance of each cell being changed and uses the Von-Neumann neighborhood.

From a starting random soup of ROYGBIV pixels

Stepping Stone Cellular Automaton

after a while it starts getting islands of the same color

Stepping Stone Cellular Automaton

If you wait long enough one of the colors will always end up dominating the entire grid. “Long enough” is a subjective term. For small grid sizes a single color can win out over the others in a few thousand steps. For larger images it could take days or longer. I had a 4K sized grid running overnight and it looked no closer to a final resolution than the above sample image.

Once I implemented Stepping Stone in Visions of Chaos I added the option to start from 2 or 4 colors. This gets the competition down to a smaller set of fighting colors.

Firstly starting from a black stripe down a white image for a 50/50 fair fight. Moore neighborhood.

Stepping Stone Cellular Automaton

Stepping Stone Cellular Automaton

Stepping Stone Cellular Automaton

And then using red, blue, green and yellow as the quarters of the image. Von-Neumann neighborhood.

Stepping Stone Cellular Automaton

Stepping Stone Cellular Automaton

Stepping Stone Cellular Automaton

David Griffeath originally included an image of Sharon Stone with his CA software to use as a starting point for the Stepping Stone CA. The first image of Sharon Stone that comes to my mind has to be her iconic leg crossing scene in Basic Instinct. The part where Newman was leering at her. So here is my Sharon Stepping Stone gif animation. Click the image to open the GIF in a new window.

Stepping Stone Cellular Automaton

As a side note, I can remember back when Basic Instinct was first released on VHS tape and we went and hired it. When the tape got to the leg uncrossing scene the tape went all static and unwatchable from previous pervs trying to frame by frame that scene and stretching the tape out (not that we were not poised with our finger on the frame by frame button to do the same thing). The good old days of VHS rental.

Visions of Chaos can use any image to run the stepping stone process.

Jason.

2017 In Review

Another year comes to an end. At the start of this year I decided to do at least one thing for Visions of Chaos each day. That one thing could be fixing a bug or adding a new feature. Sometimes it would just be a small change, other times a new mode. For most of 2017 I did manage this. There was a week or two around the middle of the year that I could not motivate myself and did nothing, but for the rest of the year Visions of Chaos benefited from a bunch of bug fixes and new features. Scrolling down in this blog until the start of 2017 shows I did make some good progress. My to do list for new features continues to grow rather than shrink and Visions of Chaos will never be finished so expect many new features in the coming year.

For my last movie of 2017 I decided to do yet another Video Feedback movie for YouTube as there were a bunch of new and interesting VF examples I found since the last movie was uploaded back at the end of June.

I have also started to try and include soundtracks with my YouTube movies. So many people commented or complained that the videos needed music. I purchased a copy of FL Studio and not really having any musical talent was able to make some soundtracks. Who knows, maybe I will start getting comments to stop adding music now.

Jason.

Multi-threading support in Visions of Chaos

A long overdue and much requested feature in Visions of Chaos has been better support for multi core CPUs. Watching Visions of Chaos churn away calculating a long series of frames for a movie and only seeing one of your CPU cores in use can be frustrating.

Converting single threaded code into multi-threaded capable code is not exactly easy (depending on the algorithm some code is easier than others) but I have started converting some of the easier modes into multi-thread capable code.

Smoothed Particle Hydrodynamics (SPH) was one of the modes in Visions of Chaos that really needed a speed up. See here and here for my previous experiments with SPH.

This next screenshot shows all the 12 cores of an i7 being used for calculating the SPH formulas. Note that the actual displaying of the particles cannot be parallel so there is not 100% CPU utilization. As the particle count goes up (and the time it takes to calculate the million particles moving takes longer than the display time) the CPU usage jumps closer to 100% on all cores.

Parallel Multiphase Smoother Particle Hydrodynamics

After conversion to multi-CPU capable code it was time to render some new 4K resolution SPH simulations. Once the particles count and resolution goes up to fill a 4K screen the times start to plummet again, but seeing these in full 4K resolution is really nice. The parts in the following movie used 1,000,000 SPH particles each which is double my previous particle counts.

Other than SPH, the other modes that take advantage of the rewritten parallel processing code are 4D Cellular Automata, Coupled Cellular Automata 2, Ying-Yang Fire Cellular Automata, Large Neighborhood Totalistic Cellular Automata and Liquid Crystal Cellular Automata. The CA modes are the easiest to convert to parallel processing as by nature they update each cell independent of the others.

There is still a lot of code and modes that would benefit from parallel processing. Yet another entry on my ever expanding to do list of features for Visions of Chaos.

Jason.