demos/life/game.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        game.cpp
   3 // Purpose:     Life! game logic
   4 // Author:      Guillermo Rodriguez Garcia, <guille@iies.es>
   5 // Modified by:
   6 // Created:     Jan/2000
   7 // RCS-ID:      $Id$
   8 // Copyright:   (c) 2000, Guillermo Rodriguez Garcia
   9 // Licence:     wxWindows licence
  10 /////////////////////////////////////////////////////////////////////////////
  11
  12 // ==========================================================================
  13 // declarations
  14 // ==========================================================================
  15
  16 // --------------------------------------------------------------------------
  17 // headers
  18 // --------------------------------------------------------------------------
  19
  20 #ifdef __GNUG__
  21     #pragma implementation "game.h"
  22 #endif
  23
  24 // for compilers that support precompilation, includes "wx/wx.h"
  25 #include "wx/wxprec.h"
  26
  27 #ifdef __BORLANDC__
  28     #pragma hdrstop
  29 #endif
  30
  31 // for all others, include the necessary headers
  32 #ifndef WX_PRECOMP
  33     #include "wx/wx.h"
  34 #endif
  35
  36 #include "game.h"
  37
  38 // ==========================================================================
  39 // implementation
  40 // ==========================================================================
  41
  42 // --------------------------------------------------------------------------
  43 // Life
  44 // --------------------------------------------------------------------------
  45
  46 /* Format of the cell: (32 bit integer)
  47  *
  48  * 0yyyyyyy yyyyyy0x xxxxxxxxx xxx000ff
  49  *
  50  * y = y coordinate (13 bits)
  51  * x = x coordinate (13 bits)
  52  * f = flags (2 bits)
  53  *
  54  * OK, there is a reason for this, I promise :-). But I won't explain
  55  * it now; it will be more clear when I implement the optimized life
  56  * algorithm for large universes.
  57  */
  58
  59 Life::Life(int width, int height)
  60 {
  61     m_wrap = TRUE;
  62     Create(width, height);
  63 }
  64
  65 Life::~Life()
  66 {
  67     Destroy();
  68 }
  69
  70 void Life::Create(int width, int height)
  71 {
  72     wxASSERT(width > 0 && height > 0 && m_cells.IsEmpty());
  73
  74     m_width = width;
  75     m_height = height;
  76
  77     // preallocate memory to speed up initialization
  78     m_cells.Alloc(m_width * m_height);
  79     m_changed.Alloc(1000);
  80
  81     // add all cells
  82     for (int j = 0; j < m_height; j++)
  83         for (int i = 0; i < m_width; i++)
  84             m_cells.Add( MakeCell(i, j, FALSE) );
  85 }
  86
  87 void Life::Destroy()
  88 {
  89     m_cells.Clear();
  90     m_changed.Clear();
  91 }
  92
  93 void Life::Clear()
  94 {
  95     // set all cells in the array to dead
  96     for (int j = 0; j < m_height; j++)
  97         for (int i = 0; i < m_width; i++)
  98             m_cells[j * m_width + i] &= ~CELL_ALIVE;
  99 }
 100
 101 Cell Life::MakeCell(int i, int j, bool alive) const
 102 {
 103     return (Cell)((j << 18) | (i << 5) | (alive? CELL_ALIVE : CELL_DEAD));
 104 }
 105
 106 bool Life::IsAlive(int i, int j) const
 107 {
 108     wxASSERT(i >= 0 && j >= 0 && i < m_width && j < m_height);
 109
 110     return (m_cells[j * m_width + i] & CELL_ALIVE);
 111 }
 112
 113 bool Life::IsAlive(Cell c) const { return (c & CELL_ALIVE); };
 114 int  Life::GetX(Cell c) const    { return (c >> 5) & 0x1fff; };
 115 int  Life::GetY(Cell c) const    { return (c >> 18); };
 116
 117 Cell Life::SetCell(int i, int j, bool alive)
 118 {
 119     wxASSERT(i >= 0 && j >= 0 && i < m_width && j < m_height);
 120
 121     Cell c = MakeCell(i, j, alive);
 122
 123     m_cells[j * m_width + i] = c;
 124     return c;
 125 }
 126
 127 void Life::SetShape(LifeShape& shape)
 128 {
 129     wxASSERT((m_width >= shape.m_width) && (m_height >= shape.m_height));
 130
 131     int i0  = (m_width - shape.m_width) / 2;
 132     int j0  = (m_height - shape.m_height) / 2;
 133     char *p = shape.m_data;
 134
 135     Clear();
 136     for (int j = j0; j < j0 + shape.m_height; j++)
 137         for (int i = i0; i < i0 + shape.m_width; i++)
 138             SetCell(i, j, *(p++) == '*');
 139 }
 140
 141 bool Life::NextTic()
 142 {
 143     int i, j;
 144
 145     m_changed.Empty();
 146
 147     /* 1st pass. Find and mark deaths and births for this generation.
 148      *
 149      * Rules:
 150      *   An organism with <= 1 neighbors will die due to isolation.
 151      *   An organism with >= 4 neighbors will die due to starvation.
 152      *   New organisms are born in cells with exactly 3 neighbors.
 153      */
 154     for (j = 0; j < m_height; j++)
 155         for (i = 0; i < m_width; i++)
 156         {
 157             int neighbors = GetNeighbors(i, j);
 158             bool alive    = IsAlive(i, j);
 159
 160             /* Set CELL_MARK if this cell must change, clear it
 161              * otherwise. We cannot toggle the CELL_ALIVE bit yet
 162              * because all deaths and births are simultaneous (it
 163              * would affect neighbouring cells).
 164              */
 165             if ((!alive && neighbors == 3) ||
 166                 (alive && (neighbors <= 1 || neighbors >= 4)))
 167             {
 168                 m_cells[j * m_width + i] |= CELL_MARK;
 169                 m_changed.Add( MakeCell(i, j, !alive) );
 170             }
 171             else
 172                 m_cells[j * m_width + i] &= ~CELL_MARK;
 173         }
 174
 175     /* 2nd pass. Stabilize.
 176      */
 177     for (j = 0; j < m_height; j++)
 178         for (i = 0; i < m_width; i++)
 179         {
 180             /* Toggle CELL_ALIVE for those cells marked in the
 181              * previous pass. Do not clear the CELL_MARK bit yet;
 182              * it is useful to know which cells have changed and
 183              * thus must be updated in the screen.
 184              */
 185             if (m_cells[j * m_width + i] & CELL_MARK)
 186                 m_cells[j * m_width + i] ^= CELL_ALIVE;
 187         }
 188
 189     return (!m_changed.IsEmpty());
 190 }
 191
 192 int Life::GetNeighbors(int x, int y) const
 193 {
 194     wxASSERT(x >= 0 && y >= 0 && x < m_width && y < m_height);
 195
 196     int neighbors = 0;
 197
 198     int i0 = (x)? (x - 1) : 0;
 199     int j0 = (y)? (y - 1) : 0;
 200     int i1 = (x < (m_width - 1))? (x + 1) : (m_width - 1);
 201     int j1 = (y < (m_height - 1))? (y + 1) : (m_height - 1);
 202
 203     if (m_wrap && ( !x || !y || x == (m_width - 1) || y == (m_height - 1)))
 204     {
 205         // this is an outer cell and wraparound is on
 206         for (int j = y - 1; j <= y + 1; j++)
 207             for (int i = x - 1; i <= x + 1; i++)
 208                 if (IsAlive( ((i < 0)? (i + m_width ) : (i % m_width)),
 209                              ((j < 0)? (j + m_height) : (j % m_height)) ))
 210                      neighbors++;
 211     }
 212     else
 213     {
 214         // this is an inner cell, or wraparound is off
 215         for (int j = j0; j <= j1; j++)
 216             for (int i = i0; i <= i1; i++)
 217                 if (IsAlive(i, j))
 218                      neighbors++;
 219     }
 220
 221     // do not count ourselves
 222     if (IsAlive(x, y)) neighbors--;
 223
 224     return neighbors;
 225 }
 226