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