If this didn't work, or for more detailed instructions see the
the Using Git page.
As you and your partner work on your joint solution, you will want to
push and pull changes from the master into your local repos frequently.
Assignment Overview
Game of Life
For this lab, you will implement a program that plays and animates 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:
A live cell with zero or one live neighbors dies from loneliness.
A live cell with four or more live neighbors dies due to overpopulation.
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).
This video shows one solution to this lab in action:
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
...
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 GOL 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).
Correctness Testing
Part of this lab involves you designing gol input files that are
desgined 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:
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 should not interfere with each other. 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.
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.
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.
Requirements
The program should take two command line arguments: the config file; and either 1 or 0 to enable or disable ascii animation of game of life simulation (clear-print-sleep at each step).
Use the C FILE interface (fopen, etc.) for file I/O. We recommend
using the fscanf function for reading in values from the file.
You should create test input files for testing the correctness of
certain aspects of your program (input files test_bigger.txt, test_edges.txt,
and test_corners.txt are required).
When run with 1 as the second command line option should implement
an ascii animation of the gol simulation, printing for each time step:
The board's value for the current time step.
The total number of live cells in the board for the current time step.
Only when printing is enabled (when second command line option is 1),
should either of these be printed out.
Also, to implement ascii animation of the game of life in the terminal,
make a call to usleep to pause after each time step so the user
can "see" the computation better. Before printing out the result of the
next timestep, call system("clear") to clear the terminal contents
of the previous interation's output; the next interation's ouput will be
written to the same spot, animating your gol computation. DO NOT clear the
very last iteration's printed result; after your program exits, the final board
state and number of live cells should be shown.
Note: the only
calls to usleep and system should be in the print
function(s); running
with 0 as the second command line option option should
include no output of the game board nor any calls to sleep or
clear functions during the run. See the example output.
The space for the GOL board(s) should be dynamically allocated in the heap.
See the example from Weekly lab as well as
Arrays in C for more
information.
Use the "Method 1" option that does a single malloc of
a contiguous chunk of N*M int (or char). Do not use int** (or char**) for this assignment.
You should not use global variables. Instead, the board(s) and
other variables should be local varibles that are passed to
functions that need them. If a function changes the the value
of an argument, remember you need to pass that argument
by reference.
For array parameters, the callee can modify what is in the bucket
values (passing an array is passing its base address to the
function).
Your program should have timing code in your solution around the GOL main
computation (don't include grid initialization). It should print out
the total time for the GOL simulation at the end of the simulation, and do
so regardless of if gol is run with 1 or 0 (animation enabled or not).
Use gettimeofday. See Hints and Tips for more information.
You should detect and handle all errors, you can call 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 system call is always
successful.
Your solution must have at least three functions in addition to main, and
likley should have more than this. Think good top-down design, and think about some of
the big steps: initializing the game board; updating one round of play;
printing the game board; ... 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, a function should not be longer than
a page. 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 function.
You code should be well-commented code and use good modular design.
See my C documentation
for C references and a C code style guide.
Your solution should be correct, robust, and free of valgrind errors
Hints, Tips, and Resources
Look at the weekly lab page and example code from this week
to see examples of file I/O,
command line arguments, and of dynamically allocated 2D arrays:
Weekly Lab Week 9
You will need to come up with a solution to computing new values at each time step that use values from the previous time step. You cannot
update new values in place on the same grid that stores the previous values needed to compute them.
Implement and test incrementally! Use valgrind as you go to catch
memory access errors as you make them.
Review pointers in C. Here are some
C programming references. In particular, my documentation about pointers in C
("C programming for CS31 Students Part 2") and other C pointer documentation
may be helpful for this assignment.
Remember C-style pass by reference to "return"
more than one value from a function.
Remember that a function can return a pointer (this may be useful
if you have an initialization function that returns a pointer to the
malloc'ed and initialized game board.
int *init_board( ...
Functions that return pointer values, generally return NULL on an error.
The caller then will check the return value and decide how to handle a
NULL return value.
man pages
for C library functions and system calls, and be careful about who is
responsible for allocating and freeing memory space passed to (and returned
by) these routines.
Files in C contains some information about file I/O in C.
I'd recommend using fscanf to read in values
from the file.
Remember that 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 * 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 is a good amount to sleep:
usleep(200000); // sleep for 200,000 micro seconds (.2 seconds)
system("clear"); clears the xterm window 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).
gettimeofday 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 1000000 micro seconds.
gettimeofday takes a struct timeval by reference
and its second argument value should be NULL:
struct timeval start_time, stop_time;
...
ret = gettimeofday(&start_time, NULL);
// code you want to time
ret = gettimeofday(&stop_time, NULL);
The timeval struct is defined in the sys/time.h library (you do not
need to define this struct, it is already defined for you):
struct timeval {
time_t tv_sec; /* number of seconds */
suseconds_t tv_usec; /* number of microseconds */
};
gettimeofday gives the time as the number of seconds and microseconds
since the Epoch (Jan 1, 1970). A single time value can be calculated
by adding these two fields together. However, these fields are in
different units, so be sure to convert one to one to the other
before adding them.
See the man page (man gettimeofday for more
information.
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).
Remember CNTRL-C will kill your program if it seems to be stuck
in an infinte loop.
If you want to try printing in color, and you are not requried to do this,
here is one way to do it:
printf("%s", "\e[1;31mThis prints Red\e[0m");
printf("%s", "\e[1;32mThis prints Green\e[0m");
printf("%s", "\e[1;33mThis prints Yellow\e[0m");
printf("%s", "\e[1;34mThis prints Blue\e[0m");
printf("%s", "\e[1;35mThis prints Magenta\e[0m");
printf("%s", "\e[1;36mThis prints Cyan\e[0m");
printf("%s", "\e[1;37mThis prints White\e[0m");
Example Output
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 test_oscillator.txt config file.
(note that this is the final output from an ascii animated run where
the board is printed out at every time step, each overwriting the
previous printed version to get the animation effect):
A run with 0 as the second parameter should print no board ouput, but
should print out the total time at the end of the simulation that measures
just the gol computation part (no board printfs or usleeps should be
executed when when the second command line argument's value is 0):
% gol test_oscillator.txt 0
total time for 19 iterations of 19x19 is 0.000381 secs
As you debug, use config files with small numbers of iterations, and
comment out the call to system("clear") so you can examine the board results
of every iteration. Once you are certain of correctness, you can enable the
ascii animation feature.
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 to mine
speed-wise, and see if you can tune your program to beat mine:
Speed Challenge.
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.
Lab Questionnaire
With every lab assignment is a file named QUESTIONNAIRE for you to fill out and submit with your lab solution. In this file you will answer some questions about the lab assignment. You should fill this out and submit it with your lab solution.
Submit
Before the Due Date
Only one of you or your partner needs to push your solution from
your local repo to the GitHub remote repo.
(It doesn't hurt if you both push, but the last pushed version before the
due date is the one we will grade, so be careful that you are pushing
the version you want to submit for grading.)
From one of your local repos (in your
~you/cs31/labs/Lab7-partner1-partner2 subdirectory):
git push
Troubleshooting
If git push fails, then there are likely local changes you haven't committed.
Commit those first, then try pushing again:
git add gol.c
git add Makefile
git add QUESTIONNAIRE
git add myinputfile.txt # add any test files you created too
git commit
git push
Another likely source of a failed push is that your partner pushed, and you
have not pulled their changes. Do a git pull. Compile and test that your
code still works. Then you can add, commit, and push.
If that doesn't work, take a look at the "Troubleshooting" section of the
Using git
page. You may need to pull and merge some changes from master into your
local. If so, this indicates that your partner pushed changes that you have
not yet merged into your local. Anytime you pull into your local, you need
to check that the result is that your code still compiles and runs before
submitting.