Generative Art - Autonomy: Cellular Automata

Manning

4.82/5 (12 votes)

30 Jun 2011CPOL11 min read

39.8K

A chapter excerpt from Generative Art

Generative Art
A practical guide using Processing

Matt Pearson

The most familiar single example of an autonomous agent is you. The cards in your wallet are writing your economic autobiography, your tweets and SMSs are writing an ASCII diary as part of a social map, and the phone in your pocket is drawing a GPS picture of your daily psycho-geography. This article, based on chapter 7 of Generative Art, familiarizes you with the concept of autonomy and the emergent complexity of this breed of object through one of the early parlor games of computer science: cellular automata.

Compliments of manning.com for The Code Project viewers is a 40% discount on Generative Art at manning.com only. Use promo code code40project and receive 40% off the eBook and pBook. All pBook purchases include FREE eFormats (PDF, ePub and Kindle) as soon as available.

Setting up the Framework

The best way to demonstrate is by example. The following listing creates a grid of cells with on/off states and a reference to their immediate neighbors.

Listing 1 CA framework

C++

Cell[][] _cellArray;
int _cellSize = 10;
int _numX, _numY;
 
void setup() {
 size(500, 300);
 _numX = floor(width/_cellSize);
 _numY = floor(height/_cellSize);
 restart();
}
 
void restart() {
 _cellArray = new Cell[_numX][_numY];   #A
 for (int x = 0; x<_numX; x++) {    #A
  for (int y = 0; y<_numY; y++) {#A
   Cell newCell = new Cell(x, y);  #A
   _cellArray[x][y] = newCell;  #A
  }  #A
 }  #A
 
 for (int x = 0; x < _numX; x++) {   #B
  for (int y = 0; y < _numY; y++) {  #B
 
   int above = y-1;  #C
   int below = y+1;  #C
   int left = x-1;  #C
   int right = x+1;  #C
 
   if (above < 0) { above = _numY-1; }  #D
   if (below == _numY) { below = 0; }  #D
   if (left < 0) { left = _numX-1; }  #D
   if (right == _numX) { right = 0; }  #D
 
   _cellArray[x][y].addNeighbour(_cellArray[left][above]);   #E
   _cellArray[x][y].addNeighbour(_cellArray[left][y]);   #E
   _cellArray[x][y].addNeighbour(_cellArray[left][below]);   #E
   _cellArray[x][y].addNeighbour(_cellArray[x][below]);   #E
   _cellArray[x][y].addNeighbour(_cellArray[right][below]);   #E
   _cellArray[x][y].addNeighbour(_cellArray[right][y]);   #E

  _cellArray[x][y].addNeighbour(_cellArray[right][above]);   #E
   _cellArray[x][y].addNeighbour(_cellArray[x][above]);   #E
  }
 }
}
 
void draw() {
 background(200);
 
 for (int x = 0; x < _numX; x++) {   #F
  for (int y = 0; y < _numY; y++) {   #F
   _cellArray[x][y].calcNextState();   #F
  }   #F
 }   #F
 
 translate(_cellSize/2, _cellSize/2);
 
 for (int x = 0; x < _numX; x++) {   #G
  for (int y = 0; y < _numY; y++) {   #G
   _cellArray[x][y].drawMe();   #G
  }   #G
 }  #G 
}   #G
 
void mousePressed() {
 restart();
}
 
//================================= object
 
class Cell {
 float x, y;
 boolean state;    #H
 boolean nextState;
 Cell[] neighbors;
 
 Cell(float ex, float why) {
  x = ex * _cellSize;
  y = why * _cellSize;
  if (random(2) > 1) {   #I
   nextState = true;   #I
  } else {   #I
   nextState = false;   #I
  }   #I
  state = nextState;
  neighbors = new Cell[0];
 }
 
 void addNeighbor(Cell cell) {
  neighbors = (Cell[])append(neighbors, cell);
 }


 void calcNextState() {
  // to come
 }
 
 void drawMe() {
  state = nextState;
  stroke(0);
  if (state == true) {
   fill(0);
  } else {
   fill(255);
  }
  ellipse(x, y, _cellSize, _cellSize);
 }
 
}
#A Creates grid of cells
#B Tells each object its neighbors
#C Gets locations to each side
#D Wraps locations at edges
#E Passes refs to surrounding locs
#F Calculates next states first
#G Draws all cells
#H On or off
#I Randomizes initial state

It’s a lengthy starting point, but nothing you haven’t encountered before. At the bottom of the script you define an object, a Cell, which has x and y positions and a state, either on or off. It also has a holder for its next state, nextState, the state it will enter the next time its drawMe method is called.

In setup, you calculate the number of rows and columns based on the width and height and the size you want the cells; then, you call the restart function to fill a 2D array with this grid.

After the grid is created, there is a second pass through the array to tell each of the cells who its neighbors are (above, below, left, and right of them).

The draw loop then does a double pass through the array. The first pass triggers each cell to calculate its next state, and the second pass triggers each to make the transition and draw itself.

Note that this needs to be done in two stages so each cell has a static set of neighbors on which to base its next state calculation.

Now that you have the grid of cells (as shown in figure 1), you can begin giving the cells their simple behaviors. The best-known CA is John Conway’s Game of Life, so that is the one we’ll start with.

Multidimensional Arrays

A one-dimensional array is a data structure for storing a list of elements. You define one as follows:

int[] numberArray = {1, 2, 3};

But, if you want to store more than a list, if you have a matrix of elements to keep track of, you can add an extra dimension to the array. A 2D array is initialized like so:

int[][] twoDimArray = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };

Essentially, you’re defining an array of arrays. In listing 1, you can see an example of creating and iterating through a 2D array.

If you want more dimensions, you can have them. You’re free to add as many dimensions as you can get your head around:

C++

int[][][] threeDimArray;

int[][][][] fourDimArray;

...

Figure 2 Conway’s Game of Life after 100 iterations

The Game of Life

The popularity of Conway’s Game of Life (GOL) is mostly due to the relevance it has found outside the field of mathematics. Biologists, economists, sociologists, and neuroscientists, amongst others, have discussed at length the parallels between the behavior of CA obeying GOL rules and the results of studies in their respective fields. It’s essentially a simple computational form of artificial life, a mathematical petri dish teeming with autonomous agents.

The rules for GOL are as follows:

Rule 1: If a live (black) cell has two or three neighbors, it continues to live. Otherwise it dies, of either loneliness or overcrowding.
Rule 2: If a dead cell has exactly three neighbors, a miracle occurs: it comes back to life.

You write this in code as follows. Complete the calcNextState function in accordance with the following listing.

Figure 3 Triangle height and rotation depend on the age of a cell. Triangle width is the neighbor count.

Figure 4 Circle size is determined by neighbor count. Lines and their rotations are determined by cell age.

Listing 2 Calculating the next state using GOL rules

C++

void calcNextState() {
  int liveCount = 0;
  for (int i=0; i < neighbours.length; i++) {
   if (neighbors[i].state == true) {
     liveCount++;
   }
  }
 
    if (state == true) {
    if ((liveCount == 2) || (liveCount == 3)) {
      nextState = true;
    } else {
      nextState = false;
    }
  } else {
    if (liveCount == 3) {
      nextState = true;
    } else {
      nextState = false;
    }
  }
}

This code first counts the number of neighbors alive and then applies GOL rules. If you run it for a few seconds, you begin to see what looks like a microscope view of abstract organisms (see figure 2). Some parts bubble and then fade out; others achieve a looping stability. There has been much study of this game, identifying the mathematical “life” that forms: gliders, toads, boats, blinkers, beacons, and so on. The GOL Wikipedia page has many animated examples of the complex shapes and patterns that arise from these simple rules: see http://en.wikipedia.org/wiki/Conway’s_Game_of_Life#Examples_of_patterns.

It would be very easy for us to get sidetracked here because what you’ve written is essentially an AI program. Artificial intelligence is a field that, admittedly, has huge potential for the creation of generative art.[1] We’ll keep our focus relatively shallow and toy with the possibilities for each of these cells, with its local, blinkered behavior, to render itself to the screen in visually interesting ways.

A simple black or white dot is only a starting point. In the two examples in figures 3 and 4, I’ve used the number of live neighbors a cell has, and the number of frames it has remained alive, to determine the size, rotation, and color of a shape drawn at that cell’s location. You may like to try similar experiments.

GOL is only one of many potential rule sets. In addition to experimenting with visualizations, I’d encourage you to try inventing your own. In the following pages, I’ll demonstrate two more well-known patterns, and one invented behavior, each of which produces forms that have analogues in the natural world.

Vichniac Vote

The first pattern, the Vichniac Vote (after Gerard Vichniac who first experimented with it), is a lesson in conformity. Each cell is particularly susceptible to peer-group pressure and looks to its neighbors to observe the current trend. If the cell’s color is in the majority, it remains unchanged. If it’s in the minority, it changes. To ensure that there is an odd number of cells on which to make the decision, the cell includes its own current state in addition to its eight neighbors in making the calculation.

To see the vote in action, rewrite the calcNextState function using the code from the following listing. To create an artificial instability in the algorithm, you’ll swap the rules for four and five neighbors; otherwise, it settles quickly into a static pattern.

Listing 3 The Vichniac Vote Rule

C++

void calcNextState() {
  int liveCount = 0;
  if (state) { liveCount++; }    #A
  for (int i=0; i < neighbors.length; i++) {    #A
   if (neighbors[i].state == true) {    #A
     liveCount++;    #A
   }    #A
  }    #A
 
  if (liveCount <= 4) {   #B
    nextState = false;   #B
  } else if (liveCount > 4) {   #B
    nextState = true;    #B
  }   #B
 
  if ((liveCount == 4) || (liveCount == 5)) {   #C
    nextState = !nextState;   #C
  }   #C
}   #C
#A Counts neighbors, including me
#B Am I in the majority?
#C Swaps rules for 4 and 5

The result is shown in figure 5. You can see how the clustering effect creates patterns similar to the hide of a cow, or the contours of a landscape seen from above.

Figure 5 The Vichniac Vote rule after 3 iterations, 11 iterations, 41 iterations, and 166 iterations

With the Vichniac Vote, the rules you apply are sociological—agents succumbing to the peer group pressure from their neighbors—but the results have an aesthetic more familiar from biology or geology. Might this imply that common computational principles underpin these disciplines?

Brian’s Brain

This is a three-state cellular automaton, meaning a cell can be in one more condition, apart from on or off. The states of a Brian’s Brain CA are firing, resting, and off. It’s designed to mimic the behavior of neurons in the brain, which fire and then rest before they can fire again. The rules are as follows:

If the state is firing, the next state is resting.
If the state is resting, the next state is off.
If the state is off, and exactly two neighbors are firing, the state becomes firing.

You’ll need to modify the cell class for this, as in the following code. Note that you have to change the type of state to int, so it can have more than two values. The integers 0, 1, and 2 indicate off, firing, and resting, respectively.

Listing 4 Cell object modified for the three-state Brian’s Brain behavior

C++

class Cell {
 float x, y;
 int state;  #A
 int nextState;
 Cell[] neighbors;
 
 Cell(float ex, float why) {
  x = ex * _cellSize;
  y = why * _cellSize;
nextState = int(random(2));
  state = nextState;
  neighbors = new Cell[0];
 }
 
 void addNeighbor(Cell cell) {
  neighbors = (Cell[])append(neighbors, cell);
 }
 
 void calcNextState() {
  if (state == 0) {
int firingCount = 0;
   for (int i=0; i < neighbors.length; i++) {
    if (neighbors[i].state == 1) {   #B
     firingCount++;  #B
    }   #B
   }
   if (firingCount == 2) {   #C
    nextState = 1;   #C
   } else {
    nextState = state;    #D
   }
  } else if (state == 1) {   #E
   nextState = 2;   #E
  } else if (state == 2) {   #F
   nextState = 0;   #F
  }
}

void drawMe() {
 state = nextState;
 stroke(0);
 if (state == 1) {
  fill(0);    #G
 } else if (state == 2) {
  fill(150);   #H
 } else {
  fill(255);   #I
 }
  ellipse(x, y, _cellSize, _cellSize);
 }
}
#A State 1, 2, or 0
#B Counts firing Neighbors
#C If two neighbors are firing, fire too
#D Else, don’t change
#E If just fired, rest
#F If rested, turn off
#G Firing = black
#H Resting = grey
#I Off = white

The results look something like figure 6. Spaceships (the CA term, not mine) move across the plane in horizontal, vertical and sometimes diagonal directions.

Figure 6 The Brian’s Brain behavior after 19 iterations

Does this behavior reflect the way your thoughts form from the electronic bursts of firing synapses? Is what you’re seeing a mathematical model of consciousness itself? Perhaps; but for our purposes, for the time being at least, it’s just another emergent behavior that you can use as the basic for a generative visualization.

Just one more example before we move on. Not one of the famous rule sets, but a custom behavior instead. The patterns it produces should be quite familiar though.

This final pattern is an example of a CA with a continuous behavior. There is no reason a cell has to be limited to two or three distinct values: its state can vary across a range of values. In this example, you’ll use 255 values, the grayscale from white to black. This is a custom behavior, so it doesn’t have a name, but I’ve based it on a standard physics model—averaging—whereby a chaotic state settles into a steady one thorough the influence of its neighbors.

The rules are as follows:

If the average of the neighboring states is 255, the state becomes 0.
If the average of the neighboring states is 0, the state becomes 255.
Otherwise, new state = current state + neighborhood average – previous state value.
If the new state goes over 255, make it 255. If the new state goes under 0, make it 0.

If you were adhering to the physics model, you’d need only the third of these rules. I’ve added the other rules for instability, to stop it from settling. The code is in the next listing. The output is shown in figure 7.

Listing 5 Custom wave-like behavior

C++

class Cell {
 float x, y;
 float state;
 float nextState;
 float lastState = 0;
 Cell[] neighbors;
 
 Cell(float ex, float why) {
  x = ex * _cellSize;
  y = why * _cellSize;
  nextState = ((x/500) + (y/300)) * 14;   #A
  state = nextState;
  neighbors = new Cell[0];
 }
 
 void addNeighbor(Cell cell) {
  neighbors = (Cell[])append(neighbors, cell);
 }
 
 void calcNextState() {
  float total = 0;  #B
  for (int i=0; i < neighbours.length; i++) {   #B
   total += neighbors[i].state;   #B
 }   #B
  float average = int(total/8);   #B
 
  if (average == 255) {
   nextState = 0;
  } else if (average == 0) {
   nextState = 255;
  } else {
   nextState = state + average;
   if (lastState > 0) { nextState -= lastState; }
   if (nextState > 255) { nextState = 255; }
   else if (nextState < 0) { nextState = 0; }
  }

  lastState = state;  #C
 }
 
 void drawMe() {
  state = nextState;
  stroke(0);
  fill(state);    #D
  ellipse(x, y, _cellSize, _cellSize);
 }
}
#A Creates initial gradient
#B Calculate neighborhood average
#C Stores previous state
#D Uses state value as fill color

Figure 7 The customized wave rule after 6, 26, 49, and 69 iterations

The most obvious comparison with this behavior is a liquid. Like rain on a shallow pool of water, it churns and varies.

The reason for this example is to emphasize how you can tweak not only the rules but also the framework itself. You don’t need a grid, you don’t need circles, and you don’t need a limited set of grayscale values: your system can be as subtle and sophisticated as you care to make it (see figure 8).

Figure 8 Single-pixel-sized cells produce more subtle (but more processor-intensive) patterns

Summary

The object-oriented approach to code is just the start. With this approach, you can begin realizing more sophisticated systems. Your objects can be autonomous agents, interacting with each other in an artificial environment, producing emergent complexity for you to visualize, an idea you explored through cellular automaton experiments.

Here are some other Manning titles you might be interested in:

	Secrets of the JavaScript Ninja John Resig and Bear Bibeault
	Android in Action, Second Edition W. Frank Ableson, Robi Sen, and Chris King
	iPhone and iPad in Action Brandon Trebitowski, Christopher Allen, and Shannon Appelcline

[1] If this subject interests you, I suggest that you seek out Douglas Hofstadter’s Pulitzer Prize winning Gödel, Escher, Bach (1979) as an entertaining, not too scary, starting point.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)