John Horton Conway's Game of Life.

John Horton Conway's Game of Life - boundary version

// 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 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;

    // 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;
        next->cell[i][j] = 
            rule[prev->cell[i][j]][nearestNeighbours(prev, 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++) {
            next->cell[i][j] = 
                rule[prev->cell[i][j]][nearestNeighbours2(prev, i, j)];
        }

        // 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;
}