Cave Cellular Automaton – Algorithm 12.3

I’ve already posted a few examples of Cellular Automata but in hindsight, some of them were a bit complicated especially for those who don’t have any prior experience with this computational paradigm. I have a few more even more complicated ones I want to highlight in future blog postings, but I thought it might be useful to post an example of a much simpler one for those just encountering the topic for the first time. This particular example comes from a blog posting “The Cave Automaton Method for Cave Generation” from Jeremy Kun’s blog Math ∩ Programming and is perhaps the simplest example I have encountered. It is worth popping over there to read his description of the method before proceeding since he explains it quite well and there is no use to rewrite what has already been well-written.

In short, though, this CA resolves within a few rounds a random interior ‘cave-like’ structure from an initial random distribution of occupied, live cells (state ‘1’), and vacant, dead ones (state ‘0’). To do this, in each round, each cell is checked in relation to its neighbours (usually 8, but 5 or 3 if on the edges or corners) to determine if its state remains the same or if it changes. The conditions for a change are as follows:

Born – If the cell is ‘dead’ (state ‘0’), and 6 or more of the neighbours are ‘alive’ (state ‘1’), the state becomes ‘alive’ (state changed from ‘0’ to ‘1’)

Die – If the cell is ‘alive’ (state ‘1’) and fewer than 3 of its neighbours are ‘alive’ (state ‘1’), the state becomes ‘dead’ (state changed from ‘1’ to ‘0’)

Jeremy Kun uses the shorthand B678/S345678 to describe this ruleset. (B = Born, S = Survive, i.e. not Die). So if there are 6,7, or 8 ‘live’ neighbours, a ‘dead’ cell is born, or if there are 3,4,5,6,7, or 8 neighbours, a ‘live’ cell ‘survives.’ The image below shows a few examples of this ruleset in action in a very simple 5×5 CA with an initial 50/50 distribution of live (grey) cells and dead (white) cells. The first three images show the initial pattern, and highlight 3 examples of the ruleset in action. The two images in the second row then show the first and second (and final) evolutions of this particular CA. It is not particularly interesting, but make sure the ruleset is clear before proceeding and setting up the simulation. Also try and answer the question, why does the CA stop evolving after the second round?

Got it? Good! Let’s move forward!

Step 1 – Setup a Grid with Random Initial States

Before working on the core logic of this script, we just need to complete a few basic steps to setup our game board or playing field. As always, we want to start small until everything is working well, at which point we can expand the size of our simulation.

Here I used the Square Grid component with 20 x 20 cells, with the (C)ell output being flattened. I then measure this output with List Length to determine how many values I need to generate with my Random number generator, which by default will output numbers to six decimal places between 0 and 1. I then want to ‘convert’ these random values to one of two states, ‘1’ being ‘alive’ or ‘0’ being dead. I do this by adding an Expression comparing the random values to a parameter I created with a slider called ‘Percentage Live vs. Dead Start’. This slider has values between .40 and .60 since much more or less than that tends to generate an uninteresting, homogenous field in the end. The ‘x’ value input into the Expression is the list of random values. The ‘y’ value is my Percentage Live Parameter. The expression itself is ” if (x>y, 1, 0)”which is Grasshopper’s syntax for saying “if x(the random value on the list) is greater than y (the percentage parameter), then output the value ‘1’, otherwise output the value ‘0’. ” The expression compares each random value against my parameter and outputs a list of 0’s and 1’s which are my initial states based on this.

The states can be previewed with a light or dark colour using the components shown in the top right of the image. Here I am using light for empty or ‘dead’ and dark for occupied or ‘live’ cells.

Step 2 – Set up Proximity Topology 

The next order of business in setting up our game board is to establish the topology of cell proximity. This is done here by finding the (C)entre point of each cell using the Area component and inputting these points into the (P)oint input of the Proximity2D component. In this particular case, and in contrast to the Fur Algorithm 12.1 which had fairly complicated proximity relations, the ‘neighbourhood’ is a very simple ‘Moore’ neighbourhood, which are the 8 cells in the compass directions N,NE,E,SE,S,SW,W,NW. To fix this neighbourhood I input the fixed value ‘8’ into the (G) input (which limits the number of relations), as well as the result of the Expression 1.5 * ‘Cell Size’ parameter to into the (R+) input which establishes a maximum radius to look for relations. The result is every internal cell, such as the one marked in red, has 8 relations, and the cells on the edges, such as the one marked in green, have 5 or 3 relations. This data is put into a data container tagged ‘Proximity Matrix Topology.’

Step 3 – Create a ‘Frame’ for the simulation

In contrast to the previous two CA examples, for this particular simulation I want a ‘frame’ at the edges of the simulation where all the edge cells are always occupied or ‘live.’ To achieve this, I will find out how many neighbours each cell has by measuring the “Proximity Matrix Topology” with the List Length component, flattening the result, and then comparing the results with the ‘Initial Cell States List’ using the Expression “if (x=8, y, 1)”. Again, in simpler English, this means “if the value of ‘x’ (the number of neighbours for each cell) is equal to 8 (meaning it is internal, and not at the edges or corners), keep the cell state as the input ‘y’ (which is the initial cell List), otherwise set the cell state to ‘1’). You can preview the result of this operation with the components shown in the top right of the image above, as in step 1.

Step 4 – Setting up the Rules of the Loop

We finally get to the heart of the simulation, where we set up our looping procedure to ‘evolve’ our Cellular Automaton. You will need the Anemone plugin–please see Algorithm 8.1 for hints on setting up a loop if you need them.

First we will implement the born rule, where a cell with a state ‘0’ changes to state ‘1’ if 6 or more neighbours are active. To do this we will resort to the proximity matrix established in step two. Here for each cell index, the index of all neighbours is provided. To understand this, it helps to zoom into one cell to see what is going on.

Cell 78 has neighbours at cell index numbers 57, 58, 59, 77, 79, 97, 98, and 99. The ‘data’ package produced by the Proximity component has associated these values together. We now want to use these indices to list the cell state values (0 or 1) of 57, 58, 59, 77, 79, 97, 98, and 99. We do this by using List Item, with our evolving cell-state list plugged into the (L)ist input and ‘Proximity Matrix Topology’ data container plugged into (i)ndex. We can then use the Mass Addition component to sum all the 0s and 1s from cells 57, 58, 59, 77, 79, 97, 98, and 99 to get the total number of ‘active’ neighbours. Flatten the (R)esult output from Mass addition to get this result for each List Item. In this case there are ‘7’ active neighbours for cell ’78,’ whose value at the start of the round was ‘0’ or dead. According to our rule, then, this cell should change its state to ‘1’.

We achieve this by using the Expression component with the instruction if (y>=6, 1, x). In plainer English, this means again that for each list item “if the value of y (the sum state of the neighbours) is greater than or equal to six, then return the result ‘1’, otherwise return the result x (which is current cell state, either ‘0’ or ‘1’,  i.e. the state is unchanged.)”  To examine if this is working, it might be helpful to preview the interim result and look at a sample of cells with panels before and after the expression is executed.

Hopefully the logic of the expression we just set up is clear as we are now going to set up a very similar Expression  for the ‘Die’ rule. Here we input the list of updated states from the ‘Born’ rule into the ‘x’ input, and the same results of the Mass Addition of neighbours into the ‘y’ input. The only difference is our expression is now “if (y>=3, x, 0)“. Hopefully by now the syntax is becoming clear. Try to understand what the expression is doing here and again check the panels to see if the expected results are being produced from a few sample cells.

Finally, we have one last Expression to add to keep our border always in a ‘live’ state. The logic here is identical to the logic employed in Step 3 so return to this step if you need to. The results of our rules being employed are then fed into the D0 input of our Loop End component.

Step 5 – Running and Expanding the Simulation

Now that the hard work is done, it is time to reap the rewards (or the frustration if you made a mistake!). You can now increase the iteration count on the Anemone loop to watch the CA ‘evolve.’ As mentioned previously, this particular ruleset produces stable results very quickly, and in my initial 20×20 grid, I reached a stable state after about 5 rounds. If everything seems to be running smoothly, you can now increase the size of the simulation. Depending on your preview settings, this needs to be handled with care! Below is an example of a 100×100 grid. Note the time to achieve a stable state goes up, but it still resolves fairly quickly, in this case after about 10 rounds.

You can also play with different initial percentages at this point to see how the results change.

Step 6 – Post Processing

Depending on your design goals, you may not want to output the results of the CA in a ‘raw’ state and you may want to do a bit of post-processing to get rid of the pixely feel. Jeremy Kun recommends on his blog running further CA’s on top of the initial one to iteratively ‘smooth’ the structure, but here I used a simpler smoothing operation. First I Dispatch the cells into two groups based on their initial state, and then using the Region Union Boolean operator, the ‘dead’ areas are brought together into closed Polylines. I then rounded out the edges with the Fillet component.

Below are two examples of a near final result using various initial parameters and by changing the random number seed.

From here, you can do other operations. Extrude them into solids and send them to a 3D printer…

Or put the voids into Algorithm 4.7 to create an archipelago of Islands.