X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/e0a4029251c1d80d50f9cb0bd152d1fca7914bc4..6a3f8b4f1f1c802df93ce7bc05588536cb7a4dad:/demos/life/game.cpp diff --git a/demos/life/game.cpp b/demos/life/game.cpp index 07a2f13401..eefae2c2de 100644 --- a/demos/life/game.cpp +++ b/demos/life/game.cpp @@ -13,64 +13,74 @@ // headers, declarations, constants // ========================================================================== -#ifdef __GNUG__ - #pragma implementation "game.h" +// For compilers that support precompilation, includes "wx/wx.h". +#include "wx/wxprec.h" + +#ifdef __BORLANDC__ +#pragma hdrstop +#endif + +#ifndef WX_PRECOMP +#include "wx/wx.h" #endif #include "wx/log.h" +#include "wx/module.h" #include "game.h" -#include // for abort #include // for memset -#define ARRAYSIZE 1024 // size of the static arrays for BeginFind & co. +#define CELLSARRAYSIZE 1024 // static array for BeginFind & co. #define ALLOCBOXES 16 // number of cellboxes to alloc at once +#define MAXDEAD 8 // tics before removing cellbox from list + // ========================================================================== // CellBox // ========================================================================== #define HASH(x, y) (((x >> 3) & 0x7f) << 7) + ((y >> 3) & 0x7f) -#define HASHSIZE 32768 -#define MAXDEAD 8 + +#define HASHSIZE 16384 // hash table size (do not change!) +#define CELLBOX 8 // cells in a cellbox (do not change!) -class CellBox +class LifeCellBox { public: - // members + // members inline bool IsAlive(int dx, int dy) const; inline bool SetCell(int dx, int dy, bool alive); // attributes - wxInt32 m_x, m_y; // position in universe - wxUint32 m_live1, m_live2; // alive cells (1 bit per cell) - wxUint32 m_old1, m_old2; // old values for m_live1, 2 - wxUint32 m_on[8]; // neighbouring info - wxUint32 m_dead; // been dead for n generations - CellBox *m_up, *m_dn, *m_lf, *m_rt; // neighbour CellBoxes - CellBox *m_prev, *m_next; // in linked list - CellBox *m_hprev, *m_hnext; // in hash table + wxInt32 m_x, m_y; // position in universe + wxUint32 m_live1, m_live2; // alive cells (1 bit per cell) + wxUint32 m_old1, m_old2; // old values for m_live1, 2 + wxUint32 m_on[8]; // neighbouring info + wxUint32 m_dead; // been dead for n generations + LifeCellBox *m_up, *m_dn, *m_lf, *m_rt; // neighbour CellBoxes + LifeCellBox *m_prev, *m_next; // in linked list + LifeCellBox *m_hprev, *m_hnext; // in hash table }; // IsAlive: // Returns whether cell dx, dy in this box is alive // -bool CellBox::IsAlive(int dx, int dy) const +bool LifeCellBox::IsAlive(int dx, int dy) const { if (dy > 3) - return (m_live2 & 1 << ((dy - 4) * 8 + dx)); + return (m_live2 & 1 << ((dy - 4) * 8 + dx)) ? true : false ; else - return (m_live1 & 1 << ((dy) * 8 + dx)); + return (m_live1 & 1 << ((dy) * 8 + dx)) ? true : false ; } // SetCell: -// Sets cell dx, dy in this box to 'alive', returns TRUE if -// the previous value was different, FALSE if it was the same. +// Sets cell dx, dy in this box to 'alive', returns true if +// the previous value was different, false if it was the same. // -bool CellBox::SetCell(int dx, int dy, bool alive) +bool LifeCellBox::SetCell(int dx, int dy, bool alive) { if (IsAlive(dx, dy) != alive) { @@ -82,10 +92,10 @@ bool CellBox::SetCell(int dx, int dy, bool alive) // reset this here to avoid updating problems m_dead = 0; - return TRUE; + return true; } else - return FALSE; + return false; } @@ -98,18 +108,25 @@ bool CellBox::SetCell(int dx, int dy, bool alive) // -------------------------------------------------------------------------- Life::Life() -{ - m_numcells = 0; - m_boxes = new CellBox *[HASHSIZE]; - m_head = NULL; - m_available = NULL; +{ + // pattern description + m_name = wxEmptyString; + m_rules = wxEmptyString; + m_description = wxEmptyString; + + // pattern data + m_numcells = 0; + m_boxes = new LifeCellBox *[HASHSIZE]; + m_head = NULL; + m_available = NULL; for (int i = 0; i < HASHSIZE; i++) m_boxes[i] = NULL; - m_cells = new Cell[ARRAYSIZE]; - m_ncells = 0; - m_findmore = FALSE; - m_changed = FALSE; + // state vars for BeginFind & FindMore + m_cells = new LifeCell[CELLSARRAYSIZE]; + m_ncells = 0; + m_findmore = false; + m_changed = false; } Life::~Life() @@ -117,29 +134,27 @@ Life::~Life() Clear(); delete[] m_boxes; - delete[] m_cells; + delete[] m_cells; } // Clear: // Clears the board, freeing all storage. -// +// void Life::Clear() { - CellBox *c, *nc; + LifeCellBox *c, *nc; - m_numcells = 0; - // clear the hash table pointers for (int i = 0; i < HASHSIZE; i++) m_boxes[i] = NULL; - + // free used boxes c = m_head; while (c) { nc = c->m_next; delete c; - c = nc; + c = nc; } m_head = NULL; @@ -149,9 +164,15 @@ void Life::Clear() { nc = c->m_next; delete c; - c = nc; + c = nc; } m_available = NULL; + + // reset state + m_name = wxEmptyString; + m_rules = wxEmptyString; + m_description = wxEmptyString; + m_numcells = 0; } // -------------------------------------------------------------------------- @@ -163,7 +184,7 @@ void Life::Clear() // bool Life::IsAlive(wxInt32 x, wxInt32 y) { - CellBox *c = LinkBox(x, y, FALSE); + LifeCellBox *c = LinkBox(x, y, false); return (c && c->IsAlive( x - c->m_x, y - c->m_y )); } @@ -173,7 +194,7 @@ bool Life::IsAlive(wxInt32 x, wxInt32 y) // void Life::SetCell(wxInt32 x, wxInt32 y, bool alive) { - CellBox *c = LinkBox(x, y); + LifeCellBox *c = LinkBox(x, y); wxUint32 dx = x - c->m_x; wxUint32 dy = y - c->m_y; @@ -184,21 +205,40 @@ void Life::SetCell(wxInt32 x, wxInt32 y, bool alive) else m_numcells--; } -} +} -void Life::SetShape(const LifeShape& shape) +void Life::SetPattern(const LifePattern& pattern) { - char *p = shape.m_data; - - int i0 = -(shape.m_width / 2); - int j0 = -(shape.m_height / 2); - int i1 = i0 + shape.m_width - 1; - int j1 = j0 + shape.m_height - 1; + wxArrayString data = pattern.m_shape; + wxString line; + long x = 0, + y = 0; Clear(); - for (int j = j0; j <= j1; j++) - for (int i = i0; i <= i1; i++) - SetCell(i, j, *(p++) == '*'); + for (size_t n = 0; n < data.GetCount(); n++) + { + line = data[n]; + + if ( (line.GetChar(0) != wxT('*')) && + (line.GetChar(0) != wxT('.')) ) + { + // assume that it is a digit or a minus sign + line.BeforeFirst(wxT(' ')).ToLong(&x); + line.AfterFirst(wxT(' ')).ToLong(&y); + } + else + { + // pattern data + for (size_t k = 0; k < line.Len(); k++) + SetCell(x + k, y, line.GetChar(k) == wxT('*')); + + y++; + } + } + + m_name = pattern.m_name; + m_rules = pattern.m_rules; + m_description = pattern.m_description; } // -------------------------------------------------------------------------- @@ -206,18 +246,18 @@ void Life::SetShape(const LifeShape& shape) // -------------------------------------------------------------------------- // CreateBox: -// Creates a new box in x, y, either taking it from the list +// Creates a box in x, y, either taking it from the list // of available boxes, or allocating a new one. // -CellBox* Life::CreateBox(wxInt32 x, wxInt32 y, wxUint32 hv) +LifeCellBox* Life::CreateBox(wxInt32 x, wxInt32 y, wxUint32 hv) { - CellBox *c; + LifeCellBox *c; // if there are no available boxes, alloc a few more if (!m_available) for (int i = 1; i <= ALLOCBOXES; i++) { - c = new CellBox(); + c = new LifeCellBox(); if (!c) { @@ -229,12 +269,9 @@ CellBox* Life::CreateBox(wxInt32 x, wxInt32 y, wxUint32 hv) // gracefully. wxLogFatalError(_("Out of memory! Aborting...")); - // the above call should abort, but it doesn't :-? - abort(); - - break; + // NOTREACHED } - + c->m_next = m_available; m_available = c; } @@ -244,7 +281,7 @@ CellBox* Life::CreateBox(wxInt32 x, wxInt32 y, wxUint32 hv) m_available = c->m_next; // reset everything - memset((void *) c, 0, sizeof(CellBox)); + memset((void *) c, 0, sizeof(LifeCellBox)); c->m_x = x; c->m_y = y; @@ -263,13 +300,13 @@ CellBox* Life::CreateBox(wxInt32 x, wxInt32 y, wxUint32 hv) // LinkBox: // Returns a pointer to the box (x, y); if it didn't exist yet, -// it returns NULL or creates a new one, depending on the 'create' -// parameter. +// it returns NULL or creates a new one, depending on the value +// of the 'create' parameter. // -CellBox* Life::LinkBox(wxInt32 x, wxInt32 y, bool create) +LifeCellBox* Life::LinkBox(wxInt32 x, wxInt32 y, bool create) { wxUint32 hv; - CellBox *c; + LifeCellBox *c; x &= 0xfffffff8; y &= 0xfffffff8; @@ -279,15 +316,15 @@ CellBox* Life::LinkBox(wxInt32 x, wxInt32 y, bool create) for (c = m_boxes[hv]; c; c = c->m_hnext) if ((c->m_x == x) && (c->m_y == y)) return c; - // if not found, and (create == TRUE), create a new one - return create? CreateBox(x, y, hv) : NULL; + // if not found, and (create == true), create a new one + return create? CreateBox(x, y, hv) : (LifeCellBox*) NULL; } // KillBox: // Removes this box from the list and the hash table and // puts it in the list of available boxes. // -void Life::KillBox(CellBox *c) +void Life::KillBox(LifeCellBox *c) { wxUint32 hv = HASH(c->m_x, c->m_y); @@ -297,13 +334,13 @@ void Life::KillBox(CellBox *c) else m_head = c->m_next; - // remove from the hash table + // remove from the hash table if (c != m_boxes[hv]) c->m_hprev->m_hnext = c->m_hnext; else m_boxes[hv] = c->m_hnext; - // update neighbours + // update neighbours if (c->m_next) c->m_next->m_prev = c->m_prev; if (c->m_hnext) c->m_hnext->m_hprev = c->m_hprev; if (c->m_up) c->m_up->m_dn = NULL; @@ -317,147 +354,247 @@ void Life::KillBox(CellBox *c) } // -------------------------------------------------------------------------- -// FindMore & co. +// Navigation // -------------------------------------------------------------------------- -// Post eight cells to the cell arrays (changed cells only) -void Life::DoLine(wxInt32 i, wxInt32 j, wxUint32 live, wxUint32 old) +LifeCell Life::FindCenter() { - wxUint32 diff = (live ^ old) & 0x000000ff; - - if (!diff) return; + double sx, sy; + int n; + sx = 0.0; + sy = 0.0; + n = 0; + + LifeCellBox *c; + for (c = m_head; c; c = c->m_next) + if (!c->m_dead) + { + sx += c->m_x; + sy += c->m_y; + n++; + } - for (wxInt32 k = 8; k; k--, i++) + if (n > 0) { - if (diff & 0x01) + sx = (sx / n) + CELLBOX / 2; + sy = (sy / n) + CELLBOX / 2; + } + + LifeCell cell; + cell.i = (wxInt32) sx; + cell.j = (wxInt32) sy; + return cell; +} + +LifeCell Life::FindNorth() +{ + wxInt32 x = 0, y = 0; + bool first = true; + + LifeCellBox *c; + for (c = m_head; c; c = c->m_next) + if (!c->m_dead && ((first) || (c->m_y < y))) { - m_cells[m_ncells].i = i; - m_cells[m_ncells].j = j; - m_ncells++; + x = c->m_x; + y = c->m_y; + first = false; } - diff >>= 1; - live >>= 1; - } + + LifeCell cell; + cell.i = first? 0 : x + CELLBOX / 2; + cell.j = first? 0 : y + CELLBOX / 2; + return cell; } - -// Post eight cells to the cell arrays (alive cells only) -void Life::DoLine(wxInt32 i, wxInt32 j, wxUint32 live) + +LifeCell Life::FindSouth() { - if (! (live & 0x000000ff)) return; + wxInt32 x = 0, y = 0; + bool first = true; - for (wxInt32 k = 8; k; k--, i++) + LifeCellBox *c; + for (c = m_head; c; c = c->m_next) + if (!c->m_dead && ((first) || (c->m_y > y))) + { + x = c->m_x; + y = c->m_y; + first = false; + } + + LifeCell cell; + cell.i = first? 0 : x + CELLBOX / 2; + cell.j = first? 0 : y + CELLBOX / 2; + return cell; +} + +LifeCell Life::FindWest() +{ + wxInt32 x = 0, y = 0; + bool first = true; + + LifeCellBox *c; + for (c = m_head; c; c = c->m_next) + if (!c->m_dead && ((first) || (c->m_x < x))) + { + x = c->m_x; + y = c->m_y; + first = false; + } + + LifeCell cell; + cell.i = first? 0 : x + CELLBOX / 2; + cell.j = first? 0 : y + CELLBOX / 2; + return cell; +} + +LifeCell Life::FindEast() +{ + wxInt32 x = 0, y = 0; + bool first = true; + + LifeCellBox *c; + for (c = m_head; c; c = c->m_next) + if (!c->m_dead && ((first) || (c->m_x > x))) + { + x = c->m_x; + y = c->m_y; + first = false; + } + + LifeCell cell; + cell.i = first? 0 : x + CELLBOX / 2; + cell.j = first? 0 : y + CELLBOX / 2; + return cell; +} + +// -------------------------------------------------------------------------- +// FindMore & co. +// -------------------------------------------------------------------------- + +// DoLine: +// Post eight cells to the cell arrays - leave out the fourth +// argument (or pass 0, the default value) to post alive cells +// only, else it will post cells which have changed. +// +void Life::DoLine(wxInt32 x, wxInt32 y, wxUint32 live, wxUint32 old) +{ + wxUint32 diff = (live ^ old) & 0xff; + + if (!diff) return; + + for (wxInt32 k = 8; k; k--, x++) { - if (live & 0x01) + if (diff & 0x01) { - m_cells[m_ncells].i = i; - m_cells[m_ncells].j = j; + m_cells[m_ncells].i = x; + m_cells[m_ncells].j = y; m_ncells++; } - live >>= 1; + diff >>= 1; } -} +} -void Life::BeginFind(wxInt32 i0, wxInt32 j0, wxInt32 i1, wxInt32 j1, bool changed) +void Life::BeginFind(wxInt32 x0, wxInt32 y0, wxInt32 x1, wxInt32 y1, bool changed) { // TODO: optimize for the case where the maximum number of // cellboxes that fit in the specified viewport is smaller // than the current total of boxes; iterating over the list // should then be faster than searching in the hash table. - - m_i0 = m_i = i0 & 0xfffffff8; - m_j0 = m_j = j0 & 0xfffffff8; - m_i1 = (i1 + 7) & 0xfffffff8; - m_j1 = (j1 + 7) & 0xfffffff8; - - m_findmore = TRUE; + + m_x0 = m_x = x0 & 0xfffffff8; + m_y0 = m_y = y0 & 0xfffffff8; + m_x1 = (x1 + 7) & 0xfffffff8; + m_y1 = (y1 + 7) & 0xfffffff8; + + m_findmore = true; m_changed = changed; } -bool Life::FindMore(Cell *cells[], size_t *ncells) +bool Life::FindMore(LifeCell *cells[], size_t *ncells) { - CellBox *c; + LifeCellBox *c; *cells = m_cells; m_ncells = 0; if (m_changed) { - for ( ; m_j <= m_j1; m_j += 8, m_i = m_i0) - for ( ; m_i <= m_i1; m_i += 8) + for ( ; m_y <= m_y1; m_y += 8, m_x = m_x0) + for ( ; m_x <= m_x1; m_x += 8) { - if ((c = LinkBox(m_i, m_j, FALSE)) == NULL) + if ((c = LinkBox(m_x, m_y, false)) == NULL) continue; - + // check whether there is enough space left in the array - if (m_ncells > (ARRAYSIZE - 64)) + if (m_ncells > (CELLSARRAYSIZE - 64)) { *ncells = m_ncells; - return FALSE; + return false; } - - DoLine(m_i, m_j , c->m_live1, c->m_old1 ); - DoLine(m_i, m_j + 1, c->m_live1 >> 8, c->m_old1 >> 8 ); - DoLine(m_i, m_j + 2, c->m_live1 >> 16, c->m_old1 >> 16); - DoLine(m_i, m_j + 3, c->m_live1 >> 24, c->m_old1 >> 24); - DoLine(m_i, m_j + 4, c->m_live2, c->m_old2 ); - DoLine(m_i, m_j + 5, c->m_live2 >> 8, c->m_old2 >> 8 ); - DoLine(m_i, m_j + 6, c->m_live2 >> 16, c->m_old2 >> 16); - DoLine(m_i, m_j + 7, c->m_live2 >> 24, c->m_old2 >> 24); + + DoLine(m_x, m_y , c->m_live1, c->m_old1 ); + DoLine(m_x, m_y + 1, c->m_live1 >> 8, c->m_old1 >> 8 ); + DoLine(m_x, m_y + 2, c->m_live1 >> 16, c->m_old1 >> 16); + DoLine(m_x, m_y + 3, c->m_live1 >> 24, c->m_old1 >> 24); + DoLine(m_x, m_y + 4, c->m_live2, c->m_old2 ); + DoLine(m_x, m_y + 5, c->m_live2 >> 8, c->m_old2 >> 8 ); + DoLine(m_x, m_y + 6, c->m_live2 >> 16, c->m_old2 >> 16); + DoLine(m_x, m_y + 7, c->m_live2 >> 24, c->m_old2 >> 24); } } else - { - for ( ; m_j <= m_j1; m_j += 8, m_i = m_i0) - for ( ; m_i <= m_i1; m_i += 8) + { + for ( ; m_y <= m_y1; m_y += 8, m_x = m_x0) + for ( ; m_x <= m_x1; m_x += 8) { - if ((c = LinkBox(m_i, m_j, FALSE)) == NULL) + if ((c = LinkBox(m_x, m_y, false)) == NULL) continue; - + // check whether there is enough space left in the array - if (m_ncells > (ARRAYSIZE - 64)) + if (m_ncells > (CELLSARRAYSIZE - 64)) { *ncells = m_ncells; - return FALSE; + return false; } - - DoLine(m_i, m_j , c->m_live1 ); - DoLine(m_i, m_j + 1, c->m_live1 >> 8 ); - DoLine(m_i, m_j + 2, c->m_live1 >> 16); - DoLine(m_i, m_j + 3, c->m_live1 >> 24); - DoLine(m_i, m_j + 4, c->m_live2 ); - DoLine(m_i, m_j + 5, c->m_live2 >> 8 ); - DoLine(m_i, m_j + 6, c->m_live2 >> 16); - DoLine(m_i, m_j + 7, c->m_live2 >> 24); + + DoLine(m_x, m_y , c->m_live1 ); + DoLine(m_x, m_y + 1, c->m_live1 >> 8 ); + DoLine(m_x, m_y + 2, c->m_live1 >> 16); + DoLine(m_x, m_y + 3, c->m_live1 >> 24); + DoLine(m_x, m_y + 4, c->m_live2 ); + DoLine(m_x, m_y + 5, c->m_live2 >> 8 ); + DoLine(m_x, m_y + 6, c->m_live2 >> 16); + DoLine(m_x, m_y + 7, c->m_live2 >> 24); } } - + *ncells = m_ncells; - m_findmore = FALSE; - return TRUE; + m_findmore = false; + return true; } - + // -------------------------------------------------------------------------- // Evolution engine // -------------------------------------------------------------------------- +extern unsigned char *g_tab; extern int g_tab1[]; extern int g_tab2[]; // NextTic: // Advance one step in evolution :-) -// +// bool Life::NextTic() { - CellBox *c, *up, *dn, *lf, *rt; + LifeCellBox *c, *up, *dn, *lf, *rt; wxUint32 t1, t2, t3, t4; - bool changed = FALSE; - + bool changed = false; + m_numcells = 0; - + // Stage 1: // Compute neighbours of each cell - // + // // WARNING: unrolled loops and lengthy code follows! - // + // c = m_head; while (c) @@ -465,25 +602,25 @@ bool Life::NextTic() if (! (c->m_live1 || c->m_live2)) { c = c->m_next; - continue; - } + continue; + } up = c->m_up; dn = c->m_dn; lf = c->m_lf; rt = c->m_rt; - // up + // up t1 = c->m_live1 & 0x000000ff; if (t1) { if (!up) { up = LinkBox(c->m_x, c->m_y - 8); - up->m_dn = c; + up->m_dn = c; } t2 = g_tab1[t1]; up->m_on[7] += t2; - c->m_on[1] += t2; + c->m_on[1] += t2; c->m_on[0] += g_tab2[t1]; } @@ -494,30 +631,30 @@ bool Life::NextTic() if (!dn) { dn = LinkBox(c->m_x, c->m_y + 8); - dn->m_up = c; + dn->m_up = c; } t2 = g_tab1[t1]; dn->m_on[0] += t2; - c->m_on[6] += t2; + c->m_on[6] += t2; c->m_on[7] += g_tab2[t1]; } - + t1 = c->m_live1; t2 = c->m_live2; - + // left if (t1 & 0x01010101) { if (!lf) { - lf = LinkBox(c->m_x - 8, c->m_y); + lf = LinkBox(c->m_x - 8, c->m_y); lf->m_rt = c; } if (t1 & 0x00000001) { if (!lf->m_up) { - lf->m_up = LinkBox(c->m_x - 8, c->m_y - 8); + lf->m_up = LinkBox(c->m_x - 8, c->m_y - 8); lf->m_up->m_dn = lf; } lf->m_up->m_on[7] += 0x10000000; @@ -526,53 +663,53 @@ bool Life::NextTic() } if (t1 & 0x00000100) { - lf->m_on[0] += 0x10000000; - lf->m_on[1] += 0x10000000; - lf->m_on[2] += 0x10000000; - } + lf->m_on[0] += 0x10000000; + lf->m_on[1] += 0x10000000; + lf->m_on[2] += 0x10000000; + } if (t1 & 0x00010000) { - lf->m_on[1] += 0x10000000; - lf->m_on[2] += 0x10000000; - lf->m_on[3] += 0x10000000; + lf->m_on[1] += 0x10000000; + lf->m_on[2] += 0x10000000; + lf->m_on[3] += 0x10000000; } if (t1 & 0x01000000) { - lf->m_on[2] += 0x10000000; - lf->m_on[3] += 0x10000000; - lf->m_on[4] += 0x10000000; + lf->m_on[2] += 0x10000000; + lf->m_on[3] += 0x10000000; + lf->m_on[4] += 0x10000000; } } if (t2 & 0x01010101) { if (!lf) { - lf = LinkBox(c->m_x - 8, c->m_y); + lf = LinkBox(c->m_x - 8, c->m_y); lf->m_rt = c; } if (t2 & 0x00000001) { - lf->m_on[3] += 0x10000000; - lf->m_on[4] += 0x10000000; - lf->m_on[5] += 0x10000000; - } + lf->m_on[3] += 0x10000000; + lf->m_on[4] += 0x10000000; + lf->m_on[5] += 0x10000000; + } if (t2 & 0x00000100) { - lf->m_on[4] += 0x10000000; - lf->m_on[5] += 0x10000000; - lf->m_on[6] += 0x10000000; - } + lf->m_on[4] += 0x10000000; + lf->m_on[5] += 0x10000000; + lf->m_on[6] += 0x10000000; + } if (t2 & 0x00010000) { - lf->m_on[5] += 0x10000000; - lf->m_on[6] += 0x10000000; - lf->m_on[7] += 0x10000000; + lf->m_on[5] += 0x10000000; + lf->m_on[6] += 0x10000000; + lf->m_on[7] += 0x10000000; } - if (t2 & 0x01000000) + if (t2 & 0x01000000) { if (!lf->m_dn) { - lf->m_dn = LinkBox(c->m_x - 8, c->m_y + 8); + lf->m_dn = LinkBox(c->m_x - 8, c->m_y + 8); lf->m_dn->m_up = lf; } lf->m_on[6] += 0x10000000; @@ -586,14 +723,14 @@ bool Life::NextTic() { if (!rt) { - rt = LinkBox(c->m_x + 8, c->m_y); + rt = LinkBox(c->m_x + 8, c->m_y); rt->m_lf = c; } if (t1 & 0x00000080) { if (!rt->m_up) { - rt->m_up = LinkBox(c->m_x + 8, c->m_y - 8); + rt->m_up = LinkBox(c->m_x + 8, c->m_y - 8); rt->m_up->m_dn = rt; } rt->m_up->m_on[7] += 0x00000001; @@ -602,53 +739,53 @@ bool Life::NextTic() } if (t1 & 0x00008000) { - rt->m_on[0] += 0x00000001; - rt->m_on[1] += 0x00000001; - rt->m_on[2] += 0x00000001; - } + rt->m_on[0] += 0x00000001; + rt->m_on[1] += 0x00000001; + rt->m_on[2] += 0x00000001; + } if (t1 & 0x00800000) { - rt->m_on[1] += 0x00000001; - rt->m_on[2] += 0x00000001; - rt->m_on[3] += 0x00000001; + rt->m_on[1] += 0x00000001; + rt->m_on[2] += 0x00000001; + rt->m_on[3] += 0x00000001; } if (t1 & 0x80000000) { - rt->m_on[2] += 0x00000001; - rt->m_on[3] += 0x00000001; - rt->m_on[4] += 0x00000001; + rt->m_on[2] += 0x00000001; + rt->m_on[3] += 0x00000001; + rt->m_on[4] += 0x00000001; } } if (t2 & 0x80808080) { if (!rt) { - rt = LinkBox(c->m_x + 8, c->m_y); + rt = LinkBox(c->m_x + 8, c->m_y); rt->m_lf = c; } if (t2 & 0x00000080) { - rt->m_on[3] += 0x00000001; - rt->m_on[4] += 0x00000001; - rt->m_on[5] += 0x00000001; - } + rt->m_on[3] += 0x00000001; + rt->m_on[4] += 0x00000001; + rt->m_on[5] += 0x00000001; + } if (t2 & 0x00008000) { - rt->m_on[4] += 0x00000001; - rt->m_on[5] += 0x00000001; - rt->m_on[6] += 0x00000001; - } + rt->m_on[4] += 0x00000001; + rt->m_on[5] += 0x00000001; + rt->m_on[6] += 0x00000001; + } if (t2 & 0x00800000) { - rt->m_on[5] += 0x00000001; - rt->m_on[6] += 0x00000001; - rt->m_on[7] += 0x00000001; + rt->m_on[5] += 0x00000001; + rt->m_on[6] += 0x00000001; + rt->m_on[7] += 0x00000001; } - if (t2 & 0x80000000) + if (t2 & 0x80000000) { if (!rt->m_dn) { - rt->m_dn = LinkBox(c->m_x + 8, c->m_y + 8); + rt->m_dn = LinkBox(c->m_x + 8, c->m_y + 8); rt->m_dn->m_up = rt; } rt->m_on[6] += 0x00000001; @@ -656,9 +793,10 @@ bool Life::NextTic() rt->m_dn->m_on[0] += 0x00000001; } } - + // inner cells - for (int i = 1; i <= 3; i++) + int i; + for (i = 1; i <= 3; i++) { t1 = ((c->m_live1) >> (i * 8)) & 0x000000ff; if (t1) @@ -668,7 +806,7 @@ bool Life::NextTic() c->m_on[i + 1] += g_tab1[t1]; } } - for (int i = 0; i <= 2; i++) + for (i = 0; i <= 2; i++) { t1 = ((c->m_live2) >> (i * 8)) & 0x000000ff; if (t1) @@ -689,89 +827,86 @@ bool Life::NextTic() // Stage 2: // Stabilize // - // WARNING: to be optimized and unrolled soon. - // c = m_head; - + while (c) { - t1 = c->m_live1; - c->m_old1 = t1; + t1 = 0; t2 = 0; - for (int i = 0; i <= 3; i++) - { - t3 = c->m_on[i]; - if (!t3) - { - t1 >>= 8; - t2 >>= 8; - continue; - } - for (int j = 0; j < 8; j++) - { - t2 >>= 1; - t4 = t3 & 0x0000000f; - - if ((t4 == 3) || ((t4 == 2) && (t1 & 0x00000001))) - { - t2 |= 0x80000000; - m_numcells++; - } - - t3 >>= 4; - t1 >>= 1; - } - c->m_on[i] = 0; - } - c->m_live1 = t2; + t3 = c->m_live1; + c->m_old1 = t3; + + t4 = c->m_on[0]; + t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 ) & 0xf) ]; + t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 4 ) & 0xf) ] << 4; + t4 = c->m_on[1]; + t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 8 ) & 0xf) ] << 8; + t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 12) & 0xf) ] << 12; + t4 = c->m_on[2]; + t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 16) & 0xf) ] << 16; + t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 20) & 0xf) ] << 20; + t4 = c->m_on[3]; + t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 24) & 0xf) ] << 24; + t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 28) & 0xf) ] << 28; + + t3 = c->m_live2; + c->m_old2 = t3; + + t4 = c->m_on[4]; + t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 ) & 0xf) ]; + t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 4 ) & 0xf) ] << 4; + t4 = c->m_on[5]; + t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 8 ) & 0xf) ] << 8; + t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 12) & 0xf) ] << 12; + t4 = c->m_on[6]; + t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 16) & 0xf) ] << 16; + t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 20) & 0xf) ] << 20; + t4 = c->m_on[7]; + t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 24) & 0xf) ] << 24; + t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 28) & 0xf) ] << 28; + + c->m_on[0] = c->m_on[1] = c->m_on[2] = c->m_on[3] = + c->m_on[4] = c->m_on[5] = c->m_on[6] = c->m_on[7] = 0; + c->m_live1 = t1; + c->m_live2 = t2; - t1 = c->m_live2; - c->m_old2 = t1; - t2 = 0; - for (int i = 4; i <= 7; i++) - { - t3 = c->m_on[i]; - if (!t3) - { - t1 >>= 8; - t2 >>= 8; - continue; - } + // count alive cells +#if 1 + wxUint32 t1_, t2_; - for (int j = 0; j < 8; j++) - { - t2 >>= 1; - t4 = t3 & 0x0000000f; - - if ((t4 == 3) || ((t4 == 2) && (t1 & 0x00000001))) - { - t2 |= 0x80000000; - m_numcells++; - } - - t3 >>= 4; - t1 >>= 1; - } - c->m_on[i] = 0; + t1_ = (t1 & 0x55555555) + (t1 >> 1 & 0x55555555); + t1_ = (t1_ & 0x33333333) + (t1_ >> 2 & 0x33333333); + + t2_ = (t2 & 0x55555555) + (t2 >> 1 & 0x55555555); + t2_ = (t2_ & 0x33333333) + (t2_ >> 2 & 0x33333333) + t1_; + t2_ = (t2_ & 0x0F0F0F0F) + (t2_ >> 4 & 0x0F0F0F0F); + t2_ = (t2_ & 0x00FF00FF) + (t2_ >> 8 & 0x00FF00FF); + + m_numcells += (t2_ & 0xFF) + (t2_ >> 16 & 0xFF); +#else + // Original, slower code + for (int i = 0; i < 32; i++) + { + if (t1 & (1 << i)) m_numcells++; + if (t2 & (1 << i)) m_numcells++; } - c->m_live2 = t2; +#endif + + changed |= ((t1 ^ c->m_old1) || (t2 ^ c->m_old2)); - // keep track of changes - changed |= ((c->m_live1 ^ c->m_old1) || (c->m_live2 ^ c->m_old2)); - // mark, and discard if necessary, dead boxes - if (c->m_live1 || c->m_live2) + if (t1 || t2) { c->m_dead = 0; c = c->m_next; } else { - CellBox *aux = c->m_next; + LifeCellBox *aux = c->m_next; if (c->m_dead++ > MAXDEAD) - KillBox(c); - + KillBox(c); + c = aux; } } @@ -779,9 +914,67 @@ bool Life::NextTic() return changed; } -// -------------------------------------------------------------------------- -// Lookup tables - these will be generated on-the-fly soon. -// -------------------------------------------------------------------------- +// ========================================================================== +// LifeModule +// ========================================================================== + +// A module to pregenerate lookup tables without having to do it +// from the application. + +class LifeModule: public wxModule +{ +DECLARE_DYNAMIC_CLASS(LifeModule) + +public: + LifeModule() {}; + bool OnInit(); + void OnExit(); +}; + +IMPLEMENT_DYNAMIC_CLASS(LifeModule, wxModule) + +bool LifeModule::OnInit() +{ + // see below + g_tab = new unsigned char [0xfffff]; + + if (!g_tab) return false; + + for (wxUint32 i = 0; i < 0xfffff; i++) + { + wxUint32 val = i >> 4; + wxUint32 old = i & 0x0000f; + wxUint32 live = 0; + + for (int j = 0; j < 4; j++) + { + live >>= 1; + + if (((val & 0xf) == 3) || (((val & 0xf) == 2) && (old & 0x1))) + live |= 0x8; + + old >>= 1; + val >>= 4; + } + + g_tab[i] = (unsigned char) live; + } + + return true; +} + +void LifeModule::OnExit() +{ + delete [] g_tab; +} + + +// This table converts from number of neighbors (like in on[]) to +// bits, for a set of four cells. It takes as index a five-digit +// hexadecimal value (0xNNNNB) where Ns hold number of neighbors +// for each cell and B holds their previous state. +// +unsigned char *g_tab; // This table converts from bits (like in live1, live2) to number // of neighbors for each cell in the upper or lower row.