Scotty Hoag
Programmer Portfolio
 
scotty.hoag@gmail.com  (209)-298-2622
NES Mug


Gosper's Glider Gun
Conway's Game of Life
Anthro-196, Tutorial #2



Conway's Game of Life started as an experiment for modeling automated systems and machines that could act and reproduce independantly using a simple set of clearly defined rules. Work like Conway's subsequently evolved into a whole area of research in Mathematics called Cellular Automation. From the Wikipedia entry:

"It [Cellular Automata] consists of a regular grid of cells, each in one of a finite number of states, such as 'On' and 'Off' ... A new generation is created (advancing t by 1), according to some fixed rule (generally, a mathematical function) that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood. For example, the rule might be that the cell is 'On' in the next generation if exactly two of the cells in the neighborhood are 'On' in the current generation, otherwise the cell is 'Off' in the next generation."

By configuring the aforementioned rules in particular ways, it is possible to create little robots that simulate various behaviors. Cellular automata have been used to model many different things from the development of skintone patterns in certain animal species to the spread of forest fires. The purpose of this tutorial is to teach you how to extend the sample code provided to you to create cellular automata for yourself. Before we dive in too deep, though, we should start by looking at Conway's original ruleset.

Conway's CA Rules
  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overcrowding.
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

Try running the sample code included in ConwaysGameOfLife.zip and see what these rules produce. Click a cell on the grid to change a DEAD cell (Clear) to an ALIVE cell (Blue), change an ALIVE cell to a ROCK (Black), or change a ROCK cell to a DEAD cell. You can also drag the mouse to "paint" multiple cells at once. The spacebar starts and pauses the simulation, while '+' and '-' change the simulation speed. 'H' toggles the help text, 'R' resets the board, 'B' turns the background image on or off, 'S' saves a screenshot, and 'A' saves a series of frames.

Smiley Simulation

To create Conway's Game of Life, we have to do two things. First, we have to build a grid of cells. Then, we have to be able to look at each cell and change its state based on the state of its neighboring cells. To accomplish the first task, we are going to use a new kind of variable called an array. An array is just a list of like variables with some convenient bonus properties. So, an int array is a basically just a list of ints.


int cellsPerRow = 5;
int girdSize = cellsPerRow*cellsPerRow;
int[] cells = new int[gridSize]; //Defines our array.

This block of code defines a 5x5 grid using a 25 element array called "cells". The One thing to remember is that the first element of an array is element number zero, and therefore the last element is one less than the number of elements we said we wanted. Thus, our 25 array indicies like this:

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Since we're going to use this list as our grid, we're going to treat it as if it were structured as a set of rows and columns like this:

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

If you change the value of cellsPerRow, you will also change the dimensions of the grid. Setting cellsPerRow to 3 will create a 9-square (3x3) grid. To access the contents of a cell, we use the bracket syntax. Think of the brackets "[]" as the square shape of the cell in the grid. To reference cell 5 of the array named "cells", we would write "cells[5]".

Next, we need to define the types of cells in our simulation. These are defined near the top of Student.pde.


int numStatusTypes = 3; //We have three statuses in our sim.
final int DEAD = 0; //DEAD cells are empty spaces.
final int ALIVE = 1; //ALIVE cells can multiply and revive dead cells.
final int ROCK = 2; //ROCK cells are permanently dead and can not be revived.

In Conway's original game, a cell could be either DEAD or ALIVE. We have added one additional type, ROCK. It behaves like you would expect (It just sits there inactive) and can not change into either a live or dead cell. We added it just to show that its relatively easy to add new types and extend Conway's rules. If you want to add your own types, be sure to change the value of the variable "numStatusTypes". For example, if we wanted to add a type "ZOMBIE", we would wind up with the following:


int numStatusTypes = 4; //We have three statuses in our sim.
final int DEAD = 0; //DEAD cells are empty spaces.
final int ALIVE = 1; //ALIVE cells can multiply and revive dead cells.
final int ROCK = 2; //ROCK cells are permanently dead and can not be revived.
final int ZOMBIE = 3;


Now that we have our grid and cells defined, we need a way to update each cell once per timestep. In the Student.pde file, there is a function called updateCell(). If you decide to use the Conway project for your homework, this is where most of your work will be. Let's take a look at it.


int updateCell(int cellNumber) {
int[] neighbors = getNeighborStatus(cellNumber);
int liveNeighbors = numNeighborsWithStatus(neighbors, ALIVE);
int thisCellsStatus = neighbors[THISCELL];

//RULES
if ((thisCellsStatus == ALIVE) && (liveNeighbors < 2)) { //Rule #1
return DEAD;
} else if ((thisCellsStatus == ALIVE) && (liveNeighbors == 2 || liveNeighbors == 3)) { //Rule #2
return ALIVE;
} else if ((thisCellsStatus == ALIVE) && (liveNeighbors > 3)) { //Rule #3
return DEAD;
} else if ((thisCellsStatus == DEAD) && (liveNeighbors == 3)) { //Rule #4
return ALIVE;
} else {
//If we don't match any of Conway's rules, just return the
//cell's value. This is in the case where we have added new types.
//Example: If this cell is a ROCK, none of the above rules will match.
return thisCellsStatus;
}
}

This is called once per cell per timestep. The number cellNumber is the grid number of the cell being updated. In order to find out what to do with cell, we have to determine the state of the cell's neighbors. The first line inside the braces, "int[] neighbors = getNeighborStatus(cellNumber);" stores a list of this cell's neighbors' statuses in an array variable called neighbors. How convenient! The neighbors list is organized as follows:

0
1
2
3
4
5
6
7
8

You can also think about it like this:

NORTHWEST
NORTH
NORTHEAST
WEST
THISCELL
EAST
SOUTHWEST
SOUTH
SOUTHEAST

So, the current cell's status is stored in "neighbor[4]" or "neighbor[THISCELL]". Neighbors that are off of the grid (If the cell you are updating is in the top row, all of the northern cells are off of the grid) have a status of DEAD.

The next line, "int liveNeighbors = numNeighborsWithStatus(neighbors, ALIVE);" creates a variable called "liveNeighbors" that stores the number of neighboring cells that are ALIVE. The first value passed to the function "numNeighborsWithStatus" is the list of neighbors and the second value is the status to count. So, calling "numNeighborsWithStatus(neighbors, ROCK);" would return the number of neighboring cells that are ROCKs. You can also count any other status that you have defined at the top of the Student.pde file.

The third line, "int thisCellsStatus = neighbors[THISCELL];" just creates a variable called "thisCellsStatus that stores the status of this cell. This is just for convenience. We could just refer to this cell's status as "neighbors[THISCELL]" if we wanted to.

That brings us to the actual rules. The large chunk of text immediately following the three lines explained above define Conway's rules. The first if-statement defines rule 1. The double-ampersand "&&" means "AND", as in "This AND that". The "return" keyword sets the new value of this cell to the given status and immediately exits the updateCell() function. So, the first line reads "If this cell is alive AND the number of live neighboring cells is less than 2, then this cell dies."

So, what's up with the "else" word? If the conditions for an if-statement are false, than the code following the word "else" is run instead. In this way, you can ask a series of questions. "Does rule 1 work here? No? How about rule two, then? No? How about rule three? Yes? Okay, we're done!" So, in the case where the first rule doesn't match, we check the second rule. The second if-statement can be read "If this cell is alive AND it has two OR three living neighbor cells, then this cell is alive." Note that the double-bar "||" stands for "OR".

If all four rules have been checked, we run the code following the final "else" keyword. This can occur because we have added an extra type of cell that was not present in Conway's original rules: The ROCK. A rock cell will not match any of the previous rules since they apply only to ALIVE and DEAD cells. In this case, we want the cell to stay as it is so we just return the cell's current status. You can add your own rules to those above by adding more if-statements into the chain, or change the existing rules. Let's add in a few rules for our ZOMBIE type:


int updateCell(int cellNumber) {
int[] neighbors = getNeighborStatus(cellNumber);
int liveNeighbors = numNeighborsWithStatus(neighbors, ALIVE);
int thisCellsStatus = neighbors[THISCELL];

//RULES
if ((thisCellsStatus == ALIVE) &&
((neighbors[NORTH] == ZOMBIE) ||
(neighbors[SOUTH] == ZOMBIE) ||
(neighbors[EAST] == ZOMBIE) ||
(neighbors[WEST] == ZOMBIE))) //Be sure your parens, brackets, and braces match up!
{
return ZOMBIE;
} else if ((thisCellsStatus == DEAD) && (neighbors[WEST] == ZOMBIE)) {
return ZOMBIE;
} else if (thisCellsStatus == ZOMBIE) {
return DEAD;
} else if ((thisCellsStatus == ALIVE) && (liveNeighbors < 2)) { //Rule #1
return DEAD;
} else if ((thisCellsStatus == ALIVE) && (liveNeighbors == 2 || liveNeighbors == 3)) { //Rule #2
return ALIVE;
} else if ((thisCellsStatus == ALIVE) && (liveNeighbors > 3)) { //Rule #3
return DEAD;
} else if ((thisCellsStatus == DEAD) && (liveNeighbors == 3)) { //Rule #4
return ALIVE;
} else {
//If we don't match any of Conway's rules, just return the
//cell's value. This is in the case where we have added new types.
//Example: If this cell is a ROCK, none of the above rules will match.
return thisCellsStatus;
}
}

We added three new rules. First, if a cell is ALIVE and a ZOMBIE exists either directly north, south, east, or west of this cell, then this cell also becomes a ZOMBIE. The next rule states that if a this cell is DEAD and a zombie exists directly to the west, then this cell becomes a ZOMBIE. The last rule says that if this cell is a ZOMBIE, the cell dies. The first rule causes zombies to turn other cells into zombies, while the second and third rules give the illusion that the zombie lurches across the screen.

Next, we need to tell Processing how to draw the cells. The function "drawCell()" is called once per cell per frame and defines how to draw the cell based on its position and status. Let's take a look at it:


void drawCell(int cellStatus, int column, int row) {
if (cellStatus == DEAD) { //Cell is dead.
fill(0, 0, 0, 0); //Color for a dead cell. (Transparent)
rect(column*cellWidth, row*cellHeight, cellWidth, cellHeight);
} else if (cellStatus == ALIVE) { //Cell is alive.
fill(0, 30, 80); //Color for a living cell.
rect(column*cellWidth, row*cellHeight, cellWidth, cellHeight);
} else if (cellStatus == ROCK) { //Cell is a rock.
fill(30, 30, 30); //Color for a rock.
rect(column*cellWidth, row*cellHeight, cellWidth, cellHeight);
}
}

Translated, the function says "If the cell is DEAD, set the color to clear and draw a rectangle. Else, if the cell is ALIVE, set the color to blue and draw a rectangle. Else, if the cell is a ROCK, set the color to dark grey and draw a rectangle. If we wanted to extend the game to include our ZOMBIE type, the new code would look something like the following:


void drawCell(int cellStatus, int column, int row) {
if (cellStatus == DEAD) { //Cell is dead.
fill(0, 0, 0, 0); //Color for a dead cell. (Transparent)
rect(column*cellWidth, row*cellHeight, cellWidth, cellHeight);
} else if (cellStatus == ALIVE) { //Cell is alive.
fill(0, 30, 80); //Color for a living cell.
rect(column*cellWidth, row*cellHeight, cellWidth, cellHeight);
} else if (cellStatus == ROCK) { //Cell is a rock.
fill(30, 30, 30); //Color for a rock.
rect(column*cellWidth, row*cellHeight, cellWidth, cellHeight);
}
else if (cellStatus == ZOMBIE) { //Cell is a zombie.
fill(0, 50, 30); //Color for a zombie.
rect(column*cellWidth, row*cellHeight, cellWidth, cellHeight);
}

}

The last function that we are going to look at is the function that writes the help text on the screen.


void printDebugText() {
fill(60, 20, 20); //Sets the text color. Change it if it is hard for you to read it.
text(
"Sim " + (runSimulation ? "Running, Pause" : "Paused, Play") +
" with spacebar, set speed with '+' and '-'." + "\n" +
"Toggle help: 'H', Toggle background: 'B', Reset grid: 'R'" + "\n" +
"Take screenshot: 'S', Save " + framesPerAnimation + " frames (animation): 'A'." + "\n" +
"Click a cell to change its status, drag to paint." + "\n" +
"Sim Speed = " + updatesPerSecond + "\n\n" +
"Total Cells = " + gridSize + "\n" +
"DEAD = " + statusCounter[DEAD] + "\n" +
"ALIVE = " + statusCounter[ALIVE] + "\n" +
"ROCK = " + statusCounter[ROCK] + "\n" +
"",
screenBuffer, screenBuffer, width-2*screenBuffer, height-2*screenBuffer);
}
}

...and we'll just make a one-line addition to add information about the zombies.


void printDebugText() {
fill(60, 20, 20); //Sets the text color. Change it if it is hard for you to read it.
text(
"Sim " + (runSimulation ? "Running, Pause" : "Paused, Play") +
" with spacebar, set speed with '+' and '-'." + "\n" +
"Toggle help: 'H', Toggle background: 'B', Reset grid: 'R'" + "\n" +
"Take screenshot: 'S', Save " + framesPerAnimation + " frames (animation): 'A'." + "\n" +
"Click a cell to change its status, drag to paint." + "\n" +
"Sim Speed = " + updatesPerSecond + "\n\n" +
"Total Cells = " + gridSize + "\n" +
"DEAD = " + statusCounter[DEAD] + "\n" +
"ALIVE = " + statusCounter[ALIVE] + "\n" +
"ROCK = " + statusCounter[ROCK] + "\n" +

"ZOMBIE = " + statusCounter[ZOMBIE] + "\n" +

"",
screenBuffer, screenBuffer, width-2*screenBuffer, height-2*screenBuffer);
}
}

...And we're done! Now let's see our Zombie hoard in action.

Zombie Simulation

That is all you need to know to make your own Cellular automata. You can create brand new types of simulations by adding new cell types and new rules. For example, you could model a forest fire with DEAD, ASH, GRASS, TREE, and FIRE types. GRASS with one FIRE neighbor catches fire itself. A TREE with three FIRE neighbors catches fire. A cell that was on fire turns into ash.

On bSpace, I have uploaded an example called ConwaysGameOfCheese_001.zip that models bacteria used for making swiss cheese. If enough ALIVE bacteria approach MILK, the MILK turns into cheese. If too many ALIVE bacteria gather around one area, they produce a carbon dioxide bubble (The holes or "eyes") in the cheese. Take a look at the sample and see what I changed to make it. Please email me if you have any questions, and have fun with your cellular automata!

Cheese Simulation