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