* This represents a "glider gun" developed at M.I.T. that first proved
* that a Life pattern could continue generation infinitely. After 39
* cylces it will emit a "glider" which will begin to move down the
* screen. A new glider is emitted each addtional 30 cycles. For
* this to work, you must play with the "flat" screen option.
* (Taken from the excellent book "The Turing Omnibus" by A.K. Dewdney.)
XX
X
X X
X X XX
XX X XX
X XXX X
XX XX XX
XX
X
* Simple "gliders" that move across the screen endlessly.
* Use with "circular" option for best effect. (This file was used
* to test and debug this Life program.)
X X X X X X X X
X X X X X X X X
XXX XXX XXX XXX XXX XXX XXX XXX
X X X X X X X X
X X X X X X X X
XXX XXX XXX XXX XXX XXX XXX XXX
X X X X X X X X
X X X X X X X X
XXX XXX XXX XXX XXX XXX XXX XXX
X X X X X X X X
X X X X X X X X
XXX XXX XXX XXX XXX XXX XXX XXX
X X X X X X X X
X X X X X X X X
XXX XXX XXX XXX XXX XXX XXX XXX
* These are some simple "gliders" that will move across the
* screen endlessly.
X
X
XXX
X
X
XXX
X
X
XXX
X
X
XXX
Adding New "Life" To FoxPro
Tom Rombouts
Introduction
============
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."
num_or_filef
num_or_filef
p_circularf
STORE .T. TO stop_flag
ACTIVATE POPUP lifeopts
Fox\<Life
ALT+L
\<File
\<Edit
\<New
\<Save
\<About
\<Exit
DO FILE_GET IN FOXLIFE.PRG
DO PATT_EDIT IN FOXLIFE.PRG
DO INSTRUCT IN FOXLIFE.PRG
DO FILE_SAVE IN FOXLIFE.PRG
DO L_ABOUT IN FOXLIFE.PRG
DO LIFE_EXIT IN FOXLIFE.PRG
num_or_filef
num_or_filef
Cycle: FF
Cells:
lastlife.dat
That's all, folks!
P_NUM_OR_FP_CIRCULARP_CHAR
e rGO_FLAG
m.FILE_FLAG
NUM_OR_FILF10
LARG_ROWS
lcuG_COLS
PerACAL
tatisADIS
eraMENU_FLAG
STOP_FLAG
QUIT_FLAG
POPULATIONGENERATIONEROW
d priECOL
LIFEMENU
nLIFEOPTS
vINSTRUCT
LFILL_RAND
PATT_LOAD
CAL_EDGE_CCAL_EDGE_FCAL_CENTERSHOW_EM
PATT_SAVE
MAINMENU
The game of Life by John Conroy
If started with a number, a random pattern starts the game.
If started with a file name, will load game based on data
in that file.
F10 will activate the menu. Hit ESC to bail out.
Enter number of cells or data file name, or hit CR:
USER_VAL
FSCR_TEMP
Generating random pattern....
NUMBER
FP_ROWS
RP_COLS
rP_CHAR
LE_FLAG
OR_FILCOL
LARSEED
lcuRNUM
PerPOPULATIONGENERATIONADIS
P_ROWS
FP_COLS
RCROW
rCCOL
m.DNCOL
UPCOL
_FILLFCOL
LARRTCOL
lcuADIS
PerACAL
ATION
P_ROWS
FP_COLS
RCROW
rCCOL
m.DNCOL
UPCOL
_FILLFCOL
LARRTCOL
lcuADIS
PerACAL
ATION:
P_ROWS
FP_COLS
RACAL
rADIS
m.CROW
UPROW
_FILDNROW
LARCCOL
lcuLFCOL
PerRTCOL
TION-
P_ROWS
FP_COLS
RCROW
rCCOL
m.ADIS
UPROW
_FILDNROW
LARLFCOL
lcuRTCOL
PerACAL
P_ROWS
FP_COLS
RP_CHAR
rPOPULATIONCROW
FILCUR_CELL
RACAL
lcuADIS
Error creating file:
Error closing file:
SAVEFILE
FP_ROWS
RP_COLS
rHANDLE
IONSROW
FILADIS
New pattern:
NEWFILE
FPATT_LOAD
G_ROWS
rG_COLS
IONP_CHAR
Reading in row FF
DATA_FILE
P_ROWS
P_COLS
rP_CHAR
IONHANDLE
FILCOL
RCUR_LINE
uPOPULATIONGENERATIONACAL
IONADIS
WIDTH
Pattern editing not completed - any key to continue
Edit mode Arrow keys move - spacebar toggles - ESC or CR to end
(.txt)