CS31 Lab 6: Game of Life

Due before 11:59pm, Thursday Nov. 13

This lab should be done with a partner of your choosing.

Lab 6 Goals:

Lab 6 Introduction

The setup procedure for this lab will be similar to Labs 2, 3 and 4. Those labs probably seem like a long time ago, so let's remind ourselves about the procedure. First, both you and your partner should run setup31 to grab the starting point code for this assignment. Suppose users molly and tejas which to work together. Molly (mdanner1) can start by running

  [~]$ setup31 labs/06 tdanner1
Once the script finishes, Tejas (tdanner1) should run
  [~]$ setup31 labs/06 mdanner1

For the next step only one partner should copy over the starting code

  [~]$ cd ~/cs31/labs/06
  [06]$ cp -r ~lammert/public/cs31/labs/06/* ./
  [06]$ ls
  Makefile  gol.c  oscillator.txt
Now push the changes to your partner
[06]$ git add *
[06]$ git commit -m "lab 6 start"
[06]$ git push
Your partner can now pull the changes. In this case if Tejas wishes to get files Molly pushed, he would run
[~]$ cd ~/cs31/labs/06
[06]$ git pull
The starting point code includes: an empty Makefile that you need to implement; gol.c into which you should implement your solution; and oscillator.txt, a sample input file to your program. You should create other input files to test your solution.

Project Details and Requirements

Game of Life

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.

Your 2-D world should be a TORUS; every cell in the grid has exactly eight neighbors. 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
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).


Implementation Details

Your program will take two command line arguments. The first is a the name of a configuration file that will specify how to initialize the game playing variables (dimensions of the grid, number of iterations, how to initialize the grid cells). The second 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).

File Format

The input file format consists of several lines of an ascii file. The first three lines give the dimensions and number of iterations, the fourth line lists the number of coordinate pairs followed by the lines with i j (row index, column index) coordinate values specifying grid cells that should be initialized to 1 (all others should be 0):
num rows
num cols
num iterations
num of following coordinate pairs (set each (i, j) value to 1
i j
i j 
...
You can create your own input files in vim or emacs by following the file input format.

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

In addition, you will add timing code to your program to time just the Game of Life computation (the timing should not including the board initialization phase of your code).

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

Requirements


Useful C functions and hints

Example Output
Here is an example of what you might see from different runs of the program. 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 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 ouput
# the total time then measures just the gol computation part because
# the printfs and usleeps should not be executed when passed 0

% gol ~/classes/cs31/f13/library/labs/06/oscillator.txt 0
total time for 19 iterations of 19x19 is 0.000381 secs
The starting configuration of the oscillator file board is:
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - @ @ @ - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - 
As you debug, use config files with small numbers of iterations, and comment out the call to system("clear") so you can examine the results of every iteration.
Submit

To submit your code, simply commit your changes locally using git add and git commit. Then run git push while in the labs/06 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.