Chapter 7. Cellular Automata

“To play life you must have a fairly large checkerboard and a plentiful supply of flat counters of two colors. It is possible to work with pencil and graph paper but it is much easier, particularly for beginners, to use counters and a board.”

— Martin Gardner, Scientific American (October 1970)

In this chapter, we’re going to take a break from talking about vectors and motion. In fact, the rest of the book will mostly focus on systems and algorithms (albeit ones that we can, should, and will apply to moving bodies). In the previous chapter, we encountered our first Processing example of a complex system: flocking. We briefly stated the core principles behind complex systems: more than the sum of its parts, a complex system is a system of elements, operating in parallel, with short-range relationships that as a whole exhibit emergent behavior. This entire chapter is going to be dedicated to building another complex system simulation in Processing. Oddly, we are going to take some steps backward and simplify the elements of our system. No longer are the individual elements going to be members of a physics world; instead we will build a system out of the simplest digital element possible, a single bit. This bit is going to be called a cell and its value (0 or 1) will be called its state. Working with such simple elements will help us understand more of the details behind how complex systems work, and we’ll also be able to elaborate on some programming techniques that we can apply to code-based projects.

7.1 What Is a Cellular Automaton?

First, let’s get one thing straight. The term cellular automata is plural. Our code examples will simulate just one—a cellular automaton, singular. To simplify our lives, we’ll also refer to cellular automata as “CA.”

In Chapters 1 through 6, our objects (mover, particle, vehicle, boid) generally existed in only one “state.” They might have moved around with advanced behaviors and physics, but ultimately they remained the same type of object over the course of their digital lifetime. We’ve alluded to the possibility that these entities can change over time (for example, the weights of steering “desires” can vary), but we haven’t fully put this into practice. In this context, cellular automata make a great first step in building a system of many objects that have varying states over time.

A cellular automaton is a model of a system of “cell” objects with the following characteristics.

The cells live on a grid. (We’ll see examples in both one and two dimensions in this chapter, though a cellular automaton can exist in any finite number of dimensions.)

Each cell has a state. The number of state possibilities is typically finite. The simplest example has the two possibilities of 1 and 0 (otherwise referred to as “on” and “off” or “alive” and “dead”).

Each cell has a neighborhood. This can be defined in any number of ways, but it is typically a list of adjacent cells.

Figure 7.1

The development of cellular automata systems is typically attributed to Stanisław Ulam and John von Neumann, who were both researchers at the Los Alamos National Laboratory in New Mexico in the 1940s. Ulam was studying the growth of crystals and von Neumann was imagining a world of self-replicating robots. That’s right, robots that build copies of themselves. Once we see some examples of CA visualized, it’ll be clear how one might imagine modeling crystal growth; the robots idea is perhaps less obvious. Consider the design of a robot as a pattern on a grid of cells (think of filling in some squares on a piece of graph paper). Now consider a set of simple rules that would allow that pattern to create copies of itself on that grid. This is essentially the process of a CA that exhibits behavior similar to biological reproduction and evolution. (Incidentally, von Neumann’s cells had twenty-nine possible states.) Von Neumann’s work in self-replication and CA is conceptually similar to what is probably the most famous cellular automaton: the “Game of Life,” which we will discuss in detail in section 7.3.

Perhaps the most significant scientific (and lengthy) work studying cellular automata arrived in 2002: Stephen Wolfram’s 1,280-page A New Kind of Science. Available in its entirety for free online, Wolfram’s book discusses how CA are not simply neat tricks, but are relevant to the study of biology, chemistry, physics, and all branches of science. This chapter will barely scratch the surface of the theories Wolfram outlines (we will focus on the code implementation) so if the examples provided spark your curiosity, you’ll find plenty more to read about in his book.

7.2 Elementary Cellular Automata

The examples in this chapter will begin with a simulation of Wolfram’s work. To understand Wolfram’s elementary CA, we should ask ourselves the question: “What is the simplest cellular automaton we can imagine?” What’s exciting about this question and its answer is that even with the simplest CA imaginable, we will see the properties of complex systems at work.

Let’s build Wolfram’s elementary CA from scratch. Concepts first, then code. What are the three key elements of a CA?

• Grid. The simplest grid would be one-dimensional: a line of cells.

Figure 7.2

• States. The simplest set of states (beyond having only one state) would be two states: 0 or 1.

Figure 7.3

• Neighborhood. The simplest neighborhood in one dimension for any given cell would be the cell itself and its two adjacent neighbors: one to the left and one to the right.

Figure 7.4

So we begin with a line of cells, each with an initial state (let’s say it is random), and each with two neighbors. We’ll have to figure out what we want to do with the cells on the edges (since those have only one neighbor each), but this is something we can sort out later.

Figure 7.5

We haven’t yet discussed, however, what is perhaps the most important detail of how cellular automata work—time. We’re not really talking about real-world time here, but about the CA living over a period of time, which could also be called a generation and, in our case, will likely refer to the frame count of an animation. The figures above show us the CA at time equals 0 or generation 0. The questions we have to ask ourselves are: How do we compute the states for all cells at generation 1? And generation 2? And so on and so forth.

Figure 7.6

Let’s say we have an individual cell in the CA, and let’s call it CELL. The formula for calculating CELL’s state at any given time t is as follows:

CELL state at time t = f(CELL neighborhood at time t - 1)

Figure 7.7

Now, in the world of cellular automata, there are many ways we could compute a cell’s state from a group of cells. Consider blurring an image. (Guess what? Image Unity works with CA-like rules.) A pixel’s new state (i.e. its color) is the average of all of its neighbors’ colors. We could also say that a cell’s new state is the sum of all of its neighbors’ states. With Wolfram’s elementary CA, however, we can actually do something a bit simpler and seemingly absurd: We can look at all the possible configurations of a cell and its neighbor and define the state outcome for every possible configuration. It seems ridiculous—wouldn’t there be way too many possibilities for this to be practical? Let’s give it a try.

We have three cells, each with a state of 0 or 1. How many possible ways can we configure the states? If you love binary, you’ll notice that three cells define a 3-bit number, and how high can you count with 3 bits? Up to 8. Let’s have a look.

Figure 7.8

Once we have defined all the possible neighborhoods, we need to define an outcome (new state value: 0 or 1) for each neighborhood configuration.

Figure 7.9

The standard Wolfram model is to start generation 0 with all cells having a state of 0 except for the middle cell, which should have a state of 1.

Figure 7.10

Referring to the ruleset above, let’s see how a given cell (we’ll pick the center one) would change from generation 0 to generation 1.

Figure 7.11

Try applying the same logic to all of the cells above and fill in the empty cells.

Now, let’s go past just one generation and color the cells —0 means white, 1 means black—and stack the generations, with each new generation appearing below the previous one.

Figure 7.12: Rule 90

The low-resolution shape we’re seeing above is the “Sierpiński triangle.” Named after the Polish mathematician Wacław Sierpiński, it’s a fractal pattern that we’ll examine in the next chapter. That’s right: this incredibly simple system of 0s and 1s, with little neighborhoods of three cells, can generate a shape as sophisticated and detailed as the Sierpiński triangle. Let’s look at it again, only with each cell a single pixel wide so that the resolution is much higher.

Now, let’s go past just one generation and color the cells —0 means white, 1 means black—and stack the generations, with each new generation appearing below the previous one.

Figure 7.13: Rule 90

This particular result didn’t happen by accident. I picked this set of rules because of the pattern it generates. Take a look at Figure 7.8 one more time. Notice how there are eight possible neighborhood configurations; we therefore define a “ruleset” as a list of 8 bits.

So this particular rule can be illustrated as follows:

Figure 7.14: Rule 90

Eight 0s and 1s means an 8-bit number. How many combinations of eight 0s and 1s are there? 256. This is just like how we define the components of an RGB color. We get 8 bits for red, green, and blue, meaning we make colors with values from 0 to 255 (256 possibilities).

In terms of a Wolfram elementary CA, we have now discovered that there are 256 possible rulesets. The above ruleset is commonly referred to as “Rule 90” because if you convert the binary sequence—01011010—to a decimal number, you’ll get the integer 90. Let’s try looking at the results of another ruleset.

Figure 7.15: Rule 222

A Textile Cone Snail (Conus textile), Cod Hole, Great Barrier Reef, Australia, 7 August 2005. Photographer: Richard Ling richard@research.canon.com.au

As we can now see, the simple act of creating a CA and defining a ruleset does not guarantee visually interesting results. Out of all 256 rulesets, only a handful produce compelling outcomes. However, it’s quite incredible that even one of these rulesets for a one-dimensional CA with only two possible states can produce the patterns we see every day in nature (see Figure 7.16), and it demonstrates how valuable these systems can be in simulation and pattern generation.

Before we go too far down the road of how Wolfram classifies the results of varying rulesets, let’s look at how we actually build a Unity scene that generates the Wolfram CA and visualizes it onscreen.

7.3 How to Program an Elementary CA

You may be thinking: “OK, I’ve got this cell thing. And the cell thing has some properties, like a state, what generation it’s on, who its neighbors are, where it lives pixel-wise on the screen. And maybe it has some functions: it can display itself, it can generate its new state, etc.” This line of thinking is an excellent one and would likely lead you to write some code like this:

    public class Cell
    {

    }
    

This line of thinking, however, is not the road we will first travel. Later in this chapter, we will discuss why an object-oriented approach could prove valuable in developing a CA simulation, but to begin, we can work with a more elementary data structure. After all, what is an elementary CA but a list of 0s and 1s? Certainly, we could describe the following CA generation using an array:

Figure 7.17

    public int[] ruleSet0 = { 1,0,1,0,0,0,0,1,0,1,1,1,0,0,0,1,1,1,0,0 };
    

To draw that array, we simply check if we’ve got a 0 or a 1 and create a fill accordingly.

    public void Display() // Drawing the cells. Cells with a state of 1 are black, cells with a state of 0 are white
    {
        if (numberOfCells <= cellCapacity)
        {
            for (int i = 0; i < cells.Length; i++)
            {
                GameObject newCell = GameObject.CreatePrimitive(PrimitiveType.Quad);
                numberOfCells++;
                Renderer r = newCell.GetComponent<Renderer>();
                r.material = new Material(Shader.Find("Diffuse"));
                Object.Destroy(newCell.GetComponent<BoxCollider>());
                if (cells[i] == 1)
                {
                    r.material.color = Color.black;
                }
                else
                {
                    r.material.color = Color.white;
                }

                // Set position based to lower left of screen, with screen offset
                newCell.transform.position = new Vector3(i - screenSize.x - xScreenOffset,
                                                generation - screenSize.y + yScreenOffset);
            }
        }
    }
    

Now that we have the array to describe the cell states of a given generation (which we’ll ultimately consider the “current” generation), we need a mechanism by which to compute the next generation. Let’s think about the pseudocode of what we are doing at the moment.

• For every cell in the array:
• Take a look at the neighborhood states: left, middle, right.
• Look up the new value for the cell state according to some ruleset.
• Set the cell’s state to that new value.
• This may lead you to write some code like this:

    public void Generate()
    {
        // First we create an empty array for the new values
        int[] nextGen = new int[cells.Length];

        // For every spot, determine new state by examing current state, and neighbor states
        // Ignore edges that only have one neighor
        for (int i = 1; i < cells.Length; i++)
        {
            int left = cells[i - 1]; // Left neighbor state
            int me = cells[i]; // Current state
            int right = cells[i + 1]; // Right neighbor state
            nextGen[i] = rules(left, me, right); // Compute next generation state based on ruleset
        }

        // The current generation is the new generation
        cells = nextGen;
        generation++;
    }
    

We’re fairly close to getting this right, but we’ve made one minor blunder and one major blunder in the above code. Let’s talk about what we’ve done well so far.

Notice how easy it is to look at a cell’s neighbors. Because an array is an ordered list of data, we can use the fact that the indices are numbered to know which cells are next to which cells. We know that cell number 15, for example, has cell 14 to its left and 16 to its right. More generally, we can say that for any cell i, its neighbors are i-1 and i+1.

We’re also farming out the calculation of a new state value to some function called rules(). Obviously, we’re going to have to write this function ourselves, but the point we’re making here is modularity. We have a basic framework for the CA in this function, and if we later want to change how the rules operate, we don’t have to touch that framework; we can simply rewrite the rules() function to compute the new states differently.

So what have we done wrong? Let’s talk through how the code will execute. First, we look at cell index i equals 0. Now let’s look at 0’s neighbors. Left is index -1. Middle is index 0. And right is index 1. However, our array by definition does not have an element with the index -1. It starts with 0. This is a problem we’ve alluded to before: the edge cases.

How do we deal with the cells on the edge who don’t have a neighbor to both their left and their right? Here are three possible solutions to this problem:

Edges remain constant. This is perhaps the simplest solution. We never bother to evaluate the edges and always leave their state value constant (0 or 1).

Edges wrap around. Think of the CA as a strip of paper and turn that strip of paper into a ring. The cell on the left edge is a neighbor of the cell on the right and vice versa. This can create the appearance of an infinite grid and is probably the most used solution.

Edges have different neighborhoods and rules. If we wanted to, we could treat the edge cells differently and create rules for cells that have a neighborhood of two instead of three. You may want to do this in some circumstances, but in our case, it’s going to be a lot of extra lines of code for little benefit.

To make the code easiest to read and understand right now, we’ll go with option #1 and just skip the edge cases, leaving their values constant. This can be accomplished by starting the loop one cell later and ending one cell earlier:

    public void Generate()
    {
        // First we create an empty array for the new values
        int[] nextGen = new int[cells.Length];

        // For every spot, determine new state by examing current state, and neighbor states
        // Ignore edges that only have one neighor
        for (int i = 1; i < cells.Length-1; i++)
        {
            int left = cells[i - 1]; // Left neighbor state
            int me = cells[i]; // Current state
            int right = cells[i + 1]; // Right neighbor state
            nextGen[i] = rules(left, me, right); // Compute next generation state based on ruleset
        }

        // The current generation is the new generation
        cells = nextGen;
        generation++;
    }
    

We’re almost done. The above code is complete except for the fact that we haven’t yet written the rules() function that computes the new state value based on the neighborhood (left, middle, and right cells). We know that function needs to return an integer (0 or 1) as well as receive three arguments (for the three neighbors).

    private int rules (int a, int b, int c)
    {
    

Now, there are many ways we could write this function, but I’d like to start with a long-winded one that will hopefully provide a clear illustration of what we are doing.

Let’s first establish how we are storing the ruleset. The ruleset, if you remember from the previous section, is a series of 8 bits (0 or 1) that defines that outcome for every possible neighborhood configuration.

Figure 7.14 Repeated

We can store this ruleset in Unity as an array.

    public int[] ruleSet0 = { 0, 1, 0, 1, 1, 0, 1, 0 };

And then say...

    if (a == 1 && b == 1 && c == 1) return ruleset[0];

If left, middle, and right all have the state 1, then that matches the configuration 111 and the new state should be equal to the first value in the ruleset array. We can now duplicate this strategy for all eight possibilities.

    private int Rules (int a, int b, int c) // Implementing the Wolfram rules
    {
        if (a == 1 && b == 1 && c == 1) return ruleset[0];
        if (a == 1 && b == 1 && c == 0) return ruleset[1];
        if (a == 1 && b == 0 && c == 1) return ruleset[2];
        if (a == 1 && b == 0 && c == 0) return ruleset[3];
        if (a == 0 && b == 1 && c == 1) return ruleset[4];
        if (a == 0 && b == 1 && c == 0) return ruleset[5];
        if (a == 0 && b == 0 && c == 1) return ruleset[6];
        if (a == 0 && b == 0 && c == 0) return ruleset[7];
        return 0;
    }
    

For this function to be valid, we have to make sure something is returned in cases where the states do not match one of the eight possibilities. We know this is impossible given the rest of our code, but Unity does not.

I like having the example written as above because it describes line by line exactly what is happening for each neighborhood configuration. However, it’s not a great solution. After all, what if we design a CA that has 4 possible states (0-3) and suddenly we have 64 possible neighborhood configurations? With 10 possible states, we have 1,000 configurations. Certainly we don’t want to type in 1,000 lines of code!

Another solution, though perhaps a bit more difficult to follow, is to convert the neighborhood configuration (a 3-bit number) into a regular integer and use that value as the index into the ruleset array.

So far in this section, we’ve written everything we need to compute the generations for a Wolfram elementary CA. Let’s take a moment to organize the above code into a class, which will ultimately help in the design of our overall scene.

    public class Chapter7Fig1CA
    {
        private int[] cells; // An array of 0s and 1s
        private int generation; // How many generations?
        private int[] ruleset; // An array to store the ruleset, for example {0,1,1,0,1,1,0,1}
        private int rowWidth; // How wide to make the array
        private int cellCapacity; // We limit how many cells we instantiate
        private int numberOfCells; // Which needs us to keep count
        private Vector2 screenSize; 
        private float yScreenOffset; // Cells are spawned with a small offset so they spawn in centered
        private float xScreenOffset; 

        public Chapter7Fig1CA(int[] ruleSetToUse)
        {
            rowWidth = 17;
            cellCapacity = 700;
            yScreenOffset = 0.5f;
            xScreenOffset = -0.5f;

            // How big our screen is in World Units
            screenSize = Camera.main.ScreenToWorldPoint(new Vector2(Screen.width, Screen.height));        
            numberOfCells = 0;
            ruleset = ruleSetToUse;
            cells = new int[cellCapacity / rowWidth];
            Restart();
        }

        public void Randomize() // If we wanted to make a random Ruleset
        {
            for (int i = 0; i < 8; i++)
            {
                ruleset[i] = Random.Range(0, 2);
            }
        }

        private void Restart()
        {
            for (int i = 0; i < cells.Length; i++)
            {
                cells[i] = 0;
            }
            cells[cells.Length / 2] = 1; // We arbitrarily start with just the middle cell having a state of "1"
            generation = 0;
        }

        // The process of creating the new generation
        public void Generate()
        {
            // First we create an empty array for the new values
            int[] nextGen = new int[cells.Length];

            // For every spot, determine new state by examing current state, and neighbor states
            // Ignore edges that only have one neighor
            for (int i = 1; i < cells.Length-1; i++)
            {
                int left = cells[i - 1]; // Left neighbor state
                int me = cells[i]; // Current state
                int right = cells[i + 1]; // Right neighbor state
                nextGen[i] = Rules(left, me, right); // Compute next generation state based on ruleset
            }

            // The current generation is the new generation
            cells = nextGen;
            generation++;
        }
    
        public void Display() // Drawing the cells. Cells with a state of 1 are black, cells with a state of 0 are white
        {
         if (numberOfCells <= cellCapacity)
            {
                for (int i = 0; i < cells.Length; i++)
                {
                    GameObject newCell = GameObject.CreatePrimitive(PrimitiveType.Quad);                
                    numberOfCells++;                
                    Renderer r = newCell.GetComponent<Renderer>();
                    r.material = new Material(Shader.Find("Diffuse"));
                    Object.Destroy(newCell.GetComponent<BoxCollider>());
                    if (cells[i] == 1)
                    {
                        r.material.color = Color.black;
                    }
                    else
                    {
                        r.material.color = Color.white;
                    }

                    // Set position based to lower left of screen, with screen offset
                    newCell.transform.position = new Vector3(i - screenSize.x - xScreenOffset, 
                                                    generation - screenSize.y + yScreenOffset);
                }
            }
        }

        private int Rules (int a, int b, int c) // Implementing the Wolfram rules
        {
            if (a == 1 && b == 1 && c == 1) return ruleset[0];
            if (a == 1 && b == 1 && c == 0) return ruleset[1];
            if (a == 1 && b == 0 && c == 1) return ruleset[2];
            if (a == 1 && b == 0 && c == 0) return ruleset[3];
            if (a == 0 && b == 1 && c == 1) return ruleset[4];
            if (a == 0 && b == 1 && c == 0) return ruleset[5];
            if (a == 0 && b == 0 && c == 1) return ruleset[6];
            if (a == 0 && b == 0 && c == 0) return ruleset[7];
            return 0;
        }

        public bool IsFinished() // The CA is done if it reaches a height limit
        {
            if (generation > Screen.height / rowWidth)
                return true;
            else
                return false;
        }
    }
    

7.4 Drawing an Elementary CA

What’s missing? Presumably, it’s our intention to display cells and their states in visual form. As we saw earlier, the standard technique for doing this is to stack the generations one on top of each other and draw a rectangle that is black (for state 1) or white (for state 0).

Figure 7.12 Repeated

Before we implement this particular visualization, I’d like to point out two things.

One, this visual interpretation of the data is completely literal. It’s useful for demonstrating the algorithms and results of Wolfram’s elementary CA, but it shouldn’t necessarily drive your own personal work. It’s rather unlikely that you are building a project that needs precisely this algorithm with this visual style. So while learning to draw the CA in this way will help you understand and implement CA systems, this skill should exist only as a foundation.

Second, the fact that we are visualizing a one-dimensional CA with a two-dimensional image can be confusing. It’s very important to remember that this is not a 2D CA. We are simply choosing to show a history of all the generations stacked vertically. This technique creates a two-dimensional image out of many instances of one-dimensional data. But the system itself is one-dimensional. Later, we are going to look at an actual 2D CA (the Game of Life) and discuss how we might choose to display such a system.

The good news is that drawing the CA is not particularly difficult. Let’s begin by looking at how we would render a single generation. Assume we have a Unity window 600 pixels wide and we want each cell to be a 10x10 square. We therefore have a CA with 60 cells. Of course, we can calculate this value dynamically.

    rowWidth = 17;
    cells = new int[cellCapacity / rowWidth];
    

In truth, we could optimize the above by having a white background and only drawing when there is a black cell (saving us the work of drawing many white squares), but in most cases this solution is good enough (and necessary for other more sophisticated designs with varying colors, etc.) Also, if we wanted each cell to be represented as a single pixel, we would not want to use Unity’s rect() function, but rather access the pixel array directly.

In the above code, you’ll notice the y-location for each rectangle is 0. If we want the generations to be drawn next to each other, with each row of cells marking a new generation, we’ll also need to compute a y-location based on how many iterations of the CA we’ve executed. We could accomplish this by adding a “generation” variable (an integer) to our CA class and incrementing it each time through generate(). With these additions, we can now look at the CA class with all the features for both computing and drawing the CA.

Example 7.1: Wolfram elementary cellular automata

• Code
• Demo

7.5 Wolfram Classification

Before we move on to looking at CA in two dimensions, it’s worth taking a brief look at Wolfram’s classification for cellular automata. As we noted earlier, the vast majority of elementary CA rulesets produce uninspiring results, while some result in wondrously complex patterns like those found in nature. Wolfram has divided up the range of outcomes into four classes:

Figure 7.18: Rule 222

Class 1: Uniformity. Class 1 CAs end up, after some number of generations, with every cell constant. This is not terribly exciting to watch. Rule 222 (above) is a class 1 CA; if you run it for enough generations, every cell will eventually become and remain black.

Figure 7.19: Rule 190

Class 2: Repetition. Like class 1 CAs, class 2 CAs remain stable, but the cell states are not constant. Rather, they oscillate in some regular pattern back and forth from 0 to 1 to 0 to 1 and so on. In rule 190 (above), each cell follows the sequence 11101110111011101110.

Figure 7.20: Rule 30

Class 3: Random. Class 3 CAs appear random and have no easily discernible pattern. In fact, rule 30 (above) is used as a random number generator in Wolfram’s Mathematica software. Again, this is a moment where we can feel amazed that such a simple system with simple rules can descend into a chaotic and random pattern.

Figure 7.21: Rule 110

Class 4: Complexity. Class 4 CAs can be thought of as a mix between class 2 and class 3. One can find repetitive, oscillating patterns inside the CA, but where and when these patterns appear is unpredictable and seemingly random. Class 4 CAs exhibit the properties of complex systems that we described earlier in this chapter and in Chapter 6. If a class 3 CA wowed you, then a class 4 like Rule 110 above should really blow your mind.

7.6 The Game of Life

The next step we are going to take is to move from a one-dimensional CA to a two-dimensional one. This will introduce some additional complexity; each cell will have a bigger neighborhood, but that will open up the door to a range of possible applications. After all, most of what we do in computer graphics lives in two dimensions, and this chapter will demonstrate how to apply CA thinking to what we draw in our Unity scenes.

In 1970, Martin Gardner wrote an article in Scientific American that documented mathematician John Conway’s new “Game of Life,” describing it as “recreational” mathematics and suggesting that the reader get out a chessboard and some checkers and “play.” While the Game of Life has become something of a computational cliché (make note of the myriad projects that display the Game of Life on LEDs, screens, projection surfaces, etc.), it is still important for us to build it from scratch. For one, it provides a good opportunity to practice our skills with two-dimensional arrays, object orientation, etc. But perhaps more importantly, its core principles are tied directly to our core goals—simulating the natural world with code. Though we may want to avoid simply duplicating it without a great deal of thought or care, the algorithm and its technical implementation will provide us with the inspiration and foundation to build simulations that exhibit the characteristics and behaviors of biological systems of reproduction.

Unlike von Neumann, who created an extraordinarily complex system of states and rules, Conway wanted to achieve a similar “lifelike” result with the simplest set of rules possible. Martin Gardner outlined Conway’s goals as follows:

“1. There should be no initial pattern for which there is a simple proof that the population can grow without limit. 2. There should be initial patterns that apparently do grow without limit. 3. There should be simple initial patterns that grow and change for a considerable period of time before coming to an end in three possible ways: fading away completely (from overcrowding or becoming too sparse), settling into a stable configuration that remains unchanged thereafter, or entering an oscillating phase in which they repeat an endless cycle of two or more periods.”

—Martin Gardner, Scientific American 223 (October 1970): 120-123.

The above might sound a bit cryptic, but it essentially describes a Wolfram class 4 CA. The CA should be patterned but unpredictable over time, eventually settling into a uniform or oscillating state. In other words, though Conway didn’t use this terminology, it should have all those properties of a complex system that we keep mentioning.

Let’s look at how the Game of Life works. It won’t take up too much time or space, since we’ve covered the basics of CA already.

Figure 7.22

First, instead of a line of cells, we now have a two-dimensional matrix of cells. As with the elementary CA, the possible states are 0 or 1. Only in this case, since we’re talking about “life," 0 means dead and 1 means alive.

The cell’s neighborhood has also expanded. If a neighbor is an adjacent cell, a neighborhood is now nine cells instead of three.

With three cells, we had a 3-bit number or eight possible configurations. With nine cells, we have 9 bits, or 512 possible neighborhoods. In most cases, it would be impractical to define an outcome for every single possibility. The Game of Life gets around this problem by defining a set of rules according to general characteristics of the neighborhood. In other words, is the neighborhood overpopulated with life? Surrounded by death? Or just right? Here are the rules of life.

• Death. If a cell is alive (state = 1) it will die (state becomes 0) under the following circumstances.
• Overpopulation: If the cell has four or more alive neighbors, it dies.
• Loneliness: If the cell has one or fewer alive neighbors, it dies.
• Birth. If a cell is dead (state = 0) it will come to life (state becomes 1) if it has exactly three alive neighbors (no more, no less).
• Stasis. In all other cases, the cell state does not change. To be thorough, let’s describe those scenarios.
• Staying Alive: If a cell is alive and has exactly two or three live neighbors, it stays alive.
• Staying Dead: If a cell is dead and has anything other than three live neighbors, it stays dead.

Let’s look at a few examples.

Figure 7.23

With the elementary CA, we were able to look at all the generations next to each other, stacked as rows in a 2D grid. With the Game of Life, however, the CA itself is in two dimensions. We could try creating an elaborate 3D visualization of the results and stack all the generations in a cube structure (and in fact, you might want to try this as an exercise). Nevertheless, the typical way the Game of Life is displayed is to treat each generation as a single frame in an animation. So instead of viewing all the generations at once, we see them one at a time, and the result resembles rapidly growing bacteria in a petri dish.

One of the exciting aspects of the Game of Life is that there are initial patterns that yield intriguing results. For example, some remain static and never change.

Figure 7.24

There are patterns that oscillate back and forth between two states.

Figure 7.25

And there are also patterns that from generation to generation move about the grid. (It’s important to note that the cells themselves aren’t actually moving, although we see the appearance of motion in the result as the cells turn on and off.)

Figure 7.26

If you are interested in these patterns, there are several good “out of the box” Game of Life demonstrations online that allow you to configure the CA’s initial state and watch it run at varying speeds. Two examples you might want to examine are:

• Exploring Emergence by Mitchel Resnick and Brian Silverman, Lifelong Kindergarten Group, MIT Media Laboratory
• Conway’s Game of Life by Steven Klise (uses Unity.js!)
• For the example we’ll build from scratch in the next section, it will be easier to simply randomly set the states for each cell.

7.7 Programming the Game of Life

Now we just need to extend our code from the Wolfram CA to two dimensions. We used a one-dimensional array to store the list of cell states before, and for the Game of Life, we can use a two-dimensional array.

    int[,] next = new int[columns, rows];
              

And to compute the next generation, just as before, we need a fresh 2D array to write to as we analyze each cell’s neighborhood and calculate a new state.

OK. Before we can sort out how to actually calculate the new state, we need to know how we can reference each cell’s neighbor. In the case of the 1D CA, this was simple: if a cell index was i, its neighbors were i-1 and i+1. Here each cell doesn’t have a single index, but rather a column and row index: x,y. As shown in Figure 7.27, we can see that its neighbors are: (x-1,y-1) (x,y-1), (x+1,y-2), (x-1,y), (x+1,y), (x-1,y+1), (x,y+1), and (x+1,y+1).

All of the Game of Life rules operate by knowing how many neighbors are alive. So if we create a neighbor counter variable and increment it each time we find a neighbor with a state of 1, we’ll have the total of live neighbors.

And again, just as with the Wolfram CA, we find ourselves in a situation where the above is a useful and clear way to write the code for teaching purposes, allowing us to see every step (each time we find a neighbor with a state of one, we increase a counter). Nevertheless, it’s a bit silly to say, “If the cell state equals one, add one to a counter” when we could just say, “Add the cell state to a counter.” After all, if the state is only a 0 or 1, the sum of all the neighbors’ states will yield the total number of live cells. Since the neighbors are arranged in a mini 3x3 grid, we can add them all up with another loop.

    int[,] next = new int[columns, rows];

    // Loop through every spot in our 2D array and check spots neighbors
    for (int x = 1; x < columns - 1; x++)
    {
        for (int y = 1; y < rows - 1; y++)
        {
            // Add up all the states in a 3x3 surrounding grid
            int neighbors = 0;
            for (int i = -1; i <= 1; i++)
            {
                for (int j = -1; j <= 1; j++)
                {
                    neighbors += board[x + i, y + j];
                }
            }
    }
    

Of course, we’ve made a mistake in the code above. In the Game of Life, the cell itself does not count as one of the neighbors. We could use a conditional to skip adding the state when both i and j equal 0, but another option would be to just subtract the cell state once we’ve finished the loop.

    neighbors -= board[x, y];
    

Finally, once we know the total number of live neighbors, we can decide what the cell’s new state should be according to the rules: birth, death, or stasis.

    // Rules of Life
    if ((board[x,y] == 1) && (neighbors < 2)) next[x,y] = 0;        // Loneliness
    else if ((board[x,y] == 1) && (neighbors > 3)) next[x,y] = 0;   // Overpopulation
    else if ((board[x,y] == 0) && (neighbors == 3)) next[x,y] = 1;  // Reproduction
    else next[x,y] = board[x,y];                                    // Stasis
    

Finally, once the next generation is calculated, we can employ the same method we used to draw the Wolfram CA—a square for each spot, white for off, black for on.

    // The process of creating the new generation
    public void Generate()
    {
        int[,] next = new int[columns, rows];

        // Loop through every spot in our 2D array and check spots neighbors
        for (int x = 1; x < columns - 1; x++)
        {
            for (int y = 1; y < rows - 1; y++)
            {
                // Add up all the states in a 3x3 surrounding grid
                int neighbors = 0;
                for (int i = -1; i <= 1; i++)
                {
                    for (int j = -1; j <= 1; j++)
                    {
                        neighbors += board[x + i, y + j];
                    }
                }

                // A little trick to subtract the current cell's state since
                // we added it in the above loop
                neighbors -= board[x, y];

                // Rules of Life
                if ((board[x,y] == 1) && (neighbors < 2)) next[x,y] = 0;        // Loneliness
                else if ((board[x,y] == 1) && (neighbors > 3)) next[x,y] = 0;   // Overpopulation
                else if ((board[x,y] == 0) && (neighbors == 3)) next[x,y] = 1;  // Reproduction
                else next[x,y] = board[x,y];                                    // Stasis
            }
        }

        // Next is now our board
        board = next;
    }
    

Example 7.2: Game of Life

• Code
• Demo

Exercise 7.6

Create a Game of Life simulation that allows you to manually configure the grid by drawing or with specific known patterns.

Exercise 7.7

Implement “wrap-around” for the Game of Life so that cells on the edges have neighbors on the opposite side of the grid.

Exercise 7.8

While the above solution (Example 7.2) is convenient, it is not particularly memory-efficient. It creates a new 2D array for every frame of animation! This matters very little for a Unity desktop application, but if you were implementing the Game of Life on a microcontroller or mobile device, you’d want to be more careful. One solution is to have only two arrays and constantly swap them, writing the next set of states into whichever one isn’t the current array. Implement this particular solution.

7.8 Object-Oriented Cells

Over the course of the previous six chapters, we’ve slowly built examples of systems of objects with properties that move about the screen. And in this chapter, although we’ve been talking about a “cell” as if it were an object, we actually haven’t been using any object orientation in our code (other than a class to describe the CA system as a whole). This has worked because a cell is such an enormously simple object (a single bit). However, in a moment, we are going to discuss some ideas for further developing CA systems, many of which involve keeping track of multiple properties for each cell. For example, what if a cell needed to remember its last ten states? Or what if we wanted to apply some of our motion and physics thinking to a CA and have the cells move about the window, dynamically changing their neighbors from frame to frame?

To accomplish any of these ideas (and more), it would be helpful to see how we might treat a cell as an object with multiple properties, rather than as a single 0 or 1. To show this, let’s just recreate the Game of Life simulation. Only instead of:

    private int[,] board;
    

Let's have:

    private Chapter7Figure3Cell[,] board;
    

where Cell is a class we will write. What are the properties of a Cell object? In our Game of Life example, each cell has a location and size, as well as a state.

    public class Chapter7Figure3Cell
    {
        // GameObject properties, to visually represent and draw our cell
        private GameObject cellRep;
        private Material cellMaterial;

        // Size of the screen in meters, or Unity units
        private Vector2 screenSize;
        private float yScreenOffset; // Cells are spawned with a small offset so they spawn in more centered
        private float xScreenOffset;

        // Location
        private float x, y;

        public int State;
    }
    

In the non-OOP version, we used a separate 2D array to keep track of the states for the current and next generation. By making a cell an object, however, each cell could keep track of both states. In this case, we’ll think of the cell as remembering its previous state (for when new states need to be computed).

    public int Previous;
            

This allows us to visualize more information about what the state is doing. For example, we could choose to color a cell differently if its state has changed. For example:

Example 7.3: Game of Life OOP

• Code
• Demo

Not much else about the code (at least for our purposes here) has to change. The neighbors can still be counted the same way; the difference is that we now need to refer to the object’s state variables as we loop through the 2D array.

    // The process of creating the new generation
    public void Generate()
    {
        for (int i = 0; i < columns; i++)
        {
            for (int j = 0; j < rows; j++)
            {
                board[i, j].SavePrevious();
            }
        }

        // Loop through every spot in our 2D array and check spots neighbors
        for (int x = 0; x < columns; x++)
        {
            for (int y = 0; y < rows; y++)
            {

                // Add up all the states in a 3x3 surrounding grid
                int neighbors = 0;
                for (int i = -1; i <= 1; i++)
                {
                    for (int j = -1; j <= 1; j++)
                    {
                        neighbors += board[(x + i + columns) % columns, (y + j + rows) % rows].Previous;
                    }
                }

                // A little trick to subtract the current cell's state since
                // we added it in the above loop
                neighbors -= board[x,y].Previous;

                // Rules of Life
                // Loneliness
                if ((board[x,y].State == 1) && (neighbors < 2)) board[x,y].NewState(0);
                // Overpopulation
                else if ((board[x,y].State == 1) && (neighbors > 3)) board[x,y].NewState(0);
                // Reproduction
                else if ((board[x,y].State == 0) && (neighbors == 3)) board[x,y].NewState(1);
                // else do nothing!

            }
        }
    }
    

7.9 Variations of Traditional CA

Now that we have covered the basic concepts, algorithms, and programming strategies behind the most famous 1D and 2D cellular automata, it’s time to think about how you might take this foundation of code and build on it, developing creative applications of CAs in your own work. In this section, we’ll talk through some ideas for expanding the features of the CA examples. Example answers to each of these exercises can be found on the book website.

1) Non-rectangular Grids. There’s no particular reason why you should limit yourself to having your cells on a rectangular grid. What happens if you design a CA with another type of shape?

Exercise 7.9

Create a CA using a grid of hexagons (as below), each with six neighbors.

2) Probabilistic. The rules of a CA don’t necessarily have to define an exact outcome.

Exercise 7.10

Rewrite the Game of Life rules as follows:

• Overpopulation: If the cell has four or more alive neighbors, it has a 80% chance of dying.
• Loneliness: If the cell has one or fewer alive neighbors, it has a 60% chance of dying.
• Etc.

3) Continuous. We’ve looked at examples where the cell’s state can only be a 1 or a 0. But what if the cell’s state was a floating point number between 0 and 1?

Exercise 7.11

Adapt Wolfram elementary CA to have the state be a float. You could define rules such as, “If the state is greater than 0.5” or “…less than 0.2.”

4) Image Processing. We briefly touched on this earlier, but many image-processing algorithms operate on CA-like rules. Blurring an image is creating a new pixel out of the average of a neighborhood of pixels. Simulations of ink dispersing on paper or water rippling over an image can be achieved with CA rules.

Exercise 7.12

Create a CA in which a pixel is a cell and a color is its state.

5) Historical. In the Game of Life object-oriented example, we used two variables to keep track of its state: current and previous. What if you use an array to keep track of a cell’s state history? This relates to the idea of a “complex adaptive system,” one that has the ability to adapt and change its rules over time by learning from its history. We’ll see an example of this in Chapter 10: Neural Networks.

Exercise 7.13

Visualize the Game of Life by coloring each cell according to how long it’s been alive or dead. Can you also use the cell’s history to inform the rules?

6) Moving cells. In these basic examples, cells have a fixed position on a grid, but you could build a CA with cells that have no fixed position and instead move about the screen.

Exercise 7.14

Use CA rules in a flocking system. What if each boid had a state (that perhaps informs its steering behaviors) and its neighborhood changed from frame to frame as it moved closer to or further from other boids?

7) Nesting. Another feature of complex systems is that they can be nested. Our world tends to work this way: a city is a complex system of people, a person is a complex system of organs, an organ is a complex system of cells, and so on and so forth.

Exercise 7.15

Design a CA in which each cell itself is a smaller CA or a system of boids.

The Ecosystem Project

Step 7 Exercise:

Incorporate cellular automata into your ecosystem. Some possibilities:

• Give each creature a state. How can that state drive their behavior? Taking inspiration from CA, how can that state change over time according to its neighbors’ states?
• Consider the ecosystem’s world to be a CA. The creatures move from tile to tile. Each tile has a state—is it land? water? food?
• Use a CA to generate a pattern for the design of a creature in your ecosystem.

Licenses

The book's text and illustrations are licensed under a Creative Commons Attribution-NonCommercial 3.0 Unported License.

All of the book's source code is licensed under the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version.

Remixer

Joshua A. Fisher is an Assistant Professor of the Center for Emerging Media Design and Development at Ball State University.

His portfolio can be found here

LinkedIn GitHub

Author

Daniel Shiffman is a Professor of the Interactive Telecommunications Program at New York University.

He is the author of Learning Processing.

Twitter GitHub