Wednesday, November 5, 2008

Cellular Automata

The visualizations in Trancit are based on a mathematical process with the ungainly name of "cellular automata." For convenience, they are usually called "CA". What makes CAs interesting are the often compelling large-scale and ever-changing images that emerge from very simple descriptions. Here's how it happens...

Briefly, a CA exists in a grid-like space, like a chess board. Each square is called a "cell". Each cell has eight neighboring cells, usually referred to by the compass directions-- the cell above is called "North", the cell to the upper right is "Northwest", and so on. In Trancit, each pixel of the screen represent s a cell.

Along with space, a CA also has time. With each tick of a clock, each cell looks at some or all of its neighbors. Then the cell does a computation based on the state of its neighbors, and that computation defines the next state for the cell.

A Concrete Example
  1. A cell can be in one of two states: "on" or "off".
  2. If a cell is off, and it has three neighbors that are on, then the cell turns on during the next tick of the clock. Otherwise, the cell stays off.
  3. If a cell is already on, it stays on if it has two or three neighbors on, otherwise the cell turns off.
These three simple "rules" define a CA, called "Life", that is famous in computer science circles. You can see how these rules play out in Trancit, by selecting the visualization "Combinate" and clicking on the button labeled "a".

You'll see the "tumblers" of the combination move to 0, 3, 3, 2, 3. We'll talk about the "0" later. The the first two 3's define that a cell which is off will turn on if it has exactly 3 neighbors on. The last two numbers, 2 and 3, state that a cell that is on should stay on if it has between 2 and three neighbors on. Otherwise the cell should turn off.

With the three simple rules of life, all sorts of patterns form in pixels of the screen. It is not very colorful; just two "states" results in just two colors, with the "off" state being black. The interesting thing about "Life" is that it generates patterns that are much bigger than a single cell, and these patterns persist and evolve over a long time.

There's no way you would guess those patterns would exist just from looking at the three simple rules. But they do emerge, and other rules generate much different emergent behavior...

A Variation
Remember the "0" value we skipped over earlier? That defines the number of ticks that a cell must stay off before we can turn it on again. If you change this value from 0 to 1 for Life, you'll see that nothing interesting happens-- the patterns die out.

Clicking on the "b" button for Combinate, we see a new rule: "1 2 2 8 0". This describes the following:
  • "1": When a cell turns off, it can not turn back on for 1 tick of the clock.
  • "2 2": If a cell is off, and able to turn on, it can turn on when exactly 2 neighboring cells are on.
  • "8 0": Literally this says a cell can stay on only if it has more than at least 8, but no more than 0 neighbors on. This is an impossible condition to satisfy, so cells always turn off after being on.
When you run this rule, the behavior is much different from Life, and a lot more interesting (though still not very colorful).

Combinate represents one particular family of rules. The buttons "c", "d" and "e" are preset to some other interesting ones. You can change the values of each of the five numbers on your own, or pick a rule set at random with the "???" button. There are many in this family that are visually a lot more interstingin Life. There are other reasons why Life is interesting though,and if you want to know more then you might start here.