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