From: Timm_Ganske@f.maus.de (Timm Ganske)
Newsgroups: comp.sys.hp48
Subject: Life development
Date: Sun, 13 Dec 92 03:37:00 GMT
Organization: MausNet (Mitglied im IN e.V.)
X-Gateway: MausGate/News 1.14D/hb

 This text describes the methods I used to implement life. Sorry for the
eventually bad english.
___________________________________________________________________________
Rules of life:
===========================================================================
1. One Generation is a rectengular grid, every element can be alive or dead.
2. The next generation is the same grid with the following changes:
 a) A cell which is alive survives only if it has 2 or 3 neighbours
 b) A cell which is dead is born to life if it has 3 neighbours

A neighbour of a cell is a cell which 'touches' the cell horizontally,
vertically or diagonally.
===========================================================================
 So if you want to calculate the next generation, you have to count the
neighbours and then make the changes. But if you count the neighbours one
cell at a time, it is going to be very slow. OK, how do you count? What are
your numbers? A cell has at maximum 8 neighbours who are alive, so you need
4 Bits to represent this. The topmost bit of these isn't interesting, because
if it is set, bit 1 (which counts 2) will be clear, and therefore the cell
will not live. A cell with 8 neighbours will die as on with 0 neighbours does.

 You need 3 bits to count the neighbours. Let's see, how can you store the
numbers? Why not organize them as the grid itself is organized?
 Of course the representation of that grid on a computer is a bitmap, on the
HP48 it is a graphics object. A pixel is set if the element is alive, and
clear if it is dead. Similar there is a GROB for every bit to count the
neighbours. And the neighbours are 8 Bitmaps, every one the grid, shifted a
little.

 How do you add a bitmap to a set of bitmaps, which is representing as much
binary numbers as the bitmap has pixels? Let's concentrate on adding one
bitmap to the bit0-bitmap.
 If a pixel is clear in both bitmaps, the pixel is cleared in the resulting
bitmap. If a pixel in exact one of the two bitmaps is set, the pixel in the
resulting bitmap is set. If a pixel is set in both bitmaps, the resulting
pixel is clear and - there is a carry!
 So there is a need to use a carry bitmap, which is given by an AND between
the two input bitmaps, and the resulting bitmap is calculated by XORing the
two input bitmaps. To make it clear:
___________________________________________________________________________
Adding two bitmaps:
===========================================================================
c(n+1) = b(n) AND input(n)           /* c = Carry */
b(n+1) = b(n) XOR input(n)           (* b = bit   */
input(0) is the original grid, input(n|n>0) is c(n)
===========================================================================
 Now let's see how to make the changes from one generation to the next. To make
it easy the KV-diagrams were invented:
___________________________________________________________________________
Decision if a cell in the next generation lives:
===========================================================================
  |-g | g | g |-g |
  | 0 | 0 |-0 |-0 |
--+---+---+---+---+    /*  g: Grid   */
 1|\/ |   |\/ |\/ |    /*  0: Bit 0  */
-2|/\ |   |/\ |/\ |    /*  1: Bit 1  */
--+---+---+---+---+    /*  2: Bit 2  */
-1|   |   |   |   |    /*  -: NOT    */
-2|   |   |   |   |
--+---+---+---+---+
-1|   |   |   |   |
 2|   |   |   |   |    /* The next generation grid is: */
--+---+---+---+---+    /* 1 and -1 and -(g and 0)      */
 1|   |   |   |   |
 2|   |   |   |   |
--+---+---+---+---+
===========================================================================
 So I hacked this in and - it worked! I rewrote the graphical bitoperations in
assembler to make it faster, RPL isn't that fast (as you know), and then
the life program was ready.

 Here it is again in the ASCd version, someone couldn't UUdecode my last
posting:
%%HP: T(1)A(R)F(.); @ tasc v2.52 file
"69A20FF714E1000000407424C41440CCD20290008FB976014313034E1B201428
A62616414216EAF1D83411000E181D80CF128AE980D0AF2815AC1CD441154716
F154716F6CEF1541136809136154112880DF8F2D760142164808C3A000407414
E44440CCD20DF0008FB976014313017414313134E1B201438A6B11428A631164
1741421478A26068A016E17EAF3D73411000E380CF12881FAEB80D0817AC3CF4
8315671537AF80E76151716F17F15671537AF80E76151716F17F68CF15611531
A980E16151113680913613780913715611531A980E16151112880DF8F2D76014
2164808CE01005074E414E44450CCD20901008FB976014313017414313134E1B
201438A6B11428A6311641741421478A26064B016E17EAF3D73411000E380CF1
2881FAEB80D0817AC3CF4E31567BFE1537AF80E76151716F17F1567BFE1537AF
80E76151716F17F62CF1561B9E1531A980E1615111368091361378091371561B
9E1531A980E16151112880DF8F2D760142164808CC1100407474F42540CCD20D
B0008FB976014313017414313114334E1B208A62214234E1B208A63116417414
21478A260616016E17EAF3D73401000E380CF128AEB80D0817AC3CF4C1156715
370E7A155716F17F64EF156115310E1A155112880DF8F2D760142164808CEC00
0407414444440CCD201E3008FB97601431301741471741431021741431031353
4E1B201428A6F41641438A6441741331211221331438A6D21741331221231331
438A66117414216E14717E8A260664313312312213314717E8A67E1331221211
3314717E8A60DAF3D73411000E380CF12881FAEB80D0817AC3CF5606F6115671
537AF80E761507AFABFE0E75BFD0E700E7E151717F13312112213315671537AF
80E761507AFABFE0E75BFD0E700E7E151717F13312212313315671537AF80E76
1507AFABFE0E75BFD0E700E7E151717F13312312113316F15671537AF80E7615
07AFABFE0E75BFD0E700E7E151717F13312112213315671537AF80E761507AFA
BFE0E75BFD0E700E7E151717F13312212313315671537AF80E761507AFABFE0E
75BFD0E700E7E151717F13312312113316F6E8E15611531A980E161501A9AB9E
0E15B9D0E100E1E151113780913713312112213315611531A980E161501A9AB9
E0E15B9D0E100E1E151113780913713312212313315611531A980E161501A9AB
9E0E15B9D0E100E1E151113780913713312312113313680913615611531A980E
161501A9AB9E0E15B9D0E100E1E151113312112213315611531A980E161501A9
AB9E0E15B9D0E100E1E151113312212313315611531A980E161501A9AB9E0E15
B9D0E100E1E151113312312113312880DF8F2D760142164808C2F30040747454
4540CCD20C32008FB976014313034E1B201428A26068F1AF2169146129164AF0
1421041643470000CA81C81C81CC41031FB550714713514334E1B208A26066A1
17EAF2143307C281E81E81EC6D5174113E281CCC81C81C81C10011381CA64A6C
103814D0810C2E610AAF0B6481011B8166600810A4E59FA7C97C50A7C1243470
0000EF68A861E2114660081CCE5AF10481B43401100CA133D21574A4E5803078
161554133E4812C6CA13311B157410B1701574A4E480C067FF13111B80C2AA58
0D0119CE1095606D80118D7CF424157717E14B17012BAC712BA4F4C081E81C63
FF154716E14816012BAC712B6EBF157112BAC712B1140E72A4F49081E66FF154
113680913612A133CA13312A6A6FAA980D28F2D760142164808C000102001210
21222D4200407405554540CCD207B1008FB976014313034E1B201428A2606481
AF2169146CE129164AF0146D7AE53170D00E61969D0B64C4A6D5AFCCDBDA1643
470000CA81C81C81CC41031FB550714713514334E1B208A2606E0117EAF21433
07C281E81E81EC6D5174113E281CCC81C81C81C10011381CA64A6C103814D081
0C2E610AAEBA6EAEE31F30E62AF0B746600A74A6E59FA7C104133C013111B80C
2AA580D0119CE1095606660118D7AE1CF472156716FAE0A76550B640E6DAE815
5717F69DF15611140E72A160E6D155113680913612A133CA13312A619FAA980D
28F2D760142164808C8C10070C49464541344F470D9D20E16321C432D6E2010C
4D6E201085D6E201095D6E2010A5E163284E204074055545D6E2010A584E2040
7424C414D6E20109584E20407424C414D6E20108584E204074745445D6E2010C
49C2A2743A23013284E20407474544584E204074144444C42323FBF13FBF1D6E
20108584E20407474F4258DBF1D6E20109584E20407414E4448DBF1D6E2010A5
84E205074E414E4448DBF1EF53293632B2130E410060C494645444F460D9D20E
16321C432D6E2010C4D6E201085D6E201095D6E2010A5E16323C03284E204074
055545D6E2010A584E20407424C414D6E20109584E20407424C414D6E2010858
4E204074745445D6E2010C49C2A2743A23013284E20407474544584E20407414
4444C42323FBF13FBF1D6E20108584E20407474F4258DBF1D6E20109584E2040
7414E4448DBF1D6E2010A584E205074E414E4448DBF1DE032378A19B6328DBF1
EF53293632B213056100604225F4D49444603392030000000000616105200080
426594359424C4548047A2084E2040C494645484E2050C49464541384E205014
24F4554584E20402494C44484E202074B4B213096000704234F4E464947470D9
D20E16323392030000000000616108441293632B2130040006042459445C4546
0C2A2031000451474C6966656820002074B420E1B20FD4008300065000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000004000000000000000000000A00000000000000
00000001304000000000000000600138780000000000000060013C3800000000
000000000A04208100000000000000040C308100000000000000000870000000
0000000000000040000000000000000000000000000000000000000000000000
0000000000CE400402494C44440E1B20F8700040008700038DFE700000000000
000000000000038DFE700000000000000000000000038D060000000000000000
00000000038D06000000000000000000000000038D0600000000000000000000
0000038D7E300000000000000000000000038D7E300000000000000000000000
038D06000000000000000000000000038D060000000000000000000000000FBD
0E7000000000000000000000000FBD0E70000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000870F11000083000040000000000000480400000044000
040000000000000231481BC2040EC3E52E00000000000A014015550400541411
10000000000231401555046E54EC0F1000000000048040155504415405110000
0000000870483154087E54F42E00000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000400000000000010000000000
000000A000000000008200000000000000001304000000004C00100000000006
001387800008104C0E1200000000060013C3800008104C0F02000000000000A0
420810000082090060000000000040C308100000010F00600000000000008700
000000000E100000000000000004000000000000100000000000000000000000
000000000000000000000000000000000000000000000000A700501424F45545
50D9D20E1632C2A20DE0009A0213939313024596D6D6027416E637B656A065F6
274656277616373756026373A0630353430225F64676165713F2A4CF76563786
5696D6A06427569602B6F607965627261627A0350756E64656E6027796C6C6B6
F6D6D656E6A024C4A5025303635323132343A0E427021303532323635313839C
2A2485A1743A24A5A193632B21308210050C49464541350D9D20E163278BF176
BA1634E1EFE0278BF18B9C1ED2A276BA1DBBF1ED2A276BA1DBBF1102E147A20E
4A20510000000000000000000E4A20510000000000000000000B21300F2E178B
F1CB2A178BF1CB2A178BF1CB2A178BF1CB2A184E2070C49464541344F493632B
21303E00040C494645440D9D20E163278BF176BA1634E1EFE0278BF18B9C1ED2
A276BA1DBBF1ED2A276BA1DBBF1102E147A20E4A20510000000000000000000E
4A20510000000000000000000B21300F2E178BF1CB2A178BF1CB2A178BF1CB2A
178BF1CB2A184E2060C494645444F493632B213088E2"
@ BYTES: #2E88h 3988
From: akcs.joehorn@hpcvbbs.cv.hp.com (Joseph K. Horn)
Date: Sun, 13 Dec 1992 12:40:04 GMT
Subject: Re: Complex Matrix?
Message-ID: <2b2b2d4d.2380.2comp.sys.hp48.1@hpcvbbs.cv.hp.com>