Friday, August 25, 2006

rh4_060825_Game Of Life


CONWAY'S GAME OF LIFE:

The GAME OF LIFE is a CELLULAR AUTOMATON devised by the British mathematician John Horton Conway in 1970. It is the best-known example of a cellular automaton.

The "game" is actually a ZERO-PLAYER GAME, meaning that its EVOLUTION is determined by its INITIAL STATE, needing no input from human players. One interacts with the Game of Life by creating an initial configuration and OBSERVING how it evolves.


RULES:

The universe of the Game of Life is an infinite two-dimensional grid of cells, each of which is either ALIVE or DEAD. Cells interact with their eight NEIGHBOURS, which are the cells that are directly horizontally, vertically, or diagonally adjacent. At each step in time, the following effects occur:

1. LONELINESS : any live cell with fewer than two neighbours dies.
2. OVERCROWDING : any live cell with more than three neighbours dies.
3. STASIS : any live cell with two or three neighbours lives, unchanged, to the next generation.
4. REPRODUCTION : any dead cell with exactly three neighbours comes to life.

The INITIAL PATTERN constitutes the first generation of the system. The second generation is created by applying the above rules simultaneously to every cell in the first generation -- births and deaths happen simultaneously, and the discrete moment at which this happens is called a TICK. The rules continue to be applied repeatedly to create further generations.



ITERATION:

From an initial pattern of living cells on the grid, observers will find, as the generations tick by, the population constantly undergoing unusual and always unexpected, change. The patterns that form from the simple rules may be considered a form of BEAUTY. In a few cases the society eventually dies out, with all living cells vanishing, although this may not happen until after a great many generations. Most initial patterns either reach stable figures - Conway calls them "still lifes" - that cannot change or patterns that oscillate forever. Patterns with no initial symmetry tend to become symmetrical. Once this happens the symmetry cannot be lost, although it may increase in richness.


ALGORYTHMS:

The earliest results in the Game of Life were obtained without the use of computers. The simplest still-lifes and oscillators were discovered while tracking the fates of various small starting configurations using graph paper, blackboards, physical game boards, for instance Go, and the like. During this early research, Conway discovered that the R-pentomino failed to stabilize in a small number of generations.

These discoveries inspired computer programmers over the world to write programs to track the evolution of Life patterns. Most of the early algorithms were similar. They represented Life patterns as two-dimensional arrays in computer memory. Typically two arrays are used, one to hold the current generation and one in which to calculate its successor. Often 0 and 1 represent dead and live cells, respectively. A double loop considers each element of the current array in turn, counting the live neighbors of each cell to decide whether the corresponding element of the successor array should be 0 or 1. At the end of this process, the contents of the successor array are moved to the current array, the successor array is cleared, and the current array is displayed.

A variety of minor enhancements to this basic scheme are possible, and there are many ways to save unnecessary computation. A cell that did not change at the last time step, and none of whose neighbors changed, is guaranteed not to change at the current time step as well, so a program that keeps track of which areas are active can save time by not updating the inactive zones.

In principle, the LIFE FIELD IS INFINITE, but computers have finite memory, and usually array sizes must be declared in advance. This leads to problems when the active area encroaches on the border of the array. Programmers have used several strategies to address these problems. The simplest strategy is simply to assume that every cell outside the array is dead. This is easy to program, but leads to inaccurate results when the active area crosses the boundary. A more sophisticated trick is to consider the left and right edges of the field to be stitched together, and the top and bottom edges also. The result is that active areas that move across a field edge reappear at the opposite edge. Inaccuracy can still result if the pattern grows too large, but at least there are no pathological edge effects. Techniques of dynamic storage allocation may also be used, creating ever-larger arrays to hold growing patterns. Alternatively, the programmer may abandon the notion of representing the Life field with a 2-dimensional array, and use a different data structure, like a vector of coordinate pairs representing live cells. This approach allows the pattern to move about the field unhindered, as long as the population does not exceed the size of the live-coordinate array. The drawback is that counting live neighbors becomes a search operation, slowing down simulation speed. With more sophisticated data structures this problem can also be largely solved.



technics: first tests on V-Ray for rhino; here Global Illumination with very few settings...

credits: every experiment has its past, future and references... here partly challenged by Chris & Ben (www.terraswarm.com) and some old demons from the AADRl background, theverymany is looking back at "Cellula Automaton" & "A New Kind Of Sciences" from Stephen Wolfram... that is a very Step01...

Labels: , ,