Lab 13: Multidimensional Vectors


Introduction

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 vectors:

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

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:

  1. If a cell has exactly three neighboring organisms, then an organism is born in that cell.
  2. If a cell has fewer than two neighboring organisms, then an organism in that cell dies of loneliness.
  3. 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:

Then applying the rules, we can generate the next generation:

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.

Files

Directory: lab13

Create the specified directory, and copy the files above into the new directory. Only 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.

Looking at the Files

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.

Design

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:

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.

Implementation

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.

Instance Variables

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 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 vector of vectors.

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 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 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:

typedef Type Identifier;
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;

Our LifeGame class now has a instance variable named myGrid that is, technically, a vector of vectors of ints. However, we'll think of myGrid as just simply a two-dimensional vector of ints.

The Constructor

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 0
In this five-by-five grid (determined by the two 5s 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, 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 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:

  1. Receive fileName.
  2. Open inStream, an ifstream to fileName, and verify that it opened successfully.
  3. Read rows and columns from inStream.
  4. For each index r in the range 0..rows-1:
    1. Declare aRow, an empty Row.
    2. For each index c in the range 0..columns-1:
      1. Read value from inStream.
      2. Append value to aRow.
      End loop.
    3. Append aRow to myGrid.
    End loop.
  5. Close 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 vectors of 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 vectors 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 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 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 ints 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.

The getRows() Accessor

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 size() function of the vector class. That is, since myGrid is a vector of Rows, the size() of myGrid is the number of rows in the configuration.

Our algorithm is thus as follows:

  1. Return the size() of myGrid.

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.

The getColumns() Accessor

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 size() function, but is slightly more tricky than our getRows() accessor. Again, myGrid is a vector of Rows. 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:

  1. If getRows() > 0,
        Return the size() of myGrid[0].
    Else
        Return 0.

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.

The print() Method

There'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, 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:

  1. Receive out, an ostream.
  2. For each index r in the range 0..getRows()-1:
    1. For each index c in the range 0..getColumns()-1:
          If myGrid[r][c] is 1:
              Display "* ".
          Otherwise
              Display " ".
          End if.
      End loop.
    2. Display a newline.
    End loop.

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.

Generating The Next Generation

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 cell c in myGrid:

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:

  1. Define tempGrid = myGrid.
  2. For each index r in the range 1..getRows()-2:
    1. For each index c in the range 1..getColumns()-2:
      1. northNeighbors = tempGrid[r-1][c-1] + tempGrid[r-1][c] + tempGrid[r-1][c+1]
      2. sideNeighbors = ???
      3. southNeighbors = ???
      4. neighbors = northNeighbors + sideNeighbors + southNeighbors
      5. 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, 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 for sideNeighbors and southNeighbors.

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 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 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

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.

Terminology

cell, column, game of life, generation, one dimension, organism, row
Lab Home Page | Prelab Questions | Homework Projects
© 2003 by Prentice Hall. All rights reserved.
Report all errors to Jeremy D. Frens.