daniel shiffman

Examples

download zipped archive of all examples

Additional Examples from Processing.org

Recursion

CA 1 (another Game of Life implementation)

CA 2

CA 3

Related:

The Computational Beauty of Nature, Gary William Flake, Chapter 5 — Self-Similarity and Fractal Geometry, Chapter 6 — L-Systems and Fractal Growth

Conway’s Game of Life, Scientific American, 1970

Exploring Emergence, Mitchel Resnick and Brian Silverman Epistemology and Learning Group MIT Media Laboratory

A History of Cellular Automata, Wolfram Science

 

Fractals and Recursion

Benoit Mandelbrot coined the term fractal in 1975 to describe self-similar shapes achieved via the process of recursion. Most of the stuff we encounter in our physical world can described by idealized geometrical forms — a postcard has a rectangular shape, a ping-pong ball is spherical, etc. However, many naturally occurring stuctures cannot be described by such simple means (snowflakes, trees, coastlines, mountains, etc.) Fractals provide a geometry for describing and simulating these types of self-similar shapes (by “self-similar” we mean no matter how “zoomed out” or “zoomed in”, the shape ultimately appears the same.)

We know that a function/method can call another function/method. We do this all the time. But can a function call itself? Functions that call themselves are called “recursive” and are appropriate for solving different types of problems. This occurs often in mathematical calculations; the most common example of this is “factorial.” The factorial of any number n, usually written as n! is defined as:

n! = 1 * 2 * 3 * 4 * . . .* n
0! = 1

We might write a function to do this in processing like:

int fact(int n) {
  int f = 1;
  for (int i = 0; i < n; i++) {
    f = f * (i+1);
  }
  return f;
}

but we can also define factorial as:

n! = n * (n-1)!
0! = 1

This is where the “recursion” or “self-reference” happens. N factorial is defined as N times N - 1 factorial. We can then write a function that does exactly this:

int fact(int n) {
  if (n == 0) {
    return 1;
  } else {
    return n * fact(n-1);
  }
}

The same principle can be applied to a drawing application. Examine the following method.

void drawCircle(int x, int y, float radius)
{
  ellipse(x, y, radius, radius);
  if(radius > 2) {
    radius *= 0.75f;
    drawCircle(x, y, radius);
  }
}

What does “drawCircle” do? It draws an ellipse based on a set of parameters received as arguments, and then calls itself with adjusted parameters. The result is a series of circles each drawn inside the previous circle. This is a trivial example since it could easily be acheived through simple iteration. However, in more complex scenarios where a method needs to call itself multiple times (!!), recursion is a wonderfully elegant solution.

void branch(float h) {
  // Each branch will be 2/3rds the size of the previous one
  h *= 0.66f;

  // All recursive functions must have an exit condition!!!!
  // Here, ours is when the length of the branch is 2 pixels or less
  if (h > 2) {
    pushMatrix();    // Save the current state of transformation (i.e. where are we now)
    rotate(theta);   // Rotate by theta
    line(0,0,0,-h);  // Draw the branch
    translate(0,-h); // Move to the end of the branch
    branch(h);       // Ok, now call myself to draw two new branches!!
    popMatrix();     // Whenever we get back here, we "pop" in order to restore the previous matrix state

    // Repeat the same thing, only branch off to the "left" this time!
    pushMatrix();
    rotate(-theta);
    line(0,0,0,-h);
    translate(0,-h);
    branch(h);
    popMatrix();
  }
}

The above code is the recursive method found in this week’s tree-drawing examples. This method draws one branch of the tree and then proceeds to call itself twice (at then end of each branch, two new branches appear). The key elements to note here are:

All recursive functions must have an exit condition! This is identical to iteration. For any “for” or “while” loop, we always have a boolean test that results in exiting that loop. Without one, the program would crash, stuck in an infinite loop. The same can be said about recursion.

Note the use of pushMatrix() and popMatrix() The key here is that we first call “pushMatrix” in order to save the current orientation (i.e. where are we on the tree structure), we then call “branch” in order to start the branching process at that location. And afterwards (!!), we call “popMatrix” to restore to the previous location. This is what allows us to branch of one way, always returning back to branch off the other way. (is your head exploding yet?). The way the computer keeps track of the function calls (via a stack) combined with using push/pop to store the transformation states allows for recursion to work beautifully here. Just try achieving the same result with simple iteration!

 
The above examples illustrate the recursive process via functions that call themselves. We can achieve similar results using a Java ArrayList as well. Consider the following algorithm:

1 — Create an empty ArrayList.

2 — Place one object in the ArrayList

3 — For every object in the ArrayList, add two more objects to the ArrayList (based on the original)

4 — repeat step 3 for n number of “generations”

 
This strategy can be used for creating various types of recursive shapes (full code available in the Koch Curve example as well as the ArrayList Branching example above.)

// Setup the arraylist and add one branch to it -- STEP 1
a = new ArrayList();
// Create a new branch
Branch b = new Branch();
// Add to arraylist -- STEP 2
a.add(b);

The above code initializes our recursive system (and would be found in “setup” or perhaps in the constructor of a class.) Step 3 would follow in the main loop of the program as follows:

// -- STEP 3
// For every branch in the ArrayList, delete it and add two more.
// This is just "pretend" code. In the actual example, the two
// new branches that are added are based on the one deleted
for (int i = a.size()-1; i >= 0; i--) {
  Branch b = (Branch) a.get(i);
  a.remove(i);
  a.add(new Branch());
  a.add(new Branch());
}

Cellular Automata

A cellular automaton is a collection of “colored” cells on a grid of specified shape that evolves through a number of discrete time steps according to a set of rules based on the states of neighboring cells. The rules are then applied iteratively for as many time steps as desired. von Neumann was one of the first people to consider such a model, and incorporated a cellular model into his “universal constructor.” Cellular automata were studied in the early 1950s as a possible model for biological systems (Wolfram 2002, p. 48). Comprehensive studies of cellular automata have been performed by S. Wolfram starting in the 1980s, and Wolfram’s fundamental research in the field culminated in the publication of his book A New Kind of Science (Wolfram 2002) in which Wolfram presents a gigantic collection of results concerning automata, among which are a number of groundbreaking new discoveries.

 
In all of the examples we’ve looked at to date, our objects generally have existed in only one “state”. They may move around with advanced behaviors/physics, but ultimately they have stayed the same type of object. More interesting results can be achieved by having entities that change/evolve over time. We examine cellular automata as our first example of a system of multiple objects with varying states. In the two examples below, each cell has one of two states (0 or 1, dead or alive, white or black, etc.). Researching further into CA systems, you might achieve varying results with multi-state systems as well as by applying the idea of “states” from CAs to systems of moving objects.

1D Cellular Automaton

The system exists as a row of cells (stored as an array of integers)

Each cell (i.e. element in the array) is either “on” or “off”, i.e. 0 or 1

Each cell has two neighbors, one to the left and one to the right

Each cell’s state at time T+1 is determined by its own state and the state of its neighbors at time T. There are 8 possible combinations. A ruleset states what the new state will be based any given combination, i.e.

[LEFT,CURRENT,RIGHT] --> NEW STATE

Following is an example ruleset:

[0,0,0] --> 0
[0,0,1] --> 1
[0,1,0] --> 0
[0,1,1] --> 1
[1,0,0] --> 1
[1,0,1] --> 0
[1,1,0] --> 1
[1,1,1] --> 0

For more information/illustration, visit: http://mathworld.wolfram.com/ElementaryCellularAutomaton.html.

2D Cellular Automaton

In the above 1D case, a cell’s state at time T+1 is computed as a function of its own state and its neighbors’ state at time T. The same is true for the 2D case, however, instead of a cell having only 2 neighors, in two dimensions it will have 8 neighbors. In 1970, John Conway, building on the work on John von Neumann, developed the “Game of Life”. The name refers to the fact that each cell is either alive or dead (in our code, again, represented as 0’s and 1’s.). The rules are as follows:

Loneliness: If a cell is alive and has less than 2 live neighbors, it dies.

Overpopulation: If a cell is alive and has more than 3 live neighbors, it dies.

Reproduction: If a cell is dead, and it has exactly 3 live neighbors, it comes to life

Statis: In all other cases, it stays as is.

 
Assume we have a cell represented as an integer “cell”, with a total number of alive neighbors represented as an integer “neighbors”. We can write code to do this test as follows:

if      ((cell == 1) && (neighbors < 2))  { cell = 0;    }
else if ((cell == 1) && (neighbors >  3)) { cell = 0;    }
else if ((cell == 0) && (neighbors == 3)) { cell = 1;    }
else                                      { cell = cell; } //unnecessarily redundant, but being explicit here

For this to really work in code, however, we use a two-dimensional array to store information related to all the cells in the system.

2D Arrays

We know that an array keeps track of multiple pieces of information in a specific, linear order. However, the data associated with certain systems (a digital image, a board game, a “cellular automata”) lives in two dimensions. To visualize this data, we need a multi-dimensional structure and we can do this by expanding the idea of an array beyond one dimension.

A 2 dimensional array is really nothing more than an array of arrays (a 3 dimensional array is an array of arrays of arrays.). In other words, if an array looks like this,

int[] myArray = {0,1,2,3};

a two-dimensional array looks like this:

int[][] myArray = {{0,1,2,3},{3,2,1,0},{3,5,6,1},{3,8,3,4}};

Nonetheless, for our purposes, we want to think of the 2D array as a matrix, i.e.:

int[][] myArray = {  {0, 1, 2, 3},
                     {3, 2, 1, 0},
                     {3, 5, 6, 1},
                     {3, 8, 3, 4}  };

We can use this type of data structure to encode information about an image. For example, the following grayscale image:

might be represented by the following array:

int[][] myArray = {  {236, 189, 189,   0},
                     {236,  80, 189, 189},
                     {236,   0, 189,  80},
                     {236, 189, 189,  80}  };

To walk through every element of a one-dimensional array, we use a for loop, i.e.:

int[] myArray = new int[10];
for (int i = 0; i < myArray.length; i++) {
  myArray[i] = 0;
}

For an N-dimensional array, in order to reference every element we must use N-nested loops, i.e.

int cols = 10;
int rows = 10;
int[][] myArray = new int[cols][rows];

for (int i = 0; i < cols; i++) {
  for (int j = 0; j < rows; j++) {
    myArray[i][j] = 0;
  }
}

and we might write a program using a 2D array to draw a grayscale image, i.e.

// Set up dimensions
size(50,50);
int cols = width;
int rows = height;

// Declare 2D array
int[][] myArray = new int[cols][rows];

// Initialize 2D array values
for (int i = 0; i < cols; i++) {
  for (int j = 0; j < rows; j++) {
    myArray[i][j] = int(random(255));
  }
}

// Draw points
for (int i = 0; i < cols; i++) {
  for (int j = 0; j < rows; j++) {
    stroke(myArray[i][j]);
    point(i,j);
  }
}

In the case of a 2D cellular automata, such as the “Game of Life”, we need two 2D arrays. One stores the all the states at time T, and the other stores the states at time T+1. After each cycle of computing the next generation, the new system (T+1) becomes the old system (T), and we compute yet another new system (T+1).

Declare the arrays:

// Game of life board
int[][] old_board, new_board;

Set random initial values:

for (int i = 0; i < cols; i++) {
  for (int j = 0; j < rows; j++) {
    if (int(random(2)) == 0) {
      old_board[i][j] = 1;
    } else {
      old_board[i][j] = 0;
    }
  }
}

Check every element in the array, count how many neighbors are alive, apply rules of life:

for (int x = 1; x < cols-1;x++) {
  for (int y = 1; y < rows-1;y++) {
    int nb = 0;
    if (old_board[x-1][y-1] == 1)  { nb++; }    //top left
    if (old_board[x  ][y-1] == 1)  { nb++; }    //top
    if (old_board[x+1][y-1] == 1)  { nb++; }    //top right
    if (old_board[x-1][y  ] == 1)  { nb++; }    //left
    if (old_board[x+1][y  ] == 1)  { nb++; }    //right
    if (old_board[x-1][y+1] == 1)  { nb++; }    //bottom left
    if (old_board[x  ][y+1] == 1)  { nb++; }    //bottom
    if (old_board[x+1][y+1] == 1)  { nb++; }    //bottom right

    //RULES OF "LIFE" HERE
    if      ((old_board[x][y] == 1) && (nb <  2)) { new_board[x][y] = 0; }                // Loneliness
    else if ((old_board[x][y] == 1) && (nb >  3)) { new_board[x][y] = 0; }                // Overpopulation
    else if ((old_board[x][y] == 0) && (nb == 3)) { new_board[x][y] = 1; }                // Reproduction
    else                                          { new_board[x][y] = old_board[x][y]; }  // Stasis
  }
}

The key! After each cycle, we swap old and new, so that new becomes old, and we can make a “new” new:

int[][] tmp = old_board;
old_board = new_board;
new_board = tmp;