We have seen that the
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
aVectoras a container capable of storing eight
We usually visualize a
vector as a linear sequence of
values that has one
dimension: just one index is sufficient to manipulate the elements
of a one dimensional vector. Consequently, a
vector has just
a length or size.
There are, however, many 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 data structure of such an object is by defining a
vector that stores other
vector< vector<char> > ticTacToeGame;Now two indices are needed to specify an element of a two-dimensional
vector: the first specifies the particular row being accessed, and the second specifies the particular column within that row.
For example, we could access the
X in the upper left corner
ticTacToeGame with the expression:
ticTacToeGameWe could access the
Xin the lower left corner with the expression:
Oin the upper right corner is accessed with the expression:
Xin the lower right corner is accessed with the expression:
In this lab'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. Each cell in the grid (except along the border) has eight neighboring cells:
Each cell may have an organism
in it, that we'll represent for now as an asterisk,
The game consists of a series of generations. Each generation (except the first) is determined by the previous generation. (You have to provide the game with the initial generation; that's the trick to the game!) To determine the next generation, we follow these rules:
These three simple rules are sufficient to observe some fascinating behaviors. For example, suppose that we begin with this configuration of three organisms:
Then applying the rules, we can generate the next generation:
have no neighboring organisms, and so they remain empty.
have one neighboring organism, and so they remain empty.
have one neighboring organism, and so the organisms in them die of loneliness.
have three neighboring organisms, and so an organism is born in each of them.
has two neighbors, and so its organism remains unchanged.
Consequently, the second generation is
To get the third generation, we re-apply the same rules to the second
generation. Organisms are born in cells
, while the organisms in cells
 die, 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---a population boom. 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.
LifeGame.docimplements the game of life itself.
lifedriver.cppimplements a driver for the game of life.
blank.lifeare sample input files.
Makefilefor making the code.
gccusers need a makefile; all others should create a project and add all of the
.cppfiles to it.
Add your name, date, and purpose to the opening documentation of the code and documentation files; if you're modifying and adding to the code written by someone else, add your data as part of the file's modification history.
LifeGame.doc provide the skeleton for a
LifeGame class, a
class to represent and perform the appropriate operations on a game
of life. The file
test.life contains the initial
configuration for the simple three organism oscillating pattern that
you can use to test what you write. The file
contains a complete driver that constructs a
with an initial configuration from a file, and then it displays the
subsequent generations as controlled by the user. The calls to
methods of class
LifeGame are commented out at present, but
we will uncomment these during the course of this exercise. Take a
few moments to study
lifedriver.cpp until you understand what
it is doing and why.
This lab's exercise is to complete the
LifeGame class. In
addition to defining the methods for the class, this will involve
implementing the following operations for class
LifeGamewill implement a constructor that reads an initial configuration from a file.
LifeGamewill provide two accessor methods,
getColumns(), to report on the dimensions of the life-game grid.
LifeGamewill provide a
nextGeneration()method to generate the next generation of the game.
print()method to print the current generation to an
ostream. The output operator
<<will be overloaded for a
LifeGameobject which will use this
We have provided prototypes and function stubs in
LifeGame.cpp for each of these functions. This exercise
will consist of completing class
LifeGame and its methods.
Once we have the operations identified, we can begin the actual
construction of the class. Begin editing the file
LifeGame.h, where you should find a skeleton for class
Each cell in a game of life may or may not have a living organism
within it, and this can (and hopefully will) change over time. There
are a variety of ways to represent such an organism: a
Let's think about what operations we want to do these
organisms. In the pictures above we represented organisms as an
asterisk, and this works quite well displayed on a screen or in this
lab exercise. However, the most important operation of a
LifeGame object is to generate a new generation. Look at the rules
for generating a new generation. All of the rules involve counting neighboring organisms. Sure, we can count the number of
times a certain
char (like an asterisk),
bool appears in the neighboring cells, but the most
natural counting object in C++ is an
int. So, we will
represent a living organism with the integer 1, and we will represent
a dead or missing organism with the integer 0. We won't even have to
do any comparisons: just add up the values in the neighboring cells!
Since a game of life involves a grid of cells, we need a
two-dimensional structure of cells. As suggested at the beginning of
this exercise, we can implement this two-dimensional structure using
vectors. Keep in mind that we'll still
think and use it like a two-dimensional structure, but underneath it
all, we'll have a
First we'll declare a new datatype named
Row to be a
vector of integers; as the name suggests,
this will represent one row of the grid. Then we can create a
Rows to represent the entire grid.
So let's first create this new datatype
Row using C++'s
typedef mechanism. Add the following statement to
the private section of class
typedef vector<int> Row;The keyword
Rowas an alternative name for the type
vector<int>---essentially a new datatype.
The general form of the
typedef mechanism is thus:
typedefThe effect of such a statement is to declare
Identifieras a synonym for the 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
Row objects. Add the following statement
to the private section of class
LifeGame, following the
LifeGame class now has a instance variable named
myGrid that is, technically, a
ints. However, we'll think of
myGrid as just simply
In order to define and initialize a
LifeGame object we need
at least one constructor. The constructor should somehow be able to
initialize the game with some initial generation. To make things a
little easier, we'll put the initial generations into files. (Check
.life files.) So our constructor will need access to
a file to initialize the game.
lifedriver.cpp begins by reading the name of the
file from the user, and then it passes the name to the
LifeGame constructor function which reads the contents of the file
and uses them to initialize the
myGrid instance variable.
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
input file provides the starting configuration for the three organism
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 (determined by the two
5s at the beginning of the file), each
1represents a cell containing an organism, and each 0 represents a cell without an organism. Any whitespace can be used to separate organisms; we've used spaces and newlines in this file so that it's a little easier for humans to read and write.
We can specify the behavior of this operation as follows:
fileNamecontains 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 configuration for a game of life.
myGridhas been initialized to the configuration given in the input file.
This turns out to be a non-trivial function, so open the
implementation file, and find the stub for the
constructor. Using object-centered design, we can derive the
following algorithm for this function:
fileName, and verify that it opened successfully.
rin the range 0..
aRow, an empty Row.
cin the range 0..
The first few steps should be quite familiar to you now (up to the nested loops), so write those first.
The two nested
for loops build
myGrid as a
ints. The loops themselves aren't tricky. You've been
writing loops for a while now, so write those
for loops next.
Keep in mind that the algorithm talks about ranges like "0..
last-1"; this is an inclusive range, including both 0 and
last-1. Typically, when working with
C++, you start at index 0 and continue the loop while the loop index
is less than
last. For example:
for (int i = 0; i <You can write these loops with different bounds, but it's not recommended. This is the pattern used by nearly all C and C++ programmers.
last; i++) ...
Now let's tackle the other steps. The nested loops are used to
initialize the two-dimensional
is actually a
vectors, these loops read in
one row of
myGrid with the inner loop, and then the outer
loop adds the current row to the end of
We first declare an empty
Row aRow;Remember that
vector<int>, so we're really asking for an empty
ints as if we had written this:
Inside the inner loop, we fill
aRow with values from the
file. Reading in the value is old hat. Adding the value to the end
aRow can be done with
inStream >> value; aRow.push_back(value);Note that you'll have to declare
valuesomewhere in the constructor.
aRow is a complete
Row (i.e., we've left the
inner loop), we then use
push_back() to append
Complete the stub for the
LifeGame constructor. Check the
syntax of what you have written by uncommenting the declaration of
lifedriver.cpp and then compiling the
code. Continue when your constructor compiles correctly.
How many rows are in the grid? Any question like this is really an operation for the class, which means that it's a method of the class. Since it's relatively simple, we consider it an accessor. The specification for this accessor would be this:
Specification:return: the number of rows in my configuration.
Even though we do not have instance variables that store the number
of rows and columns in our configuration, defining an accessor to
retrieve this information is fairly simple, using the
function of the
vector class. That is, since
myGrid is the number of rows in the configuration.
Our algorithm is thus as follows:
Since this is such a simple algorithm, we define it inline in the
header file. Uncomment the
getRows() stub in the header file,
and complete the definition. Compile everything, and fix any syntax
problems. When it is correct, copy-and-paste a copy into
LifeGame.doc and continue.
You might expect that if knowing the number of rows is a good idea, then knowing the number of columns is also a good idea. It is.
Specification:return: the number of columns in my configuration.
Solving this problem is again fairly simple using the
function, but is slightly more tricky than our
myGrid is a
The number of columns in our configuration is the
size() of a
myGrid. Since we've assumed that our
grid is rectangular, the
size() of any
myGrid will do.
Of course, the row index must be valid, so row
seems best. Unless there are no rows at all. Then we can assume
that there are no columns. So we end up with this algorithm:
Some compilers might find this to complicated to make it inline, so you can find it in the implementation file. Uncomment the stub, and complete the definition. Compile and fix any syntax problems.
There's already an overloaded definition of
operator<< in the
header file, and this definition calls the
print() method of
LifeGame. However, we don't have a definition for
In the driver, uncomment the line that displays the value of
theGame, and compile your code. You should get a linker error which
print() cannot be found.
Let's define the
print() method and take care of this error.
Using object-centered design, we can specify the behavior of this
method as follows:
output: my current configuration.
out, containing my configuration.
Completing our design, we can derive the following algorithm that
for loops, an inner loop to output the values in
each row and an outer loop to output the rows:
rin the range 0..getRows()-1:
cin the range 0..getColumns()-1:
Do you suppose it's any coincidence that whenever we work through our
vector we end up with two loops,
one nested in the other?
This algorithm scans cell-by-cell through
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 display of ones and zeros.
Since this algorithm is fairly complicated, define this method in the
implementation file. Uncomment the stub, and complete the
definition. To test your code, uncomment the statement in the driver
theGame. Compile and run your code. Use
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. Move on when this is working properly.
nextGeneration() is the workhorse of the class
since it must encode the rules of the game. We can specify what it
does as follows:
Specification:postcondition: For each cell
chad exactly three neighboring cells containing 1s, then
ccontains a 1.
- Otherwise, if
chad less than two neighbors containing 1s, or if
chad more than three neighbors containins 1s, then
ccontains a 0.
This postcondition is really a rephrasing of the rules of the game of life.
In order to process all of the cells, we will need two nested
for loops (again!) to process the rows and columns of
myGrid. Within the inner loop, we can count the number of neighbors
for the current cell, and set its value appropriately as required to
satisfy the postcondition.
We do, however, have to worry about two problems. First, the next
generation is determined by the current generation. We cannot
overwrite the current generation with the next one since the current
generation is needed to determine the next. Consequently, we begin
by making a copy of
myGrid to remember the current
generation, and then we use this copy to calculate the neighbors.
The second problem is that cells at the edges of the grid do not have the required eight neighbors. We'll make things easy for us by excluding them from consideration.
We thus end up with the following (incomplete) algorithm:
rin the range 1..getRows()-2:
cin the range 1..getColumns()-2:
neighbors = northNeighbors + sideNeighbors + southNeighbors
neighborsis less-than 2 or
neighborsis greater-than 3:
Since each cell is an integer, 0 representing an empty cell and 1 representing an organism, we can simply add the values in the surrounding cells to compute the number of neighbors.
The algorithm, though, leaves two of the computations unfinished for
you to complete. Use the
northNeighbors computation and
the picture of a cell at the beginning of this exercise to finish the
Question #13.1: Come up with computations for
sideNeighbors computation should look at only the
neighbors directly west and east of the current cell. Do not
include the current cell.
Using this algorithm, uncomment and complete the stub for function
nextGeneration() in the implementation file. Compile your
code, and test the program using
test.life. Your program
should now be fully functional and ready to use to play the game of
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 effectively
immortal under the rules of the game.
By contrast, some initial configurations are very unstable, and the
society of organisms quickly breaks down, resulting in their
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
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.lifesimply adds another organism at the end of each cross:
* * * * * * * * * * * * * * * * * * * * * * * *
Question #13.2: How does this second cross-society fare compared to the first cross-society?
Each of our configurations has thus far been symmetric, but there is
no requirement that this be the case. Some asymmetric 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 cycle 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.
Question #13.3: What happens with the gliders in
Make copies of
blank.life, and edit these copies to create
your own original configurations. Run them through your program.
Keep experimenting until you find a simple initial configuration that
after 100 generations is still changing.
Submit a copy of all of your code as well as your answers to the questions posed in this lab exercise. Also submit your alive-after-100-generations configuration, and a transcript of a sample execution of your program on this configuration.