Update a cellular automata using different neighborhoods and rules every second step. Green is the current cell. Red are the cells checked each step. The first step uses the 4 neighbor cells north, south, east and west. The second step uses the 4 diagonal neighbors. Then they alternate each step of the CA. Each neighborhood has its own set of rules for birth and survival.
There are a total of 2^20 or 1,048,576 possible rules using this method. 9*2^20 (9,437,184) if you take into account a maximum state value of between 2 and 10 for each cell.
Click the following to open a short GIF animation of each of the rules. The thumbnails are a mess.
Amoebas
Fireworks
Gliders
Life-ish
Traffic
Walkers and Spinners
Extending the possible maximum states of each cell up to 10 shows potential with some more interesting structures.
Expanding Ships
Fireballs
Spirals
Stick Growth
My next idea was to extend the neighborhoods as follows
The settings are extended to handle the larger neighborhood.
This gives 2^52 or 4 quadrillion (4,503,599,627,370,496 to be exact) possible rules (and that is only for 2 state rules). A maximum cell state of 10 gives 9*2^52 or 40 quadrillion (40,532,396,646,334,464) possible rules. Finding those sweet spots of interest between dying out and total chaos becomes even more daunting.
I wasn’t confident that those neighborhoods would give any interesting results beyond chaotic noise, but they are showing potential so far from random searches and mutations of rules.
Amoeba
BZ-ish
Fire Ships
Pulsating
Thick Ripples
The Alternating Neighborhood Cellular Automata are now available as part of the latest version of Visions of Chaos.
Another new cellular automaton. This time inspired by this post by Xiaohan Zhang (@hellocharlien on Twitter). I messaged Xiaohan about his algorithm and he generously provided the source code to his CA processing sketch here.
I called them the “Zhang Cellular Automata” as there was no official name given to these.
How they work
Setup a 2D array of integers for the CA cells. Fill with random values between 0 and numstates-1. I allow up to 9 for the numstates which means a 0 dead state and 1-8 alive states for cells.
Create a rule table which is an array 9×9 integers in size. Fill with random values between 0 and numstates-1.
Now the steps when processing each cell.
1. Count how many of the 8 Moore Neighborhood neighbors there are in each state (between 0 and numstates-1). This gives you an array countStatesOfNeighbors[0..numstates-1].
2. Remember the current cell state value.
3. Loop through the possible state ranges from 0 to numstates-1.
4. If the rule entry matches the loop then assign the loop value to the cell, otherwise the cell remains as is.
Here is my code for updating each cell
mystate:=c[x,y];
for s:=0 to numstates-1 do
begin
if (countStatesOfNeighbors[s]=rule[myState,s]) then
begin
mystate:=s;
break;
end;
end;
t[x,y]:=mystate;
Results
There are interesting cyclic results that tend to go through cycles of life and death. One state will fill out an area of random noise with a new pattern and that pattern allows a new pattern to fill it, before the original random state refills the area.
Since there is no name given for this CA, I called it the “Two Steps Back Cellular Automata”.
How it works
This time it is a more simple 1D CA.
Each cell is updated by counting the neighbors 2 cells either side of it and itself (5 cells) and the same 5 cells in the previous generation. This gives you a possible count of active cells between 0 and 10. The count is used into a rule array for the new cell state.
For example, if your rule array is rule[1,0,0,0,0,1,0,1,1,0,1] and the cell has 5 neighbor cells that are alive, then the new cell would be alive too (the rule counts start at 0, so the 6th entry in the rule array is for 5 active neighbors and that entry is 1).
You can convert the 11 digit rule into a binary string. The above is 10000101101 which converts into the decimal number 1069 (not 1441 as in Charlie’s post – looks like he reversed the binary digits before conversion).
Results
There are 2048 possible rules. Not a big amount compared to some CAs, so it was easy to setup a loop and generate all 2048 rules. These are a few of the interesting results starting from a single centered alive cell. I have included a low res and high detail version of each rule.
Rule 313
Rule 366
Rule 384
Rule 494
Rule 798
Rule 995
Rule 1069
Rule 1072
Rule 1437
Rule 1438
Rule 1623
Rule 1822
Rule 2019
Extending the neighborhood
Once I went through those 2048 possibilities I extended the neighborhood 1 cell either side. So a total of 14 neighbor cells to check. This bumps the total possible rules up to 32768. I called these ones the “Two Steps Back Extended Cellular Automata”.
Extended Results
Again I kicked off a batch run and waited for the 32,768 results to render. Here are some of the more interesting results.
This new form of Cellular Automata (at least they are new to me) came from a Tumblr post from Neil Makes Games (@NKnauth on Twitter). His post refers to @LorenSchmidt on Twitter, but I could not find the original post. There is enough info in Neil’s post to let me implement and experiment with these CAs.
Due to lack of a name and because I made some changes to the implementation I called them “Indexed Totalistic Cellular Automata”. The rule is totalistic in that it uses the total counts of neighbor cells to determine the new cell state, and the state counts act as an index into the rule array.
Define the rule
The rule for these CAs are based on a 2D rule table like the following.
The table is mapped to a 9×9 2D rule array of integers. That covers all possible state 1 and state 2 cell counts. There is no “fade out” or “die off” period where cells that “die” go into a semi-dead state before fully dying. All cell updates are based solely on the rule table.
Filling the grid array
The original used values between 1 and 3 to fill the grid. I use between 0 and 3. The different results of including and excluding the 0 are outlined below.
Processing the grid each step
Count the state 1 and state 2 cells in the immediate 8 cell Moore Neighborhood.
Use the state 1 and state 2 counts as an index into the rule array, ie result=rule[state1count,state2count]
If the result is 3 then the cell remains the same. If the result is 1 or 2 then the cell becomes 1 or 2. In the original CA there is no state 0 in the rule array, but I added it in so that if the result is 0 the cell becomes empty.
Results
From an initial experiment with these I have seen some interesting results. Click the following images to see an animated gif of the CAs.
There are many unique gliders.
And this fireworks doily like display
Extending the neighborhood size
I also played with extending the Moore Neighborhood to all cells within 2 grid distances (total of 24 possible neighbors).
The extended neighborhood tends to give more blobbly amoeba results. Although I have only started to experiment with these CAs so more unique outcomes should hopefully pop up in the future.
Extending to three dimensions
I did some tests with extending into 3D. 26 neighbors per cell. No results worth posting yet. I will update if I find any interesting results in 3D.
Availability
These new CAs are now included with Visions of Chaos. If you do find any new interesting rules, let me know.
I have played with 3D strange attractors in the past (see here and here). Those attractors were formed by plotting millions of points in 3D space.
The points plotted will seem to jump around randomly at first, but after a few million or so points they do start to form the attractor shapes.
The attractors in this post are slightly different. The attractor formula is still iterated in the same way, but in these attractors the points form a series of points along a curve. This curve can be plotted as a line in 3D space. I couldn’t find an official term difference between the attractors plotted by points vs the attractors plotted by lines. If there is one, let me know.
I had to have a go at adding these to Visions of Chaos as a new mode, so off I went.
The attractor formulas involved are fairly simple and the source code for each type really helped me get the attractor math going quickly. In the end I implemented 60 of the attractors on Jürgen’s page.
Displaying the attractors
If you use one of the attractor formulas you will end up with a long list of points in 3D space that need to be displayed.
I used a series of OpenGL cylinders between the points. This is OK but really doesn’t work as you have breaks where the cylinders do not join each other correctly. I need to implement some code to extrude a circle or other shapes along a curve when I get some time, but unless you look very closely at the following movie you won’t notice the breaks.
Red and blue glasses anaglyph display
I have also added a 3D Strange Attractors album to my flickr gallery. If you have a pair of the old anaglyph red and blue glasses you can also see some anaglyph images of the attractors in this gallery.
Here is a movie of the anaglyph attractors rotating.
Cross-eyed stereogram
Another method of seeing these in 3D. Slightly cross your eyes until the 2 images merge into 1.
You may need to find that sweet spot between movie size and your distance from the screen to see the 3D at its best.
Some quick programmer tips
If you work from Jürgen Meier’s excellent reference you may (or at least I did) notice some of the attractors do not plot the same as his. The cause of this is most likely (other than a typo in parameters) will be the delta value. The delta is that “small amount” that each iteration of the attractor is multiplied by to stop it “blowing up” and having all the points escape to infinity. If you notice your plot exploding lower the delta by a factor of ten and try again. Similarly some delta values seem too small so the plot takes a long time. Increasing delta will speed up the plot. You just need to tweak the delta until you get that sweet spot between accuracy and speed.
Another point to mention. When you calculate any strange attractor (this applies for 2D and 3D when using points or lines) you need to skip plotting the first thousand points. This allows the attractor to “settle” into the attractor’s basin. Otherwise you get a line or points that are not part of the attractor. An example is this image
That little squiggly tail at the bottom is where the plot started and is not part of the attractor. I have seen this same error in articles in reputable journals too sometimes, with images of strange attractors with tails that are not part of the basin of attraction.
Once you have the attractor points they will all tend to fall within different XYZ coordinate ranges. Scaling them all into a fixed range (in my case I used -0.5 to +0.5) allows them all to be centered on the screen when rendering and allows them to be easily shaded by converting XZY to RGB. All it took was a bit of whiteboard scribbling and I had nicely centered attractors.
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.
Rule 95
A few of the rules did produce highways the same as the regular Ant Automaton in 2D and 3D does.
Rule 252
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
Rule 2327
Rule 67
and also produced some complex highways.
Rule 71
Rule 138
Rule 471
Rule 2644
The following rule created a symmetric structure before creating a straight highway.
One of their more fascinating projects is Accretor in which they use cellular automata and 3D printing to create physical objects like the following;
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.
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.
You can also start with a symmetric seed…
…that leads to symmetric results and structures.
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.
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;
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.
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.
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.
Results
Here is a 4K sample movie of the resulting CAs using the methods described in this blog post.
After posting that movie I got numerous complaints about the individual parts ending too quickly. I decided to try rendering longer parts. This can be a real test of patience as once the number of individual cubes rises it can take around half an hour PER FRAME to render. I had 5 PCs churning away 24 hours a day for 2 weeks rendering movies. The result is as follows.
If anyone sees this and complains the parts are still too short they can use their computing resources and generate their own long lasting examples. This has also inspired me to try and develop my own custom raytracer for a lot of cubes or spheres using GPU acceleration. Mitsuba and/or Renderman give really nice shaded results but they both can be very slow when rendering millions of cubes or spheres.
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.
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;
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.
Future Ideas
Extend the neighborhood beyond the immediate 26 neighbor cells. See if more complicated structures appear.
2D Version
See this blog post for some results from experimenting with a 2D version of the Accretor Cellular Automata.
4D Version
I have also extended the Accretor logic into four dimensions. Click the following image to see an example animated GIF file.
No full sample movie yet as I have other things to work on and I don’t have the patience for week long renders at the moment. When I do get some spare time to let my PCs churn I will upload a sample to YouTube and link it here. In the meantime you can play with the 4D version in Visions of Chaos if you are interested as I do include some other samples with it. If you find any other nice examples send them to me.
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
after a while it starts getting islands of the same color
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.
And then using red, blue, green and yellow as the quarters of the image. Von-Neumann neighborhood.
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.
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.
Softology's Blog 