This is a two week lab, with an intermediate checkpoint.

Checkpoint: By the checkpoint deadline (11:59pm, Wednesday, November 6, 2024), look at the Requirements for what you need to have done by then.

Completed Lab: The entire lab is due 11:59pm, Wednesday, November 13, 2024, and your code must be able to caclulate the number of alive cells for all edge and corner cases.

Check the Lab 7 Partners link for your lab partner and review the CS31 Partner Etiquette and Expectations.

1. Lab Goals

  • Gain experience using 2D arrays and command-line arguments.

  • Learn how to use a visualization library.

  • Improve your proficiency in C file I/0, using pointers, dynamic memory allocation, and passing pointers to functions.

  • Further practice using gdb and valgrind for debugging C programs.

  • Measure the execution time for parts of your program’s execution.

  • Design input files to test correctness of your solution.

2. Lab Overview

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 are born, live, and die based based on their surrounding neighbors.

Your world is represented by a two dimensional (2D) array of cells, where each cell stores 0 or 1.

If the grid cell’s value is 1, it represents a live cell; if it’s 0, it represents a dead cell.

At each discrete time step, every cell in the grid gets a new value based on the current value of its eight neighboring cells:

  1. A live cell…​

    • …​with 0 or 1 live neighbors dies from loneliness.

    • …​with 2 or 3 live neighbors stays alive.

    • …​with 4 or more live neighbors dies due to overpopulation.

  2. A dead cell…​

    • …​with exactly 3 live neighbors becomes alive.

    • …​with any other number of live neigbors remains dead.

In your 2D world, every cell in the grid has exactly eight neighbors, even if it is on the edge of the grid. 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

Conway’s Game of Life description from Wikipedia shows some example patterns (such as Blinker, Toad or Beacon) you can use to test the correctness of your solution.

This video shows a solution for the Game of Life program running on one of the provided example files. (See Section 4.6 for details).

3. Lab Starting Point Code

3.1. Getting Your Lab Repo

Both you and your partner should clone your lab repo into your cs31/Labs subdirectory:

  1. get your Lab ssh-URL from the CS31 GitHub organization. The repository to clone is named Lab7-userID1-userID2, where user1 and user2 are the user names of you and your lab partner.

  2. cd into your cs31/Labs subdirectory:

    $ cd ~/cs31/Labs
$ pwd

  3. clone your repo

    $ git clone [your Lab7-userID1-userID2 url]
$ cd Lab7-userID1-userID2
$ ls
gol.c     oscillator_output  README.adoc      test_corners.txt
Makefile  oscillator.txt     test_bigger.txt  test_edges.txt

3.2. Starting Point Code

The files included in your repo are:

  • Makefile: builds gol executable file

  • README.adoc: some notes to you

  • gol.c: starting point for the lab. Your solution goes here.

  • oscillator.txt: one example input file to gol (you will create more as you test your solution)

  • oscillator_output: example output from a working solution (see Section 5 for an example of how to use this to see if your output matches mine)

  • test_corners.txt, test_edges.txt: empty input files to test gol (you will fill in each one with a test that tests the correctness of your solution when cells are on the edge of the grid).

  • test_bigger.txt: an empty input file you will fill in to test gol on larger worlds (this is useful to compare timings of run modes 0 and 1, and for testing run mode 2 on some larger worlds)

4. Lab Details

Your program will take two command line arguments. The first is the name of a configuration file that specifies how to initialize the game-playing variables (dimensions of the grid, number of iterations, and initial values of the grid cells). The second is an integer flag (0, 1 or 2) that indicates the game’s output mode: how the output should be displayed. The output mode values mean:

  • Mode 0: run gol with no output (This mode only outputs final game state statistics, including timing information about how long it took to run.)

  • Mode 1: run gol with ascii animation (This mode also includes timing and outputs final game state statistics.)

  • Mode 2: run gol with ParaVisi animation (This mode does not including timing or final game state statistics.)

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

Here are some examples of valid command line invocations of the program:

# Run with configuration file "oscillator.txt". Do not print the board
# state as it runs. Prints total time and live cells at the end.
$ ./gol oscillator.txt  0

# Run with configuration file "test_edges.txt". Use ASCII animation, printing
# the board state after each step. Prints total time and live cells at the end.
$ ./gol test_edges.txt  1

# Run with configuration file "test_corners.txt". Use ParaVisi animation only.
# Do NOT print out total time or live cells at end.
$ ./gol test_corners.txt 2

4.1. File format

The input configuration file 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 and column index) coordinate values to indicate which grid cells should be initialized to 1 (alive) at startup. All other cells should be 0 (dead).

number of grid rows  (vertical board space)
number of grid cols  (horizontal board space)
number of iterations to simulate
number of coordinate pairs alive at startup
i j
i j
...

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

    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.

  • The initial board configuration is considered "iteration 0", so the "number of iterations to simulate" field of the file indicates how many additional iterations to execute. For example, if the number of iterations in the file is 100, your output should show iteration 0 as the starting state of the board, and then it should simulate and print iterations 1 to 100 (100 total iterations after the initial state).

4.2. Create your own input files

Included with the starting-point code is one example input file you can use (oscillator.txt). You should 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 "glider" pattern that starts in the lower left and walks up to the upper right of grid:

30
30
100
5
29 1
28 2
27 0
27 1
27 2

4.3. Add timing

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 add timing to your program. Call this function before and after the part of the code you want to time and subtract the results of teh two calss to get the total execution time. Note that 1 second is 1,000,000 microseconds.

gettimeofday takes as its first argument the address of a struct timeval. For this lab you should provide NULL as the second argument value. The function returns 0 if it was successful or -1 if it failed.

To time a portion of code, call gettimeofday around the code you want to time. For example:

struct timeval start_time, stop_time;

ret = gettimeofday(&start_time, NULL);
// code you want to time inserted between these two lines
ret = gettimeofday(&stop_time, NULL);

gettimeofday sets the time in the the passed struct timeval as the number of seconds plus and number of microseconds since the Unix epoch (Jan 1, 1970). The value of the tv_sec field is the number of *whole seconds, and the value of the tv_usec is the number of additional microseconds. The single current time value can be calculated by combining these two fields together. However, these fields are in different units (one is seconds, the other is microseconds), so be sure to convert one to the other before adding them.

See the man page (man gettimeofday) for more information.

4.4. Computing cell 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 neighbors' current values, 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).

4.5. Correctness testing

Part of this lab involves you designing input files that are designed to test, debug, and verify the correctness of different aspects of your gol solution. We suggest that you start with some input files to test small, simple worlds.

With the starting point code are three test files that you need to implement, use for your own testing, and submit with your solution. You are welcome to, and encouraged to, submit more test files than these three, but these are required:

  1. test_edges.txt: this file should create a board used for testing and verifying the correctness of updating edge cells (cells on the north, or south, or east, or west edge of the grid, but not including the corner cells). We suggest creating a small to medium size board for this one, and it is fine if this file includes a test for just one of the 4 edges (north, south, east, or west). However, you should test all edges with separate test files like the one you submit as this example, and you are welcome to submit these other test files.

  2. test_corners.txt: this file should create a board used for testing the correctness of updating one or more of the 4 corner cells. Like the test_edges.txt file, this does not need to include a test for all 4 corners simultaneously; it can test just one of the corners. You should, however, make sure you have additional files that you use to test the other 3 corners for correctness.

  3. test_bigger.txt: this file should test a larger board size than the oscillator file’s board, and should have several patterns on the board that are far enough apart to not interfere with each other (at least at first). It should be a test of the middle of the board (don’t worry about edges or corners here). For example, you could have a few still and/or oscillator patterns on the board in locations that they should not affect each other over time steps. You may want to have a pattern that grows too.

In addition to these, you will want to create other input files to test correctness and features of your solution, and also just for fun!

4.6. 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! Printing is slow, so running your program without printing will finish much faster.

$ ./gol oscillator.txt 1

Round: 19
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . @ . . . . . . . . . .
 . . . . . . . . . @ . . . . . . . . . .
 . . . . . . . . . @ . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .
Live cells: 3


Total time: 2.145 seconds
After 19 rounds on 20x20, number of live cells is 3


$ ./gol oscillator.txt 0
Total time: 0.001 seconds
After 19 rounds on 20x20, number of live cells is 3

4.7. Starting-point code and what you need to add

You will implement your solution in the gol.c file.

There is a start of the definition of a struct gol_data. You should use the fields we have already defined for you in this struct, but you will also need to add more for your solution.

The main function in gol.c is almost complete (see the TODO comments for just the parts you need to add). It contains the main control flow of your program:

  1. Initialize gol game playing state from command line arguments (the input file, and run/output mode values). There is a call from main to the function init_game_data_from_args that you will need to write.

  2. Call the function that runs the simulation, play_gol, in different ways depending on the run mode specified. You need to implement the core simulation functionality in the play_gol function. However, the main control flow for calling play_gol in different ways based on the run mode is already implemented for you in main. It does the following:

    1. if OUTPUT_NONE (mode 0): calls play_gol, and prints out final statistics (time and total live cells).

    2. if OUTPUT_ASCII (mode 1): calls play_gol, and print out final state of the board, and final stats (time and total live cells). It also calls the print_board function to print out the game board. print_board is almost completely implemented for you (and don’t change what it prints out). See the TODO notes about the missing part you need to add.

    3. if OUTPUT_VISI (mode 2): calls the ParaVisi library functions to start the animation (init_pthread_visi, get_animation_buffer, connect_animation, and run_animation), and does NOT print out final statistics at the end.

  3. Clean up any program state before exit.

There are calls to printf to print out final game statistics in main. You SHOULD NOT change these calls. You will need to add code to main to perform timing for run modes (0 and 1). Otherwise, most of the code you add is to functions play_gol and init_game_data_from_args, and in other additional game playing and initialization functions you write as part of good modular code design.

5. Lab Requirements

5.1. Checkpoint Requirements

  • By the checkpoint (11:59pm, Wednesday, November 6, 2024), your code should be implement the following. Refer to the full lab requirements below for details of these parts.

    • Read in the input file using the init_game_data_from_args and print out the starting board using the print_board function.

    • Implement the play_gol function to play one round of the game of life, printing the new board and updated value of total_live. For now, you can ignore edge and corner cells and test with just the oscillator pattern (start with indices 1 to n-2).

    • Implement output modes 0 and 1: OUTPUT_NONE and OUTPUT_ASCII.

5.2. Full Lab Requirements

  • Use the main function’s main control flow that is already filled in for you (see the TODO and NOTE in comments in gol.c for more details):

    • Use the fields already defined in the struct gol_data. You will also need to add fields to this struct to implement your solution.

    • Implement initialization in the init_game_data_from_args function that is part of the starting point code.

    • Complete the print_board function.

    • Implement the main game playing functionality in the play_gol function that is part of the starting point code.

  • Your program must take two command line arguments: the config file name and an integer to determine the output mode:

    1. OUTPUT_NONE mode: Report the time at the end, but don’t print the board to the terminal or graphically.

    2. OUTPUT_ASCII mode: Report the time at the end and print the board at each iteration (call system("clear") at the start of each round to get the animation part of this).

    3. OUTPUT_VISI: Display the visualization graphically, using ParaVisi visualization library.

  • When run in OUTPUT_VISI and OUTPUT_ASCII mode, your program will want to contain calls to usleep to slow down the animation. When run in OUTPUT_NONE mode, your program should not call usleep; it should run as fast as possible.

  • When running in OUTPUT_ASCII mode, you should print the board using the provided print_board function’s formatting. That is, you should NOT make changes to the fprintf(…​) calls that are already in gol.c.

    You are welcome to add your own printf() calls though. You can verify that your output conforms to the expected format 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> my_output

# Compare your output against mine
$ diff -u -s my_output oscillator_output

    If formatted correctly, you’ll see: "Files my_output and oscillator_output 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. When your and my output differ, it is sometimes helpful to view the differences side-by-side. You can do this by running sdiff on the two output files:

    $ sdiff my_output oscillator_output

  • 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 Week 7 as well as from Chapter 2 of the textbook and Arrays in C for more information. Use the option that does a single malloc of a contiguous chunk of N*M cells. Do not use the int** (or char**) approaches for this assignment.

  • Your gol game playing should play for the specified number of rounds read from the input file. At the end of each round, it should set total_live to the number of live cells in the world and perform a visualization step — or not — based on the run mode.

  • Other than the total_live global variable that should be updated each round to the total number of live cells in the world, 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). When run in mode OUTPUT_NONE or OUTPUT_ASCII, your program will 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, fclose, 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). Create input files to check that your code can handle errors such as being provided a file with an incorrect file format. Refer to bad_cells.txt in the weekly lab code.

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-commented 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 represents 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 caused by you (see next bullet point). You should only run valgrind with OUTPUT_NONE and OUTPUT_ASCII: valgrind is not compatible with running in OUTPUT_VISI.

  • You are NOT responsible for fixing errors caused by the ParaVisi library. This run of valgrind has no "definitely lost" bytes and therefore is free of any leaks that you produced. All of the "in use at exit" and "still reachable" errors below are caused by the ParaVisi library — not by you.

==2249305== HEAP SUMMARY:
==2249305==     in use at exit: 18,804 bytes in 9 blocks
==2249305==   total heap usage: 206 allocs, 197 frees, 115,458 bytes allocated
==2249305==
==2249305== LEAK SUMMARY:
==2249305==    definitely lost: 0 bytes in 0 blocks
==2249305==    indirectly lost: 0 bytes in 0 blocks
==2249305==      possibly lost: 0 bytes in 0 blocks
==2249305==    still reachable: 18,804 bytes in 9 blocks
==2249305==         suppressed: 0 bytes in 0 blocks

  • All TODO comments in the starting point code should be removed in your final submission. These are notes to you for what you need to add into the starting point code and where you need to add it.

6. Tips

  • Implement and test incrementally!

  • Use gdb as you incrementally implement and test to find and fix bugs as you go. 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.

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

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

  • When debugging your code, it is helpful to run your program in OUTPUT_ASCII mode (in mode 1), so that you can see what your program is doing. You also may want to use input config files with a small number of iterations for testing, and different config files for testing specific functionality. You can also comment out the calls to system("clear"); to get rid of the animation part of the ASCII animation. Doing this will allow you to scroll up the terminal window to to see the board after each iteration.

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

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

  • ParaVisi display: One thing to note about the ParaVisi display is that it displays coordinate (0,0) at the bottom left of the visualization, and coordinate (rows-1, 0) at the top left. This means you will need to perform some calculation on the row index into the color3 array to "flip" the visualization horizontally to match your view of it (so the ASCII and the ParaVis display the world in the same way for the same input file). The visi_example.c example we look at during the lab shows an example of how you can do this!

7. Submitting

When you’ve completed the lab, submit your solution by pushing your changes to your GitLab repository.

Here are the commands to submit your solution (from one of you or your partner’s cs31/Labs/Lab7-userID1-userID2 directory:

$ git add gol.c *.txt
$ git commit -m "Lab 7 completed"
$ git push

And of course, if you want to submit any nifty starting point world config files you come up with, please do:

$ git add coolworld.txt
$ git commit -m "cool world"
$ git push

If you have difficulty pushing your changes, see the "Troubleshooting" section and "can’t push" sections at the end of the Using Git for CS31 Labs page. And for more information and help with using git, see the git help page.

8. Extra Challenge

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 my implementation: Speed Challenge.

The extra challenge isn’t worth any points, but is just for fun. Even if you do not do the extra challenge, you may want to read it over to learn a bit more about running timed experiments, and about gcc compiler optimization flags.

9. Handy Resources

General Lab Resources

C programming Resource