Monthly Archives: August 2013

Cellular Automaton

Early on when I started programming I came across “Conway’s life” which is the classic example of cellular automaton. I was programming in Modula-2 on DOS at the time, and wrote an implementation of Conway’s Life. I was fascinated at the little “life forms” that it created, and would watch it for ages. Since then, whenever I have started using a new language or system I tend to write a version of Life. I have programmed dozens now. I have varied it along the way. Sometimes the universe has an edge, sometimes it wraps. Sometimes there are two colours of cells instead of one.

While programming C on Windows is by no means new to me now, the OpenGL framework is. So I decided I should write another implementation of Conway’s life using OpenGL and make it cross platform for Windows, OSX, and Linux.

The following (reduced) screen shots are of a typical run. The first image is shortly after it has started. There are many cells changing with every frame.

ConwaysLife_Early

Later on the cells become less dense and a lot of areas have stabilised.

ConwaysLife_Mid

And finally the entire universe stabilises. Every pattern is either static or is oscillating between a small number of states.ConwaysLife_End

 

Having finished this I wanted to experiment with a different cellular automaton that I had seen years ago. I’ve titled it “racist cells”. Every position in the “universe” is filled with a cell from one of five colours. At each iteration a cell can decide whether it wants to move or stay. If it moves it swaps position with another cell in the universe that also wishes to move. The probability of moving is higher when the cell is surrounded by cells of other colours. The universe is initially seeded by a random distribution of the cells. There is an equal number of each colour. Unlike Conway’s life cells are not destroyed or created. There is always the same number of each colour at each iteration.

The early stage looks like TV static, as all the cells are random and almost all the cells are wanting to move at each iteration.

RacistCells_Early

After a few iterations the cells have started coming closer to other cells of their same colour and happier to stay. So you see it forming into small coloured blobs. There is a lot of movement though because there are a lot of places where the colours are still mixed.

RacistCells_Mid

Over time the colonies become larger as the cells in the centre of each colony are happy to stay put. The boundaries are fought over and the colonies become larger pushing other ones away.
The trend continues but slows down. There are less borders and less movement.
Eventually there will only be one blob per colour (remember the universe wraps). Each blob will be 20% of universe. The borders will then slowly move, but the overall pattern will look the same.

RacistCells_Late

Unlike Conway’s life, this has a random element to it, so each frame is not predictable from the previous one. The probabilities for moving can be modified in the program giving quite different results.

For the examples above the probabilities are given as:
{ 20, 50, 60, 200, 210, 220, 250, 253, 255 }
For each cell a random value between 0 and 255 is picked. The threshold for moving is taken from the array above. The position in the array is based on number of cells of same colour surrounding.

So if a cell is has no neighbouring cells of same colour as it, then it will move if the random number is over 20. In other words, a 92% chance of moving. If a cell has 7 out of 8 neighbours the same colour then its chance of moving is about 0.8%. And if all 8 neighbours are the same colour then it will not move at all.

Its quite a lot of fun to play around with these values in the array and see the different outcomes.

CellularAutomaton.zip – This contains the C source code and executables for Windows, OSX, and Linux. This is free and unencumbered software released into the public domain.

Advertisements