From: stirling@ozrout.uucp (Stirling Westrup)
Subject: Re: Life machines?
Organization: Andre P. Ozrout
Date: Thu, 23 Jul 1992 12:53:05 GMT

ts@cup.portal.com (Tim W Smith) writes
>> What's the highest rate achieved by a Life (dedicated or not)? (I don't
>> know a good metric for this, probably cells/sec is the best approximation
>> to one...)
>
>You have to distinguish between a fixed universe (e.g., N x M) or a
>variable universe (e.g., some data structure that just keeps track
>of live cells, and so only limits the universe to how big a coordinate
>you can store in the data structure).
>
>For a variable universe, I've got an N Log N algorithm, where N is the
>number of live cells.  Here's the straightforward way to do this:

[Nifty algorithm deleted]

I like your approach, but it never occured to me when I set out to write my
own variable-universe life program.  Mine worked by storing the life grid
as a quadtree, with the smallest leaf's being an 8x8 array of cells
described by 8 bytes.  Each node of the tree contains 4 node pointers, and
any state information that I may want to cache.  (I mark live nodes that
contain still life, and only recompute them at need).

I'm not sure what kind of speed I get from the program.  I'm running it on
a 33Mhz 386, and after roughly 7000 generations of the puffer train, I have
a life pattern with a population of about 20000 live cells, in a universe
2^13 cells on a side.  At this stage I get about 1 generation every 2 or 3
seconds.  Not very high on the life speed charts I'm afraid, even if you 
figure that the leaf chunking means processing roughly double the number of
live pixels.  Thats around 13 KCPS.  Anyway, I run out of memory if I try
to do anything bigger, so I'm in the middle of recoding my engine to use
packed quadtrees.  That way the 300K of structures that describe generation
7000 of the puffer train will fit in just under 40K.  I don't know what the
new speed will be like though, since I'm going to have to throw out all of
the old code.

The one thing I liked about the old code was the routine that calculated
a new life leaf from an old one.  It took an array of 10 16-bit values
(the old leaf with its neighbors edges added in) and did the calculation
for all of the pixels in a row in parallel.  For the curious, here it is:


/*
  lifgen - the life engine itself.  This fellow should be down-coded to
  assembly language in order to speed things up.
  He accepts a pointer to a LifLef to modify, and nine pointers to
  the data to use to build the new generation.
*/
Void lifgen
  ( LifLef *dst,
    N16 arr[10]
  )
  { Nat r;
    Static N16 p,n,t;
    Static N16 d0,d1;
    Static N16 b0,b1;
    Static N16 a0,a1;
    Static N16 c0,c1;
    Static N16 rc,r0,r1,r2;
    Static N16 tc,t0,t1,t2;
    Static N16 x,y;

    dst->flg = FLG_NUL;                     /* clear all flags */
    dst->pop = 0;                           /* clear population */

    for( r = 1; r < 9; r++ )
      {
          p = arr[r-1];                     /* previous row */
          t = arr[r];                       /* this row */
          n = arr[r+1];                     /* next row */
          if( p | t | n)
            {
              d0 = p ^ n;                   /* bit 0 of p+n, this column */
              d1 = p & n;                   /* bit 1 of p+n, this column */
              b0 = d0 ^ t;                  /* bit 0 of p+n+t, this column */
              b1 = d1 | (d0 & t);           /* bit 1 of p+n+t, this column */
              a0 = b0 << 1;                 /* bit 0 of p+n+t, prev column */
              a1 = b1 << 1;                 /* bit 1 of p+n+t, prev column */
              c0 = b0 >> 1;                 /* bit 0 of p+n+t, next column */
              c1 = b1 >> 1;                 /* bit 1 of p+n+t, next column */
              rc = a0 & c0;                 /* carry from r0 */
              r0 = a0 ^ c0;                 /* bit 0 of sum of side columns */
              r1 = a1 ^ c1 ^ rc;            /* bit 1 of sum of side columns */
              r2 = (a1 & c1) | ((a1|c1) & rc);  /* bit 2 of sum */
              tc = r0 & d0;                 /* carry from t0 */
              t0 = r0 ^ d0;                 /* bit 0 of total neighbors */
              t1 = r1 ^ d1 ^ tc;            /* bit 1 of total neighbors */
              t2 = r2  ^ ((r1 & d1) | ((r1|d1) & tc)); /* bit 2 of total */
              x = (t | t0) & t1 & ~t2;      /* the answer for this row */
            }
          else
            x = 0;
          if( (x ^ t) & 0x1FE )
            dst->flg |= FLG_CHG;            /* life pattern changed */
          y = (x>>1) & 0xFF;
          if( y )
            dst->flg |= FLG_LIV;            /* leaf is still alive */
          dst->pop += bitcnt[y];            /* add population of this row */
          dst->row[r-1] = y;
      }
  }


Anyway, I'm willing to give the source for the old version to anyone who's
interested, but its not much more than a bare engine.  A user interface
would be nice, and porting it to something other than Turbo C's BGI should
be possible without too much effort.

-- 
||    BUNGEE SIDEWAYS!                              o   )))
||                                                 /-- ///
|P~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\_  \\\      __ -_
||    stirling@ozrout.uucp                                 ((( (_)T(_)
Newsgroups: alt.folklore.computers