demos/life/game.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        game.cpp
   3 // Purpose:     Life! game logic
   4 // Author:      Guillermo Rodriguez Garcia, <guille@iies.es>
   5 // Modified by:
   6 // Created:     Jan/2000
   7 // RCS-ID:      $Id$
   8 // Copyright:   (c) 2000, Guillermo Rodriguez Garcia
   9 // Licence:     wxWindows licence
  10 /////////////////////////////////////////////////////////////////////////////
  11
  12 // ==========================================================================
  13 // headers, declarations, constants
  14 // ==========================================================================
  15
  16 #ifdef __GNUG__
  17     #pragma implementation "game.h"
  18 #endif
  19
  20 #include "wx/log.h"
  21 #include "game.h"
  22
  23 #include <stdlib.h>           // for abort
  24 #include <string.h>           // for memset
  25
  26
  27 #define ARRAYSIZE  1024      // size of the static arrays for BeginFind & co.
  28 #define ALLOCBOXES 16         // number of cellboxes to alloc at once
  29
  30 // ==========================================================================
  31 // CellBox
  32 // ==========================================================================
  33
  34 #define HASH(x, y) (((x >> 3) & 0x7f) << 7) + ((y >> 3) & 0x7f)
  35 #define HASHSIZE   32768
  36 #define MAXDEAD    8
  37
  38
  39 class CellBox
  40 {
  41 public:
  42     // members
  43     inline bool IsAlive(int dx, int dy) const;
  44     inline bool SetCell(int dx, int dy, bool alive);
  45
  46     // attributes
  47     wxInt32   m_x, m_y;                     // position in universe
  48     wxUint32  m_live1, m_live2;             // alive cells (1 bit per cell)
  49     wxUint32  m_old1, m_old2;               // old values for m_live1, 2
  50     wxUint32  m_on[8];                      // neighbouring info
  51     wxUint32  m_dead;                       // been dead for n generations
  52     CellBox  *m_up, *m_dn, *m_lf, *m_rt;    // neighbour CellBoxes
  53     CellBox  *m_prev, *m_next;              // in linked list
  54     CellBox  *m_hprev, *m_hnext;            // in hash table
  55 };
  56
  57
  58 // IsAlive:
  59 //  Returns whether cell dx, dy in this box is alive
  60 //
  61 bool CellBox::IsAlive(int dx, int dy) const
  62 {
  63     if (dy > 3)
  64         return (m_live2 & 1 << ((dy - 4) * 8 + dx));
  65     else
  66         return (m_live1 & 1 << ((dy) * 8 + dx));
  67 }
  68
  69 // SetCell:
  70 //  Sets cell dx, dy in this box to 'alive', returns TRUE if
  71 //  the previous value was different, FALSE if it was the same.
  72 //
  73 bool CellBox::SetCell(int dx, int dy, bool alive)
  74 {
  75     if (IsAlive(dx, dy) != alive)
  76     {
  77        if (dy > 3)
  78            m_live2 ^= 1 << ((dy - 4) * 8 + dx);
  79        else
  80            m_live1 ^= 1 << ((dy) * 8 + dx);
  81
  82        // reset this here to avoid updating problems
  83        m_dead = 0;
  84
  85        return TRUE;
  86     }
  87     else
  88        return FALSE;
  89 }
  90
  91
  92 // ==========================================================================
  93 // Life
  94 // ==========================================================================
  95
  96 // --------------------------------------------------------------------------
  97 // Ctor and dtor
  98 // --------------------------------------------------------------------------
  99
 100 Life::Life()
 101 {
 102     m_numcells  = 0;
 103     m_boxes     = new CellBox *[HASHSIZE];
 104     m_head      = NULL;
 105     m_available = NULL;
 106     for (int i = 0; i < HASHSIZE; i++)
 107         m_boxes[i] = NULL;
 108
 109     m_cells     = new Cell[ARRAYSIZE];
 110     m_ncells    = 0;
 111     m_findmore  = FALSE;
 112     m_changed   = FALSE;
 113 }
 114
 115 Life::~Life()
 116 {
 117     Clear();
 118
 119     delete[] m_boxes;
 120     delete[] m_cells;
 121 }
 122
 123 // Clear:
 124 //  Clears the board, freeing all storage.
 125 //
 126 void Life::Clear()
 127 {
 128     CellBox *c, *nc;
 129
 130     m_numcells = 0;
 131
 132     // clear the hash table pointers
 133     for (int i = 0; i < HASHSIZE; i++)
 134         m_boxes[i] = NULL;
 135
 136     // free used boxes
 137     c = m_head;
 138     while (c)
 139     {
 140         nc = c->m_next;
 141         delete c;
 142         c = nc;
 143     }
 144     m_head = NULL;
 145
 146     // free available boxes
 147     c = m_available;
 148     while (c)
 149     {
 150         nc = c->m_next;
 151         delete c;
 152         c = nc;
 153     }
 154     m_available = NULL;
 155 }
 156
 157 // --------------------------------------------------------------------------
 158 // Test and set individual cells
 159 // --------------------------------------------------------------------------
 160
 161 // IsAlive:
 162 //  Returns whether cell (x, y) is alive.
 163 //
 164 bool Life::IsAlive(wxInt32 x, wxInt32 y)
 165 {
 166     CellBox *c = LinkBox(x, y, FALSE);
 167
 168     return (c && c->IsAlive( x - c->m_x, y - c->m_y ));
 169 }
 170
 171 // SetCell:
 172 //  Sets or clears cell (x, y), according to the 'alive' param.
 173 //
 174 void Life::SetCell(wxInt32 x, wxInt32 y, bool alive)
 175 {
 176     CellBox *c  = LinkBox(x, y);
 177     wxUint32 dx = x - c->m_x;
 178     wxUint32 dy = y - c->m_y;
 179
 180     if (c->SetCell(dx, dy, alive))
 181     {
 182         if (alive)
 183             m_numcells++;
 184         else
 185             m_numcells--;
 186     }
 187 }
 188
 189 void Life::SetShape(const LifeShape& shape)
 190 {
 191     char *p = shape.m_data;
 192
 193     int i0 = -(shape.m_width / 2);
 194     int j0 = -(shape.m_height / 2);
 195     int i1 = i0 + shape.m_width - 1;
 196     int j1 = j0 + shape.m_height - 1;
 197
 198     Clear();
 199     for (int j = j0; j <= j1; j++)
 200         for (int i = i0; i <= i1; i++)
 201             SetCell(i, j, *(p++) == '*');
 202 }
 203
 204 // --------------------------------------------------------------------------
 205 // Cellbox management functions
 206 // --------------------------------------------------------------------------
 207
 208 // CreateBox:
 209 //  Creates a new box in x, y, either taking it from the list
 210 //  of available boxes, or allocating a new one.
 211 //
 212 CellBox* Life::CreateBox(wxInt32 x, wxInt32 y, wxUint32 hv)
 213 {
 214     CellBox *c;
 215
 216     // if there are no available boxes, alloc a few more
 217     if (!m_available)
 218         for (int i = 1; i <= ALLOCBOXES; i++)
 219         {
 220             c = new CellBox();
 221
 222             if (!c)
 223             {
 224                 // TODO: handle memory errors. Note that right now, if we
 225                 // couldn't allocate at least one cellbox, we will crash
 226                 // before leaving CreateBox(). Probably we should try to
 227                 // allocate some boxes *before* the m_available list goes
 228                 // empty, so that we have a margin to handle errors
 229                 // gracefully.
 230                 wxLogFatalError(_("Out of memory! Aborting..."));
 231
 232                 // the above call should abort, but it doesn't :-?
 233                 abort();
 234
 235                 break;
 236             }
 237
 238             c->m_next = m_available;
 239             m_available = c;
 240         }
 241
 242     // take a cellbox from the list of available boxes
 243     c = m_available;
 244     m_available = c->m_next;
 245
 246     // reset everything
 247     memset((void *) c, 0, sizeof(CellBox));
 248     c->m_x = x;
 249     c->m_y = y;
 250
 251     // insert c in the list
 252     c->m_next = m_head;
 253     m_head = c;
 254     if (c->m_next) c->m_next->m_prev = c;
 255
 256     // insert c in the hash table
 257     c->m_hnext = m_boxes[hv];
 258     m_boxes[hv] = c;
 259     if (c->m_hnext) c->m_hnext->m_hprev = c;
 260
 261     return c;
 262 }
 263
 264 // LinkBox:
 265 //  Returns a pointer to the box (x, y); if it didn't exist yet,
 266 //  it returns NULL or creates a new one, depending on the 'create'
 267 //  parameter.
 268 //
 269 CellBox* Life::LinkBox(wxInt32 x, wxInt32 y, bool create)
 270 {
 271     wxUint32 hv;
 272     CellBox *c;
 273
 274     x &= 0xfffffff8;
 275     y &= 0xfffffff8;
 276     hv = HASH(x, y);
 277
 278     // search in the hash table
 279     for (c = m_boxes[hv]; c; c = c->m_hnext)
 280         if ((c->m_x == x) && (c->m_y == y)) return c;
 281
 282     // if not found, and (create == TRUE), create a new one
 283     return create? CreateBox(x, y, hv) : NULL;
 284 }
 285
 286 // KillBox:
 287 //  Removes this box from the list and the hash table and
 288 //  puts it in the list of available boxes.
 289 //
 290 void Life::KillBox(CellBox *c)
 291 {
 292     wxUint32 hv = HASH(c->m_x, c->m_y);
 293
 294     // remove from the list
 295     if (c != m_head)
 296         c->m_prev->m_next = c->m_next;
 297     else
 298         m_head = c->m_next;
 299
 300     // remove from the hash table
 301     if (c != m_boxes[hv])
 302         c->m_hprev->m_hnext = c->m_hnext;
 303     else
 304         m_boxes[hv] = c->m_hnext;
 305
 306     // update neighbours
 307     if (c->m_next) c->m_next->m_prev = c->m_prev;
 308     if (c->m_hnext) c->m_hnext->m_hprev = c->m_hprev;
 309     if (c->m_up) c->m_up->m_dn = NULL;
 310     if (c->m_dn) c->m_dn->m_up = NULL;
 311     if (c->m_lf) c->m_lf->m_rt = NULL;
 312     if (c->m_rt) c->m_rt->m_lf = NULL;
 313
 314     // append to the list of available boxes
 315     c->m_next = m_available;
 316     m_available = c;
 317 }
 318
 319 // --------------------------------------------------------------------------
 320 // FindMore & co.
 321 // --------------------------------------------------------------------------
 322
 323 // Post eight cells to the cell arrays (changed cells only)
 324 void Life::DoLine(wxInt32 i, wxInt32 j, wxUint32 live, wxUint32 old)
 325 {
 326     wxUint32 diff = (live ^ old) & 0x000000ff;
 327
 328     if (!diff) return;
 329
 330     for (wxInt32 k = 8; k; k--, i++)
 331     {
 332         if (diff & 0x01)
 333         {
 334             m_cells[m_ncells].i = i;
 335             m_cells[m_ncells].j = j;
 336             m_ncells++;
 337         }
 338         diff >>= 1;
 339         live >>= 1;
 340     }
 341 }
 342
 343 // Post eight cells to the cell arrays (alive cells only)
 344 void Life::DoLine(wxInt32 i, wxInt32 j, wxUint32 live)
 345 {
 346     if (! (live & 0x000000ff)) return;
 347
 348     for (wxInt32 k = 8; k; k--, i++)
 349     {
 350         if (live & 0x01)
 351         {
 352             m_cells[m_ncells].i = i;
 353             m_cells[m_ncells].j = j;
 354             m_ncells++;
 355         }
 356         live >>= 1;
 357     }
 358 }
 359
 360 void Life::BeginFind(wxInt32 i0, wxInt32 j0, wxInt32 i1, wxInt32 j1, bool changed)
 361 {
 362     // TODO: optimize for the case where the maximum number of
 363     // cellboxes that fit in the specified viewport is smaller
 364     // than the current total of boxes; iterating over the list
 365     // should then be faster than searching in the hash table.
 366
 367     m_i0 = m_i = i0 & 0xfffffff8;
 368     m_j0 = m_j = j0 & 0xfffffff8;
 369     m_i1 = (i1 + 7) & 0xfffffff8;
 370     m_j1 = (j1 + 7) & 0xfffffff8;
 371
 372     m_findmore = TRUE;
 373     m_changed = changed;
 374 }
 375
 376 bool Life::FindMore(Cell *cells[], size_t *ncells)
 377 {
 378     CellBox *c;
 379     *cells = m_cells;
 380     m_ncells = 0;
 381
 382     if (m_changed)
 383     {
 384         for ( ; m_j <= m_j1; m_j += 8, m_i = m_i0)
 385             for ( ; m_i <= m_i1; m_i += 8)
 386             {
 387                 if ((c = LinkBox(m_i, m_j, FALSE)) == NULL)
 388                     continue;
 389
 390                 // check whether there is enough space left in the array
 391                 if (m_ncells > (ARRAYSIZE - 64))
 392                 {
 393                     *ncells = m_ncells;
 394                     return FALSE;
 395                 }
 396
 397                 DoLine(m_i, m_j    , c->m_live1,       c->m_old1      );
 398                 DoLine(m_i, m_j + 1, c->m_live1 >> 8,  c->m_old1 >> 8 );
 399                 DoLine(m_i, m_j + 2, c->m_live1 >> 16, c->m_old1 >> 16);
 400                 DoLine(m_i, m_j + 3, c->m_live1 >> 24, c->m_old1 >> 24);
 401                 DoLine(m_i, m_j + 4, c->m_live2,       c->m_old2      );
 402                 DoLine(m_i, m_j + 5, c->m_live2 >> 8,  c->m_old2 >> 8 );
 403                 DoLine(m_i, m_j + 6, c->m_live2 >> 16, c->m_old2 >> 16);
 404                 DoLine(m_i, m_j + 7, c->m_live2 >> 24, c->m_old2 >> 24);
 405             }
 406     }
 407     else
 408     {
 409         for ( ; m_j <= m_j1; m_j += 8, m_i = m_i0)
 410             for ( ; m_i <= m_i1; m_i += 8)
 411             {
 412                 if ((c = LinkBox(m_i, m_j, FALSE)) == NULL)
 413                     continue;
 414
 415                 // check whether there is enough space left in the array
 416                 if (m_ncells > (ARRAYSIZE - 64))
 417                 {
 418                     *ncells = m_ncells;
 419                     return FALSE;
 420                 }
 421
 422                 DoLine(m_i, m_j    , c->m_live1      );
 423                 DoLine(m_i, m_j + 1, c->m_live1 >> 8 );
 424                 DoLine(m_i, m_j + 2, c->m_live1 >> 16);
 425                 DoLine(m_i, m_j + 3, c->m_live1 >> 24);
 426                 DoLine(m_i, m_j + 4, c->m_live2      );
 427                 DoLine(m_i, m_j + 5, c->m_live2 >> 8 );
 428                 DoLine(m_i, m_j + 6, c->m_live2 >> 16);
 429                 DoLine(m_i, m_j + 7, c->m_live2 >> 24);
 430             }
 431     }
 432
 433     *ncells = m_ncells;
 434     m_findmore = FALSE;
 435     return TRUE;
 436 }
 437
 438 // --------------------------------------------------------------------------
 439 // Evolution engine
 440 // --------------------------------------------------------------------------
 441
 442 extern int g_tab1[];
 443 extern int g_tab2[];
 444
 445 // NextTic:
 446 //  Advance one step in evolution :-)
 447 //
 448 bool Life::NextTic()
 449 {
 450     CellBox  *c, *up, *dn, *lf, *rt;
 451     wxUint32 t1, t2, t3, t4;
 452     bool     changed = FALSE;
 453
 454     m_numcells = 0;
 455
 456     // Stage 1:
 457     // Compute neighbours of each cell
 458     //
 459     // WARNING: unrolled loops and lengthy code follows!
 460     //
 461     c = m_head;
 462
 463     while (c)
 464     {
 465         if (! (c->m_live1 || c->m_live2))
 466         {
 467             c = c->m_next;
 468             continue;
 469         }
 470         up = c->m_up;
 471         dn = c->m_dn;
 472         lf = c->m_lf;
 473         rt = c->m_rt;
 474
 475         // up
 476         t1 = c->m_live1 & 0x000000ff;
 477         if (t1)
 478         {
 479             if (!up)
 480             {
 481                 up = LinkBox(c->m_x, c->m_y - 8);
 482                 up->m_dn = c;
 483             }
 484             t2 = g_tab1[t1];
 485             up->m_on[7] += t2;
 486             c->m_on[1] += t2;
 487             c->m_on[0] += g_tab2[t1];
 488         }
 489
 490         // down
 491         t1 = (c->m_live2 & 0xff000000) >> 24;
 492         if (t1)
 493         {
 494             if (!dn)
 495             {
 496                 dn = LinkBox(c->m_x, c->m_y + 8);
 497                 dn->m_up = c;
 498             }
 499             t2 = g_tab1[t1];
 500             dn->m_on[0] += t2;
 501             c->m_on[6] += t2;
 502             c->m_on[7] += g_tab2[t1];
 503         }
 504
 505         t1 = c->m_live1;
 506         t2 = c->m_live2;
 507
 508         // left
 509         if (t1 & 0x01010101)
 510         {
 511             if (!lf)
 512             {
 513                 lf = LinkBox(c->m_x - 8, c->m_y);
 514                 lf->m_rt = c;
 515             }
 516             if (t1 & 0x00000001)
 517             {
 518                if (!lf->m_up)
 519                {
 520                    lf->m_up = LinkBox(c->m_x - 8, c->m_y - 8);
 521                    lf->m_up->m_dn = lf;
 522                }
 523                lf->m_up->m_on[7] += 0x10000000;
 524                lf->m_on[0] += 0x10000000;
 525                lf->m_on[1] += 0x10000000;
 526             }
 527             if (t1 & 0x00000100)
 528             {
 529                lf->m_on[0] += 0x10000000;
 530                lf->m_on[1] += 0x10000000;
 531                lf->m_on[2] += 0x10000000;
 532             }
 533             if (t1 & 0x00010000)
 534             {
 535                lf->m_on[1] += 0x10000000;
 536                lf->m_on[2] += 0x10000000;
 537                lf->m_on[3] += 0x10000000;
 538             }
 539             if (t1 & 0x01000000)
 540             {
 541                lf->m_on[2] += 0x10000000;
 542                lf->m_on[3] += 0x10000000;
 543                lf->m_on[4] += 0x10000000;
 544             }
 545         }
 546         if (t2 & 0x01010101)
 547         {
 548             if (!lf)
 549             {
 550                 lf = LinkBox(c->m_x - 8, c->m_y);
 551                 lf->m_rt = c;
 552             }
 553             if (t2 & 0x00000001)
 554             {
 555                lf->m_on[3] += 0x10000000;
 556                lf->m_on[4] += 0x10000000;
 557                lf->m_on[5] += 0x10000000;
 558             }
 559             if (t2 & 0x00000100)
 560             {
 561                lf->m_on[4] += 0x10000000;
 562                lf->m_on[5] += 0x10000000;
 563                lf->m_on[6] += 0x10000000;
 564             }
 565             if (t2 & 0x00010000)
 566             {
 567                lf->m_on[5] += 0x10000000;
 568                lf->m_on[6] += 0x10000000;
 569                lf->m_on[7] += 0x10000000;
 570             }
 571             if (t2 & 0x01000000)
 572             {
 573                if (!lf->m_dn)
 574                {
 575                    lf->m_dn = LinkBox(c->m_x - 8, c->m_y + 8);
 576                    lf->m_dn->m_up = lf;
 577                }
 578                lf->m_on[6] += 0x10000000;
 579                lf->m_on[7] += 0x10000000;
 580                lf->m_dn->m_on[0] += 0x10000000;
 581             }
 582         }
 583
 584         // right
 585         if (t1 & 0x80808080)
 586         {
 587             if (!rt)
 588             {
 589                 rt = LinkBox(c->m_x + 8, c->m_y);
 590                 rt->m_lf = c;
 591             }
 592             if (t1 & 0x00000080)
 593             {
 594                if (!rt->m_up)
 595                {
 596                    rt->m_up = LinkBox(c->m_x + 8, c->m_y - 8);
 597                    rt->m_up->m_dn = rt;
 598                }
 599                rt->m_up->m_on[7] += 0x00000001;
 600                rt->m_on[0] += 0x00000001;
 601                rt->m_on[1] += 0x00000001;
 602             }
 603             if (t1 & 0x00008000)
 604             {
 605                rt->m_on[0] += 0x00000001;
 606                rt->m_on[1] += 0x00000001;
 607                rt->m_on[2] += 0x00000001;
 608             }
 609             if (t1 & 0x00800000)
 610             {
 611                rt->m_on[1] += 0x00000001;
 612                rt->m_on[2] += 0x00000001;
 613                rt->m_on[3] += 0x00000001;
 614             }
 615             if (t1 & 0x80000000)
 616             {
 617                rt->m_on[2] += 0x00000001;
 618                rt->m_on[3] += 0x00000001;
 619                rt->m_on[4] += 0x00000001;
 620             }
 621         }
 622         if (t2 & 0x80808080)
 623         {
 624             if (!rt)
 625             {
 626                 rt = LinkBox(c->m_x + 8, c->m_y);
 627                 rt->m_lf = c;
 628             }
 629             if (t2 & 0x00000080)
 630             {
 631                rt->m_on[3] += 0x00000001;
 632                rt->m_on[4] += 0x00000001;
 633                rt->m_on[5] += 0x00000001;
 634             }
 635             if (t2 & 0x00008000)
 636             {
 637                rt->m_on[4] += 0x00000001;
 638                rt->m_on[5] += 0x00000001;
 639                rt->m_on[6] += 0x00000001;
 640             }
 641             if (t2 & 0x00800000)
 642             {
 643                rt->m_on[5] += 0x00000001;
 644                rt->m_on[6] += 0x00000001;
 645                rt->m_on[7] += 0x00000001;
 646             }
 647             if (t2 & 0x80000000)
 648             {
 649                if (!rt->m_dn)
 650                {
 651                    rt->m_dn = LinkBox(c->m_x + 8, c->m_y + 8);
 652                    rt->m_dn->m_up = rt;
 653                }
 654                rt->m_on[6] += 0x00000001;
 655                rt->m_on[7] += 0x00000001;
 656                rt->m_dn->m_on[0] += 0x00000001;
 657             }
 658         }
 659
 660         // inner cells
 661         for (int i = 1; i <= 3; i++)
 662         {
 663             t1 = ((c->m_live1) >> (i * 8)) & 0x000000ff;
 664             if (t1)
 665             {
 666                 c->m_on[i - 1] += g_tab1[t1];
 667                 c->m_on[i    ] += g_tab2[t1];
 668                 c->m_on[i + 1] += g_tab1[t1];
 669             }
 670         }
 671         for (int i = 0; i <= 2; i++)
 672         {
 673             t1 = ((c->m_live2) >> (i * 8)) & 0x000000ff;
 674             if (t1)
 675             {
 676                 c->m_on[i + 3] += g_tab1[t1];
 677                 c->m_on[i + 4] += g_tab2[t1];
 678                 c->m_on[i + 5] += g_tab1[t1];
 679             }
 680         }
 681
 682         c->m_up = up;
 683         c->m_dn = dn;
 684         c->m_lf = lf;
 685         c->m_rt = rt;
 686         c = c->m_next;
 687     }
 688
 689     // Stage 2:
 690     // Stabilize
 691     //
 692     // WARNING: to be optimized and unrolled soon.
 693     //
 694     c = m_head;
 695
 696     while (c)
 697     {
 698         t1 = c->m_live1;
 699         c->m_old1 = t1;
 700         t2 = 0;
 701         for (int i = 0; i <= 3; i++)
 702         {
 703             t3 = c->m_on[i];
 704             if (!t3)
 705             {
 706                 t1 >>= 8;
 707                 t2 >>= 8;
 708                 continue;
 709             }
 710
 711             for (int j = 0; j < 8; j++)
 712             {
 713                 t2 >>= 1;
 714                 t4 = t3 & 0x0000000f;
 715
 716                 if ((t4 == 3) || ((t4 == 2) && (t1 & 0x00000001)))
 717                 {
 718                     t2 |= 0x80000000;
 719                     m_numcells++;
 720                 }
 721
 722                 t3 >>= 4;
 723                 t1 >>= 1;
 724             }
 725             c->m_on[i] = 0;
 726         }
 727         c->m_live1 = t2;
 728
 729         t1 = c->m_live2;
 730         c->m_old2 = t1;
 731         t2 = 0;
 732         for (int i = 4; i <= 7; i++)
 733         {
 734             t3 = c->m_on[i];
 735             if (!t3)
 736             {
 737                 t1 >>= 8;
 738                 t2 >>= 8;
 739                 continue;
 740             }
 741
 742             for (int j = 0; j < 8; j++)
 743             {
 744                 t2 >>= 1;
 745                 t4 = t3 & 0x0000000f;
 746
 747                 if ((t4 == 3) || ((t4 == 2) && (t1 & 0x00000001)))
 748                 {
 749                     t2 |= 0x80000000;
 750                     m_numcells++;
 751                 }
 752
 753                 t3 >>= 4;
 754                 t1 >>= 1;
 755             }
 756             c->m_on[i] = 0;
 757         }
 758         c->m_live2 = t2;
 759
 760         // keep track of changes
 761         changed |= ((c->m_live1 ^ c->m_old1) || (c->m_live2 ^ c->m_old2));
 762
 763         // mark, and discard if necessary, dead boxes
 764         if (c->m_live1 || c->m_live2)
 765         {
 766             c->m_dead = 0;
 767             c = c->m_next;
 768         }
 769         else
 770         {
 771             CellBox *aux = c->m_next;
 772             if (c->m_dead++ > MAXDEAD)
 773                KillBox(c);
 774
 775             c = aux;
 776         }
 777     }
 778
 779     return changed;
 780 }
 781
 782 // --------------------------------------------------------------------------
 783 // Lookup tables - these will be generated on-the-fly soon.
 784 // --------------------------------------------------------------------------
 785
 786 // This table converts from bits (like in live1, live2) to number
 787 // of neighbors for each cell in the upper or lower row.
 788 //
 789 int g_tab1[]=
 790 {
 791     0x00000000,
 792     0x00000011,
 793     0x00000111,
 794     0x00000122,
 795     0x00001110,
 796     0x00001121,
 797     0x00001221,
 798     0x00001232,
 799     0x00011100,
 800     0x00011111,
 801     0x00011211,
 802     0x00011222,
 803     0x00012210,
 804     0x00012221,
 805     0x00012321,
 806     0x00012332,
 807     0x00111000,
 808     0x00111011,
 809     0x00111111,
 810     0x00111122,
 811     0x00112110,
 812     0x00112121,
 813     0x00112221,
 814     0x00112232,
 815     0x00122100,
 816     0x00122111,
 817     0x00122211,
 818     0x00122222,
 819     0x00123210,
 820     0x00123221,
 821     0x00123321,
 822     0x00123332,
 823     0x01110000,
 824     0x01110011,
 825     0x01110111,
 826     0x01110122,
 827     0x01111110,
 828     0x01111121,
 829     0x01111221,
 830     0x01111232,
 831     0x01121100,
 832     0x01121111,
 833     0x01121211,
 834     0x01121222,
 835     0x01122210,
 836     0x01122221,
 837     0x01122321,
 838     0x01122332,
 839     0x01221000,
 840     0x01221011,
 841     0x01221111,
 842     0x01221122,
 843     0x01222110,
 844     0x01222121,
 845     0x01222221,
 846     0x01222232,
 847     0x01232100,
 848     0x01232111,
 849     0x01232211,
 850     0x01232222,
 851     0x01233210,
 852     0x01233221,
 853     0x01233321,
 854     0x01233332,
 855     0x11100000,
 856     0x11100011,
 857     0x11100111,
 858     0x11100122,
 859     0x11101110,
 860     0x11101121,
 861     0x11101221,
 862     0x11101232,
 863     0x11111100,
 864     0x11111111,
 865     0x11111211,
 866     0x11111222,
 867     0x11112210,
 868     0x11112221,
 869     0x11112321,
 870     0x11112332,
 871     0x11211000,
 872     0x11211011,
 873     0x11211111,
 874     0x11211122,
 875     0x11212110,
 876     0x11212121,
 877     0x11212221,
 878     0x11212232,
 879     0x11222100,
 880     0x11222111,
 881     0x11222211,
 882     0x11222222,
 883     0x11223210,
 884     0x11223221,
 885     0x11223321,
 886     0x11223332,
 887     0x12210000,
 888     0x12210011,
 889     0x12210111,
 890     0x12210122,
 891     0x12211110,
 892     0x12211121,
 893     0x12211221,
 894     0x12211232,
 895     0x12221100,
 896     0x12221111,
 897     0x12221211,
 898     0x12221222,
 899     0x12222210,
 900     0x12222221,
 901     0x12222321,
 902     0x12222332,
 903     0x12321000,
 904     0x12321011,
 905     0x12321111,
 906     0x12321122,
 907     0x12322110,
 908     0x12322121,
 909     0x12322221,
 910     0x12322232,
 911     0x12332100,
 912     0x12332111,
 913     0x12332211,
 914     0x12332222,
 915     0x12333210,
 916     0x12333221,
 917     0x12333321,
 918     0x12333332,
 919     0x11000000,
 920     0x11000011,
 921     0x11000111,
 922     0x11000122,
 923     0x11001110,
 924     0x11001121,
 925     0x11001221,
 926     0x11001232,
 927     0x11011100,
 928     0x11011111,
 929     0x11011211,
 930     0x11011222,
 931     0x11012210,
 932     0x11012221,
 933     0x11012321,
 934     0x11012332,
 935     0x11111000,
 936     0x11111011,
 937     0x11111111,
 938     0x11111122,
 939     0x11112110,
 940     0x11112121,
 941     0x11112221,
 942     0x11112232,
 943     0x11122100,
 944     0x11122111,
 945     0x11122211,
 946     0x11122222,
 947     0x11123210,
 948     0x11123221,
 949     0x11123321,
 950     0x11123332,
 951     0x12110000,
 952     0x12110011,
 953     0x12110111,
 954     0x12110122,
 955     0x12111110,
 956     0x12111121,
 957     0x12111221,
 958     0x12111232,
 959     0x12121100,
 960     0x12121111,
 961     0x12121211,
 962     0x12121222,
 963     0x12122210,
 964     0x12122221,
 965     0x12122321,
 966     0x12122332,
 967     0x12221000,
 968     0x12221011,
 969     0x12221111,
 970     0x12221122,
 971     0x12222110,
 972     0x12222121,
 973     0x12222221,
 974     0x12222232,
 975     0x12232100,
 976     0x12232111,
 977     0x12232211,
 978     0x12232222,
 979     0x12233210,
 980     0x12233221,
 981     0x12233321,
 982     0x12233332,
 983     0x22100000,
 984     0x22100011,
 985     0x22100111,
 986     0x22100122,
 987     0x22101110,
 988     0x22101121,
 989     0x22101221,
 990     0x22101232,
 991     0x22111100,
 992     0x22111111,
 993     0x22111211,
 994     0x22111222,
 995     0x22112210,
 996     0x22112221,
 997     0x22112321,
 998     0x22112332,
 999     0x22211000,
1000     0x22211011,
1001     0x22211111,
1002     0x22211122,
1003     0x22212110,
1004     0x22212121,
1005     0x22212221,
1006     0x22212232,
1007     0x22222100,
1008     0x22222111,
1009     0x22222211,
1010     0x22222222,
1011     0x22223210,
1012     0x22223221,
1013     0x22223321,
1014     0x22223332,
1015     0x23210000,
1016     0x23210011,
1017     0x23210111,
1018     0x23210122,
1019     0x23211110,
1020     0x23211121,
1021     0x23211221,
1022     0x23211232,
1023     0x23221100,
1024     0x23221111,
1025     0x23221211,
1026     0x23221222,
1027     0x23222210,
1028     0x23222221,
1029     0x23222321,
1030     0x23222332,
1031     0x23321000,
1032     0x23321011,
1033     0x23321111,
1034     0x23321122,
1035     0x23322110,
1036     0x23322121,
1037     0x23322221,
1038     0x23322232,
1039     0x23332100,
1040     0x23332111,
1041     0x23332211,
1042     0x23332222,
1043     0x23333210,
1044     0x23333221,
1045     0x23333321,
1046     0x23333332
1047 };
1048
1049 // This table converts from bits (like in live1, live2) to number
1050 // of neighbors for each cell in the same row (excluding ourselves)
1051 //
1052 int g_tab2[]=
1053 {
1054     0x00000000,
1055     0x00000010,
1056     0x00000101,
1057     0x00000111,
1058     0x00001010,
1059     0x00001020,
1060     0x00001111,
1061     0x00001121,
1062     0x00010100,
1063     0x00010110,
1064     0x00010201,
1065     0x00010211,
1066     0x00011110,
1067     0x00011120,
1068     0x00011211,
1069     0x00011221,
1070     0x00101000,
1071     0x00101010,
1072     0x00101101,
1073     0x00101111,
1074     0x00102010,
1075     0x00102020,
1076     0x00102111,
1077     0x00102121,
1078     0x00111100,
1079     0x00111110,
1080     0x00111201,
1081     0x00111211,
1082     0x00112110,
1083     0x00112120,
1084     0x00112211,
1085     0x00112221,
1086     0x01010000,
1087     0x01010010,
1088     0x01010101,
1089     0x01010111,
1090     0x01011010,
1091     0x01011020,
1092     0x01011111,
1093     0x01011121,
1094     0x01020100,
1095     0x01020110,
1096     0x01020201,
1097     0x01020211,
1098     0x01021110,
1099     0x01021120,
1100     0x01021211,
1101     0x01021221,
1102     0x01111000,
1103     0x01111010,
1104     0x01111101,
1105     0x01111111,
1106     0x01112010,
1107     0x01112020,
1108     0x01112111,
1109     0x01112121,
1110     0x01121100,
1111     0x01121110,
1112     0x01121201,
1113     0x01121211,
1114     0x01122110,
1115     0x01122120,
1116     0x01122211,
1117     0x01122221,
1118     0x10100000,
1119     0x10100010,
1120     0x10100101,
1121     0x10100111,
1122     0x10101010,
1123     0x10101020,
1124     0x10101111,
1125     0x10101121,
1126     0x10110100,
1127     0x10110110,
1128     0x10110201,
1129     0x10110211,
1130     0x10111110,
1131     0x10111120,
1132     0x10111211,
1133     0x10111221,
1134     0x10201000,
1135     0x10201010,
1136     0x10201101,
1137     0x10201111,
1138     0x10202010,
1139     0x10202020,
1140     0x10202111,
1141     0x10202121,
1142     0x10211100,
1143     0x10211110,
1144     0x10211201,
1145     0x10211211,
1146     0x10212110,
1147     0x10212120,
1148     0x10212211,
1149     0x10212221,
1150     0x11110000,
1151     0x11110010,
1152     0x11110101,
1153     0x11110111,
1154     0x11111010,
1155     0x11111020,
1156     0x11111111,
1157     0x11111121,
1158     0x11120100,
1159     0x11120110,
1160     0x11120201,
1161     0x11120211,
1162     0x11121110,
1163     0x11121120,
1164     0x11121211,
1165     0x11121221,
1166     0x11211000,
1167     0x11211010,
1168     0x11211101,
1169     0x11211111,
1170     0x11212010,
1171     0x11212020,
1172     0x11212111,
1173     0x11212121,
1174     0x11221100,
1175     0x11221110,
1176     0x11221201,
1177     0x11221211,
1178     0x11222110,
1179     0x11222120,
1180     0x11222211,
1181     0x11222221,
1182     0x01000000,
1183     0x01000010,
1184     0x01000101,
1185     0x01000111,
1186     0x01001010,
1187     0x01001020,
1188     0x01001111,
1189     0x01001121,
1190     0x01010100,
1191     0x01010110,
1192     0x01010201,
1193     0x01010211,
1194     0x01011110,
1195     0x01011120,
1196     0x01011211,
1197     0x01011221,
1198     0x01101000,
1199     0x01101010,
1200     0x01101101,
1201     0x01101111,
1202     0x01102010,
1203     0x01102020,
1204     0x01102111,
1205     0x01102121,
1206     0x01111100,
1207     0x01111110,
1208     0x01111201,
1209     0x01111211,
1210     0x01112110,
1211     0x01112120,
1212     0x01112211,
1213     0x01112221,
1214     0x02010000,
1215     0x02010010,
1216     0x02010101,
1217     0x02010111,
1218     0x02011010,
1219     0x02011020,
1220     0x02011111,
1221     0x02011121,
1222     0x02020100,
1223     0x02020110,
1224     0x02020201,
1225     0x02020211,
1226     0x02021110,
1227     0x02021120,
1228     0x02021211,
1229     0x02021221,
1230     0x02111000,
1231     0x02111010,
1232     0x02111101,
1233     0x02111111,
1234     0x02112010,
1235     0x02112020,
1236     0x02112111,
1237     0x02112121,
1238     0x02121100,
1239     0x02121110,
1240     0x02121201,
1241     0x02121211,
1242     0x02122110,
1243     0x02122120,
1244     0x02122211,
1245     0x02122221,
1246     0x11100000,
1247     0x11100010,
1248     0x11100101,
1249     0x11100111,
1250     0x11101010,
1251     0x11101020,
1252     0x11101111,
1253     0x11101121,
1254     0x11110100,
1255     0x11110110,
1256     0x11110201,
1257     0x11110211,
1258     0x11111110,
1259     0x11111120,
1260     0x11111211,
1261     0x11111221,
1262     0x11201000,
1263     0x11201010,
1264     0x11201101,
1265     0x11201111,
1266     0x11202010,
1267     0x11202020,
1268     0x11202111,
1269     0x11202121,
1270     0x11211100,
1271     0x11211110,
1272     0x11211201,
1273     0x11211211,
1274     0x11212110,
1275     0x11212120,
1276     0x11212211,
1277     0x11212221,
1278     0x12110000,
1279     0x12110010,
1280     0x12110101,
1281     0x12110111,
1282     0x12111010,
1283     0x12111020,
1284     0x12111111,
1285     0x12111121,
1286     0x12120100,
1287     0x12120110,
1288     0x12120201,
1289     0x12120211,
1290     0x12121110,
1291     0x12121120,
1292     0x12121211,
1293     0x12121221,
1294     0x12211000,
1295     0x12211010,
1296     0x12211101,
1297     0x12211111,
1298     0x12212010,
1299     0x12212020,
1300     0x12212111,
1301     0x12212121,
1302     0x12221100,
1303     0x12221110,
1304     0x12221201,
1305     0x12221211,
1306     0x12222110,
1307     0x12222120,
1308     0x12222211,
1309     0x12222221
1310 };