Here is a detailed description of the algorithm used to grow from one generation to the next, and the associated data structure. Since the code below is based on the actual code in Winlife32, but with various implementation details removed for clarity, it cannot be compiled but should give the general idea fairly clearly.
Live cells are represented as arrays of X-coordinates, with one array for each row contaning any live cells. The last entry of each row is a dummy whose value is higher than any possible coordinate. The structure looks like this.
typedef UINT coord_t;
const UINT maxCoord = UINTMAX-1;
struct row_t {
row_t *rNext; // Next row in universe
UINT rPop; // Population of row
coord_t rNum; // Number (coordinate) of row
coord_t rCell[1]; // First cell
};
Memory management and allocation is actually quite complicated if it is to be efficient, but for now we assume the existence of a function makeRow that creates a row of adequate size, without worrying about the details. We also assume a function addRow which adds a row to the universe under construction.
There are two nested loops that drive the algorithm. The outer loop is executed once per row. The inner loop is executed once per possible new cell.
At the outer level, we keep track of which rows actually exist through the rowState variable. There is a one for each row which exists, and a zero for rows which are empty. This is only used so that we can correctly manipulate the row pointers: prevR, thisR, nextR.
Within a row, we keep three cell pointers into the respective rows: prevC, thisC, nextC. These actually point to the next live cell after the current candidate. Thus if we are currently considering the cell at X-coordinate 73, these will point to the next live cell whose coordinate is greater than 73 (or the terminator). The state of the candidate cell is recorded in colState, which has three fields of three bits each, corresponding to the three neighbor cells in the three adjacent rows. Moving to the next cell can therefore be done by masking the "previous cell" bits and shifting left. The decision as to whether a cell should be alive or not is then a lookup of colState in a 512-entry array. Thus the algorithm does not depend on any particular rules.
// ----------------------------------------------------------------------
// Grow a universe.
//
// We run the same algorithm for each possible output row. A row is
// "possible" if at least one of itself and its neighbours is non-null
// (i.e. has a population). We keep track of the rows in a state
// variable, which is modified according to the next row. If one or more
// of the relevant rows is null, we set the corresponding pointer to a
// special dummy row which has no valid cells in it.
//
// Once we have identified the neighbour rows, we allocate space for the
// row to be grown. This is big enough to hold the maximum population of
// the row, which is equal to the sum of the populations of the three
// rows.
//
// Then we pass down the row. In a technique similar to that used for the
// rows, we keep a state variable for each row showing which neighbours
// are alive. (For speed, these are combined into a single variable). This
// combined state variable is looked up in the growth table to decide both
// what to do and the next state.
// ----------------------------------------------------------------------
void grow() {
row_t *row = getFirstRow();
row_t *prevR, *thisR, *nextR=NULL;
row_t *newR; // row under construction
row_t *prevNewR=NULL;
coord_t *prevC, *thisC, *nextC;
coord_t *newC; // next cell in row under construction
coord_t rowNo = lowestCoord;
coord_t colNoPlus1;
enum rowStates { rs_000=0, rs_001, rs_010, rs_011, rs_100, rs_101,
rs_110, rs_111 };
int rowState=rs_000;
int colState;
if (row!=NULL) {
//
// First deal with the row state. This is a bit vector whose bits
// represent whether or not the corresponding row was null or not. In
// effect we shift the bits left by one, and adjust the row points
// accordingly. Afterwards, we look to see whether the "real" row pointer,
// which always points to the next non-null row after the one we are
// dealing with, is actually the next row. This determines the "new"
// (lowest) bit of the next state. Note the invariant that if the low bit
// of the state is 1, then row=nextR...
for (;;) {
switch(rowState) {
case rs_000: // no local rows left, move on to close gap
case rs_100:
if (row==&dummyRow)
goto allRowsDone; // break out of for loop if all done
rowNo=row->RowNum()-1;
thisR=prevR=&dummyRow;
rowState=rs_000;
break;
case rs_001:
case rs_101:
rowNo ;
prevR=&dummyRow;
thisR=nextR;
row=row->rNext;
rowState=rs_010;
break;
case rs_010:
case rs_110:
rowNo ;
prevR=thisR;
thisR=&dummyRow;
rowState=rs_100;
break;
case rs_011:
case rs_111:
rowNo ;
prevR=thisR;
thisR=nextR;
row=row->rNext;
rowState=rs_110;
break;
};
if (row==NULL) // if now at the end...
row=&dummyRow; // point to the dummy
if (row->RowNum() == rowNo 1) {
rowState ;
nextR=row;
} else {
nextR=&dummyRow;
};
prevC=prevR->RowCell(); // set the cell pointers, that move
thisC=thisR->RowCell(); // down the rows
nextC=nextR->RowCell();
newR = makeRow();
newC = newRow->rCell;
colState=0;
for (;;) {
if (colState==0) { // advance to next interesting cell
colNoPlus1=min(*prevC, *thisC, *nextC);
if (colNoPlus1==endRowMarker)
break; // finished the row
};
if (*prevC==colNoPlus1) {
prevC ;
colState = 1<<6;
};
if (*thisC==colNoPlus1) {
thisC ;
colState = 1<<3;
};
if (*nextC==colNoPlus1) {
nextC ;
colState = 1;
};
if (growthRule[colState]) {
*newC = colNoPlus1-1;
newR->rPop;
};
colState = (colState & ((0x3<<6) (0x3<<3) 0x3) << 1; // just keep bits for this and next cell
colNoPlus1 ;
};
*newC = maxCoord 1;
addRow(newR);
}
}
};