Lab 12: Two-dimensional vectors
Lab 12: Two-dimensional vectors
Introduction
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
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 a cell has exactly three neighboring "organisms,"
then an "organism" is "born" in that cell.
-
If a cell has fewer than two neighboring "organisms,"
then an "organism" in that cell "dies of loneliness."
-
If a cell has more than three neighboring "organisms,"
then an "organism" in that cell "dies of overcrowding."
These three simple rules are sufficient to observe some
fascinating behaviors.
For example, suppose that we begin with this configuration of
three "organisms":
If this is our first generation, then the second generation
is produced by applying our three rules to each cell in the grid:
-
Cells
[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.
-
Cells
[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.
-
Cells
[1][2], and
[3][2]
have one neighboring "organism,"
and so the "organisms" in them die of loneliness.
-
Cells
[2][1], and
[2][3]
have three neighboring "organisms,"
and so an "organism" is born in each of them.
-
Cell
[2][2] has two neighbors,
and so its "organism" remains unchanged.
The second generation thus appears as follows:
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.
Getting Started
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
makefile12
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.
Design
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:
-
To simplify the initialization of a
LifeGame object,
our LifeGame will use a constructor that
reads an initial configuration from a file.
-
To allow a program using the
LifeGame class
to determine its dimensions, our LifeGame class
will provide two "accessor" function members:
Rows() and Columns().
-
To change a
LifeGame object from its current
configuration to that of the next generation,
our LifeGame class will provide
a NextGeneration() function member.
-
To display the current configuration of a
LifeGame
object, our LifeGame class will provide a
Print() function member.
The output operator << will be overloaded
using this Print() function member.
To keep our game simple, these are all of the operations we will provide.
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.
Implementation
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.
Data Members
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 RowType as a one-dimensional vector of integers,
and then declare our two-dimensional type as a vector
of RowType objects.
To declare the name RowType 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> RowType;
Where a "normal" declaration statement of the form
vector<int> RowType;
defines RowType as an object of type vector<int>,
placing the keyword typedef before such a declaration
declares RowType as a an alternative name for the type
vector<int>.
The general form of the typedef mechanism is thus:
typedef Type Identifier ;
and the effect of such a statement is to declare Identifier
as a synonym for the type Type.
Once the identifier RowType is declared as a synonym for
vector<int>, we can then define a two-dimensional grid of cells
as a vector of RowType objects.
Add the following statement to the private section of class LifeGame,
following the typedef statement:
vector<RowType> 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.
The Class Constructor
In order to define and initialize a LifeGame object
with a starting configuration, we need
-
The initial configuration; and
-
A constructor function to initialize
myGrid
to that configuration.
For convenience, we have chosen to store the initial configuration
in a file.
Our program life.cpp begins by reading the name of the file
from the user, and then passes this to the LifeGame constructor
function, which reads the contents of the file and uses them to initialize
the myGrid data member.
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 0
In 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:
The Rows() Accessor
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.
The Columns() Accessor
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.
The Print() Function Member
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 theBoard 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 theBoard.
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.
Generating The Next Generation
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 Life Game
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.
Phrases you should now understand:
One-Dimensional Vector, Two-Dimensional Vector, Row, Column.
Submit:
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.
|
|
|
|
Home
Help
Lab 0
Lab 1
Lab 2
Lab 3a
Lab 3b
Lab 4
Lab 5
Lab 6
Lab 7
Lab 8
Lab 9
Lab 10
Lab 11
Lab 12
Lab 13
Membership
Login |