#pragma implementation "game.h"
#endif
+// 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 <stdlib.h> // for abort
#include <string.h> // for memset
-#define ARRAYSIZE 1024 // size of the static arrays for BeginFind & co.
+#define ARRAYSIZE 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)
{
// reset this here to avoid updating problems
m_dead = 0;
- return TRUE;
+ return true;
}
else
- return FALSE;
+ return false;
}
// --------------------------------------------------------------------------
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[ARRAYSIZE];
+ m_ncells = 0;
+ m_findmore = false;
+ m_changed = false;
}
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;
{
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;
}
// --------------------------------------------------------------------------
//
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 ));
}
//
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;
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;
}
// --------------------------------------------------------------------------
// --------------------------------------------------------------------------
// 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)
{
// 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;
}
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;
// 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;
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);
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;
}
// --------------------------------------------------------------------------
-// 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;
+}
+
+LifeCell Life::FindSouth()
+{
+ 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;
+}
+
+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;
}
-
-// Post eight cells to the cell arrays (alive cells only)
-void Life::DoLine(wxInt32 i, wxInt32 j, wxUint32 live)
+
+// --------------------------------------------------------------------------
+// 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)
{
- if (! (live & 0x000000ff)) return;
+ wxUint32 diff = (live ^ old) & 0xff;
+
+ if (!diff) return;
- for (wxInt32 k = 8; k; k--, i++)
+ 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))
{
*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))
{
*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)
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];
}
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;
}
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;
{
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;
}
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;
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)
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)
// 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;
}
}
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.
projects / wxWidgets.git / blobdiff