CS 31 Lab 6: Game of Life

Handy References

• A description of Conway's Game of Life
• More information about 2D arrays and reading files.
• Use the man command on the terminal to view the manual page for a function that you're curious about using. For example: man gettimeofday will show you a detailed description of how to use the gettimeofday function.

Lab 6 Goals:

• Experience 2D arrays, command line arguments, and file I/O in C.
• Gain additional practice with pointers, dynamic memory allocation, and passing pointers to functions.
• Measure the execution time for parts of your program's execution.
• Use GDB and valgrind to debug C programs as necessary.

Lab Description

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:

1. A live cell with zero or one live neighbors dies from loneliness.
2. A live cell with four or more live neighbors dies due to overpopulation.
3. A dead cell with exactly three live neighbors becomes alive.

All other cells remain in the same state between rounds.

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 @.

x  @  x  _  _  _  _
x  x  x  _  _  _  _
_  _  _  _  _  _  _
_  _  _  _  _  _  _
_  _  _  _  _  _  _
_  _  _  _  _  _  _
x  x  x  _  _  _  _

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).

Getting Started

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!

Implementation Details

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, 1, or 2) that will indicate how the game's output should be displayed.

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

# run with config vales from file3.txt and output with a graphics library
./gol file3.txt 2

Your program should handle badly formed command lines (e.g. print out an error message and exit).

File Format

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 (alive) at startup (all others should be 0 / dead):

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 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. Note that 1 second is 1,000,000 microseconds.

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).

Computing Values at Each time step

One problem you will need to solve is how to update each grid cell value at each time step. Because each grid cell's value is based on its neighbor's current value, you cannot update each cell's new value in place (otherwise its neighbors will read the new value and not the current value in computing their new value).

Example Output

Here is an example of what you might see from different runs. We're printing '@' for live cells and '_' for dead ones because it is easier to see than '0' and '1' characters.

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 might end like:
$ ./gol oscillator.txt 1

Round: 20
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ @ @ @ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Live cells: 3


Total time: 2.074092

A run with 0 as the second parameter should print no output the total time then measures just the gol computation part because the prints and sleeps should not be executed.

$ ./gol oscillator.txt 0
Total time: 0.001066

Your instructor's in-class demo (and subsequent video recording) will serve as examples of running with the graphical visualization library.

Requirements

• When reading the list of initially live cells from the input file, the cells will be provided as a coordinate pair: i, j. i represents the row number, j represents the column number. The origin (0,0) is the top left corner.


• Your program must take two command line arguments: the config file name and an integer to determine the output mode:
0. Report the time at the end, but don't print the board to the terminal or graphically.
1. Report the time at the end and print the board at each iteration.
2. Display the simulation graphically.


• When running in output mode 1, you should print the board using the provided print_board function's formatting. That is, you should NOT make changes to the fprintf(stderr, ...) that are already there. You're welcome to add your own printf() calls though. You can verify that your output conforms to the expected format (for easier grading) by comparing your output against mine with the diff command:

  # Run your program and save all the fprintf output to a file named output.txt
  ./gol oscillator.txt 1 2> output.txt
  
  # Compare your output against mine
  diff -u -s output.txt oscillator_output.txt
  

  If formatted correctly, you'll see: "Files output.txt and oscillator_output.txt are identical". If not, you'll see output that compares how they differ. Feel free to contact your instructor(s) for help with output formatting. This bit of the lab is here for ease of grading purposes.


• The space for the GOL board(s) should be dynamically allocated on the heap according to the grid dimensions specified in the input configuration file. See the example from lab as well as Arrays in C for more information. Use the option that does a single malloc of a contiguous chunk of N*M. Do not use the int** (or char**) for this assignment.


• Your solution should not use global variables. Instead, the board(s) and other variables should be passed to the functions that need them using the provided gol_data struct. If you want a function to change the value of an argument, remember you need to pass that argument as a pointer.


• Your program should have timing code in your solution around the GOL main computation (don't include grid initialization). Print out the total time for the GOL simulation at the end of the simulation. Use gettimeofday before and after the section of code you wish to time and subtract to compute the time duration.


• Use the C FILE interface (fopen, fscanf, etc.) for file I/O. You should detect and handle all errors, calling exit(1) if the error is unrecoverable (after printing out an error message, of course). This means that any time you call a function that returns a value, there should be a check for error return values and they should be handled: do not just assume that every function call and every C library or system call is always successful!


• Your solution should be well-commended and apply good top-down design, dividing functionality into functions. Consider the big steps: initializing the game board, updating one round of play, printing the game board, etc. main should represent the high-level steps with calls to high-level functions that perform each of the big steps. These functions in turn should use helper functions to implement well-defined pieces of functionality. As a rule of thumb, a function should not be longer than 100 - 150 lines. There are exceptions, but if you are writing a function that is getting really long, break it up into several parts, each implemented by a separate helper function.


• For full credit, your solution should be correct, robust, and free of valgrind errors. When running valgrind, use "valgrind-gol" for this lab, as it will suppress some errors in the graphics library that aren't your fault. You are NOT responsible for running valgrind in output mode 2 (graphics), but you should get no errors or warnings (other than those that are suppressed) for output modes 0 and 1.

Tips

• Implement and test incrementally! Use valgrind as you go to catch memory access errors as you make them.


• As you test and debug, you may find it useful to use config files with small numbers of iterations and to comment out the call to system("clear") so you can examine the results of every intermediate iteration.


• Recall that passing pointers to a function allow you to to "return" more than one value from a function, since that function's execution can have "side effects" that modify the value that's pointed to.


• You do not need to read all of a file's contents at once. Your program can read part of the file contents, do something else, and then later read more of the file contents. If you do this, you may need to pass the FILE * handle to the open file to several functions, so think about where you want to open the file in your code to make this easy to do.


• usleep: pauses the program for some number of micro seconds. This is useful in print mode to slow down your program after each step so that you can see what it is doing. About .2 seconds is a good amount to sleep:

  usleep(100000);  // sleep for 100,000 micro seconds (0.1 seconds)
  

• system("clear"); clears the text on the terminal so that the next output is at the top of the window (useful for printing the grid at each timestep to the same window location).


• atoi converts a string to an integer. For example, int x = atoi("1234"), assigns x the int value 1234. This is useful in your command line parsing functions for converting command line arguments that are read in as strings to their numeric values. See the man page for atoi for other similar functions to convert stings to other numeric types (man atoi).


• CNTRL-C will kill your program if it seems to be stuck in an infinite loop.

Submitting

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.