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