Fourth Tutorial: Cellular Automata.
In this tutorial we are going to look at a type of computational model called a Cellular Automata (at Wikipedia and at Wolfram alpha) or CA for short. CAs were proposed by John von Neumann and Stanislaw Ulam, while working at Los Alamos National Laboratory, while working on the American nuclear program in the late forties. Cellular automata consist of a number of cells which can have different states, and certain rules for changing these, depending of the states of their neighbours. Cellular automata are interesting because through a very simple mechanism they can model a large number of natural phenomena, from fluid dynamics to the growth of corals or population dynamics and ecological systems. In 2002, Stephen Wolfram published his book “a New Kind of Science” , in which he proposed Cellular Automata and other simple computational models as the basis for a new way of representing, modelling and studying physical phenomena. Cellular Automata have also been proposed as models of city growth, and particularly studied by Michael Batty at UCL, together with other models of self-organisation. Actually, before we proceed to implement our CAs, it is worth mentioning software which are strictly dedicated to the programming of Cellular Automata, Agents, and other types of self-organising, parallel systems, such as StarLogo and NetLogo, which are often meant to be very simple to use.
In this tutorial we are going to look to how to write a Cellular Automata in Processing. There are also a number of examples of Cellular Automata directly accessible in the Examples folder (“File->Examples…”), under “Topics”, or under “Books->Nature of Code Book ” by Daniel Shiffman (you can also find the examples at the Processing website, and the Nature of Code book website).
We are going to look first at some basic concepts that we will be using:
First, an array with more than one dimension, actually, a two dimensional array (the method is the same if we want a three-dimensional, four-dimensional or n dimensional array…usually more than 3 dimensions are quite rare, and in general it means that your are thinking about something the wrong way). We are going to use this 2dimensional array to store a grid made of rectangular cells for our Cellular Automata. A 2dimensional array is apparently not that different form a regular array, except that instead of having one index, it has 2, one for columns and one for rows (it doesn’t really matter which one is which, as long as one is consistent when using them in a program). Actually, a 2 dimensional array in Processing is rather an array of arrays… one could think of a normal array that has as its elements other arrays. Here is a tutorial, if you want to learn more.
So the basic declaration of a 2 Dimensional Array is like this (an array of booleans in this case):
boolean[][] aGridOfCells;
Before we use it, we need to allocate it, as with the one dimensional arrays. For example
aGridOfCells=boolean[30][20] ;
Will allocate “aGridOfCells” to be 30 columns width and 20 rows high (there are no really directions in an array, and we may as well have said that it has 30 rows and 20 columns, but we will stick to this convention in our tutorial, it is a bit more intuitive, specially when drawing the array).
We can access any element in the array the same way as with the one dimensional array, but now with two different indices, one for the columns, and one for the rows. For example to set the element in column 7 and row 3 to “true”, we would do:
aGridOfCells[7][3]=true;
Another important thing with 2dimensional arrays is the way we iterate through all its elements. We usually do this with a nested loop, that is, a loop inside a loop. Here is a small processing sketch that declares, allocates, initialises with random values and draws a 2dimensional array (check the loops inside the loops).
boolean[][] aGridOfCells; //the declaration of a 2D Array of booleans
int columns=40;
int rows=30;
//just the size of each cell in pixels, to draw it
int pixelsPerCell=4;
void setup(){
size(400,400);
stroke(100);//grey stroke
aGridOfCells =new boolean[columns][rows]; //allocation (all elements in the array are automatically initialised to false).
//for iterating through all the elements in the array, we need to have a loop inside a loop...
for(int i=0;i<columns;i++){ //iterate through all the columns
for(int j=0;j<rows;j++){ //iterate through all the rows in each column
//we generate a random number between 0 and 100... if smaller than 20, we turn "on" the cell
if(random(0,100)<20){
aGridOfCells[i][j]=true;
}
}
}
}
void draw(){
background(255);
//for drawing, we also iterate through every element in the array
for(int i=0;i<columns;i++){ //iterate through all the columns
for(int j=0;j<rows;j++){
if(aGridOfCells[i][j]==true){
fill(255); //if "on" set colour white
}else{ //else, it is "off", set it black
fill(0);
}
rect(i*pixelsPerCell, j*pixelsPerCell,pixelsPerCell,pixelsPerCell);
}
}
}
A two dimensional Cellular Automata consists of an array of current states, an array of future states, a way of checking the states of the neighbours of each cell, and rules that determine the future state och each cell depending of the states of its neighbours. In the following example, I have tried to divide the code in many small parts, each in a separate function. This is basically good practice, you should not write loooong bits of code with lots of loops and conditions nested in each other. Dividing code into separate functions makes it more understandable, easier to debug, and more modular, which means that it is easier to reuse and change. I will introduce the different functions and parts as they would be executed when the program runs. This is also a good way of reading code; rather than reading it from start to end as a piece of normal text, or the different bits separately, start untangling it from the parts that you know. In processing this would mean start from the declaration of global variables, that is, those declared outside any curly brackets (usually at the top), continue with the setup() ,check all functions called from there, and then do the same with draw(). So there we go…
The program begins by declaring the 2D array for the current states, and another 2D array to store the future states. We also use a couple of variables (like above) to define the size of the arrays, and the size in pixels of each cell:
boolean[][] cellsNow; //2 dimensional array of bools boolean[][] cellsFuture; //2 dimensional array of bools // columns and rows are not really necessary, one could // use cells.length and cells[0].length instead, but makes // things clearer int columns, rows; int scale=5; //this means that the cells will be 5x5 pixels...
Now we go to the setup():
void setup(){
size(500,500);
frameRate(1); //one frame per second...slow motion
background(255); //draw background white
//we calculate the columns and rows so they fill the screen
//when we draw them...
columns=width/scale;
rows=height/scale;
cellsNow=new boolean[columns][rows]; //in an array, booleans will be automatically set to false...
cellsFuture=new boolean[columns][rows];
//we set the cell at the centre "on" (true)
cellsNow[columns/2][rows/2]=true;
}
So far everything looks quite similar to the previous example…We also have a draw:
void draw(){
background(255); //clean the background
drawCells(); //draw
tick(); //calculate future values
update();
}
That calls first a “drawCells();” function, which is as follows (similar to the one we have already seen):
void drawCells(){
for(int i=0;i<columns;i++){//we go through all the columns
for(int j=0;j<rows;j++){
if(cellsNow[i][j]==true){
fill(0); //black if true
}else{
fill(255); //white if false
}
rect(i*scale,j*scale,scale,scale);
}
}
}
…and two other functions, which I have called “tick()” (as a tick in a clock) and “update()”. We will look first at “tick()”:
void tick(){
for(int i=0;i<columns;i++){//we go through all the columns
for(int j=0;j<rows;j++){
int numNeigs= countNeighbours(i,j);
cellsFuture[i][j]=applyRules(numNeigs);
}
}
}
It iterates through all cells with a nested loop, as we have seen, and it calls two other functions: “countNeighbours()”, which takes i and j as parameters, and which sets an int called numNeigs, and “applyRules()”, which we use to set the future state of each cell. We will look first at countNeighbours(), which it also calls the helper function “wrap()”:
int countNeighbours(int col,int row){
//this is what is generally known as the "Moore neighborhood".
//it comprises the 8 cells surrounding the one in col and row.
//We have to be carefull with the cells in the borders (col==0,
//col==colums-1, row==0 and row==rows-1). We decide to use a method
//similar to the"wrap around world" we have seen with the particles/agents.
int totalNeighbours=0;
for(int i=col-1;i<=col+1;i++){
//wrap the column.
int neigColumn=wrap(i,columns);
for(int j=row-1;j<=row+1;j++){
//wrap the row.
int neigRow=wrap(j,rows);
//now we count it, if it is "on" (true)
if(cellsNow[neigColumn][neigRow]==true){
totalNeighbours++;
}
} //end of row loop
} //end of column loop
return totalNeighbours;
}
//this checks if a value val is between 0 and max
//if it is, it just returns it. If it isn't, it "wraps"
//the values, so if val would be max, it would return 0,
//and if it would be -1, it returns max+(-1).
int wrap(int val,int max){
int result;
if(val<0){
result=max+val;
}
else if(val>=max){
result=val-max;
}
else{
result=val;
}
return result;
}
“countNeighbours()” counts how many cells of the ones around the one placed in col and row (include the cell in col and row), are set to “true”, and returns that value. If the cells to count don’t exist because col or row are in the borders of the array, it take the value of the cells on the opposite side. This “wrapping around the edges” is a standard technique to deal with the borders of Cellular Automata, and it si often called a “toroidal arrangement”, because if one imagines the lattice of cells to be on a sheet of material, and one first bends the top and the bottom of the sheet together, forming a tube, and then the bends both sides of the tube, one gets a torus (a doughnut), like this:
Toroidal wrapping of a CA
Now that we have seen what “countNeighbours()” does, lets see what the other function called from “tick()”, that is, “applyRules()” does:
boolean applyRules(int numNeigs){
boolean[] rules=new boolean[10];
rules[0]=false;
rules[1]=true;
rules[2]=true;
rules[3]=true;
rules[4]=false;
rules[5]=false;
rules[6]=false;
rules[7]=false;
rules[8]=true;
rules[9]=false;
return rules[numNeigs];
}
this is a bit of a smart way of using rules… and it does not need a function, but this way it is easier to modify…the number of neighbours may range from 0 to 9 (if we count the current cell).
So if we have a table with one entry for each posibility (from 0 to 9), and with its possible outcome (true or false) we cover all possible combinations. This is sometimes called a “look up table”. There are other ways of implementing this, for example with a few “if()” or with a “switch()” statement (which we have not looked at in the course).
That is mostly it… we have only left to explain the “update()” function, which is quite basic, since it just copies the calculated future values to the present, that is, all values from the cellsFuture array to the cellsNow array:
void update(){
//copying all values.
for(int i=0;i<columns;i++){//we go through all the columns
for(int j=0;j<rows;j++){
cellsNow[i][j]=cellsFuture[i][j];
}
}
}
This is lots of code, but if you look carefully, you realise that much of it is actually similar bits (the nested loops, for example) repeated, and that the logic of the Cellular automata is quite simple Here is by the way a link to a processing file with all the code together: BasicCA2D
This Cellular automata is loosely based in the rules described by Stephen Wolfram in “a New Kind of Science”, in Chapter 5, “Two Dimensions and Beyond”. You can try different rules and study the basics of the cellular automata. Study the references and links given, particularly other CA code written in Processing, see how it differs from the one presented here. You can for example look at one of the most famous CAs, Conway’s “Game of Life”, see the rules and think how you could implement it. There is actually a Processing version among the examples also…