But they are not as fascinating as CA’s where you expand the neighborhood to include all the eight adjacent cells. That’s called the Moore Neighborhood.

Representing the time dimension. As the intersting part is the evolution of the system, representing time is essential. With a two-dimensional CA it has to be done using animations, and who doesn’t like blinking pixels. This makes CA’s makes even more fun.

In order to decide the state of a cell I look at the Moore neighborhood for every cell on the grid, and count how many neighboring cells are alive. If a cell is alive, then we have to determine whether it survives or dies. If a cell is dead / empty there is the posibility of birth. By defining how many neighbors a cell has to have to survive, and hov many it takes to “give birth” it is possible to run the automata. And this is enough to define a highly complex behavior.

The ubiquitous Conway’s game of life survives if there are 2 or 3 neighbor’s alive and a cell is born if 2 cells are alive, this can be written as : S/B = 23/2. Using a notation like this makes it easy to try out new rules, just adjusting the S/B sets.

I made a small c++ program again using CImg to render these automatons. It’s a rather quick hack, and as such there are plenty off room for optimizing.

But for now it does its job and I don’t intend to develop it further, at least for now. And I think that CIimg might not be the best api for this, I need to look into SDL.

I spent way too much time hacking around to get a nice coloring scheme, and well CImgs intended users are making image manipulation, and not generating images from scratch. SDL is’t intended to generate images from scratch either, but as far as i can tell its easier to manipulate images as int arrays.

Well it does work and i were able to try out some of the rules listed at Wikipedia article about Life like cellular automatons, there online java simulators somewhere on the Internets so I won’t bother to upload any videos – as its much more fun to watch in action an play about with the settings as you go along. If you want to play with the code, well here it is : Cellular Automaton code it’s ugly and you need CImg.h

And now I’ve just downloaded EvoCell which has all the features and a lot more.

Online simulator : MJcell this is a very good implementation. Its fast and has lots of rules and patterns

Are quite fun and very intriguing.

What and how.

Generally you represent cells on a grid, and you “evolve” them using simple rules, based on how many neighbors they have.

In the simple version I so far have toyed around with. A cell is either dead or alive.

In one dimension, there are a ruleset and notation called the wolfram rules. Where you use a integer to represent a rule. Each cells faith is based on its own state and the state to its two adjacent neighbors. Here is a table from wikipedia

Rule 30 cellular automaton

Its rule 30 because 11110 is the binary representation of 30. This notation makes implementation quite easy. I implemented it this way :

• Create an image, fill with black
• Start with initializing the bottom row, put in cells of a different color at random
• for the row above calculate for each position :

int shift =0;
if (img( (i>0) ? i-1 : img.dimx()-1 , j, 0,0)==c[0])
shift +=4;
if (img(i, j, 0)==c[0])
shift +=2;
if (img((i+1)%img.dimx(), j, 0)==c[0])
shift +=1;

• basically its if left neighbor is alive shift = 4, itself is 2 and right neighbor 1. I wrap neighborhoods so its topological like a cylinder.
• Heres the smart thing about wolfram rules, we now have the state of the neighborhood represented as an integer. And if we shift the rule with this integer, the lowest bit will represent the state of the current cell. (rule<<shift)&1.
• continue through all rows from top to bottom.

This will generate some interesting patterns, rule 30 is a lot a triangles. And they have some interesting properties. I make them because I find them visually appealing, but the do have other merits. Look at the wikipedia entry for more

Technicalities : I made a small program in c++ using CImg. CImg is easy to use, and its quick to setup up a disply and handle events. (eg lefttclik =use same rule, initializ again, rightclik = next rule)

And though one dimensional cellular automata’s are intriguing and “fun”. They quickly get boring to look at, so I went for two dimensions. More about that in a later post.

The concept is that every acepting state represents black area, and and using a recursive definition of the areas.

Here is the area for the string “031”

Using this recursive definition it is posible to adress alle aereas, well in reality I choose a “resolution” and using strings upto a certeain length. I generate all the strings and check whether they are accepted, and should be colored.

A couple of examples.

The hack I used to make the images above (regexp_picture_render), you need the dRegAut packackage thou it might work with this (http://www.brics.dk/automaton/)

Here is a few regexps to try out, some are more interesting than others…

• (1+0+2+3)*(30+03+12+21)

• (0+1+2+3)*(22+11+00+33)(1+2)

• (0+1+2+3)*(33+00)(1+2+3+0)*(0+3)

• (1+2+3)*03(1+2)

• ((0+1+2+3)*(12+21))+((03+30)(0+1+2+3)*)

• (((0+1+2+3)*(12+21))+((03+30)(0+1+2+3)*))(1+2+3)*(1+2)

• (((0+1+2+3)*(12+21))+((03+30)(0+1+2+3)*))(1+2)(1+2+3+0)*(0+3)

• (((0+1+2+3)*(12+21))+((03+30)(0+1+2+3)*))(1+2+3)*03(1+2)

• (((0+1+2+3)*(2+1))+((2+1)(0+1+2+3)*))(1+2+3+0)*0(1+2)

• (((0+1+2+3)*(2+1))+((2+1)(0+1+2+3)*))(1+2+3+0)*3(0+3)

• (1+2+3+0)*(1+2)(0+3)(1+2)

• (1+2+3+0)*(1+2)(0+3)(1+2)