home *** CD-ROM | disk | FTP | other *** search
/ CP/M / CPM_CDROM.iso / mbug / mbug134.arc / LIFEDEMO.DOC < prev    next >
Text File  |  1979-12-31  |  6KB  |  167 lines
  1.                           Conway's LIFE revisited
  2.                               by Frank Connell
  3.  
  4.  
  5.  
  6. What computer owner hasn't heard of John Conway's famous game of 
  7. "LIFE"? 
  8.  
  9. And what computer programmer, after typing in or downloading simple 
  10. programs, has not been disappointed with the display and lack of 
  11. speed? Let's see if we can't hurry things up a bit!
  12.  
  13. This is the programming scheme most are familiar with:
  14.  
  15. make two arrays of x columns and y rows
  16. place live cells in first array
  17.  
  18. for each generation:
  19.        for column = 1 to x
  20.             for row = 1 to y
  21.                  count neighbours
  22.                  decide if alive or dead in next generation
  23.                  put live cells into second array
  24.             next row
  25.        next column
  26. copy second array to first
  27. next
  28.  
  29. The algorithm has the advantages of simplicity and an easy-to-grasp 
  30. logic, but inspection reveals some reasons for its poor performance.
  31.  
  32. 1) The time required to scan the arrays increases geometrically with 
  33. size.; a 10x10 array has 100 positions, a 20x20 array has 400. As you 
  34. make the array bigger, performance rapidly suffers.
  35.  
  36. 2) The algorithm spends much time in pointless calculations. A 20x20 
  37. array might have only 20 of its 400 cells occupied, but the algorithm 
  38. does calculations for all 400 cells, ignoring the obvious fact that 
  39. cells isolated from living cells have no neighbours and will not 
  40. become occupied.
  41.  
  42. A much faster algorithm, described below, uses lists of only those 
  43. cells which might possibly change in the next generation.
  44.  
  45. The scheme uses three lists:
  46.      live_list      cells alive this generation
  47.      die_list       living cells which will die next generation
  48.      check_list     dead cells which may become alive next generation
  49.  
  50. and two arrays:
  51.      nbr_array      the number of neighbours for each cell
  52.      flag_array     records if cell alive or dead, and if its
  53.                     neighbours have been added to check_list
  54.  
  55. (In the assembly language version, I have utilised the unused bits of 
  56. nbr_array as my flag_array, saving on space).
  57. .pa
  58. initialise:
  59.  
  60.        set up PCG characters for display
  61.        initialise arrays to zero
  62.        read live_list from disk, data or screen
  63.        null check_list, die_list
  64.  
  65. mainloop:
  66.  
  67.        for each cell in die_list
  68.           flag_array = 0
  69.           erase cell
  70.        next
  71.  
  72.        for each cell in live_list
  73.           flag_array = 1
  74.           display cell
  75.        next
  76.  
  77.        for each cell in live_list
  78.           for each of its 8 neighbours
  79.                increment nbr_array
  80.                if high bit flag_array not set
  81.                     add neighbour to check_list
  82.                     set high bit flag_array
  83.                endif
  84.           next
  85.        next
  86.  
  87.        for each cell in die_list
  88.           for each of its 8 neighbours
  89.                decrement nbr_array
  90.                if high bit flag_array not set
  91.                     add neighbour to check_list
  92.                     set high bit flag_array
  93.                endif
  94.           next
  95.        next
  96.  
  97.        null live_list, die_list
  98.  
  99.        for each cell in check_list
  100.           reset high bit flag_array
  101.           if flag_array = 0 AND nbr_array = 3
  102.                add cell to live_list
  103.           else if flag_array = 1 AND (nbr_array<2 OR nbr_array>3)
  104.                add cell to die_list
  105.           endif
  106.        next
  107.  
  108.        repeat mainloop
  109. .pa
  110. Check your bulletin board for the file LIFEDEMO.COM, a demonstration 
  111. of the technique using an array of 80x48 cells.
  112.  
  113. As you read this, I am working on a "deluxe version" which will have 
  114. many added features: a large library of starting patterns, control 
  115. over display speed (sometimes things change too fast to follow!), the 
  116. ability to design or modify your own patterns with a mouse (256TC) or 
  117. cursor keys, and the option of saving interesting discoveries to your 
  118. own disk library. This program, NEWLIFE.COM, will be available soon 
  119. for the paltry sum of $20. Keep watching the BBS!
  120.  
  121. In the meantime, you may enjoy exploring the fast LIFE algorithm in 
  122. your own programming hours.
  123.  
  124. Reference:     Data Structures and Program Design
  125.                Robert L. Kruse
  126.                Prentice-Hall International (Sydney) 1984
  127.  
  128. This is an excellent book for programmers, using Pascal to illustrate 
  129. many valuable techniques concerning linked lists, binary trees, 
  130. sorting methods and information retrieval.
  131.  
  132.                            The Game of Life
  133.  
  134. The game (better described as a simulation) of LIFE was introduced to 
  135. the computer hackers of the world in 1970 by British mathematician 
  136. J.H. Conway, and helped on its way to being a computer classic by 
  137. Martin Gardner in the pages of Scientific American magazine. It owes 
  138. its popularity to the fact that it is an ideal display for home 
  139. computers, and an ideal vehicle for home programmers.
  140.  
  141. LIFE takes place on a rectangular grid of cells which can either be 
  142. occupied by an organism or not. Which cells live and which die from 
  143. generation to generation are found from the following rules:
  144.  
  145.        1) The neighbours of a cell are those which touch it 
  146.        vertically, horizontally and diagonally.
  147.  
  148.        2) A living cell with either two or three neighbours remains 
  149.        alive in the next generation, otherwise it dies.
  150.  
  151.        3) If a cell is dead, it will become alive in the next 
  152.        generation only if it has exactly three live neighbours.
  153.  
  154.        4) All births and deaths occur at the same time.
  155.  
  156. It is a fact of life that from very simple starting configurations, 
  157. complicated, beautiful and often fascinating patterns of cell colonies 
  158. can grow over many generations.
  159.  
  160. The grid in my versions of LIFE "wraps around" so that cells moving 
  161. off the left and bottom of the screen reappear at the right and top. 
  162. This is not quite what Mr Conway described, but an infinite unbounded 
  163. grid is a little beyond this programmer's capabilities!
  164.  
  165. Frank Connell  5/10/89
  166.  
  167.