Cellular Automata Experiments

It is my intention to occasionally talk about the work I do in university in these blogs. However for the most part first year has, not so unsurprisingly, been mostly about foundations. Foundations are important, but not particularly interesting blog material. This is likely to change next semester when I start my first ASC and can report on that. But for now I’ll talk about the first assignment I did in Comp1100, an introductory course to programming. The assignment had an extension task element to it, which I twisted as best I could into a scientific experiment.

Cellular Automata

The first assignment we did in Comp1100 was on Cellular Automata. For those who haven’t heard about them before, they are pretty cool things. Imagine a grid – on this grid squares can be black or white. White squares are inactive and represent a background whereas black squares are active. The pattern of active and inactive squares is determined by a pattern which changes over time according to specific rules. This can best be represented by a simple example:

Conway's Life

Each frame of “time” in this cellular automata is derived from the frame before it using purely mathematical algorithms.

Cellular Automata were invented at around the same time as computers were, as the amount of computations needed to draw them are very tedious by hand. However they are not just pretty patterns, they have significant mathematical, computational, and biological importance. The main reason for this is that they display simple forms of emergence. From simple rules we see patterns emerge in the structures. Perhaps more interesting is the fact that we see things happening which we could not have predicted, like the creation of “gliders” in the animation above. Cellular Automata eventually gave rise to the field of Artificial Life, which I will no doubt talk about at a later date. I’ll quickly go through two of the most famous cellular automata, as examples and because they are both really cool. (N.B. You may be interested to know that in most cellular automata the “grid” wraps around on itself at both the top and bottom, making the board essentially equivalent to a torus (the same way a map of earth is equivalent to a sphere)

Famous Cellular Automata:

1. Conway’s Game of Life (Play it Here)

Conway's Life Animation

Conway’s game of life is one of the first and most famous cellular automata ever invented. It was designed on a simple premise, cells will “die” if they are overpopulated or underpopulated – but otherwise they will grow and spread. From this somewhat simple premise we see a huge array of different structures emerging. Different patterns will tend to be “stable” and either stay statically in one place, or will move around. This in many ways lives up to its name and on a very rudimentary scale it mimics life on earth. The development of complex structures from chaos is the reason life exists at all, and the extreme complexity which arises from the comparatively tiny amount of rules in the game can help explain why life on earth shows such immense complexity itself.

2. Langton’s Ant

Langton’s Ant was the first Cellular Automata I ever heard of, and I remember being fascinated by it. Unlike Life which charts a whole world of creatures, Langton’s Ant is about a single creature and the path it makes. As it moves it leaves a black trail behind it. At every white square it hits it will turn 90 degrees left before advancing again, then when it eventually hits a black square it turns 90 degrees right and turns the black square back to white. So it will continue in a seemingly random fashion, traversing around and around in completely patternless shapes. That is, until suddenly it doesn’t. At an certain point in its pattern it creates a “highway” which involves a set of steps which will be indefinitely repeated. This is a “Stable” configuration which it just happens to stumble upon but it is a configuration it will maintain. Again this is an example of structure arising from chaos.

Highway

Designing My Own Cellular Automata

While my assignment dealt mostly with simple programming and getting cellular automata to work in the first place, it also had an extension section where we could try and get other cellular automata to work. While copying other famous examples would be fun, I thought it would be more interesting to try my own variations on the theme. By developing my own algorithms I would be able to see unique results, which would be far more interesting.

I began my quest to make interesting cellular automata by deciding that the ones I made would be variations on the theme of Conway’s Life. I wanted my active states to represent different organisms in a world. Unlike Conway’s Life however I decided to have more than just active and inactive states – I made two separate types of active states. In other words there are two different “teams” (or species if you will) of cellular automata. This fundamental difference opened up a new array of options – particularly in how these different types could interact. I completed three variations on the theme: Teams, Sheep, and Prey. Sheep was by far the most successful in terms of interesting patterns. I’ll go through the rules and results each of them gave below.

(For all my tests I used starting boards which had roughly random assortments of each type – I have not extensively tested them in any other specific starting patterns. I also used high-density versions of Conway’s life for my versions.).

1. Teams

My first creation was called teams and was simply the existence of two teams together in one world – Red and Blue. My rules were as follows: (Note: Neighbours is refers to a Moore Neighbourhood, in other words, all adjacent squares are neighbours)

  1. A Red square will stay Red if it has 2 or 3 Red neighbours, any more or less and it will become inactive.
  2. A Blue square will stay Blue if it has 2 or 3 Blue neighbours, any more or less and it will become inactive.
  3. An inactive cell will become Red or Blue if it has 2 neighbours of that type, if it has 2 neighbors of both types it will remain inactive.

The results of this were interesting, but not shocking:

Cellular Automata Teams

As you can see between 0 and 1 iterations we see a lot of the organisms die due to overcrowding. By the 6th iteration we see that populations are beginning to form in clumps of their own kind, distinct from one another. This is somewhat interesting an occurrence to have happened, especially as it lays the foundation of later iterations. I should note that these populations are dynamic and individual cells change from active to inactive regularly.

By the 12th iteration the whole world is heavily populated and the borders of the two species are pushing against each other – they are prevented from spreading by each other, and are thus competing for space. Finally we see that as time goes on the red side has largely won the fight for space – although it seems quite unable to  push back the blue entirely. The fact that red won is very likely a result of the initial random state – but it proves that in the fight for space the two species can in fact force each other to extinction.

2. Sheep

Sheep was my second creation and I consider it to be my best so far. In teams I had had two organisms which were essentially the same, they followed the same rules. In sheep that changed – I created two types of organisms, Sheep (white) and Grass (green). My logic was that grass would expand and grow somewhat rapidly, it has no problems with overcrowding so can fill in solid spaces. Sheep on the other hand require nearby grass to survive – however if there are too many sheep to one area of grass then the grass will die, and the sheep will starve shortly afterwards. Thus the rules for sheep became:

  1. A Grass square will only die if there are 3 or more Sheep neighbours.
  2. A Sheep square will die if it has 0 Grass neighbours.
  3. An inactive cell will become a sheep if there are two or more sheep neighbours (sheep are not asexual 😉 ) and at least 3 grass neighbours (sheep only breed when food is plentiful).
  4. An inactive cell will become grass if it has no sheep neighbours and at least 3 grass neighbours.

Cellular Automata Sheep

The results show a very interesting progression of stages, each with its own interesting phenomena. We can see that in the first 30 or so iterations that grass begins to grow quite rapidly, sheep in tow. We see colonies of sheep growing on the sides of expanding patches of grass which start to dominate the world. However in addition we also see various shaped colonies of sheep and grass which are living perfectly stable (and static) lives, where neither sheep nor grass are dieing or reproducing.

However as time goes on (168 being an example) we see that almost the entire field is covered in huge areas of grass, with uniform sheep boundaries eating away at their sides. The grass grows in curly waves and semi-circles because areas next to sheep do not grow, while sides away from sheep do, meaning the edge of the grass curls around the line of sheep. These huge waves will collide with smaller colonies and completely ruin the equilibrium they have, making them just another part of the  larger cycles.

The process of waves moving around continues for a long time and for a while it seems the system will remain forever in this dynamic state. However the static colonies find a way to strike back. A special subset of static colonies is able to resist being destroyed by large waves, these specially shaped colony types thus survive and remain. Over time they must be created due to probability and chance, and they are never destroyed and so begin to accumulate. Furthermore, while completely immune colonies are very rare, colonies immune to only one side are less rare. This means that these one-side immune colonies can build with their backs to immune colonies and expand that way. This increased probability results in the quickened spread of static sustainable colonies over time. By the iteration 3409 shown there is only a single cross shaped path left where the original waves are, the rest is static. And by 3540 the world is entirely stable and will no longer change. This exact value will change depending on the random start, but the result is the same.

3. Prey

The final variation on the theme I created was prey. The system would work much like sheep, except the instead of having grass being eaten, it would be another normal conway organism, affected by overpopulation etc. I believe I could have done better on the implementation of this version, but I ran out of time and I believe that as it is the system illustrates what is happening. Prey are green and Predators are red in this version. The rules I used are as follows:

  1. Predators die if they have no prey neighbours.
  2. Prey will stay alive if they have 2 or 3 prey neighbours and no predators, otherwise they will die.
  3. Inactive cells with one predator and at least two prey neighbours will become predators.
  4. Inactive cells with  no predators and at least two prey neighbours will become prey.

Prey-Results

As we can see in these results, the beginning of this simulation involves the majority of the board dying from overcrowding or starvation. However we see small pockets of predators and prey surviving together. These expand, the prey expanding far quicker than the predators so that by iteration 39 there are large prey populations. However by this point the predators too begin to increase and eat their way out in circles through the prey. Unlike in sheep, the systems here are all dynamic due to the overcrowding killing individuals. By later iterations the system becomes a dynamic equilibrium between predators and prey and as far as I can tell it continues this way indefinitely.

Conclusion

I am glad I did try to create my own cellular automata as the results were very interesting. It was not particularly difficult to come up with the basic rules for the system – and once they are run it is amazing to see the complex results that occur as a result. Sheep in shows how such simple rules can really lead to an extremely complex system, with multiple stages and even what could be considered natural selection. The simple truism that things which sustain will sustain is what kept the immune colonies going – and this is a fantastic parallel to life and how we think its origins began. All you need is a structure that can either stay alive or replicate itself, and over time one is bound to arise.


Advertisements

~ by Myles O'Neill on May 24, 2009.

One Response to “Cellular Automata Experiments”

  1. wow tht makes JOUR1112 look rather easy…..

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

 
%d bloggers like this: