We have seen that the C++ vector type allows us to construct objects in which we can conveniently store a sequence of values. For example, the statement:
vector<double> aVector(8);defines the object aVector as a container capable of storing eight values:
We usually visualize a vector as a linear sequence of values that has one dimension: the length or size of the vector. There are, however, objects that are more naturally visualized as having two dimensions, such as a tic-tac-toe game, which is organized by rows and columns:
One way to build a software model of such an object is by defining a vector that stores other vectors:
vector< vector<char> > ticTacToeGame; ...Where a single index is needed to specify an element of a one-dimensional vector, two indices are needed to specify an element of a two-dimensional vector: the first to specify the particular row being accessed, and the second to specify the particular column within that row. For example, we could access the X in the upper left corner of ticTacToeGame with the expression:
ticTacToeGame[0][0]we could access the X in the lower left corner with the expression:
ticTacToeGame[2][0]the O in the upper right corner with the expression:
ticTacToeGame[0][2]and the X in the lower right corner with the expression:
ticTacToeGame[2][2]In today's exercise, we will use this idea to build a class that allows us to play an interesting game known as the game of life.
The game of life was invented by mathematician John Conway as a simple model representing a society of organisms. The basic premise is to create a rectangular grid of cells, so that each cell has eight neighboring cells:
That is, if a cell's row-index is r and its column-index is c, then its northwest neighbor has the index [r-1][c-1], its northern neighbor has the index [r-1][c], its northeast neighbor has the index [r-1][c+1], its western neighbor has the index [r][c-1], its eastern neighbor has the index [r][c+1], its southwest neighbor has the index [r+1][c-1], its southern neighbor has the index [r+1][c], and its southeast neighbor has the index [r+1][c+1].
Each cell may or may not contain an "organism," designated by an asterisk (*).
The game consists of a series of generations, with the "organisms" in any given generation determined by the "organisms" of the preceding generation, and these rules:
If this is our first generation, then the second generation is produced by applying our three rules to each cell in the grid:
To get the third generation, we re-apply the same rules to the second generation. As a result, "organisms" are born in cells [1][2] and [3][2], while the "organisms" in cells [2][1] and [2][3] give birth, returning us to the original configuration!
This particular configuration continues to oscillate back and forth from generation to generation. It can be thought of as representing a "society of organisms" that while changing from generation to generation, remains stable if it is not disturbed by outside influences. Other configurations grow larger and larger with each generation until the entire grid is nearly filled; and thus model "societies" with population booms. Others grow smaller and smaller until all organisms are dead, modeling "societies" that lead to the extinction of their "organisms." We will see examples of each of these at the end of this exercise.
Create a new directory in which to do this exercise. Then save copies of LifeGame.h, LifeGame.cpp, LifeGame.doc, life.cpp, test.life, and Makefile in this directory. The files Life.h, Life.cpp and Life.doc provide the skeleton for a LifeGame class -- a class to represent and perform the appropriate operations on a game of life. test.life contains the initial configuration for the simple three "organism" oscillating pattern that you can use to test what you write. The file life.cpp contains a complete driver to construct a LifeGame object with an initial configuration from a file, and then display the subsequent generations as controlled by the user. The calls to function members of class LifeGame are "commented" at present, but we will "uncomment" these during the course of today's exercise. Take a few moments to study life.cpp until you understand what it is doing and why.
Today's exercise is to complete the LifeGame class. In addition to defining the data members for the class, this will involve implementing the following operations for class LifeGame:
We have provided prototypes and function stubs in LifeGame.h and LifeGame.cpp for each of these functions. Today's exercise will consist of completing class LifeGame and its function members.
Once we have the operations identified (even as informally as this), we can begin the actual construction of the class. Begin editing the file LifeGame.h, where you should find a skeleton for class LifeGame.
Each cell in a game of life may or may not have a living "organism" within it, and this can change over time. There are a variety of ways to represent such an object (e.g., a char, a bool, an int, ...). However, implementing the game's rules requires that we count the number of neighboring cells containing living "organisms." Since counting is easily accomplished by adding numbers, we will represent a cell containing a living "organism" with the integer 1, and represent a cell without a living "organism" with the integer 0.
Since a game of life involves a grid of cells, we need a two-dimensional structure of cells. One easy-to-read way to accomplish this is to first declare a new type Row as a one-dimensional vector of integers, and then declare our two-dimensional type as a vector of Row objects.
To declare the name Row as a type representing a one-dimensional vector of integers, we can use the C++ typedef mechanism -- add the following statement to the private section of class LifeGame (in LifeGame.h and LifeGame.doc):
typedef vector<int> Row;Where a "normal" declaration statement of the form
vector<int> Row;defines Row as an object of type vector
typedef Type Identifier ;and the effect of such a statement is to declare Identifier as a synonym for the type Type.
Once the identifier Row is declared as a synonym for vector<int>, we can then define a two-dimensional grid of cells as a vector of Row objects. Add the following statement to the private section of class LifeGame, following the typedef statement:
vector<Row> myGrid;and to LifeGame.doc. Our LifeGame class now has a data member named myGrid that is a two-dimensional vector of integers! Of course, without a constructor to properly initialize it, myGrid is an empty two-dimensional vector, so let us proceed to the LifeGame operations.
In order to define and initialize a LifeGame object with a starting configuration, we need
For simplicity, we will assume that the first line of the file contains two integers: the number of rows and the number of columns in the grid of cells. The remainder of the file will then be a grid of starting values for the cells. For example, our test.life input file provides the starting configuration for the three "organism" oscillating pattern, and it is structured as follows:
5 5 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0In this five-by-five grid, each 1 represents a cell containing an "organism," and each 0 represents a cell without an "organism."
From the perspective of the LifeGame, we can specify the behavior of this operation as follows:
Receive: fileName, a string.
Precondition: fileName contains the name of an input file,
the first line of that file specifies the rows and columns,
and the remainder of the file is a life configuration.
Postcondition: myGrid has been initialized to the configuration
given in the input file.
This turns out to be a non-trivial function,
so open LifeGame.cpp and find the stub for the LifeGame
constructor function.
Using object-centered design, we can derive the following algorithm
for this function:
0. Receive fileName.
1. Open inStream, an ifstream to fileName,
and verify that it opened successfully.
2. Read rows and columns from inStream.
3. For each index r in the range 0..rows-1:
a. Declare aRow, an empty Row.
b. For each index c in the range 0..columns-1:
1) Read value from inStream.
2) Append value to aRow.
End loop.
c. Append aRow to myGrid.
End loop.
4. Close inStream.
Step 0 is accomplished automatically for us when the user
defines a LifeGame object.
Steps 1, 2 and 4 should be familiar to you by now,
so uncomment the constructor stub in LifeGame.cpp
and insert the necessary statements to accomplish these steps.
Step 3 is a bit trickier, since it involves two nested for loops that build myGrid as a rows-by-columns two-dimensional vector of vectors. The tricky part is that we must build each Row separately, by first declaring an empty Row:
Row aRow;and then fill this Row with values using the nested loop that reads a value from the file and appends it to aRow using the vector function member push_back():
inStream >> value; aRow.push_back(value);Once aRow is a complete Row, we then use push_back() to append it to myGrid:
myGrid.push_back(aRow);Using this information, complete the stub for the LifeGame constructor. Then check the syntax of what you have written by "uncommenting" the declaration of theGame in life.cpp and then compiling using make. Continue when your constructor translates correctly.
Given this class constructor, a declaration like:
LifeGame theGame(inFile);will construct theGame as an object of type LifeGame and initialize it to the configuration stored in inFile. For example, if inFile contains the name of a file in which is stored our previous five-by-five configuration, then following the execution of this statement, we can visualize theGame as follows:
We can specify this problem as follows:
Return: the number of rows in my configuration.Even though we do not have data members that store the number of rows and columns in our configuration, defining an accessor function to retrieve this information is fairly simple, using the size() function of the vector class. That is, since myGrid is a vector of Rows:
vector<Row> myGrid;the size() of myGrid is the number of rows in the configuration. Our algorithm is thus as follows:
Return the size() of myGrid.Since this is such a simple algorithm, uncomment the Rows() stub in LifeGame.h, and use this information to complete it. Then use make to check the syntax of what you have written. When it is correct, copy-and-paste a copy into LifeGame.doc and continue.
We can specify this problem as follows:
Return: the number of columns in my configuration.Solving this problem is again fairly simple using the size() function, but is slightly more tricky than our Rows() accessor. More precisely, myGrid is a vector of Rows:
vector<Row> myGrid;and so the number of columns in our configuration is the size() of a Row of myGrid. Since we are assuming that our configuration is rectangular, the size() of any Row in myGridwill do (e.g., myGrid[0]).
Of course, this assumes that we have at least one Row in our configuration -- an assumption we should verify. Our algorithm is thus as follows:
If Rows() > 0,
Return the size() of myGrid[0].
Else
Return 0.
This is a bit complicated to inline,
so "uncomment" the Columns() stub in LifeGame.cpp
and use this information to complete the stub.
Then use make to check the syntax of what you have written,
and continue when it is correct.
We have provided an overloaded definition of operator<<, but this definition calls the Print() member of class LifeGame. In life.cpp, "uncomment" the line that displays the value of theGame and use make to translate your program. You should get a linker error. The reason is that the Print() function is called by operator<<, and since LifeGame contains a prototype for the function, the compilation completes successfully. However, since Print() is not defined, the linker is unable to find a definition of Print(), and so it generates the linking error.
Let's define the Print() function and take care of this error. Using object-centered design, we can specify the behavior of this function from the perspective of a LifeGame as follows:
Receive: out, an ostream. Output: my current configuration. Passback: out, containing my configuration.Completing our design, we can derive the following algorithm that uses nested for loops: an inner loop to output the values in each row, and an outer loop to output the rows:
0. Receive out, an ostream.
1. For each index r in the range 0..Rows()-1:
a. For each index c in the range 0..Columns()-1:
If myGrid[r][c] is 1:
Display "* ". // an asterisk and a space
Otherwise
Display " ". // two spaces
End if.
End loop.
b. Display a newline. // end of a Row
End loop.
This algorithm scans cell-by-cell through myGrid,
displaying two spaces for those cells containing 0
(i.e., nothing "living"),
and displaying an asterisk and a space for each cell containing 1
(i.e., a "living organism").
This makes for more readable output than a page full of ones and zeros.
Since this is fairly complicated, use this algorithm to complete the stub of function Print() in LifeGame.cpp. To test your code, "uncomment" the statement in life.cpp that displays theGame. Then use make to translate life, and then run it to test the correctness of your class thus far, using test.life as the configuration-input file. If all is well, you will see the starting configuration of our simple five-by-five oscillating configuration. If not, use the debugger to find and locate your logic errors.
Function NextGeneration() is the workhorse of the class, since it must encode "the rules of the game." We can specify what it does as follows:
Postcondition:
For each cell c in myGrid:
If c had exactly three neighboring cells containing 1s:
Then c contains a 1.
Otherwise, if c had less than two neighbors containing 1s, OR
c had more than three neighbors containins 1s:
Then c contains a 0.
This postcondition gives us a great deal of insight into the problem.
We will need two nested for loops to process the rows and
columns of myGrid.
Within the inner loop, we will need to count the number of neighbors
for the currently-referenced cell,
and set its value appropriately as required to satisfy the postcondition.
One subtle part is that we must compute the number of neighbors containing ones using the current configuration of cells. That is, if we compute the number of neighbors of myGrid[r][c], and then change myGrid[r][c] according to the rules above, then the "neighbor-computation" in each of the cells that neighbor myGrid[r][c] will be modified accordingly. To avoid this problem, we must begin by making a copy of myGrid, and then use this copy to perform all "neighbor-computations."
The other subtle part is that cells at the "edges" of the grid do not have the required eight neighbors, so we exclude them from consideration.
Putting these pieces together gives us the following algorithm:
1. Define tempGrid = myGrid.
2. For each index r in the range 1..Rows()-2:
For each index c in the range 1..Columns()-2:
a. neighbors = // sum neighbors to the
tempGrid[r-1][c-1] + // NW
tempGrid[r-1][c] + // N
tempGrid[r-1][c+1] + // NE
tempGrid[r][c-1] + // W
tempGrid[r][c+1] + // E
tempGrid[r+1][c-1] + // SW
tempGrid[r+1][c] + // S
tempGrid[r+1][c+1]. // SE
b. If neighbors is 3:
Set myGrid[r][c] to 1.
Else, if neighbors is less-than 2 OR
neighbors is greater-than 3:
Set myGrid[r][c] to 0.
End if.
End loop.
End loop.
Since each cell is an integer, with 0 representing an empty cell
and a 1 representing a cell with an "organism" in it,
we can simply add the values in the surrounding cells to
compute the number of neighbors.
Using this algorithm, uncomment and complete the stub for function NextGeneration() in LifeGame.cpp. Then use make to translate your code, and test what you have written using test.life. Your program should now be fully functional and ready to use to play the 'game' of life.
Playing the game of Life consists of creating initial configurations of "organisms," and then running the program and stepping through the generations to see what happens to the society as time passes. While test.life gave us a simple way to see if our program was working correctly, that particular configuration is actually quite dull, because very little changes as time passes.
To see an even more stable configuration, try the configuration in stable.life. The "organisms" in this configuration don't change at all from generation to generation, and are effectivly "immortal" under the rules of the game. (This indicates why the old phrase, "May you live in interesting times!" is generally regarded as a curse -- stability tends to be dull.)
By contrast, some initial configurations are very unstable, and the "society of organisms" quickly breaks down, resulting in their extinction. Try quick.life for an example.
With other configurations, the "society" seems to flourish for a while, and then extinction occurs quite suddenly and unexpectedly. Try cross1.life.
Sometimes a few "individuals" make all the difference between whether a society flourishes or becomes extinct. The initial configuration in cross1.life is the following "iron cross":
* * *
*
* * *
* * * * * *
* * *
*
* * *
cross2.life simply adds another
organism at the end of each cross:
*
* * *
*
* * *
* * * * * * * *
* * *
*
* * *
*
How does this "society" fare compared to that of cross1.life?
Each of our configurations has thus far been symmetric, but there is no requirement that this be the case. Some assymetric configurations are more interesting than the symmetric ones. For example, try out glider.life. This particular "society" goes through a periodic cycle of four configurations, and each generation moves a space across the grid. The result is a "migratory society" that moves through the grid as time passes. This behavior is similar to that of some insect colonies, or flocks of birds.
When two gliders collide, the results are unpredictable. Sometimes they lead to extinction of both "societies" and sometimes they result in something entirely different. Which is the case for gliders.life?
Using your text editor, modify the configuration in blank.life to create your own original configuration. Then run it using life. Keep experimenting until you find a simple initial configuration that after 100 generations is still changing.
The game of Life thus provides a simple, interesting model of the relationships in a society.
One-Dimensional Vector, Two-Dimensional Vector, Row, Column.
Hard copies of your final version of Life.h and Life.cpp, plus a hard copy showing the initial configuration you created, and the resulting configuration after 100 generations.
Forward to the Homework Projects