Sections  Introduction  Emergence  Complexity  Chaos Thoery  Cellular Automata  Life Forms  Neural Networks   Evolution  L systesm  Uses people.htmlBooks Links about this site Site Index  Front Page
Stewart Dean's Guide to Artificial Life

Cellular Automata

New: Conway's life in Flash.
To go with this section I have created a mini version of conway's life. Click here to launch. .

The father of Cellular Automata, and aLife come to that, is John von Neumann. He was the first to propose a system for producing life like results from simple rules. His aim was self reproduction; a John von Neumann machine is one that can do this. A cellular automata is an array of 'cells' that interact with their neighbors. These arrays can take on any number of dimensions, starting from a one dimensional string of cells. Each cell has its own State that can be a variable, property or other information. By receiving input from connected cells or general messages a cell uses its own set of rules to determine what its reaction should be. This reaction is a change of state and can also be a trigger to send out its own messages. These messages are passed onto other selected cells which cause them to act like wise.

Natural cells work much in the same way. For example in an embryo messages are spread by timed releases of chemicals by cells which tell a cell which type of cell it should be. Each cell has a look up library, the code of DNA, to control its actions. A cell also has a chemical plant and chemical responses that act as its input and output devices. These plants are controlled by RNA, the slaves of DNA. Different doses of chemicals and in different combinations cause a cell to act in different ways. Sometime small changes in chemical density can lead to radical changes in cell formation. This is how cell barriers are formed. By a mixture of co-operation and competition complex forms, like a human baby, can be built up.

Artificial cellular automata are usually a lot simpler but can mimic many of the behavioral patterns of natural biological systems. In Tom Ray's Tierra each 'creature' could be seen as a cell which has then got to compete and co-operate with all the other cells that use the shared resources available. See the evolution section for more details.

The most famous example of Cellular Automata is Conway's life. As described in the introduction, Life is based upon the theories of Von Neumann, the father of Alife. This cellular is a two dimensional grid in which each square can take on of two states, off or on. Each cell is identical and runs by the same rules. The rules are:

  1. A living cell with only 0 or 1 living neighbors dies from isolation.
  2. A living cell with 4 or more living neighbour dies from overcrowding.
  3. A dead cell with exactly 3 living neighbour becomes alive.
  4. All other cells remain unchanged.
These rules are applied to all the cells simultaneously. Each time whole array is recalculated it is called a generation. As the program runs through multiple generation the array can be see to be moving in strange, non-random ways. From any mildly complex starting point different behavioral patterns will emerge. One of the most common are groups of cells called blinkers. These are bars of other shapes that constantly switch between two formations according to the rules. Left untouched they will blink for ever. This is called a periodic system.

Other patterns may die away all together. These are unstable systems. Few unstable systems can be seen in nature because they don not last long. Nature is full of stable, and more importantly, complex states. Life has its share of complex states. These are states that don't stay still or die out. The most famous are gliders. A glider is pictured here.


Most complicated patterns used a starting point in Life will, sooner or later throw out gliders. These, as the name implies, gliders across the screen and would do so for ever if they do not hit anything. The existence of gliders in life soon made other people think it might be able to produce other more complex patterns. One main problem was the problem of maintaining motion. This problem was solved with the discovery of the glider gun (left). Two main types of these exist and can be used to produce strange results. Using glider guns other types of pattern could be reproduced like the fish gun. (Cue joke: I've got a fish tank, it fires real fish.)

Finally here is a complex pattern that creates a random stream of gliders. The picture does not really convey the way it works, this is only possible to demonstrate when the pattern is in motion. Using a combination of glider guns, fish guns and feedback as found in chaotic systems this diagram manages to produce a near random output. In theory using a combination of guns, blockers and feedback it would be possible to emulate the workings of a computer, the only trouble being that of size. It is estimated a grid the size of a small city would be needed to produce sufficient complexity and imagine how much memory that would take.

Cellular automata are a sub set of alife as most creatures could be said to be mobile or kinetic cellular automata. Even human behaviour is not outside the realms of CA. In computer graphics there is a branch of modeling called particle physics. In particle physics, in computer graphic terms, each particle is a polygon or animated creature. Each interacts with the general environment obeying the laws of physics (or any other rules the creator deems fit). The results are as diverse as flocking creatures to the simulation of water falls and explosions to the flow of a crowd as it fills a football stadium. The creatures section explores this more.

Another example of the uses of cellular automata is in the simulation of the spread of forest fires. Given a landscape of different types of ground cells (bare earth, forest, dense forest or grass) and add information, such as the time for fire activity in each square, patterns associated with the spread of fire soon emerge. Even with total random starting points, these patterns will still occur.



Please send any corrections, comments or additions to: alife(at)stewdean(dot)com
 

 back a bit  next bit