CS31 Lab 7: Game of Life

Due before midnight Thursday, April 12

Here are the new partnerships and here's a link to GitHub.

Lab 7 Goals:

Contents:

Overview

For this lab, you will implement Conway's Game of Life. Devised by mathematician John Conway, Life is a grid-based simulation that demonstrates how complex behavior can emerge from simple rules. At each discrete time step, every cell in the grid is either "alive" or "dead." The cells get updated for the next time step based on how many of the eight adjacent cells contain alive cells (neighbors).

  1. An alive cell with zero or one neighbors dies of loneliness.
  2. An alive cell with four or more neighbors dies from overpopulation.
  3. An alive cell with two or three neighbors stays alive.
  4. A dead cell with exactly three neighbors becomes alive.

This video shows one solution to this lab in action:


Details

You should represent the grid (or board) using a two-dimensional array, where a value of 0 indicates a dead cell and 1 indicates an alive cell. So that every cell in the board can have eight adjacent cells, we will think about the board as a torus. That is, cells on one edge of the board are considered adjacent to cells on the opposite edge.

In the boards shown below, cells marked with an 'x' are adjacent to the cell whose value is shown as 1.

0  x  1  x  0  0  0              x  0  0  0  0  x  x
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  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  0  0  0  0  x  x
0  x  x  x  0  0  0              x  0  0  0  0  x  1

Note that you cannot update the board in-place (with a single 2D array). As soon as you change the value held in a particular cell, you have also changed the neighbor counts for this cell's adjacent cells. So you will need two boards to run the simulation. On even-numbered iterations you will count neighbors using board #1 and write updates to board #2. On odd-numbered iterations, do the reverse.

Your program will read in a file that specifies the initial board configuration and the number of iterations to simulate. (Each iteration corresponds to one time step / board update.) The format of the input files is as follows:

number of rows
number of columns
number of iterations
numbers of cells that are alive initially
row index and column index of first alive cell
row index and column index of second alive cell
...
Here's an example of a valid input file (walker.txt):
10
10
50
5
9 1
8 2
7 0
7 1
7 2

If your program read in this file, it would start with a 10 by 10 board like the one below, and then update the board 50 times.

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 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 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0

Your program will take two command line arguments. The first is the name of the configuration file. The second indicates whether the board updates should be animated (1) or whether we only care to see how long the updates took to compute (0).

$ ./gol oscillator.txt  0
19 iterations of a 19x19 board took 0.000665 seconds.
$ ./gol oscillator.txt  1
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - @ @ @ - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - -
number of live cells: 3
19 iterations of a 19x19 board took 3.872943 seconds.

In the second example run above, you are seeing the final board. Along the way the program should show all the intermediate boards.


Additional Requirements

Hints, Tips, and Resources