// John Horton Conway's game of Life. // Modified to automatically find glider patterns. // Michael Ashley / UNSW / 23-May-2003 #define displayWidth (8*80) #define displayHeight (8*24) #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <unistd.h> #include <sys/time.h> /* Each cell has a value of 0 or 1. The value of a cell in the next generation depends on its current value, and the sum of the values of the neighbouring 8 cells. The rules are: Death: If an occupied cell has 0, 1, 4, 5, 6, 7, or 8 occupied neighbours, the organism dies (0, 1 neighbours: of loneliness; 4 thru 8: of overcrowding). Survival: If an occupied cell has two or three neighbours, the organism survives to the next generation. Birth: If an unoccupied cell has three occupied neighbours, it becomes occupied. These rules can be written in terms of a 2D array, where the first index is either 0 or 1 depending on the value of cell under consideration, and the second index ranges from 0 to 8 inclusive, and is the number of occupied nearest neighbours. The value of the array gives the state of the cell in the next generation. */ int rule[2][9] = {{0,0,0,1,0,0,0,0,0}, {0,0,1,1,0,0,0,0,0}}; /* Now we create a type that contains all the information we need to know about the state of the system. */ typedef struct { unsigned char cell[displayHeight][displayWidth]; } state; void initialise(state * s) { // Initialises the state pointed to by s. This is where we put our // initial conditions. int i, j; struct timeval t; // Zero the state. for (i = 0; i < displayHeight; i++) { for (j = 0; j < displayWidth; j++) { s->cell[i][j] = 0; } } #if 0 // A "glider" pattern. s->cell[40][10] = 1; s->cell[41][10] = 1; s->cell[42][10] = 1; s->cell[42][11] = 1; s->cell[41][12] = 1; #endif // A random pattern. // Obtain the time of day, to microsecond resolution. assert(0 == gettimeofday(&t, NULL)); // Use the number of microseconds as the seed for the system // random number generator. srandom(t.tv_usec); // Here we randomly choose 1/2th of the cells to be alive, // within a central region of the state. for (i = 3*displayHeight/8; i < 5*displayHeight/8; i++) { for (j = 3*displayWidth/8; j < 5*displayWidth/8; j++) { s->cell[i][j] = random() > 4*(RAND_MAX/8); } } } void displayState(state * s, int i, int j) { // Displays up to a 20x20 pixel box including cell [i][j] of state // *s using ASCII characters. int iMin, iMax, jMin, jMax; iMin = i - 10; if (iMin < 0) iMin = 0; jMin = j - 10; if (jMin < 0) jMin = 0; iMax = i + 10; if (iMax >= displayHeight) iMax = displayHeight-1; jMax = j + 10; if (jMax >= displayWidth) jMax = displayWidth-1; for (i = iMin; i < iMax; i++) { for (j = jMin; j < jMax; j++) { if (s->cell[i][j]) { printf("*"); } else { printf(" "); } } printf("\n"); } } inline int nearestNeighbours(state *s, int i, int j) { // Returns the number of nearest neighbours in the state *s at // location [i][j]. We just sum up the neighbouring 8 cells, with // careful allowance for hitting the boundary. return (i > 0 && j > 0 && s->cell[i-1][j-1]) + (i > 0 && s->cell[i-1][j] ) + (i > 0 && j < displayWidth-1 && s->cell[i-1][j+1]) + ( j > 0 && s->cell[i] [j-1]) + ( j < displayWidth-1 && s->cell[i] [j+1]) + (i < displayHeight-1 && j > 0 && s->cell[i+1][j-1]) + (i < displayHeight-1 && s->cell[i+1][j] ) + (i < displayHeight-1 && j < displayWidth-1 && s->cell[i+1][j+1]); } inline int nearestNeighbours2(state *s, int i, int j) { // Returns the number of nearest neighbours in the state *s at // location [i][j], assuming that we are at least one cell away // from the boundary. return s->cell[i-1][j-1] + s->cell[i-1][j] + s->cell[i-1][j+1] + s->cell[i] [j-1] + s->cell[i] [j+1] + s->cell[i+1][j-1] + s->cell[i+1][j] + s->cell[i+1][j+1]; } inline int nearestNeighbours3(state *s, int i, int j) { // Returns the number of nearest neighbours in the state *s at // location [i][j], assuming that we are at least one cell away // from the boundary, and that the previous cell (at [i][j-1]) // had zero nearest neighbours. return s->cell[i] [j-1] + s->cell[i-1][j+1] + s->cell[i] [j+1] + s->cell[i+1][j+1]; } inline int processBoundary(state *prev, state *next, int i, int j) { // Evolve the cell [i][j] on the boundary of the universe, from // state *prev to state *next, returning the number of nearest // neighbours. If a cell will become alive, display the // neighbouring cells and exit. int n; n = nearestNeighbours(prev, i, j); if (n != 0) { displayState(prev, i, j); exit(0); } next->cell[i][j] = rule[prev->cell[i][j]][n]; return n; } inline void evolve(state * prev, state * next) { // Evolves state *prev by one generation, returning the result in // *next. This function makes special allowance for the boundary // of the space. int i, j, n; // Process the first row. i = 0; for (j = 0; j < displayWidth; j++) { processBoundary(prev, next, i, j); } for (i = 1; i < displayHeight-1; i++) { // Process the first column of each row. j = 0; n = processBoundary(prev, next, i, j); // Process cells that are not on the boundary. This is where // almost all the computation takes place. for (j = 1; j < displayWidth-1; j++) { // Handle the special case that the last cell had no nearest // neighbours. if (n == 0) { n = nearestNeighbours3(prev, i, j); next->cell[i][j] = rule[prev->cell[i][j]][n]; } else { n = nearestNeighbours2(prev, i, j); next->cell[i][j] = rule[prev->cell[i][j]][n]; } } // Process the last column of each row. n = nearestNeighbours(prev, i, j); if (n != 0) { displayState(prev, i, j); exit(0); } next->cell[i][j] = rule[prev->cell[i][j]][n]; } // Process the last row. for (j = 0; j < displayWidth; j++) { processBoundary(prev, next, i, j); } } int main(int argc, char **argv) { state s0, s1; int i; initialise(&s0); // To display the state at each generation, uncomment the "displayState" // lines. To slow down the display, uncomment the "usleep" lines. for (i = 0; i < 50000; i++) { // displayState(&s0); evolve(&s0, &s1); // usleep(100000); // displayState(&s1); evolve(&s1, &s0); // usleep(100000); } return 0; }
And here is an example of its output, showing the classical Game of Life glider:
* * ** *