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
aVector
as a container capable of storing
eight double
objects.
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
s:
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
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 is accessed with the
expression:
ticTacToeGame[0][2]The
X
in the lower right corner is accessed with the
expression:
ticTacToeGame[2][2]
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:
[0][0]
, [1][0]
, [2][0]
, [3][0]
, [4][0]
, [0][4]
, [1][4]
, [2][4]
, [3][4]
, and [4][4]
have no neighboring
organisms, and so they remain empty.[0][1]
, [1][1]
, [0][2]
, [0][3]
, [1][3]
, [3][1]
, [3][3]
, [4][1]
, [4][2]
, and [4][3]
have one neighboring
organism, and so they remain empty.[1][2]
, and [3][2]
have one neighboring
organism, and so the organisms in them die of loneliness.[2][1]
, and [2][3]
have three neighboring
organisms, and so an organism is born in each of them.[2][2]
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 [1][2]
and [3][2]
, while the organisms in cells [2][1]
and [2][3]
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.
Directory: lab13
LifeGame.h
, LifeGame.cpp
, and
LifeGame.doc
implements the game of life itself.lifedriver.cpp
implements a driver for the game of
life.test.life
, stable.life
,
quick.life
, cross1.life
,
cross2.life
, glider.life
,
gliders.life
, and blank.life
are
sample input files.Makefile
for making the code.gcc
users need a makefile; all others
should create a project and add all of the .cpp
files 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.
The files LifeGame.h
, LifeGame.cpp
and 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 lifedriver.cpp
contains a complete driver that constructs a LifeGame
object
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 LifeGame
:
LifeGame
will implement a constructor that reads an
initial configuration from a file.LifeGame
will provide two accessor methods, getRows()
and getColumns()
, to report on the dimensions of the life-game
grid.LifeGame
will provide a nextGeneration()
method to
generate the next generation of the game.LifeGame
will provide print()
method to print the
current generation to an ostream
. The output operator
<<
will be overloaded for a LifeGame
object which
will use this print()
method.We have provided prototypes and function stubs in LifeGame.h
and 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 LifeGame
.
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 char
,
a bool
, an int
, etc.
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), string
, or
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
a vector
of vector
s. Keep in mind that we'll still
think and use it like a two-dimensional structure, but underneath it
all, we'll have a vector
of vector
s.
First we'll declare a new datatype named Row
to be a
one-dimensional vector
of integers; as the name suggests,
this will represent one row of the grid. Then we can create a vector
of Row
s 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 LifeGame
:
typedef vector<int> Row;The keyword
typedef
declares Row
as 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 declareType
Identifier
;
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;
Our LifeGame
class now has a instance variable named myGrid
that is, technically, a vector
of vector
s of
int
s. However, we'll think of myGrid
as just simply
a two-dimensional vector
of int
s.
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
out the .life
files.) So our constructor will need access to
a file to initialize the game.
Our program 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 test.life
input file provides the starting configuration for the three organism
oscillating pattern:
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
5
s at the
beginning of the file), each 1
represents 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:
Specification:receive:fileName
, astring
.
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 configuration for a game of life.
postcondition:myGrid
has 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 LifeGame
constructor. Using object-centered design, we can derive the
following algorithm for this function:
fileName
.inStream
, an ifstream
to fileName
, and verify that it opened successfully.rows
and columns
from inStream
.r
in the range 0..rows
-1:
aRow
, an empty Row.c
in the range 0..columns
-1:
value
from inStream
.value
to aRow
.aRow
to myGrid
.inStream
.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 rows
-by-columns
vector
of vector
s of
int
s. 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 vector
s in
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 < last
; 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.
Now let's tackle the other steps. The nested loops are used to
initialize the two-dimensional myGrid
. Since myGrid
is actually a vector
of vector
s, 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 myGrid
itself.
We first declare an empty Row
:
Row aRow;Remember that
Row
is a vector<int>
, so we're really
asking for an empty vector
of int
s as if we had
written this:
vector<int> aRow;
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
of aRow
can be done with push_back()
:
inStream >> value; aRow.push_back(value);Note that you'll have to declare
value
somewhere in the
constructor.
Once aRow
is a complete Row
(i.e., we've left the
inner loop), we then use push_back()
to append aRow
to myGrid
:
myGrid.push_back(aRow);
Complete the stub for the LifeGame
constructor. Check the
syntax of what you have written by uncommenting the declaration of
theGame
in lifedriver.cpp
and then compiling the
code. Continue when your constructor compiles correctly.
getRows()
AccessorHow 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 size()
function of the vector
class. That is, since myGrid
is a vector
of Row
s, the size()
of 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.
getColumns()
AccessorYou 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 size()
function, but is slightly more tricky than our getRows()
accessor. Again, myGrid
is a vector
of Row
s.
The number of columns in our configuration is the size()
of a
Row
of myGrid
. Since we've assumed that our
grid is rectangular, the size()
of any Row
in myGrid
will do.
Of course, the row index must be valid, so row myGrid[0]
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.
print()
MethodThere's already an overloaded definition of operator<<
in the
header file, and this definition calls the print()
method of
class LifeGame
. However, we don't have a definition for
print()
yet.
In the driver, uncomment the line that displays the value of theGame
, and compile your code. You should get a linker error which
complains that 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:
Specification:receive:out
, anostream
.
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:
out
, an ostream
.r
in the range 0..getRows()-1:
c
in the range 0..getColumns()-1:
myGrid[r][c]
is 1:Do you suppose it's any coincidence that whenever we work through our
two-dimensional vector
we end up with two loops,
one nested in the other?
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 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
that displays 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.
The method 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 cellc
inmyGrid
:
- If
c
had exactly three neighboring cells containing 1s, thenc
contains a 1.- Otherwise, if
c
had less than two neighbors containing 1s, or ifc
had more than three neighbors containins 1s, thenc
contains 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:
tempGrid
= myGrid
.r
in the range 1..getRows()-2:
c
in the range 1..getColumns()-2:
northNeighbors
=
tempGrid[r-1][c-1]
+ tempGrid[r-1][c]
+
tempGrid[r-1][c+1]
sideNeighbors
= ???southNeighbors
= ???neighbors = northNeighbors + sideNeighbors +
southNeighbors
neighbors
is 3:
myGrid[r][c]
to 1.neighbors
is less-than 2 or neighbors
is greater-than 3:
myGrid[r][c]
to 0.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
other computations:
Question #13.1: Come up with computations forsideNeighbors
andsouthNeighbors
.
The 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
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 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
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:
* * * * * * * * * * * * * * * * * * * * * * * *
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 gliders.life
?
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.