3
\$\begingroup\$

Here is an implementation of Conway's Game of Life. It is kind of a brute force but it works fine. I have a special question about the method cv::Mat render() const, which renders and returns a cv::Mat. Should I return a reference cv::Mat& render() const or allocate an object on the heap and return the pointer? I would also appreciate any constructive feedback about my coding style (especially about how I handle and access memory), which is very influenced by Java IMO.

#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#include <opencv2/opencv.hpp>
#include <cstdlib>
#include <ctime>
#include <random>
#include <windows.h>
#include <vector>

#define UPSAMPLING 10

/**
 * Generating random number
 */
inline int random(int bottom, int top) {
    std::random_device dev;
    std::mt19937 rng(dev());
    std::uniform_int_distribution <std::mt19937::result_type> dist(bottom, top - 1);
    return dist(rng);
}


/**
 * Board game
 */
class Board {
public:
    std::vector <std::vector<bool>> cells;
    int width;
    int height;

    Board(int width, int height) : width(width), height(height) {
        this->cells = std::vector < std::vector < bool >> (height, std::vector<bool>(width, false));
        std::random_device dev;
        std::mt19937 rng(dev());
        std::uniform_int_distribution <std::mt19937::result_type> distX(0, width - 1);
        std::uniform_int_distribution <std::mt19937::result_type> distY(0, height - 1);
        for (int i = 0; i < (width * height) / 2; i++) {
            int x = distX(rng);
            int y = distY(rng);
            cells[y][x] = true;
        }
    }

    inline int aliveNeighbors(int x, int y) const {
        int ret = 0;
        for (int yi = y - 1; yi <= y + 1; yi++) {
            if ((yi >= 0 && yi < this->height)) {
                for (int xi = x - 1; xi <= x + 1; xi++) {
                    if (xi >= 0 && xi < this->width) {
                        if (xi != x || yi != y) {
                            ret += cells[yi][xi];
                        }
                    }
                }
            }
        }
        return ret;
    }

    void nextRound() {
        std::vector <std::vector<bool>> ret(this->height, std::vector<bool>(width, false));
        for (auto y = 0UL; y < this->cells.size(); y++) {
            for (auto x = 0UL; x < this->cells[y].size(); x++) {
                int aliveNs = this->aliveNeighbors(x, y);
                if (!cells[y][x]) {
                    if (aliveNs == 3) {
                        ret[y][x] = true;
                    }
                } else {
                    if (aliveNs < 2 || aliveNs > 3) {
                        ret[y][x] = false;
                    } else {
                        ret[y][x] = true;
                    }
                }
            }
        }
        this->cells = ret;
    }

    cv::Mat render() const {
        cv::Mat ret = cv::Mat::zeros(width * UPSAMPLING, height * UPSAMPLING, CV_8UC3);
        for (auto y = 0UL; y < this->cells.size(); y++) {
            for (auto x = 0UL; x < this->cells[y].size(); x++) {
                if (cells[y][x]) {
                    cv::Vec3b color(random(0, 255), random(0, 255), random(0, 255));
                    for (auto kx = 1; kx < UPSAMPLING; kx++) {
                        for (auto ky = 1; ky < UPSAMPLING; ky++) {
                            ret.at<cv::Vec3b>(x * UPSAMPLING + kx, y * UPSAMPLING + ky) = color;
                        }
                    }
                }
            }
        }
        return ret;
    }
};

int main() {
    int size = 100;
    Board board(size, size);
    cv::namedWindow("Conway game of life", cv::WINDOW_AUTOSIZE);
    while (cv::waitKey(1) != 27) {
        auto frame = board.render();
        cv::imshow("Conway game of life", board.render());
        board.nextRound();
        Sleep(100);
    }
    cv::destroyAllWindows();
    return 0;
}
\$\endgroup\$
2
  • \$\begingroup\$ This seems to be missing the definitions of HkCluster and generateColors. \$\endgroup\$ – Edward May 26 '20 at 12:43
  • \$\begingroup\$ @Edward I excluded the definition because it was not relevant for the implementation. However I forget to delete their usages. Thank you \$\endgroup\$ – Long Nguyen May 26 '20 at 12:50
5
\$\begingroup\$

This code is neat and easy to read and understand. Good job! Here are some things that may help you improve your program.

Write portable code

This code can easily compile and run on Linux as well as Windows with a few small changes. First, eliminate #include <windows.h> because it won't be needed. Next, instead of using Sleep(100) we could use this:

    std::this_thread::sleep_for(100ms);

That makes it portable, but there's a better way.

Understand your code libraries

The cv::waitKey takes as its argument, the number of milliseconds to show the image. So what this means is that you can simply delete the line that says Sleep(100) and change the while loop to this:

while (cv::waitKey(100) != 27) {

Eliminate unused variables

The variable frame in your main code is defined but never used. Since unused variables are a sign of poor code quality, you should seek to eliminate them. Your compiler is probably smart enough to warn you about such things if you know how to ask it to do so.

Use const and constexpr where practical

It's good that you used a named variable for size in main but it could be improved slightly by also declaring it const or better, constexpr. I'd do the same with the title, rather than repeating the string:

auto constexpr title = "Conway game of life";

Also the UPSAMPLING constant would be better as a constexpr int rather than a #define. Making that change allows for type checking and costs nothing in terms of runtime performance.

Use only required #includes

The code has several #includes that are not needed. This clutters the code and makes it more difficult to read and understand. Only include files that are actually needed. In this case, the only required includes are these:

#include <opencv2/opencv.hpp>
#include <random>
#include <vector>

Don't reseed the random number generator more than once

The program currently constructs and reseeds the random number generator with every call to random. This is really neither necessary nor advisable. Instead, just call it once when the program begins. We can do that by making the first two variables static like this:

inline int random(int bottom, int top) {
    static std::random_device dev;
    static std::mt19937 rng(dev());
    std::uniform_int_distribution <std::mt19937::result_type> dist(bottom, top - 1);
    return dist(rng);
}

Make data members private

There doesn't appear to be any reason for data members of Board to be public, so best practice is to make them private.

Simplify expressions

The code contains some expressions which seem overly verbose. For example, instead of this:

if (!cells[y][x]) {
    if (aliveNs == 3) {
        ret[y][x] = true;
    }
} else {
    if (aliveNs < 2 || aliveNs > 3) {
        ret[y][x] = false;
    } else {
        ret[y][x] = true;
    }
}

I would write this:

ret[y][x] = (aliveNs == 3) || (aliveNs == 2 && cells[y][x]);

Use standard library functions

The constructor for Board is currently this:

Board(int width, int height) : width(width), height(height) {
    this->cells = std::vector < std::vector < bool >> (height, std::vector<bool>(width, false));
    std::random_device dev;
    std::mt19937 rng(dev());
    std::uniform_int_distribution <std::mt19937::result_type> distX(0, width - 1);
    std::uniform_int_distribution <std::mt19937::result_type> distY(0, height - 1);
    for (int i = 0; i < (width * height) / 2; i++) {
        int x = distX(rng);
        int y = distY(rng);
        cells[y][x] = true;
    }
}

That's not wrong, but it's much more complicated than it needs to be. Here's how I'd write that:

Board(int width, int height, float density = 0.5) : 
    width(width),
    height(height),
    cells((width + 2) * (height + 2))
{
    std::random_device dev;
    std::mt19937 rng(dev());
    std::bernoulli_distribution b(density);
    std::generate(cells.begin(), cells.end(), [&b, &rng](){ return b(rng); });
}

Now instead of explicitly looping, we use std::generate and we use std::bernoulli_distribution explicitly to show that 50% of the cells should be populated by default, but it's a parameter (density) that may be altered by the caller. I've also changed the member data variable to this:

const unsigned width;
const unsigned height;
std::vector <bool> cells;

By having a single vector, we have a more compact structure. This requires some adjustments to the rest of the code, as shown in the following suggestion.

Use iterators instead of indexing

The double array indexing is not a particularly efficent way of traversing a data structure. Better, in my view, would be to use a single dimension array and then use an iterator. For instance, here is how I would write the aliveNeighbors function:

inline int aliveNeighbors(std::vector<bool>::const_iterator it) const {
    static const std::array<int, 8> deltas {
        -2-1-width, -2-width, -2+1-width,
            -1,             +1,
        +2-1+width, +2+width, +2+1+width,
    };
    return std::accumulate(deltas.begin(), deltas.end(), 0, [this, it](int neighbors, int delta){
                return neighbors + *(it+delta);
            });
}

This uses a number of things. First, it uses a static const std::array to store the deltas to the neighbors, given an iterator. That is, it allows the program to compute the location of each neighbor. Next, we use std::accumulate to iterate through the deltas and count the neighbors. It uses a lambda as the function to accumulate the neighbor count. There is another implicit feature that helps simplify the code. That feature is the next suggestion.

Simplify range checking by eliminating the need for it

The existing aliveNeighbors code does a lot of checking to make sure that all of the checked neighbors are in range. That's much better than not checking and overrunning the bounds of the board, but there's a simpler way to accomplish the same effect. You may have noticed that the initialization of cells above was this:

cells((width + 2) * (height + 2))

The purpose for the additional two rows and two columns is to act as a frame around the real board. This allows the aliveNeighbors code above to omit checking because the calling code assures that the iterator is always within the real board. So nextRound() looks like this:

void nextRound() {
    std::vector <bool> ret(cells.size());
    auto src = cells.begin() + 3 + width;
    auto dst = ret.begin() + 3 + width;
    for (auto y{height}; y; --y) {
        for (auto x{width}; x; --x) {
            int aliveNs = aliveNeighbors(src);
            *dst = (aliveNs == 3) || (aliveNs == 2 && *src); 
            ++src;
            ++dst;
        }
        src += 2;
        dst += 2;
    }
    std::swap(cells, ret);
}

The last line uses swap as described in the next suggestion.

Use swap to replace large data structures

Unlike Java, C++ requires the programmer to manage memory. While modern C++ makes this mostly fairly painless, there are some aspect to be aware of. This is a slight variation on the copy-and-swap idiom. Here, the ret is created and then populated, and then swapped with the original cells array. Because ret goes out of scope at the end of the function, the destructor will run. By using swap, the destructor will operate on the previous version of cell, neatly releasing the memory.

Fix the bug

In the current version of render we have this code:

cv::Mat ret = cv::Mat::zeros(width * UPSAMPLING, height * UPSAMPLING, CV_8UC3);

The problem is that the first two arguments to zeros are rows and columns, so these should be swapped for the code to work correctly for non-square boards. The same reversal is required for the ret.at<> line.

Thoughts on efficiency

Since a delay is part of the program, making the program run faster isn't necessarily a goal, but here are some thoughts on efficiency if you wanted to explore this further. First, I realized belatedly that I hadn't answered your question about the return value for Board::render(). In my view, you have it exactly right in the code now. Returning a reference would be an error because, as soon as the function ends and the ret variable goes out of scope, the destructor is called, rendering a reference invalid. When you return by value as the current code has it, notionally, a copy is created. (I say "notionally" because most compilers are, in fact, smart enough to implement Named Return Value Optimization (NRVO) to avoid actually making a copy.) Also, while you could allocate on the heap and return a pointer, freeing that memory now becomes another problem. For all of these reasons, I'd say that the way you have it is just right.

However, one option for a possible efficiency gain would be for the Board object to contain two copies of the board and simply keep track of which is the current view within nextRound() and render(). That way instead of reallocating a new one (and destroying one) on each call to nextRound, the program could simply use the same two vectors and simply swap them each loop iteration.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you very much. I really enjoyed your detailed review which pointed out many things I overlooked. I wish you all the best. \$\endgroup\$ – Long Nguyen May 26 '20 at 20:14

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.