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