// John Horton Conway's game of Life. // Michael Ashley / UNSW / 23-May-2003 #define displayWidth 80 #define displayHeight 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; #if 0 // Zero the state. for (i = 0; i < displayHeight; i++) { for (j = 0; j < displayWidth; j++) { s->cell[i][j] = 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/8th of the cells to be alive. for (i = 0; i < displayHeight; i++) { for (j = 0; j < displayWidth; j++) { s->cell[i][j] = random() > 7*(RAND_MAX/8); } } } 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 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++) { next->cell[i][j] = rule[prev->cell[i][j]][nearestNeighbours(prev, i, j)]; } for (i = 1; i < displayHeight-1; i++) { // Process the first column of each row. j = 0; n = nearestNeighbours(prev, i, j); next->cell[i][j] = rule[prev->cell[i][j]][n]; // 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. next->cell[i][j] = rule[prev->cell[i][j]][nearestNeighbours(prev, i, j)]; } // Process the last row. for (j = 0; j < displayWidth; j++) { next->cell[i][j] = rule[prev->cell[i][j]][nearestNeighbours(prev, i, j)]; } } void displayState(state * s) { // Displays state *s using ASCII characters. int i, j; for (i = 0; i < displayHeight; i++) { for (j = 0; j < displayWidth; j++) { if (s->cell[i][j]) { printf("*"); } else { printf(" "); } } printf("\n"); } } 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; }