Lab 11: Multidimensional Arrays and Vectors


We have seen that we can use arrays or vectors to store sequences of values. For example, the declarations

    double arrvec[50];

    vector<double> arrvec(50);

define an object arrvec as a container that can store 50 double values.

We usually visualize such a container as one-dimensional objects — i.e., a linear sequence of values. And as we saw in the previous lab exercise, a single index is sufficient to access the elements of a one-dimensional array or vector because it is a linear structure.

There are, however, many objects that are more naturally visualized as having two (or more) dimensions such as a tic-tac-toe game

and a magic square

which are organized into rows and columns.

    Such two-dimensional structures can be represented in a program as an array of arrays such as

    int magicSquare[3][3];
or as a vector of vectors:

    vector< vector<int> > magicSquare;
To access an element of a two-dimensional array or vector, two indices are needed: the first to specify the row in which it located and the second to specify a column within that row. For example, we could access the integer 17 in the upper left corner of magicSquare with the expression


the integer 11 in the lower left corner with


and the integer 13 in the center with


In this lab exercise, we will use a two-dimensional array to implement an interesting game known as the game of life.

The Game of Life

The Game of Life (also known simply as Life) is a cellular automaton that was devised by the British mathematician John Conway as a simple model of a society of organisms. The "playing board" is a rectangular grid of cells. Each cell in the grid (except along the border) has eight neighboring cells: 3 cells above it, 3 cells below it, and 1 on each side of it.

Each cell may have an organism in it that we'll represent by an asterisk, *.

The game consists of a series of generations. You provide the initial configuration of organisms, and each generation thereafter is determined by applying the following rules to the previous generation:

  1. If an empty 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.

For example, suppose that we begin with the following configuration of three organisms:

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

Represented graphically, the second generation is

To get the third generation, we apply the rules to the second generation. Organisms are born in cells [1][2] and [3][2] and the organisms in cells [2][1] and [2][3] die, which means that we have returned to the original configuration!

This particular configuration continues to oscillate back and forth from generation to generation. We might think of this as representing a society of organisms that although changing from one generation to the next, it 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 eventually become extinct. Examples of these kinds of behavior will be described later in this lab exercise.



This lab exercise is to complete the life.cpp program. This will involve adding and testing code to do the following:

  1. Read the grid configuration from a data file and store it in a two-dimensional array.
  2. Display the contents of this file on the screen so they can be checked.
  3. Write a display() function to output each generation to a file via an ostream.
  4. Write a generate() function to generate the next generation.


Now that we have the operations identified, we can start writing code to implement them. So open the file life.cpp which contains a partially-written program that you will be completing and testing in this lab exercise.

Modeling the Life grid

To represent the grid we will use a two-dimensional array (or if your instructor prefers, a vector of vectors.) However, to create this array, we need to know:

— its dimensions, and
— the type of its elements.

We can define a two-dimensional array type with a declaration of the form

typedef ElementType ArrayTypeIdentifier[ROWS][COLUMNS];

where ROWS and COLUMNS are integer constants that specify the array's dimensions;
ElementType is the type of its elements; and
ArrayTypeIdentifer is the name of this new type that we have defined.

Question #11.1 Define an array type named LifeGrid at comment #1 near the beginning of life.cpp. For this exercise, all of the grids will have 50 or fewer rows and columns so you can use this to specify the number of rows and columns. As explained next, we will use short (or short int) for the type of the array elements.
We turn now to the question of why we are using short for the type of the cells when all of our examples represented the presence of an organism with an asterisk (*) and an empty cell with a blank. So wny not use char for the cell type?

If we look at the most important operation of a LifeGrid object — generating a new generation — and at the rules for producing a new generation, we see that they involve counting neighboring organisms. This would mean counting the number of times a certain character — an asterisk — appears in each of the neighboring cells by comparing each of their contents with an asterisk. And this must be done for every cell in the grid! But if we use a grid of integers rather than characters, representing the presence of an organism with 1 and an empty cell by 0, no comparisons are required — just sum the values in the neighboring cells! And because there are only eight neighbors, we can use short integers to reduce the memory requirements for this array.

But what about the earlier pictures of a LifeGrid object? If the asterisks are replaced by 1s and the empty cells with 0s, it surely won't be as picturesque as the asterisk-blank representation! The solution? Let's use the 0-1 representation in the data file that will be input and stored internally as a grid of 0s and 1s but then output it as the more visually pleasing grid of asterisks and blanks!

Constructing the LifeGrid

After the opening information about the game of Life and the maximum size allowed for a grid, the main() function in life.cpp begins by creating the LifeGrid array grid as a MAX_ROWS x MAX_COLUMNS array. It then asks the user for the name of a file containing a Life pattern and vvvopens an ifstream named fin to that file.

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 those cells. For example, our 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 5 × 5 grid (as specified in the first line of the file), each 1 represents a cell containing an organism and each 0 represents a cell without an organism. Note: Any whitespace can be used to separate the cells in the file; in this example, single spaces and newlines were used to make it easy to read.

Question #11.2 At comment #2 in main() of life.cpp, write code to read the number of rows and columns in the grid of cells from the data file via the input file stream fin. Then use nested for loops to copy the 0s and 1s from the data file via the ifstream fin into the upper-left corner of grid — i.e., this grid of cells would be copied into rows 0, 1, ..., 4 and columns 0, 1, ..., 4 of grid.

Now that the Life configuration has been transferred from the file to grid, we can move on to task #2 in our design plan:

2. Display the contents of this file on the screen so they can be checked.

Question #11.3 At comment #3 in main() of life.cpp, display the contents of grid using the same format as shown above:
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

The display() Function

The format of our output of grid is the same as that in the data file from which its contents were transferred. But in the game of Life, the grids are shown as grids of cells in which an asterisk is used instead of 1 and a space instead of a zero. The function display() will output grid in this asterisk-space format. And to give it somewhat of a grid-like appearance, it will output periods to mark the corners of the cells.

Also, for some patterns it can take a large number of generations to study their behaviors. To make it easier to study the successive generations, we will output them to a file so they can be examined later.

Question #11.4 The opening statements of the function display() output a top border for the grid by writing a series of period-space combinations ( ". " ) to a file via the ifstream fout. At comment #4 in the definition of this function, write nested loops to output the rest of the grid by outputting in each row:

    ". " (to mark the left border) followed by "* " for each 1 and ". " for each 0 in that row.

For the file "test.file", the first two generations will be output as:

Generation #1
. . . . . . . 
. . . . . . .
. . . . . . .
. . * * * . .
. . . . . . .
. . . . . . .
. . . . . . . 

Generation #2
. . . . . . . 
. . . . . . .
. . . * . . .
. . . * . . .
. . . * . . .
. . . . . . .
. . . . . . . 

Here is an algorithm for this part of display() that may help with writing the code:

Generating The Next Generation

The function generate() is the workhorse of this program because it must encode the rules of the game:

In order to process all of the cells, we will need two nested for loops again to process the rows and columns of grid. The inner loop should count the number of neighbors for the current cell and then set the value of that cell appropriately as required by the rules of the game.

But there are two problems. First, the next generation is determined by the current generation. We cannot overwrite the current generation with the next one because the current generation is needed to determine the next. So we will begin by making a copy of grid and then use this copy to calculate each cell's neighbors.

The second problem is that cells at the edges of the grid do not have the required eight neighbors. To simplify things, we'll assume that these are "boundary" cells and don't ever change; so we can simply exclude them from consideration by letting the row index run from 1 to numRows − 1 and the column index run from 1 to numColumns − 1.

This gives the following (partial) algorithm for generating the next grid of cells:

  1. Make a copy newgrid of grid.
  2. For each index r in the range from 1 to numRows − 1
          For each index c in the range from 1 to numColumns − 1
              a. Calculate topNeighbors = grid[r - 1][c - 1] + grid[r - 1][c] + grid[r - 1][c + 1]
              b. bottomNeighbors = ???
              c. sideNeighbors = ???
              d. Calculate neighbors = sum of the three preceding sets of neighbors.
              e. Apply the rules of the game to set newgrid[r][c]
  3. Now copy newGrid to grid. (Because it is a reference parameter, it will be passed back to main().)

As we noted earlier, because 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 in Step 2-d of the algorithm.

The algorithm, however, leaves two of the computations unfinished for you to complete. Use the topNeighbors computation and the picture of a cell at the beginning of this exercise to finish the other computations.

Question #11.5
  1. Complete the algorithm above for generating a new Life generation by finding the formulas to replace the ???s in the computations of bottomNeighbors and sideNeighbors.

  2. Then, using this algorithm, complete the definition of the function generate(). Compile your code, and test the program using When completed, your program should be ready to process other initial configurations.

Playing 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. Although gave us a simple way to check how our program was working, it is a rather uninteresting configuration because very little changes as time passes.

Now try the configuration in Here the generations don't change at all from one to the next — thus the name. Some initial configurations appear to be unstable but after awhile, they reach stability. Try for an example. And for some configurations, The society of organisms quickly breaks down and after a few generations, becomes extinct; is one such example.

Sometimes adding or removing a few individuals makes all the difference between on how a society changes. To illustrate thus, here is the initial configuration in; it is sometimes referred to as an iron cross:


    * * *
*     *     *
* * *   * * *
*     *     *
    * * *
Now suppose we add an organism at the end of each cross, as in
      * * *
  *     *     *
* * * *   * * * *
  *     *     *
      * * *

Question #11.6: How do the generations of this cross-society compare with those of 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 This 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 #11.7: What happens with the gliders in Try at least 35 generations. (Looks like we've come full circle!)


The file contains a 25 × 35 grid of all 0s. Make several copies of this file and edit them to create your own original configurations and run them through the Life program. See if you can find a simple initial configuration that is still changing after 100 generations.

Lab Home Page

Report errors to Larry Nyhoff (