X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/2480be69b159027a3673eee1a4fc4e16287d058d..89b3361ec25cf1e6d255b14c7633d8375646e4fb:/demos/life/game.cpp diff --git a/demos/life/game.cpp b/demos/life/game.cpp index ce51d42bd9..eefae2c2de 100644 --- a/demos/life/game.cpp +++ b/demos/life/game.cpp @@ -10,217 +10,1494 @@ ///////////////////////////////////////////////////////////////////////////// // ========================================================================== -// declarations +// headers, declarations, constants // ========================================================================== -// -------------------------------------------------------------------------- -// headers -// -------------------------------------------------------------------------- - -#ifdef __GNUG__ - #pragma implementation "game.h" -#endif - -// for compilers that support precompilation, includes "wx/wx.h" +// For compilers that support precompilation, includes "wx/wx.h". #include "wx/wxprec.h" #ifdef __BORLANDC__ - #pragma hdrstop +#pragma hdrstop #endif -// for all others, include the necessary headers #ifndef WX_PRECOMP - #include "wx/wx.h" +#include "wx/wx.h" #endif +#include "wx/log.h" +#include "wx/module.h" #include "game.h" +#include // for memset + + +#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 + + // ========================================================================== -// implementation +// CellBox // ========================================================================== -// -------------------------------------------------------------------------- +#define HASH(x, y) (((x >> 3) & 0x7f) << 7) + ((y >> 3) & 0x7f) + +#define HASHSIZE 16384 // hash table size (do not change!) +#define CELLBOX 8 // cells in a cellbox (do not change!) + + +class LifeCellBox +{ +public: + // 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 + 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 LifeCellBox::IsAlive(int dx, int dy) const +{ + if (dy > 3) + return (m_live2 & 1 << ((dy - 4) * 8 + dx)) ? true : false ; + else + 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. +// +bool LifeCellBox::SetCell(int dx, int dy, bool alive) +{ + if (IsAlive(dx, dy) != alive) + { + if (dy > 3) + m_live2 ^= 1 << ((dy - 4) * 8 + dx); + else + m_live1 ^= 1 << ((dy) * 8 + dx); + + // reset this here to avoid updating problems + m_dead = 0; + + return true; + } + else + return false; +} + + +// ========================================================================== // Life +// ========================================================================== + // -------------------------------------------------------------------------- +// Ctor and dtor +// -------------------------------------------------------------------------- + +Life::Life() +{ + // 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; -/* Format of the cell: (32 bit integer) - * - * 0yyyyyyy yyyyyy0x xxxxxxxxx xxx000ff - * - * y = y coordinate (13 bits) - * x = x coordinate (13 bits) - * f = flags (2 bits) - * - * OK, there is a reason for this, I promise :-). But I won't explain - * it now; it will be more clear when I implement the optimized life - * algorithm for large universes. - */ - -Life::Life(int width, int height) -{ - m_wrap = TRUE; - Create(width, height); + // state vars for BeginFind & FindMore + m_cells = new LifeCell[CELLSARRAYSIZE]; + m_ncells = 0; + m_findmore = false; + m_changed = false; } Life::~Life() { - Destroy(); + Clear(); + + delete[] m_boxes; + delete[] m_cells; } -void Life::Create(int width, int height) +// Clear: +// Clears the board, freeing all storage. +// +void Life::Clear() { - wxASSERT(width > 0 && height > 0 && m_cells.IsEmpty()); + LifeCellBox *c, *nc; - m_width = width; - m_height = height; + // clear the hash table pointers + for (int i = 0; i < HASHSIZE; i++) + m_boxes[i] = NULL; - // preallocate memory to speed up initialization - m_cells.Alloc(m_width * m_height); - m_changed.Alloc(1000); + // free used boxes + c = m_head; + while (c) + { + nc = c->m_next; + delete c; + c = nc; + } + m_head = NULL; + + // free available boxes + c = m_available; + while (c) + { + nc = c->m_next; + delete c; + c = nc; + } + m_available = NULL; - // add all cells - for (int j = 0; j < m_height; j++) - for (int i = 0; i < m_width; i++) - m_cells.Add( MakeCell(i, j, FALSE) ); + // reset state + m_name = wxEmptyString; + m_rules = wxEmptyString; + m_description = wxEmptyString; + m_numcells = 0; } -void Life::Destroy() +// -------------------------------------------------------------------------- +// Test and set individual cells +// -------------------------------------------------------------------------- + +// IsAlive: +// Returns whether cell (x, y) is alive. +// +bool Life::IsAlive(wxInt32 x, wxInt32 y) { - m_cells.Clear(); - m_changed.Clear(); + LifeCellBox *c = LinkBox(x, y, false); + + return (c && c->IsAlive( x - c->m_x, y - c->m_y )); } -void Life::Clear() +// SetCell: +// Sets or clears cell (x, y), according to the 'alive' param. +// +void Life::SetCell(wxInt32 x, wxInt32 y, bool alive) { - // set all cells in the array to dead - for (int j = 0; j < m_height; j++) - for (int i = 0; i < m_width; i++) - m_cells[j * m_width + i] &= ~CELL_ALIVE; + LifeCellBox *c = LinkBox(x, y); + wxUint32 dx = x - c->m_x; + wxUint32 dy = y - c->m_y; + + if (c->SetCell(dx, dy, alive)) + { + if (alive) + m_numcells++; + else + m_numcells--; + } } -Cell Life::MakeCell(int i, int j, bool alive) const +void Life::SetPattern(const LifePattern& pattern) { - return (Cell)((j << 18) | (i << 5) | (alive? CELL_ALIVE : CELL_DEAD)); + wxArrayString data = pattern.m_shape; + wxString line; + long x = 0, + y = 0; + + Clear(); + 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; } -bool Life::IsAlive(int i, int j) const +// -------------------------------------------------------------------------- +// Cellbox management functions +// -------------------------------------------------------------------------- + +// CreateBox: +// Creates a box in x, y, either taking it from the list +// of available boxes, or allocating a new one. +// +LifeCellBox* Life::CreateBox(wxInt32 x, wxInt32 y, wxUint32 hv) { - wxASSERT(i >= 0 && j >= 0 && i < m_width && j < m_height); + LifeCellBox *c; + + // if there are no available boxes, alloc a few more + if (!m_available) + for (int i = 1; i <= ALLOCBOXES; i++) + { + c = new LifeCellBox(); + + if (!c) + { + // TODO: handle memory errors. Note that right now, if we + // couldn't allocate at least one cellbox, we will crash + // before leaving CreateBox(). Probably we should try to + // allocate some boxes *before* the m_available list goes + // empty, so that we have a margin to handle errors + // gracefully. + wxLogFatalError(_("Out of memory! Aborting...")); + + // NOTREACHED + } + + c->m_next = m_available; + m_available = c; + } + + // take a cellbox from the list of available boxes + c = m_available; + m_available = c->m_next; + + // reset everything + memset((void *) c, 0, sizeof(LifeCellBox)); + c->m_x = x; + c->m_y = y; + + // insert c in the list + c->m_next = m_head; + m_head = c; + if (c->m_next) c->m_next->m_prev = c; + + // insert c in the hash table + c->m_hnext = m_boxes[hv]; + m_boxes[hv] = c; + if (c->m_hnext) c->m_hnext->m_hprev = c; - return (m_cells[j * m_width + i] & CELL_ALIVE); + return c; } -bool Life::IsAlive(Cell c) const { return (c & CELL_ALIVE); }; -int Life::GetX(Cell c) const { return (c >> 5) & 0x1fff; }; -int Life::GetY(Cell c) const { return (c >> 18); }; +// 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 value +// of the 'create' parameter. +// +LifeCellBox* Life::LinkBox(wxInt32 x, wxInt32 y, bool create) +{ + wxUint32 hv; + LifeCellBox *c; + + x &= 0xfffffff8; + y &= 0xfffffff8; + hv = HASH(x, y); -Cell Life::SetCell(int i, int j, bool alive) + // search in the hash table + 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) : (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(LifeCellBox *c) { - wxASSERT(i >= 0 && j >= 0 && i < m_width && j < m_height); + wxUint32 hv = HASH(c->m_x, c->m_y); - Cell c = MakeCell(i, j, alive); + // remove from the list + if (c != m_head) + c->m_prev->m_next = c->m_next; + else + m_head = c->m_next; - m_cells[j * m_width + i] = c; - return c; + // 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 + 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; + if (c->m_dn) c->m_dn->m_up = NULL; + if (c->m_lf) c->m_lf->m_rt = NULL; + if (c->m_rt) c->m_rt->m_lf = NULL; + + // append to the list of available boxes + c->m_next = m_available; + m_available = c; } -void Life::SetShape(LifeShape& shape) +// -------------------------------------------------------------------------- +// Navigation +// -------------------------------------------------------------------------- + +LifeCell Life::FindCenter() { - wxASSERT((m_width >= shape.m_width) && (m_height >= shape.m_height)); + double sx, sy; + int n; + sx = 0.0; + sy = 0.0; + n = 0; - int i0 = (m_width - shape.m_width) / 2; - int j0 = (m_height - shape.m_height) / 2; - char *p = shape.m_data; + LifeCellBox *c; + for (c = m_head; c; c = c->m_next) + if (!c->m_dead) + { + sx += c->m_x; + sy += c->m_y; + n++; + } - Clear(); - for (int j = j0; j < j0 + shape.m_height; j++) - for (int i = i0; i < i0 + shape.m_width; i++) - SetCell(i, j, *(p++) == '*'); + if (n > 0) + { + sx = (sx / n) + CELLBOX / 2; + sy = (sy / n) + CELLBOX / 2; + } + + LifeCell cell; + cell.i = (wxInt32) sx; + cell.j = (wxInt32) sy; + return cell; } -bool Life::NextTic() +LifeCell Life::FindNorth() { - int i, j; + 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))) + { + 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; +} - m_changed.Empty(); +LifeCell Life::FindSouth() +{ + wxInt32 x = 0, y = 0; + bool first = true; - /* 1st pass. Find and mark deaths and births for this generation. - * - * Rules: - * An organism with <= 1 neighbors will die due to isolation. - * An organism with >= 4 neighbors will die due to starvation. - * New organisms are born in cells with exactly 3 neighbors. - */ - for (j = 0; j < m_height; j++) - for (i = 0; i < m_width; i++) + LifeCellBox *c; + for (c = m_head; c; c = c->m_next) + if (!c->m_dead && ((first) || (c->m_y > y))) { - int neighbors = GetNeighbors(i, j); - bool alive = IsAlive(i, j); + x = c->m_x; + y = c->m_y; + first = false; + } - /* Set CELL_MARK if this cell must change, clear it - * otherwise. We cannot toggle the CELL_ALIVE bit yet - * because all deaths and births are simultaneous (it - * would affect neighbouring cells). - */ - if ((!alive && neighbors == 3) || - (alive && (neighbors <= 1 || neighbors >= 4))) - { - m_cells[j * m_width + i] |= CELL_MARK; - m_changed.Add( MakeCell(i, j, !alive) ); - } - else - m_cells[j * m_width + i] &= ~CELL_MARK; + 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; } - /* 2nd pass. Stabilize. - */ - for (j = 0; j < m_height; j++) - for (i = 0; i < m_width; i++) + 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))) { - /* Toggle CELL_ALIVE for those cells marked in the - * previous pass. Do not clear the CELL_MARK bit yet; - * it is useful to know which cells have changed and - * thus must be updated in the screen. - */ - if (m_cells[j * m_width + i] & CELL_MARK) - m_cells[j * m_width + i] ^= CELL_ALIVE; + x = c->m_x; + y = c->m_y; + first = false; } - return (!m_changed.IsEmpty()); + LifeCell cell; + cell.i = first? 0 : x + CELLBOX / 2; + cell.j = first? 0 : y + CELLBOX / 2; + return cell; } -int Life::GetNeighbors(int x, int y) const +// -------------------------------------------------------------------------- +// 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) { - wxASSERT(x >= 0 && y >= 0 && x < m_width && y < m_height); + wxUint32 diff = (live ^ old) & 0xff; - int neighbors = 0; + if (!diff) return; - int i0 = (x)? (x - 1) : 0; - int j0 = (y)? (y - 1) : 0; - int i1 = (x < (m_width - 1))? (x + 1) : (m_width - 1); - int j1 = (y < (m_height - 1))? (y + 1) : (m_height - 1); + for (wxInt32 k = 8; k; k--, x++) + { + if (diff & 0x01) + { + m_cells[m_ncells].i = x; + m_cells[m_ncells].j = y; + m_ncells++; + } + diff >>= 1; + } +} + +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. - if (m_wrap && ( !x || !y || x == (m_width - 1) || y == (m_height - 1))) + 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(LifeCell *cells[], size_t *ncells) +{ + LifeCellBox *c; + *cells = m_cells; + m_ncells = 0; + + if (m_changed) { - // this is an outer cell and wraparound is on - for (int j = y - 1; j <= y + 1; j++) - for (int i = x - 1; i <= x + 1; i++) - if (IsAlive( ((i < 0)? (i + m_width ) : (i % m_width)), - ((j < 0)? (j + m_height) : (j % m_height)) )) - neighbors++; + for ( ; m_y <= m_y1; m_y += 8, m_x = m_x0) + for ( ; m_x <= m_x1; m_x += 8) + { + if ((c = LinkBox(m_x, m_y, false)) == NULL) + continue; + + // check whether there is enough space left in the array + if (m_ncells > (CELLSARRAYSIZE - 64)) + { + *ncells = m_ncells; + return false; + } + + 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 { - // this is an inner cell, or wraparound is off - for (int j = j0; j <= j1; j++) - for (int i = i0; i <= i1; i++) - if (IsAlive(i, j)) - neighbors++; + for ( ; m_y <= m_y1; m_y += 8, m_x = m_x0) + for ( ; m_x <= m_x1; m_x += 8) + { + if ((c = LinkBox(m_x, m_y, false)) == NULL) + continue; + + // check whether there is enough space left in the array + if (m_ncells > (CELLSARRAYSIZE - 64)) + { + *ncells = m_ncells; + return false; + } + + 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; +} + +// -------------------------------------------------------------------------- +// Evolution engine +// -------------------------------------------------------------------------- + +extern unsigned char *g_tab; +extern int g_tab1[]; +extern int g_tab2[]; + +// NextTic: +// Advance one step in evolution :-) +// +bool Life::NextTic() +{ + LifeCellBox *c, *up, *dn, *lf, *rt; + wxUint32 t1, t2, t3, t4; + 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) + { + if (! (c->m_live1 || c->m_live2)) + { + c = c->m_next; + continue; + } + up = c->m_up; + dn = c->m_dn; + lf = c->m_lf; + rt = c->m_rt; + + // up + t1 = c->m_live1 & 0x000000ff; + if (t1) + { + if (!up) + { + up = LinkBox(c->m_x, c->m_y - 8); + up->m_dn = c; + } + t2 = g_tab1[t1]; + up->m_on[7] += t2; + c->m_on[1] += t2; + c->m_on[0] += g_tab2[t1]; + } + + // down + t1 = (c->m_live2 & 0xff000000) >> 24; + if (t1) + { + if (!dn) + { + dn = LinkBox(c->m_x, c->m_y + 8); + dn->m_up = c; + } + t2 = g_tab1[t1]; + dn->m_on[0] += 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->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->m_dn = lf; + } + lf->m_up->m_on[7] += 0x10000000; + lf->m_on[0] += 0x10000000; + lf->m_on[1] += 0x10000000; + } + if (t1 & 0x00000100) + { + 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; + } + if (t1 & 0x01000000) + { + 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->m_rt = c; + } + if (t2 & 0x00000001) + { + 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; + } + if (t2 & 0x00010000) + { + lf->m_on[5] += 0x10000000; + lf->m_on[6] += 0x10000000; + lf->m_on[7] += 0x10000000; + } + if (t2 & 0x01000000) + { + if (!lf->m_dn) + { + lf->m_dn = LinkBox(c->m_x - 8, c->m_y + 8); + lf->m_dn->m_up = lf; + } + lf->m_on[6] += 0x10000000; + lf->m_on[7] += 0x10000000; + lf->m_dn->m_on[0] += 0x10000000; + } + } + + // right + if (t1 & 0x80808080) + { + if (!rt) + { + 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->m_dn = rt; + } + rt->m_up->m_on[7] += 0x00000001; + rt->m_on[0] += 0x00000001; + rt->m_on[1] += 0x00000001; + } + if (t1 & 0x00008000) + { + 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; + } + if (t1 & 0x80000000) + { + 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->m_lf = c; + } + if (t2 & 0x00000080) + { + 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; + } + if (t2 & 0x00800000) + { + rt->m_on[5] += 0x00000001; + rt->m_on[6] += 0x00000001; + rt->m_on[7] += 0x00000001; + } + if (t2 & 0x80000000) + { + if (!rt->m_dn) + { + rt->m_dn = LinkBox(c->m_x + 8, c->m_y + 8); + rt->m_dn->m_up = rt; + } + rt->m_on[6] += 0x00000001; + rt->m_on[7] += 0x00000001; + rt->m_dn->m_on[0] += 0x00000001; + } + } + + // inner cells + int i; + for (i = 1; i <= 3; i++) + { + t1 = ((c->m_live1) >> (i * 8)) & 0x000000ff; + if (t1) + { + c->m_on[i - 1] += g_tab1[t1]; + c->m_on[i ] += g_tab2[t1]; + c->m_on[i + 1] += g_tab1[t1]; + } + } + for (i = 0; i <= 2; i++) + { + t1 = ((c->m_live2) >> (i * 8)) & 0x000000ff; + if (t1) + { + c->m_on[i + 3] += g_tab1[t1]; + c->m_on[i + 4] += g_tab2[t1]; + c->m_on[i + 5] += g_tab1[t1]; + } + } + + c->m_up = up; + c->m_dn = dn; + c->m_lf = lf; + c->m_rt = rt; + c = c->m_next; + } + + // Stage 2: + // Stabilize + // + c = m_head; + + while (c) + { + t1 = 0; + t2 = 0; + + 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; + + // count alive cells +#if 1 + wxUint32 t1_, t2_; + + 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++; + } +#endif + + changed |= ((t1 ^ c->m_old1) || (t2 ^ c->m_old2)); + + // mark, and discard if necessary, dead boxes + if (t1 || t2) + { + c->m_dead = 0; + c = c->m_next; + } + else + { + LifeCellBox *aux = c->m_next; + if (c->m_dead++ > MAXDEAD) + KillBox(c); + + c = aux; + } + } + + return changed; +} + +// ========================================================================== +// 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; } - // do not count ourselves - if (IsAlive(x, y)) neighbors--; + return true; +} - return neighbors; +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. +// +int g_tab1[]= +{ + 0x00000000, + 0x00000011, + 0x00000111, + 0x00000122, + 0x00001110, + 0x00001121, + 0x00001221, + 0x00001232, + 0x00011100, + 0x00011111, + 0x00011211, + 0x00011222, + 0x00012210, + 0x00012221, + 0x00012321, + 0x00012332, + 0x00111000, + 0x00111011, + 0x00111111, + 0x00111122, + 0x00112110, + 0x00112121, + 0x00112221, + 0x00112232, + 0x00122100, + 0x00122111, + 0x00122211, + 0x00122222, + 0x00123210, + 0x00123221, + 0x00123321, + 0x00123332, + 0x01110000, + 0x01110011, + 0x01110111, + 0x01110122, + 0x01111110, + 0x01111121, + 0x01111221, + 0x01111232, + 0x01121100, + 0x01121111, + 0x01121211, + 0x01121222, + 0x01122210, + 0x01122221, + 0x01122321, + 0x01122332, + 0x01221000, + 0x01221011, + 0x01221111, + 0x01221122, + 0x01222110, + 0x01222121, + 0x01222221, + 0x01222232, + 0x01232100, + 0x01232111, + 0x01232211, + 0x01232222, + 0x01233210, + 0x01233221, + 0x01233321, + 0x01233332, + 0x11100000, + 0x11100011, + 0x11100111, + 0x11100122, + 0x11101110, + 0x11101121, + 0x11101221, + 0x11101232, + 0x11111100, + 0x11111111, + 0x11111211, + 0x11111222, + 0x11112210, + 0x11112221, + 0x11112321, + 0x11112332, + 0x11211000, + 0x11211011, + 0x11211111, + 0x11211122, + 0x11212110, + 0x11212121, + 0x11212221, + 0x11212232, + 0x11222100, + 0x11222111, + 0x11222211, + 0x11222222, + 0x11223210, + 0x11223221, + 0x11223321, + 0x11223332, + 0x12210000, + 0x12210011, + 0x12210111, + 0x12210122, + 0x12211110, + 0x12211121, + 0x12211221, + 0x12211232, + 0x12221100, + 0x12221111, + 0x12221211, + 0x12221222, + 0x12222210, + 0x12222221, + 0x12222321, + 0x12222332, + 0x12321000, + 0x12321011, + 0x12321111, + 0x12321122, + 0x12322110, + 0x12322121, + 0x12322221, + 0x12322232, + 0x12332100, + 0x12332111, + 0x12332211, + 0x12332222, + 0x12333210, + 0x12333221, + 0x12333321, + 0x12333332, + 0x11000000, + 0x11000011, + 0x11000111, + 0x11000122, + 0x11001110, + 0x11001121, + 0x11001221, + 0x11001232, + 0x11011100, + 0x11011111, + 0x11011211, + 0x11011222, + 0x11012210, + 0x11012221, + 0x11012321, + 0x11012332, + 0x11111000, + 0x11111011, + 0x11111111, + 0x11111122, + 0x11112110, + 0x11112121, + 0x11112221, + 0x11112232, + 0x11122100, + 0x11122111, + 0x11122211, + 0x11122222, + 0x11123210, + 0x11123221, + 0x11123321, + 0x11123332, + 0x12110000, + 0x12110011, + 0x12110111, + 0x12110122, + 0x12111110, + 0x12111121, + 0x12111221, + 0x12111232, + 0x12121100, + 0x12121111, + 0x12121211, + 0x12121222, + 0x12122210, + 0x12122221, + 0x12122321, + 0x12122332, + 0x12221000, + 0x12221011, + 0x12221111, + 0x12221122, + 0x12222110, + 0x12222121, + 0x12222221, + 0x12222232, + 0x12232100, + 0x12232111, + 0x12232211, + 0x12232222, + 0x12233210, + 0x12233221, + 0x12233321, + 0x12233332, + 0x22100000, + 0x22100011, + 0x22100111, + 0x22100122, + 0x22101110, + 0x22101121, + 0x22101221, + 0x22101232, + 0x22111100, + 0x22111111, + 0x22111211, + 0x22111222, + 0x22112210, + 0x22112221, + 0x22112321, + 0x22112332, + 0x22211000, + 0x22211011, + 0x22211111, + 0x22211122, + 0x22212110, + 0x22212121, + 0x22212221, + 0x22212232, + 0x22222100, + 0x22222111, + 0x22222211, + 0x22222222, + 0x22223210, + 0x22223221, + 0x22223321, + 0x22223332, + 0x23210000, + 0x23210011, + 0x23210111, + 0x23210122, + 0x23211110, + 0x23211121, + 0x23211221, + 0x23211232, + 0x23221100, + 0x23221111, + 0x23221211, + 0x23221222, + 0x23222210, + 0x23222221, + 0x23222321, + 0x23222332, + 0x23321000, + 0x23321011, + 0x23321111, + 0x23321122, + 0x23322110, + 0x23322121, + 0x23322221, + 0x23322232, + 0x23332100, + 0x23332111, + 0x23332211, + 0x23332222, + 0x23333210, + 0x23333221, + 0x23333321, + 0x23333332 +}; + +// This table converts from bits (like in live1, live2) to number +// of neighbors for each cell in the same row (excluding ourselves) +// +int g_tab2[]= +{ + 0x00000000, + 0x00000010, + 0x00000101, + 0x00000111, + 0x00001010, + 0x00001020, + 0x00001111, + 0x00001121, + 0x00010100, + 0x00010110, + 0x00010201, + 0x00010211, + 0x00011110, + 0x00011120, + 0x00011211, + 0x00011221, + 0x00101000, + 0x00101010, + 0x00101101, + 0x00101111, + 0x00102010, + 0x00102020, + 0x00102111, + 0x00102121, + 0x00111100, + 0x00111110, + 0x00111201, + 0x00111211, + 0x00112110, + 0x00112120, + 0x00112211, + 0x00112221, + 0x01010000, + 0x01010010, + 0x01010101, + 0x01010111, + 0x01011010, + 0x01011020, + 0x01011111, + 0x01011121, + 0x01020100, + 0x01020110, + 0x01020201, + 0x01020211, + 0x01021110, + 0x01021120, + 0x01021211, + 0x01021221, + 0x01111000, + 0x01111010, + 0x01111101, + 0x01111111, + 0x01112010, + 0x01112020, + 0x01112111, + 0x01112121, + 0x01121100, + 0x01121110, + 0x01121201, + 0x01121211, + 0x01122110, + 0x01122120, + 0x01122211, + 0x01122221, + 0x10100000, + 0x10100010, + 0x10100101, + 0x10100111, + 0x10101010, + 0x10101020, + 0x10101111, + 0x10101121, + 0x10110100, + 0x10110110, + 0x10110201, + 0x10110211, + 0x10111110, + 0x10111120, + 0x10111211, + 0x10111221, + 0x10201000, + 0x10201010, + 0x10201101, + 0x10201111, + 0x10202010, + 0x10202020, + 0x10202111, + 0x10202121, + 0x10211100, + 0x10211110, + 0x10211201, + 0x10211211, + 0x10212110, + 0x10212120, + 0x10212211, + 0x10212221, + 0x11110000, + 0x11110010, + 0x11110101, + 0x11110111, + 0x11111010, + 0x11111020, + 0x11111111, + 0x11111121, + 0x11120100, + 0x11120110, + 0x11120201, + 0x11120211, + 0x11121110, + 0x11121120, + 0x11121211, + 0x11121221, + 0x11211000, + 0x11211010, + 0x11211101, + 0x11211111, + 0x11212010, + 0x11212020, + 0x11212111, + 0x11212121, + 0x11221100, + 0x11221110, + 0x11221201, + 0x11221211, + 0x11222110, + 0x11222120, + 0x11222211, + 0x11222221, + 0x01000000, + 0x01000010, + 0x01000101, + 0x01000111, + 0x01001010, + 0x01001020, + 0x01001111, + 0x01001121, + 0x01010100, + 0x01010110, + 0x01010201, + 0x01010211, + 0x01011110, + 0x01011120, + 0x01011211, + 0x01011221, + 0x01101000, + 0x01101010, + 0x01101101, + 0x01101111, + 0x01102010, + 0x01102020, + 0x01102111, + 0x01102121, + 0x01111100, + 0x01111110, + 0x01111201, + 0x01111211, + 0x01112110, + 0x01112120, + 0x01112211, + 0x01112221, + 0x02010000, + 0x02010010, + 0x02010101, + 0x02010111, + 0x02011010, + 0x02011020, + 0x02011111, + 0x02011121, + 0x02020100, + 0x02020110, + 0x02020201, + 0x02020211, + 0x02021110, + 0x02021120, + 0x02021211, + 0x02021221, + 0x02111000, + 0x02111010, + 0x02111101, + 0x02111111, + 0x02112010, + 0x02112020, + 0x02112111, + 0x02112121, + 0x02121100, + 0x02121110, + 0x02121201, + 0x02121211, + 0x02122110, + 0x02122120, + 0x02122211, + 0x02122221, + 0x11100000, + 0x11100010, + 0x11100101, + 0x11100111, + 0x11101010, + 0x11101020, + 0x11101111, + 0x11101121, + 0x11110100, + 0x11110110, + 0x11110201, + 0x11110211, + 0x11111110, + 0x11111120, + 0x11111211, + 0x11111221, + 0x11201000, + 0x11201010, + 0x11201101, + 0x11201111, + 0x11202010, + 0x11202020, + 0x11202111, + 0x11202121, + 0x11211100, + 0x11211110, + 0x11211201, + 0x11211211, + 0x11212110, + 0x11212120, + 0x11212211, + 0x11212221, + 0x12110000, + 0x12110010, + 0x12110101, + 0x12110111, + 0x12111010, + 0x12111020, + 0x12111111, + 0x12111121, + 0x12120100, + 0x12120110, + 0x12120201, + 0x12120211, + 0x12121110, + 0x12121120, + 0x12121211, + 0x12121221, + 0x12211000, + 0x12211010, + 0x12211101, + 0x12211111, + 0x12212010, + 0x12212020, + 0x12212111, + 0x12212121, + 0x12221100, + 0x12221110, + 0x12221201, + 0x12221211, + 0x12222110, + 0x12222120, + 0x12222211, + 0x12222221 +};