For this lab, you will implement a program that plays Conway's Game of Life. Conway's Game of Life is an example of discrete event simulation, where a world of entities live, die, or are born based based on their surrounding neighbors. Each time step simulates another round of living or dying.
Your world is represented by a 2-D array of values (0 or 1). If a grid cell's value is 1, it represents a live object, if it is 0 a dead object. At each discrete time step, every cell in the 2-D grid gets a new value based on the current value of its eight neighbors:
Your 2-D world should be a torus, meaning every cell in the grid has exactly eight neighbors, even if their on the edge of the grid. In the torus world, cells on the edge of the grid have neighbors that wrap around to the opposite edge. For example, the grid locations marked with an 'x' are the eight neighbors of the grid cell whose value is shown as 1.
x 1 x 0 0 0 0 x x x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 x x x 0 0 0 0
The Conway's Game of Life description from Wikipedia shows some example patterns you can use to test the correctness of your solution (like Blinker, Toad or Beacon).
First, both you and your partner should clone your git repository from Swarthmore GitHub Enterprise to grab the starting point code.
The starting point code includes: gol.c which you should use to implement your solution and osicllator.txt, a sample input file to your program. You should create other input files to test your solution.
Your program will take two command line arguments. The first is the name of a configuration file that will specify how to initialize the game playing variables (dimensions of the grid, number of iterations, and how to initialize the grid cells). The second is an integer flag (0 or 1) that will indicate whether or not the game of life board should be printed out after every iteration or not.
Here are some example command lines:
# run with config values read from file1.txt and do not print the board: ./gol file1.txt 0 # run with config file file2.txt and print the board after each step: ./gol file2.txt 1
Your program should handle badly formed command lines (e.g. print out an error message and exit).
The input file format consists of several lines of ASCII text. The first three lines specify the grid dimensions and number of iterations. The fourth line lists the number of coordinate pairs that will follow. The remaining lines specify i j (row index, column index) coordinate values to indicate which grid cells should be initialized to 1 at startup (all others should be 0):
number of grid rows number of grid cols number of iterations to simulate number of coordinate pairs (set each (i, j) value to 1) that come next i j i j ...
You may assume that the grid will have at least four rows and four columns. In other words, you do not need to worry about weird cases (e.g., 2x2 grid) in which another cell is both the left and right neighbor at the same time.
You can create your own input files in vim (or emacs) by writing text that conforms to the file input format specification. For example, a file with the following contents generates an interesting pattern that starts in the lower left and walk up to upper right of grid:
30 30 100 5 29 1 28 2 27 0 27 1 27 2
Additionally, you will add timing code to your program to time just the GOL simulation (the timing should not include the board initialization phase of your code).
The gettimeofday function can be used to instrument your program with timers. Call this function before and after the part of the code you want to time and subtract to get total time. 1 second is 1,000,000 micro seconds.gettimeofday takes a struct timeval pointer (the struct whose values it should fill in), and the second argument value should be NULL:
struct timeval start_time; ... ret = gettimeofday(&start_time, NULL);
See the man page (man gettimeofday for more information).
Here is an example of what you might see from different runs. I'm printing '@' for 1's and '-' for 0's because it is easier to see than '0' and '1' characters. You do not need to use the same characters as me, but choose characters that are easy to visually distinguish so you can easily see the iterations.
The first example shows the end board configuration from a run that is initialized to run from the oscillator.txt config file. And, the second is the same configuration, but run with 0 as the second parameter (notice the time difference between the two):
# a run with output: $ ./gol oscillator.txt 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - @ - - - - - - - - - - - - - - - - - - @ - - - - - - - - - - - - - - - - - - @ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - total time for 19 iterations of 19x19 is 2.019754 secs
A run with 0 as the second parameter should print no output the total time then measures just the gol computation part because the printfs and usleeps should not be executed.
% gol oscillator.txt 0 total time for 19 iterations of 19x19 is 0.000381 secs
The starting configuration of the oscillator file board is:
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - @ @ @ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
int *init_board( ...Functions that return pointer values, generally return NULL on an error. The caller should therefore check the return value and decide how to handle a NULL return value. Refer to man pages for C library functions and system calls, and be careful about who (you or the library?) is responsible for allocating and freeing memory space passed to (and returned by) these routines.
usleep(200000); // sleep for 200,000 micro seconds (.2 seconds)
After completing a well-designed, well-commented, correct solution to the required parts of this assignment, as an extra challenge you can see how your program compares speed-wise, and see if you can tune your program to beat Tia's implementation: Speed Challenge.
Even if you do not do the extra challange, you may want to read it over to learn a bit more about running timed experiments, and about gcc compiler optimization flags.
Please remove any debugging output prior to submitting.
To submit your code, simply commit your changes locally using git add and git commit. Then run git push while in your lab directory. Only one partner needs to run the final push, but make sure both partners have pulled and merged each others changes. See the section on Using a shared repo on the git help page.