Rule 30 – a 1D cellular automaton implemented using Processing

Processing is a simple but very powerful Java based scripting environment that allows one to quickly implement graphics (2D and 3D) prototypes. There are some pretty impressive visualization examples out there for you to feast your eyes on and mine is a simple contribution but hopefully interesting.

Cellular automaton are the basis for Stephen Wolfram’s theories in his book “A New Kind Of Science”. On the surface they are deceptively simple but, just like fractals, they can generate highly complex detail and seem to be able to replicate natural phenomena.

I’ve implemented a simple 1D cellular automaton in the script included here based on information on Wolfram’s Mathworld site.

The image this code generates is a pretty pyramid shape of generations of the bits generated by a rule (more on that below) called “Rule 30” which, according to Wolfram, generates a random sequence of bits. It’s actually used as the basis for Mathematica’s random number generator. It also looks quite pretty:
Rule 30

The algorithm is very simple, and I think (hope) it’s pretty well commented and should be easy to understand but let me just outline it for reference:

  • Start with a sequence of bits. It can be initialized to whatever you want but I’ve set it to all 0 except 1 bit in the “center” of the bit string (width of screen in pixels). This bit acts as a seed
  • Read each bit and select an output bit depending on it’s nearest neighbours (left,right) using a simple FSM rule. I’ve encoded the famous “Rule 30” but it could be any other rule…try it!
  • Render the line…and go to the next line

It really is that simple. The code does a little bit of fancy double buffering of the line rendered and the output line and the rest is basic use of Processing’s incredibly simple and powerful functionality.

Enjoy…


/*
Elementary Cellular Automaton (1-D) implementation
We render "generations" of the automaton, one per screen line, starting with at the top with a "seed".
Each generation (line) is rendered by testing each pixel's neighbours and selecting the appropriate rule.

*/

// the rule determining if a pixels is “on” or “off” depending on the state of its neighbours
int[] rule;
// the
int[] grid;
int WIDTH = 800;

void setup() {
size(WIDTH,WIDTH/2); //< half height to terminate nicely since we don’t deal with pixels at the borders
background(0);
noLoop(); //< only need to render one frame

rule = new int[2*2*2]; //< 8 rules
grid = new int[width*2]; //< double buffer; holds this and last generation

// initialize first generation with 1 pixel in the center
for ( int n=0; n < width; ++n ) {
grid[n] = (n == (width/2) ? 1 : 0);
}

// “rule 30”
// This rule is actually used to generate random numbers in Mathematica
rule[0] = 0;
rule[1] = 0;
rule[2] = 0;
rule[3] = 1;
rule[4] = 1;
rule[5] = 1;
rule[6] = 1;
rule[7] = 0;
}

void draw() {

loadPixels();

// double buffer selector
int sel = 1;
for( int generation = 1; generation < height; ++generation ) {

// double buffer selector: alternates between 1 and 0 (every other line)
sel ^= 1;
// read from last generation line
int read_offs = sel*width;
// write to this generation line
int write_offs = (sel^1)*width;

// offset into screen buffer of current line
int pixel_offs = generation*width;

// generate the image, line by line (generation by generation)
for ( int n = 1; n < (width-1); ++n ) {

// read out this and 2 neighbouring values
int n1 = grid[read_offs+(n-1)];
int n2 = grid[read_offs+n];
int n3 = grid[read_offs+(n+1)];
int value;

//simple state machine to select the appropriate rule
if ( n1==1 ) {
if ( n2==1 ) {
if ( n3==1 ) {
// 1,1,1
value = rule[0];
}
else {
// 1,1,0
value = rule[1];
}
}
else {
if ( n3==1 ) {
// 1,0,1
value = rule[2];
}
else {
// 1,0,0
value = rule[3];
}
}
}
else {
if ( n2==1 ) {
if ( n3==1 ) {
// 0,1,1
value = rule[4];
}
else {
// 0,1,0
value = rule[5];
}
}
else {
if ( n3==1 ) {
// 0,0,1
value = rule[6];
}
else {
// 0,0,0
value = rule[7];
}
}
}

// update the current “write buffer” for the next round
grid[write_offs+n] = value;
// draw and map so we get a fade out towards the bottom
pixels[pixel_offs+n] = color(value*map(generation, 1,height, 255,20));
}
}

updatePixels();

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s