home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ARM Club 3
/
TheARMClub_PDCD3.iso
/
hensa
/
genetics
/
listlife_1
/
TechDocs
< prev
Wrap
Text File
|
1994-11-28
|
4KB
|
81 lines
This file contains technical details of ListLife, a fast (1000
gens/sec!) implementation of Conway's Game of Life by Tony Finch.
This program has a very crude front end and no introductory
documentation because I only wrote it to try out the algorithm. If you
want a nice front end with lots of example patterns and helpfiles, then
pester me. My addresses are below.
It is called ListLife because it stores the Life arena as a list of the
positions of the live cells (rather than in a bitmap). This means the
arena can be large (2e9 by 2e9) whilst taking up little space and time.
Memory limits the number of live cells to about 2 million (if you can
get a 16MB wimpslot). Thanks to Olly Betts for this idea. I couldn't be
work out how his program worked, so I wrote this one which turned out
three times faster!
The list of live cells is stored in order by rows. Since each row has
the same Y coordinate throughout, that is stored once per row. To
distinguish Y coordinates from X coordinates, Ys are negative and Xs are
positive. This saves time as well as space since the program does not
have to deal with Y coordinates when looping along a line.
The inner loop scans along 3 adjacent lines together, maintaining a
small (3x3) bitmap in one of the registers. This bitmap is the
neighbourhood of the cell that is being examined. Because this bitmap
takes only 512 different values, the operations of counting up the live
neighbours and deciding whether the cell should live or die can be done
by a simple table lookup and compare with 0.
Blank areas are skipped by comparing the bitmap with 0, then seeing
which coordinate from the 3 lines is next and continuing from there.
This is when the program checks for the end of the line. Because the X
coordinates are sorted into decreasing order, the program just finds the
maximum of the next coordinates on the three lines (which values are
cached in the registers). If this value is less than 0, then the line is
complete.
The algorithm does special things to handle X loops where less than
three lines are occupied. These cases could be handled by the 3 line
loop by leaving the relevant next-coordinate-cache register negative,
but special case code is quicker.
The plot routine is worth a mention. The coordinates of each point
have to be checked against the screen limits; the inner loop is
carefully crafted so that this check is combined with calculating the
point's offset from the edge of the screen, so saving an instruction.
This loop could probably do with being unrolled.
The larger structure is interesting too. The previous generation is
removed from the screen (clearing the whole screen is slower) and then
the new generation is plotted. If these are done sequentially, the
display becomes very flickery, so the display is unplotted and replotted
line by line. You can see this quite well on the Maximum Growth pattern.
Try replacing the CALL update on line 1700 to CALL undraw: CALL
redraw. (This is the smallest known spacefiller, and possibly the
fastest growing pattern possible. It expands at the maximum possible
speed, and fills the middle to a density of 1/2.)
Some example patterns are included as data statements in the program, as
well as a random square generater. My usual benchmark is the Rabbit,
which starts with 9 cells and grows for 17331 generations, growing to a
population of about 2400 cells. On my 25MHz A5000 it averages 169
gens/sec. On a Risc PC 600 of unknown details it did 222 gens/sec. To
justify my claim of 1000 gens/sec, the program can do an R pentomino
(1103 generations, c. 200 cells) in 0.82 secs. These timings were made
in mode 0 without plotting (whoever said benchmarks had to reflect
reality?).
If you wnat to find more info and programs and patterns (but in a PC and
unix centred sort of way) then FTP to life.anu.edu.au and look in
/pub/complex_systems.
If you want to contact me and ask if I'm doing anything useful, then
email fanf2@cam.ac.uk
snail Trinity College 3 Natwoke Close
Cambridge Beaconsfield
CB2 1TQ Bucks
HP9 2AR