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