If you are the prototypical computer nerd, and spent much of your undergraduate waking hours in the middle of the night, staring at increasingly blurry screens or wading through multi-pound printouts, then "Life" needs no further introduction. On the other hand, if you remember "Life" either as a breakfast cereal, or else a board game where you carefully prepared for the day of reckoning, then read on.
"Life" is arguably one of the most popular computer games ever. (Although "Leisure Suit Larry" may likely pre-empt it soon!) Actually, Life is more than just a game. It is actually a form of a mathematical theory that has been analyzed and written about more than you might think possible.
Life was invented around 1970 by John Conway, and first presented to the world in Martin Gardner's "Mathematical Games" column in the October, 1970 "Scientific American." A follow-up column appeared in the February, 1971 "Scientific American." The rules are very simple:
1. The game is played on a two dimensional grid of rectangular cells. (This version uses all but the bottom line of the screen as a 24 x 80 grid.)
2. Each cell can be in one of two states, either "dead" (or empty) or else "alive" (or full).
3. Each cell has eight neighbor cells, the four cells touching it, and the four cells "kitty corner" to it.
4. If a Life cell has less than two immediate neighbors, it dies of loneliness. If a Life cell has more than three neighbors, it dies of overcrowding.
5. If an dead Life cell has exactly three neighbors, it is brought to life.
Essentially, you start with either a random pattern, or else a carefully prepared set of initial cells. The computer then continually re-calculates each new generation based on the above rules, and updates the screen accordingly. (In case it is not clear above, the entire pattern must be recalculated before any cells are either born or die.)
When the game was first introduced, its creator, John Conway, made the prediction that any starting pattern would eventually either lead to no living cells at all, or else end up in a perpetually repeating pattern. Soon, however, a group of M.I.T. students came up with a pattern known as a "glider gun" that would shoot out perpetually living "gliders" that moved across the screen, every 30 moves. Given an infinite grid, such a pattern obviously increases the total population of cells perpetually.
For some people, this game becomes fascinating and almost addictive. (At least for a short period - I suspect many look back later and can not understand why they spent so many hours of fleeting youth on such frivolity! :-) ) The more you observe it, the more you will start to recognize some of the same patterns that appear again and again. Note that this version allows you to save games in progress, and to edit ASCII files with a text editor to create new starting patterns.
If you wish to know even more about Life, look up the subject "Cellular Automata" (or possibly "Finite State Automata") in your favorite CS library. (Oddly enough, E.F. Codd, the man who gave us the 12 rules of relational databases, wrote one of the first works in this area titled simply "Cellular Automata" in 1968.) Over the years, the game has been mentioned many more times in computer and mathematical oriented publications. In fact, as of 1978, there was even a quarterly magazine ("Lifeline") devoted solely to Life! The address was Robert Wainwright, 1280 Edcris Road, Yorktown Heights, NY, 10598.
Notes on this Implementation
============================
This version started out as anonymous C source from USENET, which was very fast but did not enforce the above stated rules 100% correctly. This FoxPro version is fairly slow by comparison, but does provide slightly more elegant saving and restore options.
Due to a full time job and the impending arrival of my first child, I did not have time to fine tune this as much as I would have liked. Still, this version does lay a good foundation for others who may wish to enhance it further. In particular, the menuing needs a bit of work, and the interactive editing of a game in progress is not finished. (Fragments of this can be seen in the code.)
The seemingly obvious approach of using two matching arrays, one for the current display and the other for re-calculation, is not necessary. Since the highest neighbor count can be 8, it was simple to use the first digit for the neighbor count, and then add this to 10 if the cell is alive, or 0 if it is not. The new modulus operator (%) of FoxPro 2.0 is then used to determine if the cell is alive or not.
Note also that I chose to make the screen "circular." That is, the cells along the top row are considered adjacent to the bottom row, and the cells on the far left column are considered adjacent to the cells on the far right column. This way, any patterns that move continuously (called "gliders" by Life buffs) will go off one side but begin to appear immediately on the other side.
Regarding saving or restoring a data file, I chose to use a space to mean a "dead" cell, and any other character to mean a "living" cell. This way, any text editor can be used to easily edit games. As in Xbase, a line in the data file (a .DAT extension is assumed) beginning with a "*" is ignored, allowing for easy documentation of patterns within the file. If a line ends before 79 columns, or a file before 24 rows, the missing cells are initialized as "dead."
Since the game Life is so well known, this would make an interesting challenge to see who could come up with the fastest calculation - display algorithm. (For example, one could display as soon as the neighbor calculation is done, saving one trip through the array. However, the even, top to bottom re-display seems most natural, methinks. To preserve this, the calculation of the corners and sides would need to be re-worked.)
As I worked on this code, I spotted some ways in which its overall speed of calculation could be improved. When determining if a cell is to live, die or be re-born, the rules are stated as looking at each of its eight neighbors. Thus, a simple implementation goes through the entire grid in order, and looks at each cells eight neighbors. Assuming a 25 x 80 grid (2000 cells) this gives us a rough total of 16,000 computations per generation.
However, in my experience with other implementations of life, I have learned a total population of between 200 and 300 is typical on a 2000 cell grid. Further, we can turn the rules around and state that if a cell is alive (has a value of 1), add one to the "neighbor count" of its eight neighbors. By taking this approach, we can look at each cell and determine if it is alive. If (and only if) it is alive, we do the calculations. Otherwise, we move immediately to the next cell. This does add one IF test for every cell in the grid, but also saves us 8 computations for each dead (0) cell.
Assuming a 2000 cell grid with 300 "live" cells, this results in 2000 IF tests, leading to 2400 (300 live cells x 8 neighbors) addition operations. Thus, this strategy results in 4400 total computations, vs. 16,000 for the more simple approach. This is a good example of a situation where knowledge of the typical case, in this example the percentage of life cells that tend to be alive, is critical to the proper selection of an algorithm. In the real world, such information is often available.
My second optimization reduces aesthetics, but increases throughput. (Being of a hackerish bent, this seemed like a great trade-off to me!) The problem is simple - Xbase screens are 0 based, but Xbase arrays are 1 based. Thus, to handle an array set up to match the rows and columns of the screen, you need to either add or subtract one somewhere along the line to get the array subscripts to match the screen row and column co-ordinates.
I did not try a final trick - using a one dimensional array or other clever data structures. It is a rule of computer science that anything that can be done in a N-dimensional array (or matrix) can also be done in a linear array (or vector). It was my belief that FoxPro would resolve the array subscripts internally far faster than I could by hand coding the arithmetic involved. (This is due to the interpreted nature of current Xbase products.) In a lower level language, however, where direct memory access is possible, this could be a fruitful approach. The "live" cells could be treated as linked lists, so that only the live ones were processed every time.
Further, since the value of a cell's neighbors is limited to a maximum of 8, one byte could store both a cell's state and the value of its neighbors. Bit twiddling could be used to adjust these values at maximum speed. However, these approaches will be left as exercises for the reader. :-)
* * * * * * *
ABOUT THE AUTHOR: Tom Rombouts has been working with Xbase products since 1985. He was one of the original testers for Emerald Bay, worked in test and development for Ashton-Tate for three years, and has written for the ".DBF" newsletter and "The C Users Journal." He currently works for Rettig-Miller Corporation in Los Angeles, and is working hard to help perfect Tom Rettig's Office for FoxPro 2.0, which he describes as a "breakthrough product that will change the way Xbase programmers develop applications."
