home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / sys / hp48 / 6304 < prev    next >
Encoding:
Internet Message Format  |  1992-12-14  |  12.1 KB
  1. Path: sparky!uunet!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!ira.uka.de!math.fu-berlin.de!uniol!hb.maus.de!f.maus.de!Timm_Ganske
  2. From: Timm_Ganske@f.maus.de (Timm Ganske)
  3. Newsgroups: comp.sys.hp48
  4. Subject: Life development
  5. Message-ID: <A20785@F.maus.de>
  6. Date: Sun, 13 Dec 92 03:37:00 GMT
  7. Organization: MausNet (Mitglied im IN e.V.)
  8. Lines: 200
  9. X-Gateway: MausGate/News 1.14D/hb
  10.  
  11.  This text describes the methods I used to implement life. Sorry for the
  12. eventually bad english.
  13. ___________________________________________________________________________
  14. Rules of life:
  15. ===========================================================================
  16. 1. One Generation is a rectengular grid, every element can be alive or dead.
  17. 2. The next generation is the same grid with the following changes:
  18.  a) A cell which is alive survives only if it has 2 or 3 neighbours
  19.  b) A cell which is dead is born to life if it has 3 neighbours
  20.  
  21. A neighbour of a cell is a cell which 'touches' the cell horizontally,
  22. vertically or diagonally.
  23. ===========================================================================
  24.  So if you want to calculate the next generation, you have to count the
  25. neighbours and then make the changes. But if you count the neighbours one
  26. cell at a time, it is going to be very slow. OK, how do you count? What are
  27. your numbers? A cell has at maximum 8 neighbours who are alive, so you need
  28. 4 Bits to represent this. The topmost bit of these isn't interesting, because
  29. if it is set, bit 1 (which counts 2) will be clear, and therefore the cell
  30. will not live. A cell with 8 neighbours will die as on with 0 neighbours does.
  31.  
  32.  You need 3 bits to count the neighbours. Let's see, how can you store the
  33. numbers? Why not organize them as the grid itself is organized?
  34.  Of course the representation of that grid on a computer is a bitmap, on the
  35. HP48 it is a graphics object. A pixel is set if the element is alive, and
  36. clear if it is dead. Similar there is a GROB for every bit to count the
  37. neighbours. And the neighbours are 8 Bitmaps, every one the grid, shifted a
  38. little.
  39.  
  40.  How do you add a bitmap to a set of bitmaps, which is representing as much
  41. binary numbers as the bitmap has pixels? Let's concentrate on adding one
  42. bitmap to the bit0-bitmap.
  43.  If a pixel is clear in both bitmaps, the pixel is cleared in the resulting
  44. bitmap. If a pixel in exact one of the two bitmaps is set, the pixel in the
  45. resulting bitmap is set. If a pixel is set in both bitmaps, the resulting
  46. pixel is clear and - there is a carry!
  47.  So there is a need to use a carry bitmap, which is given by an AND between
  48. the two input bitmaps, and the resulting bitmap is calculated by XORing the
  49. two input bitmaps. To make it clear:
  50. ___________________________________________________________________________
  51. Adding two bitmaps:
  52. ===========================================================================
  53. c(n+1) = b(n) AND input(n)           /* c = Carry */
  54. b(n+1) = b(n) XOR input(n)           (* b = bit   */
  55. input(0) is the original grid, input(n|n>0) is c(n)
  56. ===========================================================================
  57.  Now let's see how to make the changes from one generation to the next. To make
  58. it easy the KV-diagrams were invented:
  59. ___________________________________________________________________________
  60. Decision if a cell in the next generation lives:
  61. ===========================================================================
  62.   |-g | g | g |-g |
  63.   | 0 | 0 |-0 |-0 |
  64. --+---+---+---+---+    /*  g: Grid   */
  65.  1|\/ |   |\/ |\/ |    /*  0: Bit 0  */
  66. -2|/\ |   |/\ |/\ |    /*  1: Bit 1  */
  67. --+---+---+---+---+    /*  2: Bit 2  */
  68. -1|   |   |   |   |    /*  -: NOT    */
  69. -2|   |   |   |   |
  70. --+---+---+---+---+
  71. -1|   |   |   |   |
  72.  2|   |   |   |   |    /* The next generation grid is: */
  73. --+---+---+---+---+    /* 1 and -1 and -(g and 0)      */
  74.  1|   |   |   |   |
  75.  2|   |   |   |   |
  76. --+---+---+---+---+
  77. ===========================================================================
  78.  So I hacked this in and - it worked! I rewrote the graphical bitoperations in
  79. assembler to make it faster, RPL isn't that fast (as you know), and then
  80. the life program was ready.
  81.  
  82.  Here it is again in the ASCd version, someone couldn't UUdecode my last
  83. posting:
  84. %%HP: T(1)A(R)F(.); @ tasc v2.52 file
  85. "69A20FF714E1000000407424C41440CCD20290008FB976014313034E1B201428
  86. A62616414216EAF1D83411000E181D80CF128AE980D0AF2815AC1CD441154716
  87. F154716F6CEF1541136809136154112880DF8F2D760142164808C3A000407414
  88. E44440CCD20DF0008FB976014313017414313134E1B201438A6B11428A631164
  89. 1741421478A26068A016E17EAF3D73411000E380CF12881FAEB80D0817AC3CF4
  90. 8315671537AF80E76151716F17F15671537AF80E76151716F17F68CF15611531
  91. A980E16151113680913613780913715611531A980E16151112880DF8F2D76014
  92. 2164808CE01005074E414E44450CCD20901008FB976014313017414313134E1B
  93. 201438A6B11428A6311641741421478A26064B016E17EAF3D73411000E380CF1
  94. 2881FAEB80D0817AC3CF4E31567BFE1537AF80E76151716F17F1567BFE1537AF
  95. 80E76151716F17F62CF1561B9E1531A980E1615111368091361378091371561B
  96. 9E1531A980E16151112880DF8F2D760142164808CC1100407474F42540CCD20D
  97. B0008FB976014313017414313114334E1B208A62214234E1B208A63116417414
  98. 21478A260616016E17EAF3D73401000E380CF128AEB80D0817AC3CF4C1156715
  99. 370E7A155716F17F64EF156115310E1A155112880DF8F2D760142164808CEC00
  100. 0407414444440CCD201E3008FB97601431301741471741431021741431031353
  101. 4E1B201428A6F41641438A6441741331211221331438A6D21741331221231331
  102. 438A66117414216E14717E8A260664313312312213314717E8A67E1331221211
  103. 3314717E8A60DAF3D73411000E380CF12881FAEB80D0817AC3CF5606F6115671
  104. 537AF80E761507AFABFE0E75BFD0E700E7E151717F13312112213315671537AF
  105. 80E761507AFABFE0E75BFD0E700E7E151717F13312212313315671537AF80E76
  106. 1507AFABFE0E75BFD0E700E7E151717F13312312113316F15671537AF80E7615
  107. 07AFABFE0E75BFD0E700E7E151717F13312112213315671537AF80E761507AFA
  108. BFE0E75BFD0E700E7E151717F13312212313315671537AF80E761507AFABFE0E
  109. 75BFD0E700E7E151717F13312312113316F6E8E15611531A980E161501A9AB9E
  110. 0E15B9D0E100E1E151113780913713312112213315611531A980E161501A9AB9
  111. E0E15B9D0E100E1E151113780913713312212313315611531A980E161501A9AB
  112. 9E0E15B9D0E100E1E151113780913713312312113313680913615611531A980E
  113. 161501A9AB9E0E15B9D0E100E1E151113312112213315611531A980E161501A9
  114. AB9E0E15B9D0E100E1E151113312212313315611531A980E161501A9AB9E0E15
  115. B9D0E100E1E151113312312113312880DF8F2D760142164808C2F30040747454
  116. 4540CCD20C32008FB976014313034E1B201428A26068F1AF2169146129164AF0
  117. 1421041643470000CA81C81C81CC41031FB550714713514334E1B208A26066A1
  118. 17EAF2143307C281E81E81EC6D5174113E281CCC81C81C81C10011381CA64A6C
  119. 103814D0810C2E610AAF0B6481011B8166600810A4E59FA7C97C50A7C1243470
  120. 0000EF68A861E2114660081CCE5AF10481B43401100CA133D21574A4E5803078
  121. 161554133E4812C6CA13311B157410B1701574A4E480C067FF13111B80C2AA58
  122. 0D0119CE1095606D80118D7CF424157717E14B17012BAC712BA4F4C081E81C63
  123. FF154716E14816012BAC712B6EBF157112BAC712B1140E72A4F49081E66FF154
  124. 113680913612A133CA13312A6A6FAA980D28F2D760142164808C000102001210
  125. 21222D4200407405554540CCD207B1008FB976014313034E1B201428A2606481
  126. AF2169146CE129164AF0146D7AE53170D00E61969D0B64C4A6D5AFCCDBDA1643
  127. 470000CA81C81C81CC41031FB550714713514334E1B208A2606E0117EAF21433
  128. 07C281E81E81EC6D5174113E281CCC81C81C81C10011381CA64A6C103814D081
  129. 0C2E610AAEBA6EAEE31F30E62AF0B746600A74A6E59FA7C104133C013111B80C
  130. 2AA580D0119CE1095606660118D7AE1CF472156716FAE0A76550B640E6DAE815
  131. 5717F69DF15611140E72A160E6D155113680913612A133CA13312A619FAA980D
  132. 28F2D760142164808C8C10070C49464541344F470D9D20E16321C432D6E2010C
  133. 4D6E201085D6E201095D6E2010A5E163284E204074055545D6E2010A584E2040
  134. 7424C414D6E20109584E20407424C414D6E20108584E204074745445D6E2010C
  135. 49C2A2743A23013284E20407474544584E204074144444C42323FBF13FBF1D6E
  136. 20108584E20407474F4258DBF1D6E20109584E20407414E4448DBF1D6E2010A5
  137. 84E205074E414E4448DBF1EF53293632B2130E410060C494645444F460D9D20E
  138. 16321C432D6E2010C4D6E201085D6E201095D6E2010A5E16323C03284E204074
  139. 055545D6E2010A584E20407424C414D6E20109584E20407424C414D6E2010858
  140. 4E204074745445D6E2010C49C2A2743A23013284E20407474544584E20407414
  141. 4444C42323FBF13FBF1D6E20108584E20407474F4258DBF1D6E20109584E2040
  142. 7414E4448DBF1D6E2010A584E205074E414E4448DBF1DE032378A19B6328DBF1
  143. EF53293632B213056100604225F4D49444603392030000000000616105200080
  144. 426594359424C4548047A2084E2040C494645484E2050C49464541384E205014
  145. 24F4554584E20402494C44484E202074B4B213096000704234F4E464947470D9
  146. D20E16323392030000000000616108441293632B2130040006042459445C4546
  147. 0C2A2031000451474C6966656820002074B420E1B20FD4008300065000000000
  148. 0000000000000000000000000000000000000000000000000000000000000000
  149. 0000000000000000000000000000000000000000000000000000000000000000
  150. 0000000000000000000000000000000000000000000000000000000000000000
  151. 0000000000000000000000000000000000000000000000000000000000000000
  152. 0000000000000000000000000000000000000000000000000000000000000000
  153. 0000000000000000000000000000000000000000000000000000000000000000
  154. 0000000000000000000000000000000000000000000000000000000000000000
  155. 0000000000000000000000000000000000000000000000000000000000000000
  156. 0000000000000000000000000000000000000000000000000000000000000000
  157. 0000000000000000000000000000000000000000000000000000000000000000
  158. 0000000000000000000000000000000000000000000000000000000000000000
  159. 0000000000000000000000000000000000000000000000000000000000000000
  160. 0000000000000000000000000000000000000000000000000000000000000000
  161. 0000000000000000000000000000000000000000000000000000000000000000
  162. 0000000000000000000000000000000000000000000000000000000000000000
  163. 0000000000000000000000000004000000000000000000000A00000000000000
  164. 00000001304000000000000000600138780000000000000060013C3800000000
  165. 000000000A04208100000000000000040C308100000000000000000870000000
  166. 0000000000000040000000000000000000000000000000000000000000000000
  167. 0000000000CE400402494C44440E1B20F8700040008700038DFE700000000000
  168. 000000000000038DFE700000000000000000000000038D060000000000000000
  169. 00000000038D06000000000000000000000000038D0600000000000000000000
  170. 0000038D7E300000000000000000000000038D7E300000000000000000000000
  171. 038D06000000000000000000000000038D060000000000000000000000000FBD
  172. 0E7000000000000000000000000FBD0E70000000000000000000000000000000
  173. 0000000000000000000000000000000000000000000000000000000000000000
  174. 0000000000000000000870F11000083000040000000000000480400000044000
  175. 040000000000000231481BC2040EC3E52E00000000000A014015550400541411
  176. 10000000000231401555046E54EC0F1000000000048040155504415405110000
  177. 0000000870483154087E54F42E00000000000000000000000000000000000000
  178. 0000000000000000000000000000000000000000000000000000000000000000
  179. 0000000000000000000000000000000000000000000000000000000000000000
  180. 0000000000000000000000000000000000000000000000000000000000000000
  181. 0000000000000000000000000000000000000000000000000000000000000000
  182. 0000000000000000000000000000000000000000000000000000000000000000
  183. 0000000000000000000000000000000000000000000000000000000000000000
  184. 0000000000000000000000000000000000000000000000000000000000000000
  185. 0000000000000000000000000000000000000000000000000000000000000000
  186. 0000000000000000000000000000000000000000000000000000000000000000
  187. 0000000000000000000000000000000000000000000000000000000000000000
  188. 0000000000000000000000000000000000000000000000000000000000000000
  189. 0000000000000000000000000000000000000000000000000000000000000000
  190. 0000000000000000000000000000000000000000000000000000000000000000
  191. 0000000000000000000000000000000000000000000000000000000000000000
  192. 0000000000000000000000000000000000000000400000000000010000000000
  193. 000000A000000000008200000000000000001304000000004C00100000000006
  194. 001387800008104C0E1200000000060013C3800008104C0F02000000000000A0
  195. 420810000082090060000000000040C308100000010F00600000000000008700
  196. 000000000E100000000000000004000000000000100000000000000000000000
  197. 000000000000000000000000000000000000000000000000A700501424F45545
  198. 50D9D20E1632C2A20DE0009A0213939313024596D6D6027416E637B656A065F6
  199. 274656277616373756026373A0630353430225F64676165713F2A4CF76563786
  200. 5696D6A06427569602B6F607965627261627A0350756E64656E6027796C6C6B6
  201. F6D6D656E6A024C4A5025303635323132343A0E427021303532323635313839C
  202. 2A2485A1743A24A5A193632B21308210050C49464541350D9D20E163278BF176
  203. BA1634E1EFE0278BF18B9C1ED2A276BA1DBBF1ED2A276BA1DBBF1102E147A20E
  204. 4A20510000000000000000000E4A20510000000000000000000B21300F2E178B
  205. F1CB2A178BF1CB2A178BF1CB2A178BF1CB2A184E2070C49464541344F493632B
  206. 21303E00040C494645440D9D20E163278BF176BA1634E1EFE0278BF18B9C1ED2
  207. A276BA1DBBF1ED2A276BA1DBBF1102E147A20E4A20510000000000000000000E
  208. 4A20510000000000000000000B21300F2E178BF1CB2A178BF1CB2A178BF1CB2A
  209. 178BF1CB2A184E2060C494645444F493632B213088E2"
  210. @ BYTES: #2E88h 3988
  211.