We have seen that we can use arrays or
vectors to store
sequences of values. For example, the declarations
define an object
arrvec as a container that can store
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
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;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
magicSquarewith 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 (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:
For example, suppose that we begin with the following configuration of three organisms:
Then applying the rules, we can generate the next generation:
— and those in the last column —
— have no neighbors and thus remain empty.
each have one neighbor so they also remain empty.
each have one neighboring organism, so the organism in them dies of loneliness.
have three neighboring organisms, so an organism is born in each of them.
has two neighbors, so it remains unchanged.
Represented graphically, the second generation is
To get the third generation, we apply the rules to the second generation.
Organisms are born in cells
the organisms in cells
 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.
life.cppimplements the game of Life. It reads the initial configuration from a data file, stores it in a two-dimensional array, and displays its contents so it can be checked by the user. It will then ask the user for the number of successive generations to be produced and will then produce and output them to a file specified by the user.
You should download this file and add your name and other information required by your instructor to the opening documentation. As you work through this lab exercise, you will be adding to and/or modifying this program.
test.lifethat you will use in this lab exercise contains the following initial configuration for the simple three-organism oscillating pattern described earlier:
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
This lab exercise is to complete the
This will involve adding and testing code to do the following:
display()function to output each generation to a file via an
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.
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];
COLUMNSare integer constants that specify the array's dimensions;
ElementTypeis the type of its elements; and
ArrayTypeIdentiferis the name of this new type that we have defined.
Question #11.1 Define an array type namedWe turn now to the question of why we are using
LifeGridat 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 int) for the type of the array elements.
shortfor 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
charfor the cell type?
If we look at the most important operation of a
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!
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
grid as a
It then asks the user for the name of a file containing a Life pattern and
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
In this 5 × 5 grid (as specified in the first line of the file), each5 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
1represents a cell containing an organism and each
0represents 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
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 fininto 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
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
life.cpp, display the contents of
gridusing 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
gridis 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
gridin 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
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:
rin the range 0 .. numRows do the following:
" // for the left border
If grid[r][c] is 1
generate() is the workhorse of this program
because it must encode the rules of the game:
c should contain a 1.
or c has more than three neighbors containing 1s, then
c should contain a 0.
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:
rin the range from 1 to
cin the range from 1 to
grid[r - 1][c - 1] + grid[r - 1][c] + grid[r - 1][c + 1]
neighbors= sum of the three preceding sets of neighbors.
grid. (Because it is a reference parameter, it will be passed back to
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
- 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.
- Then, using this algorithm, complete the definition of the function
generate(). Compile your code, and test the program using
test.life. When completed, your program should be ready to process other initial configurations.
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
test.life 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
stable.life. 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
quick.life 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
cross1.life; 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
glider.life. 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
gliders.life? Try at least 35 generations. (Looks like we've come full circle!)
blank.life 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