Sunday, March 15, 2009
Conway's Game of Life
This is a simple programming game first proposed by British mathematician John Horton Conway in 1970. It is the best-known example of a cellular automaton.
The idea is that you have a 2-dimensional grid with cells. These cells can be alive or dead (on or off,true or false, colored or blank). When the simulation is running the state of a cell is determined by three simple rules:
1.- If the cell has no living neighbors or just one, it will be dead (caused by loneliness);
2.- If four or more of the cells next to it are alive, it will be dead (overcrowding);
3.- If a dead cell has exactly three living neighbors it will come alive (Bitstorm).
The effect of these simple rules can be quite surprising. The starting grid can be very chaotic, but after a while you can see patterns emerge, and even stable situations can be reached where nothing will change any more, or the same patterns are just repeated over and over.
From an Excel implementation of this algorithm, I can describe:
1.- "Main" Sheet
This is where the evolution happens, each evolving cell has the same value:
a.- Reset is the name given to a specific cell in the Main Worksheet, and which can be either False (iteration continues as usual), or True (Cell acquires Value of its equivalent cell in "Template" Sheet, in this particular example, Cell L3.
b.- Usual iteration will determine the number of neighbouring True cells for each cell, and apply the rules as explained above.
2.- "nbors" Sheet
This sheet holds the exact same matrix as in "Main". Each cell here has the value
Please note this is a matricial function in Excel.
This is, each cell will sum what happens with each of its 9 surrounding cells. The result will thus be the number of True Cells around it.
3.- "Template" Sheet
Sheet equivalent in dimensions to the other two mentioned above, but which only holds cells with either True or False Values. This matrix will determine the values assumed when Reset is set to True in our "Main" sheet and an iteration is run.
Please feel free to download and play around with an example of such an Excel Database here.