1
\$\begingroup\$

I have programmed Conway's Game of Life in C++.

/*
    Any live cell with fewer than two live neighbors dies, as if by under population.
    Any live cell with two or three live neighbors lives on to the next generation.
    Any live cell with more than three live neighbors dies, as if by overpopulation.
    Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
*/

#include <iostream>
#include <fstream>
#include <array>
#include <vector>
#include <string>
#include <stdlib.h>

#define EXTRA_SPACE 1
#define GRID_SIZE 35

#define ALIVE_CELL '#'
#define DEAD_CELL ' '

struct CellCoords { int y, x; };

void setup_grid();
void generation();
void display_grid();
void sleep(int);

std::array<std::array<char, GRID_SIZE + EXTRA_SPACE * 2>, GRID_SIZE + EXTRA_SPACE * 2> grid;

int main() {

    setup_grid();

    int gen = 1;

    do {
        system("cls");
        std::cout << std::endl << "Generation " << gen << std::endl;
        display_grid();
        sleep(100);
        generation();
        gen++;
    } while (true);

    std::cin.get();
    return 0;
}

void setup_grid() {

    std::ifstream file("grid.txt");
    std::string line;
    int i = EXTRA_SPACE;

    while (std::getline(file, line)) {
        for (int j = EXTRA_SPACE; j < GRID_SIZE; j++) {
            if (line[j] == '1')
                grid[i][j] = ALIVE_CELL;
            else
                grid[i][j] = DEAD_CELL;
        }
        i++;
    }

    file.close();
}

void generation() {

    std::vector<CellCoords> cells_to_kill;
    std::vector<CellCoords> cells_to_be_born;

    int neighbors;

    for (int y = EXTRA_SPACE; y < GRID_SIZE; y++) {
        for (int x = EXTRA_SPACE; x < GRID_SIZE; x++) {

            neighbors = 0;

            if (grid[y - 1][x    ] == ALIVE_CELL) neighbors++;
            if (grid[y - 1][x + 1] == ALIVE_CELL) neighbors++;
            if (grid[y    ][x + 1] == ALIVE_CELL) neighbors++;
            if (grid[y + 1][x + 1] == ALIVE_CELL) neighbors++;
            if (grid[y + 1][x    ] == ALIVE_CELL) neighbors++;
            if (grid[y + 1][x - 1] == ALIVE_CELL) neighbors++;
            if (grid[y    ][x - 1] == ALIVE_CELL) neighbors++;
            if (grid[y - 1][x - 1] == ALIVE_CELL) neighbors++;

            if (grid[y][x] == ALIVE_CELL) {
                if (neighbors < 2 || neighbors > 3)
                    cells_to_kill.push_back({ y, x });
            } else if (neighbors == 3) {
                    cells_to_be_born.push_back({ y, x });
            }
        }
    }

    for (int i = 0; i < cells_to_kill.size(); i++) {
        CellCoords cell = cells_to_kill[i];
        grid[cell.y][cell.x] = DEAD_CELL;
    }

    for (int i = 0; i < cells_to_be_born.size(); i++) {
        CellCoords cell = cells_to_be_born[i];
        grid[cell.y][cell.x] = ALIVE_CELL;
    }
}

void display_grid() {

    std::cout << std::endl;

    for (int y = EXTRA_SPACE; y < GRID_SIZE; y++) {
        for (int x = EXTRA_SPACE; x < GRID_SIZE; x++) {
            std::cout << grid[y][x] << ' ';
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

void sleep(int time) {
    for (int i = 0; i < time; i++);
}

How can I improve the code? Was making an extra 2 rows and columns in the grid array a good idea?

\$\endgroup\$
3
\$\begingroup\$

Consider making a class for the grid

To answer your specific question: yes, padding the grid with a couple of extra cells makes your logic simpler, but I'll show an alternative approach that you might like to consider.

Instead of a global array with fixed size, let's make a Grid class that knows how to find an element:

class Grid
{
public:
    Grid(std::size_t width, std::size_t height);

    char operator()(int x, int y) const;
    void set(int x, int y, char value);
};

This gives us the ability to implement operator() to do what we want at the edges. We could say that all cells outside the bounds are dead and cannot support life (as the existing code does), or that alternating cells alive (as a checkerboard pattern around the grid: (x + y) % 2), or wrap around (so the board forms a torus), or reflect the board (as if in a mirror). This method of extending beyond the bounds of the data is a common technique when processing raster images, so it's a good learning point to take from this review.

When implementing this structure (with variable width and height), it's natural to simply substitute the array of arrays with a vector of vectors. That would be a mistake, because the vector's storage is outside the object, and we lose locality of reference. Instead, it's better to use a flat array, and use a method to find a point's location:

class Grid
{
    int width;
    int height;
    std::vector<char> m = {};

    const char& cell(int x, int y) const;
    char& cell(int x, int y);
public:
    Grid(int width, int height);

    char operator()(int x, int y) const;
    void set(int x, int y, char value);
};

Grid::Grid(int width, int height)
    : width{width}, height{height}
{
    if (width <= 0) { throw std::out_of_range("width"); }
    if (height <= 0) { throw std::out_of_range("height"); }
    m.resize(width * height);
    std::fill(m.begin(), m.end(), DEAD_CELL);
}

const char& Grid::cell(int x, int y) const
{
    return m[x + y * width];
}
char& Grid::cell(int x, int y)
{
    return m[x + y * width];
}

char Grid::operator()(int x, int y) const
{
    if (x < 0 || x >= width || y < 0 || y >= height) {
        // out of range - pad values
        return DEAD_CELL;
    }
    return cell(x, y);
}

void Grid::set(int x, int y, char value)
{
    if (x < 0 || x >= width || y < 0 || y >= height) {
        // out of range - ignore
        return;
    }
    cell(x, y) = value;
}

Instead of filling the array with DEAD_CELL, we could choose instead to use 0 and 1 for dead and live cells respectively, and convert to printable characters only for I/O. (Don't change m to vector<bool>, though - that's a problematic specialization that's worth avoiding).

Obviously, once we have a Grid class, then reading, printing and iterating the grid can all become members of the class (and possibly we don't need the public set() that I wrote above).


Reduce memory allocation and release

One area of inefficiency in the code is the use of lists of actions at each generation. Every generation() creates two new vectors, meaning at least two allocations. It's worth having these vectors be members of the Grid and just clear() them after each iteration, so that the storage isn't repeatedly allocated an released.

An alternative approach keeps a second vector of cells around to write to (this is another image-processing technique). For a quiet board, this is likely more storage, but it's a constant amount, and not allocated or released. It's even possible to combine current and next generation into the same grid storage, using different bits in the char elements, but that will then require another pass over the data to move from one generation to the next, compared with a simple swap() when using two vectors:

void Grid::next_generation()
{
    // Compute next generation into m2
    for (int y = 0;  y < height; ++y) {
        for (int x = 0;  x < width;  ++x) {
            int neighbours = (*this)(x - 1, y - 1)
                +            (*this)(x - 1, y    )
                +            (*this)(x - 1, y + 1)
                +            (*this)(x    , y - 1)
                +            (*this)(x    , y + 1)
                +            (*this)(x + 1, y - 1)
                +            (*this)(x + 1, y    )
                +            (*this)(x + 1, y + 1);
            m2[x + y * width] = is_alive((*this)(x,y), neighbours);
        }
    }
    // Now make m2 the current generation
    m.swap(m2);
}

I've moved the policy logic (which determines whether the result cell should live) to its own function:

static bool is_alive(bool alive_now, int neighbours)
{
    switch (neighbours) {
    case 0:
    case 1:
        // underpopulation
        return false;
    case 2:
        // survival
        return alive_now;
    case 3:
        // reproduction
        return true;
    case 4:
    case 5:
    case 6:
    case 7:
        // overpopulation
        return false;
    }
    // neighbours must be in range 0-7
    assert(false);
}

A Grid to go with that looks like this:

class Grid
{
    int width;
    int height;
    std::vector<char> m = {};   // 0 = dead, 1`= alive
    std::vector<char> m2 = {};  // double-buffer m
public:
    Grid(int width, int height);

    char operator()(int x, int y) const;

    void next_generation();
};

Grid::Grid(int width, int height)
    : width{width}, height{height}
{
    if (width <= 0) { throw std::out_of_range("width"); }
    if (height <= 0) { throw std::out_of_range("height"); }
    m.resize(width * height);
    m2.resize(width * height);
}

char Grid::operator()(int x, int y) const
{
    if (x < 0 || x >= width || y < 0 || y >= height) {
        // out of range - pad values
        return 0;
    }
    return m[x + y * width];
}

Details review

#include <stdlib.h>

Prefer <cstdlib> when writing new C++ code, then qualify std::system() where we use it.

#define EXTRA_SPACE 1
#define GRID_SIZE 35

Avoid preprocessor macros; prefer constexp int instead.

void setup_grid();
void display_grid();

These could be >> and << streaming operators for the Grid class.

The free functions ought to have internal linkage; declare them in the anonymous namespace to prevent conflicts if you want to combine with other programs one day.

   system("cls");

Always check the return value of system(). Here, you're executing a program that doesn't exist on my system, so it just gives a whole lot of error output. If this is intended to clear the screen, consider using a Curses implementation (but be aware that it's still not going to be effective when output is going to a file, a printer or an Emacs buffer). As it's the only part of the code that's not portable C++, it's well worth considering another approach here.

std::ifstream file("grid.txt");
std::string line;

while (std::getline(file, line)) {

We need to check whether any of this succeeds. At present, if the file can't be read, the whole array remains default-initialized, which is really not what we want. If the file is incomplete, then at least part of the array won't be correctly set. Worse that than, if the file has more than GRID_SIZE + EXTRA_SPACE lines, then we write outside of grid, which is Undefined Behaviour. This function really needs a lot more error checking.

And don't hard-code the name of the input file. It's much better to allow the user to pass it as a command-line argument - or we could even read from standard input.

       if (line[j] == '1')

Why are we using different characters for input than the ones we use for output? If we make input and output formats compatible, it's probably to our advantage.

file.close();

Since we're not checking the status of file after closing, we can omit this and just let the destructor do the closing.

for (int y = EXTRA_SPACE; y < GRID_SIZE; y++) {
    for (int x = EXTRA_SPACE; x < GRID_SIZE; x++) {

The upper limit needs to be GRID_SIZE + EXTRA_SPACE. This problem is repeated in display_grid(), too.

for (int i = 0; i < cells_to_kill.size(); i++) {

We're comparing signed and unsigned types here, which probably indicates that we need to enable more compiler warnings. We could fix this by making i a std::size_t. Better still would be to use range-based for:

for (auto const& cell: cells_to_kill) {
    grid[cell.y][cell.x] = DEAD_CELL;
}

for (auto const& cell: cells_to_be_born) {
    grid[cell.y][cell.x] = ALIVE_CELL;
}
void sleep(int time) {
    for (int i = 0; i < time; i++);
}

This doesn't necessarily do what it claims. It has no side-effects, and a good compiler is perfectly entitled to treat this as a no-op. Even if you do manage to create a busy-loop, that's very rude to other processes (and to the power consumption, even on an otherwise idle system) and is highly variable depending on the target system's processing speed.

It's not clear what the units are intended to be; we can make the formal argument name be more descriptive than time (and/or rename the function - then it won't clash with POSIX sleep() for instance):

#include <chrono>
#include <thread>
void sleep_ms(int milliseconds) {
    std::this_thread::sleep_for(std::chrono::milliseconds(milliseconds));
}
\$\endgroup\$
  • \$\begingroup\$ class cell; class const_cell; are these intentional in the first code listing? I don't see them mentioned anywhere. \$\endgroup\$ – user673679 Sep 21 '18 at 15:34
  • \$\begingroup\$ Thanks @user673679 - a leftover of something I decided against in the end. Now removed. \$\endgroup\$ – Toby Speight Sep 25 '18 at 7:46
3
\$\begingroup\$

Overall, this is pretty good. You've avoided the most common mistakes I see, like bad naming, using magic numbers, passing bare values that really belong together in a data structure. Nice job! I appreciate the comment at the top that explains the rules, too.

To answer your question, I think that using the extra rows and columns is a great idea. They're 2 characters per row, and 2 extra rows. It's not a lot of memory, and it makes the code much cleaner.

Here are some thoughts on some things that could be improved.

Avoid Globals

Your game board is a global variable. You've structured the code nicely, so it only ever gets modified in generation(), but small programs have a tendency to become large programs, and global variables in large programs have a tendency to get modified all over the place. I'd move the grid variable into main() and pass a reference to it into the various functions that use it.

Always Name Your Arguments

Your definition of the sleep() function looks like this:

void sleep(int);

What is the int? A function prototype with unnamed arguments is close to useless. Now I have to read through the function to get any useful information about what the parameter means. If it was named something like iterations or time like in the actual function it would be infinitely better.

Things in main()

The gen variable is set up, and it's incremented, but it's never checked. It's just busywork for your CPU. If you were going to use it to bail out of the loop after so many iterations, it would be useful, but you've made an infinite loop. So I'd just get rid of it.

You're using std::endl at the end of every line you print. That's pretty heavy-weight. It flushes the output buffer. I'd say in most cases you want to just use "\n" instead. Maybe you could use std::endl after printing the last character of the board.

Your command to clear the screen is non-standard. My system doesn't have a command named cls on it, so that just outputs an ugly error message. I don't do a lot of console programming, so I'm not sure if there's a universal way to clear the screen, but you might look into ANSI escape codes.

The sleep() Function

Likewise, your sleep() function has some issues. There's a standard POSIX function named sleep() that is often used to sleep the process for an amount of time. I don't know whether it exists on Windows or not. But regardless of that, the way you've implemented it, it will sleep for a different amount of time on different machines. So a 1GHz machine will probably take twice as long to complete that loop as a 2GHz machine. You probably don't want that. I recommend finding a more standard method for performing sleep on your target system. Something that at least checks the clock rather than just counting.

According to the comments, you can use:

#include <chrono>
#include <thread>
...
std::this_thread::sleep_for(std::chrono::milliseconds(500));

setup_grid()

For the most part, setup_grid() looks pretty decent. If any errors occur, you will end up with a partially uninitialized grid, though. You might want to at least clear it all to DEAD_CELL to start with so you have something sensible in there. Better yet, if any errors occur, return them to the caller and let the caller decide how to handle them (tell the user, exit the program, whatever).

You don't need the file.close() at the end. The destructor for std::ifstream will call it for you when the function ends.

generation()

This function is pretty well written, too. I didn't have time to do timing trials, but I have to wonder if using the same grid for input and output is fastest? (Not that it matters given your sleep() function!) Another way to handle it would be to pass in 2 grids - the current state and the next state. Rather than noting which cells changed and then overwriting them, you'd simply fill in the new cells given the state of the old cells. It might be a wash, though. You could code it up and profile it to be sure.

There's nothing wrong with the set of if statements you have for checking the cells. In fact, some would argue that you've done loop unrolling which could theoretically improve performance. I think it would be easier to read, though, if it were done in a loop like this:

for (int cell_y = y - 1; cell_y < y + 1; ++cell_y) {
    for (int cell_x = x - 1; cell_x < x + 1; ++cell_x) {
        if (grid[cell_y][cell_x] == ALIVE_CELL) {
            neighbors++;
        }
    }
}

As noted, this will count the current cell, so you can subtract it out at the end with:

if (grid[y][x] == ALIVE_CELL) {
    neighbors--;
}

At the very least, you should avoid writing the condition and the statement it executes on the same line, as it makes it impossible to tell whether the statement executed or not when stepping through with a debugger. Not a big deal here, but it can be in larger programs, so it's a good habit to avoid putting it all on one line.

I recommend always using braces in if statements, even if they're only one line as that avoids another common error, which is adding a line to an if without realizing you didn't actually add it. Like this:

 if (someCondition)
    doSomething();
    doSomethingElse();

In this case, doSomethingElse(); will be called regardless of whether someCondition is true or false because there are no braces around the intended body of the if statement.

\$\endgroup\$
  • 2
    \$\begingroup\$ std::this_thread::sleep_for(std::chrono::milliseconds(500)); with <thread> and <chrono> includes is the cross-platform way to sleep. \$\endgroup\$ – user673679 Sep 20 '18 at 6:55
  • 1
    \$\begingroup\$ Your replacement loop mistakenly counts the current cell amongst the neigbours - you either need to skip that value, subtract it afterwards, or adjust how the rules are applied. \$\endgroup\$ – Toby Speight Sep 21 '18 at 9:46
  • 1
    \$\begingroup\$ Oh, good catch! I will update it. Thanks! \$\endgroup\$ – user1118321 Sep 21 '18 at 14:22
  • \$\begingroup\$ @user673679 Thanks! I've added that as well. \$\endgroup\$ – user1118321 Sep 21 '18 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.