Thanks to Julie Zelenski for the idea and Jerry Cain, Keith Schwarz, Cynthia Lee and Marty Stepp for revisions.
A still image of the Game of Life
For your first assignment... We make the Game of Life!
The purpose of this assignment is to gain familiarity with basic C++ features such as functions, strings, and I/O streams, using provided libraries, and decomposing a large problem into smaller functions. This is an individual assignment. You should write your own solution and not work in a pair on this program.
The Game of Life is a simulation originally conceived by the British mathematician J. H. Conway in 1970 and popularized by Martin Gardner in his Scientific American column. The game models the life cycle of bacteria using a two-dimensional grid of cells. Given an initial pattern, the game simulates the birth and death of future generations of cells using a set of simple rules. In this assignment you will implement a simplified version of Conway's simulation and a basic user interface for watching the bacteria grow over time.
The starter code for this project is available as a ZIP archive:
Your Game of Life program should begin by prompting the user for a file name and using that file's contents to set the initial state of your bacterial colony grid. Then, it should ask if the simulation should wrap around the grid (see below for the details of wrapping). Then the program will allow the user to advance the colony through generations of growth. The user can type
t to "tick" forward the bacteria simulation by one generation, or
a to begin an animation loop that ticks forward the simulation by several generations, once every 50 milliseconds; or
q to quit. Your menu should be case-insensitive; for example, an uppercase or lowercase
Q should work (hint: you can use the
toLowerCase() function to convert a string to lowercase).
Here is an example log of the interaction between your program and the user (with console input in blue).
Of course there are many other interactions you could have. Here is a bunch more examples. They show what to do in many cases, for example bad input filenames.
You will turn in only the following files:
life.cpp, the C++ code for the Game of Life simulation
mycolony.txt, your own unique Game of Life input file representing a bacterial colony's starting state
The ZIP archive contains other files and libraries; you should not modify these. When grading/testing your code, we will run your
life.cpp with our own original versions of the support files, so your code must work with them.
Submit your files at cs198.stanford.edu/paperless.
Each grid location is either empty or occupied by a single living cell (X). A location's neighbors are any cells in the surrounding eight adjacent locations. In the example at right, the shaded middle location has three neighbors containing living cells. A square that is on the border of the grid has fewer than eight neighbors in the non-wrapping version of the simulation (see below for the wrapping version). For example, the top-right X square in the example at right has only three neighboring squares, and only one of them contains a living cell (the shaded square), so it has one living neighbor.
The simulation starts with an initial pattern of cells on the grid and computes successive generations of cells according to the following rules:
The births and deaths that transform one generation to the next all take effect simultaneously. When you are computing a new generation, new births/deaths in that generation don't impact other cells in that generation. Any changes (births or deaths) in a given generation k start to have effect on other neighboring cells in generation k+1.
Check your understanding of the game rules by looking at the following example. The two patterns should alternate forever:
Here is a second example. The pattern at right does not change on each iteration, because each cell has exactly three living neighbors. This is called a "stable" pattern or a "still life".
The grid of bacteria in your program gets its initial state from one of a set of provided input text files, which follow a particular format. When your program reads the grid file, you should re-prompt the user if the file specified does not exist. If it does exist, you may assume that all of its contents are valid. You do not need to write any code to handle a misformatted file. The behavior of your program in such a case is not defined in this spec; it can crash, it can terminate, etc. You may also assume that the input file name typed by the user does not contain any spaces.
In each input file, the first two lines will contain integers r and c representing the number of rows and columns in the grid, respectively. The next lines of the file will contain the grid itself, a set of characters of size r x c with a line break (\n) after each row. Each grid character will be either a '-' (minus sign) for an empty dead cell, or an 'X' (uppercase X) for a living cell. The input file might contain additional lines of information after the grid lines, such as comments by its author or even junk/garbage data; any such content should be ignored by your program.
The input files will exist in the same working directory as your program. For example, the following text might be the contents of a file simple.txt, a 5x9 grid with 3 initially live cells (the arrow notes are not part of the actual file):
5 ← number of rows tall 9 ← number of columns wide --------- --------- ← - is a dead cell ---XXX--- ← X is a living cell --------- ---------
Grid: The grid of bacterial cells could be stored in a 2-dimensional array, but arrays in C++ lack some features and are generally difficult for new students to use. They do not know their own length, they cause strange bugs if you try to index out of the bounds of the array, and they require understanding C++ topics such as pointers and memory allocation. So instead of using an array to represent your grid, you will use an object of the
Grid class, which is part of the provided Stanford C++ library.
Grid object offers a cleaner abstraction of a 2-dimensional data set, with several useful methods and features. See the course lecture examples and/or section 5.1 of the Programming Abstractions in C++ textbook for a list of members of the
Grid class (e.g., the
grid.inBounds() function will come in very handy). You can also use the
= assignment operator to copy the state of one
Grid object to another.
Your main function should create your
Grid and pass it to the other functions. Since it is expensive to make copies of a
Grid, if your code passes a
Grid object as a parameter from one function to another, it should always do so by reference (
Grid). See the lecture notes for examples. Since you don't know the size of the grid until you read the input file, you can call
resize on the Grid object once you know the proper size.
I/O: Your program has a console-based user interface, although there is a relatively easy extension that includes a GUI. You can produce console output using
cout and the Stanford C++ library's console-related functions such as
getLine (uppercase L) to read from the console. You should not use
cin to read from the console. See the Stanford C++ library documentation for input/output here.
You will also write code for reading input files. Read a file using an
ifstream object, along with functions such as
getline (lowercase L) to read lines from the file. Here are some useful ifstream-related functions from filelib and strlib:
Continually prompts the user using the provided prompt until a valid filename is entered. Once the user enters a valid filename, the function opens the specified file using the provided (by reference)
||Reads the next line from the given stream and stores it into the given string variable by reference.|
||Returns an int value equivalent to the given string; for example,"42" → 42|
||Returns a string value equivalent to the given integer; for example,42 → "42"|
Make sure to close your input file streams when you are done reading the given file:
Checking for valid input: Note that your program needs to check for valid user input in a few places:
q(case-insensitively), you should re-prompt the user to enter a new command.
n, you should re-prompt the user to enter a new answer.
Animation: When the user selects the animation option, the console output should look like the following:
a)nimate, t)ick, q)uit? a How many frames? xyz Illegal integer format. Try again. How many frames? 5 (five new generations are shown, with screen clear and 50ms pause before each)
The screen is supposed to clear between each generation of cells, leading to what looks like a smooth animation effect. Here is a short video showing an example animation (for the glider colony):
To help you perform animation, use the following global functions from the Stanford C++ library:
||Causes the program to halt execution for the given number of milliseconds|
||Erases all currently visible text from the output console (call this between frames)|
The non-wrapping version of the assignment treats the edges of the grid as the end of the game world. Cells on the border do not always have eight neighbors. In the wrapping version, all cells will have eight neighbors, as follows: the right-most squares are considered to be "neighbors" of the left-most, and the top-most are considered to be "neighbors" of the bottom-most. In order to provide wrapping functionality, modify your game logic so that these rules are followed. This will allow moving patterns such as "gliders" to wrap around indefinitely.
The logic for this is not too difficult, and you may want to
use the remainder operator (
%) to perform part of
this task. The remainder function works as follows:
(a % b) returns the remainder of a / b
For positive values, the operator returns the value of the remainder,
which "wraps" around to the value. E.g.,
6 % 5 is
1, which would
be correctly wrapped on a grid from 0-4 (which has 5 values).
For negative values, the remainder function does not wrap in C++, but wrapping can be accomplished by simply adding the number of rows or columns in the grid to the negative value. In fact, to wrap properly in all cases, simply add the number of rows or columns to the location, and then apply the remainder operator.
For example, let's say you were checking the bottom left corner of a 5x5 grid (with indexes 0-4 for both the rows and columns), at location (4,0), as shown in the diagram below.
The blue squares show the neighbors with wrapping, and going clockwise from the top-left corner of the neigbors, would be at locations (3,-1), (3,0), (3,1), (4,-1), (4,1), (5,-1), (5,0), and (5,1). But, both the negative values and the values above 4 are out of bounds. If we apply the remainder operator as detailed above, we will get a proper wrapping of the values. If we add the corresponding number of rows or columns (5 in this case, for both), and then apply the remainder operator with the same value to each of the coordinate pairs, we will get a proper wrap. Using coordinate (5, -1) as an example, this would become:
((5 + 5) % 5, (-1 + 5) % 5) = (10 % 5, 4 % 5) = (0, 4)
and that coordinate is properly wrapped to the top right corner.
Many of the provided colonies will behave differently with and without wrapping. For instance, without wrapping, the glider colony will move to the bottom of the screen in a straight line and stop. With wrapping, the glider colony will move to the bottom of the screen and continue wrapping around and moving forever in a straight line.
Along with your program, submit a file mycolony.txt that contains a valid initial colony that can be used as input. This can be anything you want, as long as it is in the input grid file format described in this document, and should be your own work (not just a copy of an existing colony input file). This is worth a small part of your grade.
Development strategy: It is tempting to try to write your entire program and then try to compile and run it; we do not recommend that strategy. Instead, you should develop your program incrementally: Write a small piece of functionality, then test/debug it until it works, then move on to another small piece. This way you are always making small consistent improvements to a base of working code. Here is a possible list of steps to develop a solution:
Gridobject. Print the
Grid's state on the console using
toStringjust to see if it has the right data in it. Use a simple test case, e.g.
Updating from one generation to the next: When you are trying to advance the bacteria from one generation to the next, you cannot do this "in place" by modifying your grid as you loop over it. Doing so will change the cells and their neighbors and break the neighbor counts for nearby cells. So you will need to create a temporary second grid. Your existing grid represents the current generation of bacteria, and you can create a second temporary second grid that allows you to compute and store the next generation without changing the current one. Once you have filled the second grid with the next generation's cell information, you can copy its contents back into the original grid and discard the temporary copy. Copying one Grid to another is easy; just assign one to the other using the = assignment operator, which makes a copy of its contents.
Output: We want your output to match ours exactly. This includes identical spacing, such as the extra spaces after the phrase, "Grid input file name? " Some students lose points for minor output formatting errors. Please run the web Output Comparison Tool on several test cases to make sure it matches without any differences.
Hints: Here are some other miscellaneous tips that may help you:
Thats all! You are done. Consider adding extra features.