Fun with Cellular Automata

Drink in that impressive title for a moment. It's definitely better than the reality of me saying "I implemented Conway's Game of Life ... in Processing ... poorly ... using Khan Academy's online code editor". It's the truth, though.

After working on pixel drawings with the kids, I was inspired to try more programs of my own. Having never implemented the Game of Life before, I thought it would be a good opportunity to put my recently-discovered expertise with pixel drawing to work. The rules of the game are simple:

  1. If a live cell has fewer than 2 neighbors, it dies (from underpopulation)
  2. If a live cell has more than 3 neighbors, it dies (from overcrowding)
  3. If a live cell has 2 or 3 neighbors, it lives on to the next generation
  4. If a dead cell has exactly 3 neighbors, it is born (from reproduction)

The bonus is that it's a "zero player" game — my favorite!

My First Attempt

Yes, it's true. I did admit to never implementing this simulation before. I'm sure this will end well.

The overall approach is simple:

  1. Create a matrix of values (0 = dead, 1 = alive)
  2. Iterate through each cell in the matrix and count the neighbors
  3. Apply the rules to the current cell to turn it on or off
  4. Repeat with the remaining cells
  5. Draw the updated grid
  6. Repeat

Following these steps allowed me to create a convincing simulation:

Not bad. After looking closer at how the simulation behaved, I noticed that the initial patterns that should create ocillators didn't ... oscillate:

My simulation wasn't treating each drawing iteration as an independent generation. Instead, the current board state was constantly being modified as I analyzed each cell in the matrix.

A Generation at a Time

To create a more conforming simulation, I modified my initial approach to buffer the next state of the board:

  1. Create 2 matrices of values to represent the current and next generation
  2. Iterate through each cell in the current generation and count the neighbors
  3. Apply the rules to turn the cell on / off in the next generation
  4. Copy the next generation to the current generation
  5. Draw the updated grid
  6. Repeat

This resulted in a more convincing simulation:

Now that I was on the right track, I wanted to see what other simulations were possible.

Changing the Rules

The Wikipedia page for the Game of Life describes some variations on the rules that result in different patterns. The well-known rules are expressed as "B3/S23" — a cell is born if it has exactly 3 neighbors, and stays alive if there are 2 or 3 neighbors. Changing these rules results in other interesting patterns. Take B1/S12, for example:

There are many other possibilities out there (try B1/S1, for example), so check out the simulation on my programs page and tweak some of the rules to see what you come up with.

Patrick is development director in Viget's Boulder, CO, office. He writes clean Ruby code and automates system infrastructure for clients such as Shure and Volunteers of America.

More posts by Patrick