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

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;

For example, we could access the X in the upper left corner of ticTacToeGame with the expression:

ticTacToeGame[0][0]

ticTacToeGame[2][0]

ticTacToeGame[0][2]

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:

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

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

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

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:

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

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 general form of the typedef mechanism is thus:

typedef Type Identifier;

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

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++) ...

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;

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

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:

• 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 if c had more than three neighbors containins 1s, then c 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:

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:

 
    * * *
      *
*     *     *
* * *   * * *
*     *     *
      *
    * * *

 
        *
      * * *
        *
  *     *     *
* * * *   * * * *
  *     *     *
        *
      * * *
        *

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