16. Vectors of vectors¶
The last three chapters of this book use 2D graphics to illustrate more ad- vanced object-oriented concepts. If you haven’t yet read Appendix C, you might want to read it now and become familiar with the ncurses API. In this chapter, we use these classes to draw characters, read user input, and to run graphical simulations.
16.1. Conway’s Game of Life¶
The Game of Life, or GoL for short, was developed by John Conway and popularized in 1970 in Martin Gardner’s column in Scientific American. Conway calls it a “zero-player game” because no players are needed to choose strategies or make decisions. After you set up the initial conditions, you watch the game play itself. That turns out to be more interesting than it sounds; you can read about it at Conway’s Game of Life.
The game board is a 2D grid of square cells. Each cell is either alive or dead; the color of the cell indicates its state. Figure 15.1 shows an example grid configuration; the five black cells are alive.
The game proceeds in time steps, during which each cell interacts with its neighbors in the eight adjacent cells. At each time step, the following rules are applied:
A live cell with fewer than two live neighbors dies, as if by underpopulation.
A live cell with more than three live neighbors dies, as if by overpopulation.
A dead cell with exactly three live neighbors becomes a live cell, as if by reproduction
Notice some consequences of these rules. If you start with a single live cell, it dies. If all cells are dead, no cells come to life. But if you have four cells in a square, they keep each other alive, so that’s a stable configuration.
Another initial configuration is shown in Figure 15.2. If you start with three horizontal cells, the center cell lives, the left and right cells die, and the top and bottom cells come to life. The result after the first time step is three vertical cells.
During the next time step, the center cell lives, the top and bottom cells die, and the left and right cells come to life. The result is three horizontal cells, so we’re back where we started, and the cycle repeats forever.
Patterns like this are called periodic, because they repeat after a period of two or more time steps. But they are also considered stable, because the total number of live cells doesn’t grow over time.
Most simple starting configurations either die out quickly or reach a stable configuration. But there are a few starting conditions that display remarkable complexity. One of those is the R-pentomino, which starts with only five cells, runs for 1,103 time steps, and ends in a stable configuration with 116 live cells.
In the following sections, we’ll implement the Game of Life in C++. We’ll first implement the cells, then the grid of cells, and finally the game itself.
16.2. The Cell Class¶
When drawing a cell, we’ll need to know its location on the screen. To represent the location, we use the x and y coordinates of the upper-left corner.
To represent the state of a cell, we use an boolean, state, which is false for dead cells and true for live cells.
Here is a Cell class that declares these instance variables:
struct Cell {
const int x;
const int y;
bool state;
};
Notice that x and y are constants. Once the cell is created, we don’t want it to move or change size. But state can and should change, so it is not a constant.
The next step is to write a constructor. Here’s one that takes x and y as parameters, and sets state to a default value:
Cell::Cell(int x, int y) : x(x), y(y) {
this->state = false;
}
Notice how the x and y variables must be initialized using the initialized list because they are constant. The following method draws a cell. Like the paint method in Appendix C, it takes a graphics context as a parameter:
void Cell::draw() {
if (is_on()) {
mvaddch(y, x, '#');
} else {
mvaddch(y, x, ' ');
}
}
The draw member function uses the state of the cell to either draw a # if the cell is alive, or a space if the cell is dead. The mvaddch function tells ncurses to move the cursor to the given position and add the given character at that position.
We also need methods to get and set the cell’s state. We could just provide get_state and set_state, but the code will be more readable if we provide methods customized for the Game of Life:
bool Cell::is_on() {
return state;
}
bool Cell::is_off() {
return !is_on();
}
void Cell::turn_on() {
state = true;
}
void Cell::turn_off() {
state = false;
}
void Cell::toggle() {
if (is_on()) {
turn_off();
} else {
turn_on();
}
}
16.3. Two-Dimensional Arrays¶
To represent a grid of cells, we can use a multidimensional array. To create a 2D array, we create a vector of vectors:
vector<vector<Cell>> array = vector<vector<Cell>>();
The result is an empty 2d array. We can add items to this array using the push_back member function:
for (int row = 0; row < num_rows; row++) {
array.push_back(vector<Cell>());
for (int col = 0; col < num_cols; col++) {
array[row].push_back(Cell(col, row));
}
}
The loop variables row and col are the row and column indexes of the cell. Note how we have create a new empty vector for each row before we push to that row.
In C++, a 2D array is really an array of arrays. You can think of it as an array of rows, where each row is an array. Figure 15.3 shows what it looks like.
When we write array[row][col], C++ uses the first index to select a row and the second index to select an element from the row. This way of representing 2D data is known as row-major order.
16.4. The Grid Class¶
Now that we have a Cell class and a way to represent a 2D array of cells, we can write a class to represent a grid of cells. We encapsulate the code from the previous section and generalize it to construct a grid with any number of rows and columns:
struct Grid {
vector<vector<Cell>> array;
Grid(int rows, int cols) {
array = vector<vector<Cell>>();
array.reserve(rows);
for (int row = 0; row < rows; row++) {
array.push_back(vector<Cell>());
array[row].reserve(cols);
for (int col = 0; col < cols; col++) {
array[row].push_back(Cell(col, row));
}
}
}
};
Using vocabulary from the previous chapter, GridCanvas “has a” 2D array of cells.
The code to draw is surprisingly straightforward: to draw the grid, we simply draw each cell. We use nested for loops to traverse the 2D array:
int Grid::num_rows() {
return array.size();
}
int Grid::num_cols() {
return array[0].size();
}
The outer loop traverses the rows; the inner loop traverses the cells in each row. You can almost read this method in English: “For each row in the array, and for each cell in the row, draw the cell” Each cell contains its coordinates, so it knows how to draw itself.
16.5. Other Grid Functions¶
In addition to draw, the Grid class provides methods for working with the grid itself. num_rows and num_cols return the number of rows and columns. We can get this information from the 2D array, using length:
int Grid::num_rows() {
return array.size();
}
int Grid::num_cols() {
return array[0].size();
}
Because we are using row-major order, the 2D array is an array of rows. num_rows simply returns the length of the rows array. num_cols returns the length of the first row, which is the number of columns. Since the rows all have the same length, we have to check only one.
Grid also provides a function that gets the Cell at a given location.
Cell& Grid::get_cell(int row, int col) {
return array[row][col];
}