7
\$\begingroup\$

Here is my implementation of Conway's Game of Life in C++ which takes advantage of multi-threading. I'm using SFML 2.5.1 for a graphics library and CMake. I also use SFML's Vector classes for convenience.

Right now the game runs in a fixed sized grid world and the update() function that applies the game rules splits the world up into parts based on how many cores are available on the current machine and updates the sections in parallel. The cells and background areas are color-coded to represent the boundaries where the world is being run on the different CPU threads. The user can draw in more "live" cells by clicking and holding the left mouse button over the game grid. The world wraps around the edges, so cells at the bottom-right corner will consider the cells in the top-left to be some of their neighbors.

I've written this project because I'm a long-time C# developer trying to learn C++, I wanted to practice writing parallel code, and to practice with a project that needs to run fast (with memory requirements being less important right now).

Some highlights of what I'm trying to get out of this project and this code review:

  • How to write performant C++ code
  • Learn the STL
  • How to write clean, readable, reusable C++ code
    • Good C++ syntax
    • Good comment placement/syntax
  • Learn the things that C++ does that C# doesn't
    • Memory management
    • Pointers/References and to know when to use Pointers
    • Behind-the-scenes mechanisms like auto-instantiation of variables (e.g. pushing a new object into a std::vector<std::pair> like vector.push_back({"string", true}); automatically instantiates a new pair object.)

GitHub Repo

Main.cpp

#include "GameOfLife.h"
#include "WorldRenderer.h"
#include <iostream>
#include <SFML/Graphics.hpp>

using namespace std;

static const int WORLD_SIZE_X = 256;
static const int WORLD_SIZE_Y = 256;

int main()
{
    // create the window
    sf::RenderWindow window(sf::VideoMode(256, 256), "Game of Life");
    // scale the image up 2x size
    window.setSize(sf::Vector2u(512, 512));

    // disable vsync and uncap framerate limit
    window.setVerticalSyncEnabled(false);
    window.setFramerateLimit(0);

    // Create the game
    GameOfLife game(sf::Vector2i(WORLD_SIZE_X, WORLD_SIZE_Y));

    // Create a world renderer
    WorldRenderer worldRenderer;

    // Track if mouse button is being held down
    bool mouseHeld = false;

    // run the program as long as the window is open
    while (window.isOpen())
    {
        // check all the window's events that were triggered since the last iteration of the loop
        sf::Event event;
        while (window.pollEvent(event))
        {
            // "close requested" event: we close the window
            if (event.type == sf::Event::Closed)
                window.close();

            // capture if the user is holding left mouse button down
            if (event.type == sf::Event::MouseButtonPressed)
            {
                if (event.mouseButton.button == sf::Mouse::Left)
                    mouseHeld = true;
            } else if (event.type == sf::Event::MouseButtonReleased)
            {
                if (event.mouseButton.button == sf::Mouse::Left)
                    mouseHeld = false;
            }
        }

        // clear the window with black color
        window.clear(sf::Color::Black);

        // if left mouse button held down then make cells under cursor alive and pause simulation
        if (mouseHeld) {
            auto mousePosition = sf::Mouse::getPosition(window);

            // normalize mouse pos
            int x = (mousePosition.x / 512.0f) * WORLD_SIZE_X;
            int y = (mousePosition.y / 512.0f) * WORLD_SIZE_Y;

            // set cell under cursor to alive
            game.setCell(x, y, true);
        }
        else {
            // update the game world
            game.update();
        }

        // render the game
        worldRenderer.render(window, game);

        // end the current frame
        window.display();
    }

    return 0;
}

GameOfLife.h

#pragma once

#include <vector>
#include <SFML/Graphics.hpp>
#include "Cell.h"

class GameOfLife
{
public:
    GameOfLife(sf::Vector2i size);

    virtual ~GameOfLife() = default;

    // Returns a reference to the cell value at the given grid position.
    uint8_t & getCell(int x, int y);

    // Returns a vector of the given cell's grid position by it's cell index.
    sf::Vector2i get2D(int index);

    // Updates the state of the game world by one tick.
    void update();

    // Update the cells from position start (inclusive) to position end (exclusive).
    std::vector<Cell> GameOfLife::doUpdate(int start, int end, int coreIdx);

    // Set the value of the cell at the given grid position to the given alive state.
    void setCell(int x, int y, bool alive);

    // A cache of all the alive cells at the end of the update() call.
    std::vector<Cell> aliveCells;

    // The maximum amount of threads to be used for update().
    const int maxThreads;

    // Represents the width and height of the simulated world.
    sf::Vector2i worldSize;

    // Returns a color to use for cells/backgrounds based on the thread ID #.
    sf::Color getThreadColor(int index);

private:
    // A 1D representation of the 2D grid that is the world.
    std::vector<uint8_t> world;

    // A buffer where the next world state is prepared, swapped with world at end of update().
    std::vector<uint8_t> worldBuffer;   
};

GameOfLife.cpp

#include "GameOfLife.h"
#include "Cell.h"
#include <iostream>
#include <vector>
#include <math.h>
#include <thread>
#include <mutex>
#include <future>
#include <chrono>

GameOfLife::GameOfLife(sf::Vector2i size) : worldSize(size), world(size.x * size.y, false), worldBuffer(world), maxThreads(std::thread::hardware_concurrency())
{
    aliveCells.reserve(size.x * size.y); // reserve space for worst-case (all cells are alive)

    // place an "acorn"
    int midX = worldSize.x / 2;
    int midY = worldSize.y / 2; 
    getCell(midX + 0, midY + 0) = 1;
    getCell(midX + 1, midY + 0) = 1;
    getCell(midX + 4, midY + 0) = 1;
    getCell(midX + 5, midY + 0) = 1;
    getCell(midX + 6, midY + 0) = 1;
    getCell(midX + 3, midY + 1) = 1;
    getCell(midX + 1, midY + 2) = 1;
}

uint8_t& GameOfLife::getCell(int x, int y)
{
    return world[y * worldSize.x + x];
}

sf::Vector2i GameOfLife::get2D(int index)
{
    int y = index / worldSize.x;
    int x = index % worldSize.x;
    return { x, y };
}

sf::Color GameOfLife::getThreadColor(int index)
{
    switch (index % 4) {
        case 0:
            return sf::Color::Red;
            break;
        case 1:
            return sf::Color::Green;
            break;
        case 2:
            return sf::Color::Blue;
            break;
        case 3:
            return sf::Color::Yellow;
            break;
    }
}

std::vector<Cell> GameOfLife::doUpdate(int start, int end, int coreIdx)
{
    std::vector<Cell> aliveCells;
    aliveCells.reserve(end - start); // reserve space for worst case (all alive cells)

    for (int i = start; i < end; i++)
    {
        auto pos = get2D(i);

        // # of alive neighbors
        int aliveCount = 0;

        // check all 8 surrounding neighbors
        for (int nX = -1; nX <= 1; nX++) // nX = -1, 0, 1
        {
            for (int nY = -1; nY <= 1; nY++) // nY = -1, 0, 1
            {
                // make sure to skip the current cell!
                if (nX == 0 && nY == 0)
                    continue;

                // wrap around to other side if neighbor would be outside world
                int newX = (nX + pos.x + worldSize.x) % worldSize.x;
                int newY = (nY + pos.y + worldSize.y) % worldSize.y;

                aliveCount += getCell(newX, newY);
            }
        }

        // Evaluate game rules on current cell
        bool dies = aliveCount == 2 || aliveCount == 3;
        bool lives = aliveCount == 3;
        worldBuffer[i] = world[i] ? dies : lives;

        // if the cell's alive push it into the vector
        if (worldBuffer[i])
            aliveCells.push_back(Cell(pos, getThreadColor(coreIdx)));
    }

    return aliveCells;
}

void GameOfLife::update()
{
    // clear aliveCells cache
    aliveCells.clear();

    // divide the grid into horizontal slices
    int chunkSize = (worldSize.x * worldSize.y) / maxThreads;

    // split the work into threads
    std::vector<std::future<std::vector<Cell>>> asyncTasks;
    for (int i = 0; i < maxThreads; i++)
    {
        int start = i * chunkSize;

        int end;
        if (i == maxThreads - 1) // if this is the last thread, endPos will be set to cover remaining "height"
            end = worldSize.x * worldSize.y;
        else
            end = (i + 1) * chunkSize;

        asyncTasks.push_back(
            std::async(std::launch::async, [this, start, end, i] { return this->doUpdate(start, end, i); })
        );
    }

    // Wait until all async tasks are finished
    for (auto&& task : asyncTasks) { // TODO Why use 'auto&&'?
        auto aliveCellsPartial = task.get();
        aliveCells.insert(std::end(aliveCells), std::begin(aliveCellsPartial), std::end(aliveCellsPartial));
    }

    // apply updates
    world.swap(worldBuffer);
}

void GameOfLife::setCell(int x, int y, bool alive)
{
    // constrain x and y
    x = std::max(std::min(x, (int) worldSize.x - 1), 0);
    y = std::max(std::min(y, (int) worldSize.y - 1), 0);
    getCell(x, y) = alive;
    aliveCells.push_back(Cell(sf::Vector2i(x, y), sf::Color::White));
}

WorldRenderer.h

#pragma once

#include <SFML/Graphics.hpp>
#include <vector>
#include "GameOfLife.h"

class WorldRenderer
{
    public:
        WorldRenderer();

        ~WorldRenderer();

        // Renders the given game to the given window.
        void render(sf::RenderWindow& window, GameOfLife& world);

    private:
        // Vertex points for the pending draw call.
        std::vector<sf::Vertex> m_vertexPoints;

        // Adds a cell-sized quad in the "grid position" specified.
        void addQuad(int gridX, int gridY, sf::Color color);

        // Adds a darker colored quad in the given coordinates.
        void addBackgroundQuad(sf::Vector2f topLeft, sf::Vector2f bottomRight, sf::Color color);

        // Renders the background colors which correspond to the thread ID and the cells they are updating.
        void renderBackgrounds(sf::RenderWindow& window, GameOfLife& world);

        // Returns a darker variant of the given color.
        sf::Color darkenColor(sf::Color input);
};

WorldRenderer.cpp

#include "WorldRenderer.h"

WorldRenderer::WorldRenderer()
{
}


WorldRenderer::~WorldRenderer()
{
}

void WorldRenderer::addQuad(int gridX, int gridY, sf::Color color)
{
    sf::Vertex topLeft;
    sf::Vertex topRight;
    sf::Vertex bottomLeft;
    sf::Vertex bottomRight;

    float gridXFloat = gridX * 1.0f;
    float gridYFloat = gridY * 1.0f;

    topLeft.position = { gridXFloat, gridYFloat };
    topRight.position = { gridXFloat + 1, gridYFloat };
    bottomLeft.position = { gridXFloat, gridYFloat + 1 };
    bottomRight.position = { gridXFloat + 1, gridYFloat + 1 };

    topLeft.color = color;
    topRight.color = color;
    bottomLeft.color = color;
    bottomRight.color = color;

    m_vertexPoints.push_back(topLeft);
    m_vertexPoints.push_back(bottomLeft);
    m_vertexPoints.push_back(bottomRight);
    m_vertexPoints.push_back(topRight);
}

void WorldRenderer::addBackgroundQuad(sf::Vector2f topLeft, sf::Vector2f bottomRight, sf::Color color)
{
    sf::Vertex vTopLeft;
    sf::Vertex vTopRight;
    sf::Vertex vBottomLeft;
    sf::Vertex vBottomRight;

    vTopLeft.position = topLeft;
    vTopRight.position = { bottomRight.x, topLeft.y };
    vBottomLeft.position = { topLeft.x, bottomRight.y };
    vBottomRight.position = bottomRight;

    vTopLeft.color = color;
    vTopRight.color = color;
    vBottomLeft.color = color;
    vBottomRight.color = color;

    m_vertexPoints.push_back(vTopLeft);
    m_vertexPoints.push_back(vBottomLeft);
    m_vertexPoints.push_back(vBottomRight);
    m_vertexPoints.push_back(vTopRight);
}

void WorldRenderer::render(sf::RenderWindow & window, GameOfLife & game)
{
    // clear m_cellVertexPoints
    m_vertexPoints.clear();

    // draw backgrounds for "core zones"
    renderBackgrounds(window, game);

    // populate m_cellVertexPoints
    for (auto cell : game.aliveCells)
    {
        addQuad(cell.position.x, cell.position.y, cell.color);
    }

    // draw quads to window
    window.draw(m_vertexPoints.data(), m_vertexPoints.size(), sf::Quads);
}

void WorldRenderer::renderBackgrounds(sf::RenderWindow & window, GameOfLife & world)
{
    int cellsPerCore = world.worldSize.x * world.worldSize.y / world.maxThreads;

    // first draw the background color of the final core index
    addBackgroundQuad(
        sf::Vector2f(0, 0),
        sf::Vector2f(world.worldSize.x, world.worldSize.y),
        darkenColor(world.getThreadColor(world.maxThreads - 1))
    );

    // draw the remaining core background colors on top, in reverse order
    for (int i = world.maxThreads - 2; i >= 0; i--) {
        auto end = world.get2D(cellsPerCore * (i + 1));
        addBackgroundQuad(
            sf::Vector2f(0, 0),
            sf::Vector2f(world.worldSize.x, end.y),
            darkenColor(world.getThreadColor(i))
        );
    }
}

sf::Color WorldRenderer::darkenColor(sf::Color input)
{
    return sf::Color(input.r / 3, input.g / 3, input.b / 3);
}

Cell.h

#pragma once

#include <SFML/Graphics.hpp>

class Cell
{
public:
    Cell(sf::Vector2i position, sf::Color color);
    ~Cell();
    sf::Vector2i position;
    sf::Color color;
};

Cell.cpp

#include "Cell.h"

Cell::Cell(sf::Vector2i position, sf::Color color) : position(position), color(color)
{
}

Cell::~Cell()
{
}
\$\endgroup\$
5
\$\begingroup\$

Avoid importing the whole of std namespace

Bringing all names in from a namespace is problematic; namespace std particularly so. See Why is “using namespace std” considered bad practice?.

Include the right headers

Main.cpp includes <iostream>, but appears not to use anything declared there.

The same is true of GameOfLife.cpp.

On the other hand, we're using std::uint8_t but failing to include <cstdint> to declare it. Although it might be brought in by one of the other headers on a particular platform, we shouldn't depend on that if we want to be portable.

Naming conventions

We normally reserve all-uppercase names for preprocessor macros, to mark them as dangerous in code. Using such names for plain constants subverts that convention, misleading the reader.

Fix compilation errors

Remove the extra qualification GameOfLife:: on member doUpdate.

GameOfLife::getThreadColor() fails to return a value when no switch cases match. Although we readers can tell that a case must always match, we should add a return statement after the switch to keep the compiler from reporting the error.

Enable and fix compilation warnings

You seem to be compiling with all warnings disabled. With g++ -Wall -Wextra -Weffc++, we get a few extra things to fix:

In file included from /home/tms/stackexchange/review/213814/GameOfLife/src/GameOfLife.cpp:1:
/home/tms/stackexchange/review/213814/GameOfLife/src/GameOfLife.h: In constructor ‘GameOfLife::GameOfLife(sf::Vector2i)’:
/home/tms/stackexchange/review/213814/GameOfLife/src/GameOfLife.h:46:23: warning: ‘GameOfLife::worldBuffer’ will be initialized after [-Wreorder]
  std::vector<uint8_t> worldBuffer;
                       ^~~~~~~~~~~
/home/tms/stackexchange/review/213814/GameOfLife/src/GameOfLife.h:33:12: warning:   ‘const int GameOfLife::maxThreads’ [-Wreorder]
  const int maxThreads;
            ^~~~~~~~~~
/home/tms/stackexchange/review/213814/GameOfLife/src/GameOfLife.cpp:11:1: warning:   when initialized here [-Wreorder]
 GameOfLife::GameOfLife(sf::Vector2i size) : worldSize(size), world(size.x * size.y, false), worldBuffer(world), maxThreads(std::thread::hardware_concurrency())
 ^~~~~~~~~~
/home/tms/stackexchange/review/213814/GameOfLife/src/GameOfLife.cpp:11:1: warning: ‘GameOfLife::aliveCells’ should be initialized in the member initialization list [-Weffc++]
[ 60%] Building CXX object CMakeFiles/GameOfLife.dir/src/WorldRenderer.cpp.o
/usr/bin/c++    -Wall -Wextra -Wwrite-strings -Wno-parentheses -Weffc++   -pthread -std=c++17 -o CMakeFiles/GameOfLife.dir/src/WorldRenderer.cpp.o -c /home/tms/stackexchange/review/213814/GameOfLife/src/WorldRenderer.cpp
/home/tms/stackexchange/review/213814/GameOfLife/src/WorldRenderer.cpp: In constructor ‘WorldRenderer::WorldRenderer()’:
/home/tms/stackexchange/review/213814/GameOfLife/src/WorldRenderer.cpp:3:1: warning: ‘WorldRenderer::m_vertexPoints’ should be initialized in the member initialization list [-Weffc++]
 WorldRenderer::WorldRenderer()
 ^~~~~~~~~~~~~
/home/tms/stackexchange/review/213814/GameOfLife/src/WorldRenderer.cpp: In member function ‘void WorldRenderer::renderBackgrounds(sf::RenderWindow&, GameOfLife&)’:
/home/tms/stackexchange/review/213814/GameOfLife/src/WorldRenderer.cpp:79:58: warning: unused parameter ‘window’ [-Wunused-parameter]
 void WorldRenderer::renderBackgrounds(sf::RenderWindow & window, GameOfLife & world)
                                       ~~~~~~~~~~~~~~~~~~~^~~~~~

These are all easily fixed. For example, we can avoid the warning about an uninitialized member by providing a default initializer (though I'd be happier if my compiler were smart enough to know which types get constructed in a genuinely uninitialized state, and warn only about those):

std::vector<sf::Vertex> m_vertexPoints = {};

We also want to turn on some compiler optimizations here; I'll use -O3. After all, there's little point conducting a review on unoptimized code.

Don't declare empty constructors and destructors

public:
    WorldRenderer();

    ~WorldRenderer();

WorldRenderer::WorldRenderer()
{
}


WorldRenderer::~WorldRenderer()
{
}

Let the compiler generate the special methods, so we don't have to:

public:
    WorldRenderer() = default;

That's much simpler. And this class:

class Cell
{
public:
  Cell(sf::Vector2i position, sf::Color color);
  ~Cell();
  sf::Vector2i position;
  sf::Color color;
};

Cell::Cell(sf::Vector2i position, sf::Color color)
    : position(position), color(color)
{
}

Cell::~Cell()
{
}

becomes simply

struct Cell
{
    sf::Vector2i position;
    sf::Color color;
};

if we change the constructor calls to plain aggregate initialization.

Reduce copying

Instead of taking a copy of game.aliveCells, it might be better to expose a read-only reference:

private:
    // Update the cells from position start(inclusive) to position end(exclusive).
    std::vector<Cell> doUpdate(int start, int end, int coreIdx);

    // A cache of all the alive cells at the end of the update() call.
    std::vector<Cell> aliveCells = {};

public:
    auto const& getLivingCells() const { return aliveCells; }
    // populate m_cellVertexPoints
    for (auto const& cell: game.getLivingCells()) {
        addQuad(cell.position.x, cell.position.y, cell.color);
    }

The const& qualifier on the return type lets client code view the contents of our vector without being able to modify it and without needing to make a copy.

And addQuad can accept a const Cell& instead of unpacking it here:

void WorldRenderer::addQuad(const Cell& cell)
{
    float gridXFloat = cell.position.x * 1.0f;
    float gridYFloat = cell.position.y * 1.0f;

    m_vertexPoints.emplace_back(sf::Vector2f{gridXFloat,     gridYFloat    }, cell.color); // top-left
    m_vertexPoints.emplace_back(sf::Vector2f{gridXFloat,     gridYFloat + 1}, cell.color); // bottom-left
    m_vertexPoints.emplace_back(sf::Vector2f{gridXFloat + 1, gridYFloat + 1}, cell.color); // bottom-right
    m_vertexPoints.emplace_back(sf::Vector2f{gridXFloat + 1, gridYFloat    }, cell.color); // top-right
}

Here, I've used emplace_back to reduce the likelihood of copying (that said, push_back() is overloaded to move-from an rvalue argument, so there's likely no real difference in the optimized binary). That takes us neatly to the next member, which can similarly be reduced:

void WorldRenderer::addBackgroundQuad(sf::Vector2f topLeft, sf::Vector2f bottomRight, sf::Color color)
{
    auto topRight = topLeft;
    auto bottomLeft = bottomRight;
    std::swap(topRight.x, bottomLeft.x);

    m_vertexPoints.emplace_back(topLeft, color);
    m_vertexPoints.emplace_back(bottomLeft, color);
    m_vertexPoints.emplace_back(bottomRight, color);
    m_vertexPoints.emplace_back(topRight, color);
}

Prefer declarative threading to hand-built parallelism

I can see that great care has been put into dividing the work into threads and collating the results, so it's hard to recommend throwing that away. But I'm going to (don't worry; having written it gives you a better understanding of what will happen behind the scenes). If we enable OpenMP (i.e. add -fopenmp to our GCC arguments, or equivalent on other compilers; use find_package(OpenMP) in CMake), then we don't need to explicitly code the mechanism of parallelisation, and instead we can focus on the content.

Here's the new update() (which also replaces doUpdate()) using OpenMP:

#include <omp.h>

void GameOfLife::update()
{
    // clear aliveCells cache
    aliveCells.clear();

#pragma omp parallel
    {
        // private, per-thread variables
        auto this_thread_color = getThreadColor(omp_get_thread_num());
        std::vector<Cell> next_generation;

#pragma omp for
        for (int i = 0;  i < worldSize.x * worldSize.y;  ++i) {
        auto pos = get2D(i);

        int aliveCount = 0;

        // check all 8 neighbors
        for (int nX = -1; nX <= 1; ++nX) {
            for (int nY = -1; nY <= 1; ++nY) {
                // skip the current cell
                if (nX == 0 && nY == 0) continue;

                // wrap around to other side if neighbor would be outside world
                int newX = (nX + pos.x + worldSize.x) % worldSize.x;
                int newY = (nY + pos.y + worldSize.y) % worldSize.y;

                aliveCount += getCell(newX, newY);
            }
        }

        // Evaluate game rules on current cell
        bool dies = aliveCount == 2 || aliveCount == 3;
        bool lives = aliveCount == 3;
        worldBuffer[i] = world[i] ? dies : lives;

        // if the cell's alive push it into the vector
        if (worldBuffer[i])
            next_generation.emplace_back(Cell{pos, this_thread_color});
        }

#pragma omp critical
        aliveCells.insert(aliveCells.end(), next_generation.begin(), next_generation.end());
    }

    // apply updates
    world.swap(worldBuffer);
}

We can now play with things such as dynamic or guided scheduling without perturbing the logic. And we can control the maximum number of threads without recompiling (using OMP_NUM_THREADS environment variable).

The pragma omp critical is required when combining results in order to ensure that the threads don't try to modify the shared aliveCells simultaneously. The other shared variables are read but not modified within the parallel section.

Fix an arithmetic bug

This conversion doesn't work after the display window has been resized by the user:

        // normalize mouse pos
        int x = (mousePosition.x / 512.0f) * WORLD_SIZE_X;
        int y = (mousePosition.y / 512.0f) * WORLD_SIZE_Y;

Minor/style issues

There's no need to explicitly return 0 from main() if we always succeed - a common convention is to do so only when there's another code path that returns non-zero.


Modified code

Main.cpp

#include "GameOfLife.h"
#include "WorldRenderer.h"

#include <SFML/Graphics.hpp>

static const sf::Vector2i World_Size = { 256, 256 };

int main()
{
    // create the window
    sf::RenderWindow window({256, 256}, "Game of Life");
    // scale the image up 2x size
    window.setSize({512, 512});

    // disable vsync and uncap framerate limit
    window.setVerticalSyncEnabled(false);
    window.setFramerateLimit(0);

    // Create the game
    GameOfLife game(World_Size);

    // Create a world renderer
    WorldRenderer worldRenderer;

    // Track if mouse button is being held down
    bool mouseHeld = false;

    // run the program as long as the window is open
    while (window.isOpen()) {
        // check all the window's events that were triggered since the last iteration of the loop
        sf::Event event;
        while (window.pollEvent(event)) {
            // "close requested" event: we close the window
            if (event.type == sf::Event::Closed)
                window.close();

            // capture if the user is holding left mouse button down
            if (event.type == sf::Event::MouseButtonPressed) {
                if (event.mouseButton.button == sf::Mouse::Left)
                    mouseHeld = true;
            } else if (event.type == sf::Event::MouseButtonReleased) {
                if (event.mouseButton.button == sf::Mouse::Left)
                    mouseHeld = false;
            }
        }

        // clear the window with black color
        window.clear(sf::Color::Black);

        // if left mouse button held down then make cells under cursor alive and pause simulation
        if (mouseHeld) {
            auto mousePosition = sf::Mouse::getPosition(window);

            // normalize mouse pos
            int x = mousePosition.x * World_Size.x / window.getSize().x;
            int y = mousePosition.y * World_Size.y / window.getSize().y;

            // set cell under cursor to alive
            game.setCell(x, y, true);
        } else {
            // update the game world
            game.update();
        }

        // render the game
        worldRenderer.render(window, game);

        // end the current frame
        window.display();
    }
}

GameOfLife.h

#pragma once

#include "Cell.h"

#include <SFML/System/Vector2.hpp>

#include <cstdint>
#include <vector>

class GameOfLife
{
public:
    GameOfLife(sf::Vector2i size);

    // Set the value of the cell at the given grid position to the given alive state.
    void setCell(int x, int y, bool alive);

    // Updates the state of the game world by one tick.
    void update();

    // Returns a reference to the cell value at the given grid position.
    std::uint8_t & getCell(int x, int y);

    // Returns a vector of the given cell's grid position by its cell index.
    sf::Vector2i get2D(int index) const;

    auto const& getLivingCells() const { return aliveCells; }

    // Returns a color to use for cells/backgrounds based on the thread ID #.
    static sf::Color getThreadColor(int index);

    // Represents the width and height of the simulated world.
    const sf::Vector2i worldSize;

private:

    // A cache of all the alive cells at the end of the update() call.
    std::vector<Cell> aliveCells = {};

    // A 1D representation of the 2D grid that is the world.
    std::vector<std::uint8_t> world;

    // A buffer where the next world state is prepared, swapped with world at end of update().
    std::vector<std::uint8_t> worldBuffer;
};

GameOfLife.cpp

#include "GameOfLife.h"

#include <omp.h>

#include <array>

GameOfLife::GameOfLife(sf::Vector2i size)
    : worldSize(size),
      world(size.x * size.y, false),
      worldBuffer(world)
{
    aliveCells.reserve(size.x * size.y); // reserve space for worst-case(all cells are alive)

    // place an "acorn"
    int midX = worldSize.x / 2;
    int midY = worldSize.y / 2;
    getCell(midX + 0, midY + 0) = 1;
    getCell(midX + 1, midY + 0) = 1;
    getCell(midX + 4, midY + 0) = 1;
    getCell(midX + 5, midY + 0) = 1;
    getCell(midX + 6, midY + 0) = 1;
    getCell(midX + 3, midY + 1) = 1;
    getCell(midX + 1, midY + 2) = 1;
}

std::uint8_t& GameOfLife::getCell(int x, int y)
{

    return world[y * worldSize.x + x];
}

sf::Vector2i GameOfLife::get2D(int index) const
{
    int y = index / worldSize.x;
    int x = index % worldSize.x;
    return { x, y };
}

sf::Color GameOfLife::getThreadColor(int index)
{
    switch (index % 4) {
    case 0:
        return sf::Color::Red;
    case 1:
        return sf::Color::Green;
    case 2:
        return sf::Color::Blue;
    case 3:
        return sf::Color::Yellow;
    }

    return sf::Color::White;
}

void GameOfLife::update()
{
    // clear aliveCells cache
    aliveCells.clear();

#pragma omp parallel
    {
        // private, per-thread variables
        auto this_thread_color = getThreadColor(omp_get_thread_num());
        std::vector<Cell> next_generation;

#pragma omp for
        for (int i = 0;  i < worldSize.x * worldSize.y;  ++i) {
            auto const pos = get2D(i);
            int aliveCount = 0;

            // check all 8 neighbors
            static const std::array<std::array<int, 2>, 8> neighbours{{{-1, -1}, {0, -1}, {1, -1},
                                                                       {-1,  0},          {1,  0},
                                                                       {-1,  1}, {0,  1}, {1,  1}}};
            for (auto const [nX, nY]: neighbours) {
                // wrap around to other side if neighbor would be outside world
                int newX = (nX + pos.x + worldSize.x) % worldSize.x;
                int newY = (nY + pos.y + worldSize.y) % worldSize.y;

                aliveCount += getCell(newX, newY);
            }

            // Evaluate game rules on current cell
            bool dies = aliveCount == 2 || aliveCount == 3;
            bool lives = aliveCount == 3;
            worldBuffer[i] = world[i] ? dies : lives;

            // if the cell's alive push it into the vector
            if (worldBuffer[i])
                next_generation.emplace_back(Cell{pos, this_thread_color});
        }

#pragma omp critical
        aliveCells.insert(aliveCells.end(), next_generation.begin(), next_generation.end());
    }

    // apply updates
    world.swap(worldBuffer);
}

void GameOfLife::setCell(int x, int y, bool alive)
{
    // constrain x and y
    x = std::max(std::min(x, (int) worldSize.x - 1), 0);
    y = std::max(std::min(y, (int) worldSize.y - 1), 0);
    getCell(x, y) = alive;
    aliveCells.push_back(Cell{sf::Vector2i(x, y), sf::Color::White});
}

WorldRenderer.h

#pragma once

#include <SFML/Graphics.hpp>
#include <vector>
#include "GameOfLife.h"

class WorldRenderer
{
public:
    WorldRenderer() = default;

    // Renders the given game to the given window.
    void render(sf::RenderWindow& window, GameOfLife& world);

private:
    // Vertex points for the pending draw call.
    std::vector<sf::Vertex> m_vertexPoints = {};

    // Adds a cell-sized quad in the "grid position" specified.
    void addQuad(const Cell& cell);

    // Adds a darker colored quad in the given coordinates.
    void addQuad(sf::Vector2f topLeft, sf::Vector2f bottomRight, sf::Color color);

    // Renders the background colors which correspond to the thread ID and the cells they are updating.
    void renderBackgrounds(GameOfLife& world);

    // Returns a darker variant of the given color.
    sf::Color darkenColor(sf::Color input);
};

WorldRenderer.cpp

#include "WorldRenderer.h"

#include <omp.h>

void WorldRenderer::addQuad(const Cell& cell)
{

    sf::Vector2f topLeft{cell.position.x * 1.0f, cell.position.y * 1.0f};
    sf::Vector2f bottomRight{topLeft.x + 1, topLeft.y + 1};
    addQuad(topLeft, bottomRight, cell.color);
}

void WorldRenderer::addQuad(sf::Vector2f topLeft, sf::Vector2f bottomRight, sf::Color color)
{
    auto topRight = topLeft;
    auto bottomLeft = bottomRight;
    std::swap(topRight.x, bottomLeft.x);

    m_vertexPoints.emplace_back(topLeft, color);
    m_vertexPoints.emplace_back(bottomLeft, color);
    m_vertexPoints.emplace_back(bottomRight, color);
    m_vertexPoints.emplace_back(topRight, color);
}

void WorldRenderer::render(sf::RenderWindow & window, GameOfLife & game)
{
    // clear m_cellVertexPoints
    m_vertexPoints.clear();

    // draw backgrounds for "core zones"
    renderBackgrounds(game);

    // populate m_cellVertexPoints
    for (auto const& cell: game.getLivingCells()) {
        addQuad(cell);
    }

    // draw quads to window
    window.draw(m_vertexPoints.data(), m_vertexPoints.size(), sf::Quads);
}

void WorldRenderer::renderBackgrounds(GameOfLife & world)
{
    auto const maxThreads = omp_get_max_threads();
    auto const threadHeight = world.worldSize.y / maxThreads;

    for (int i = 0;  i < maxThreads;  ++i) {
        sf::Vector2f topLeft{0, 1.f * i * threadHeight};
        sf::Vector2f bottomRight{1.f * world.worldSize.x + 1, topLeft.y + 1.f * world.worldSize.y / maxThreads + 1};
        addQuad(topLeft, bottomRight, darkenColor(world.getThreadColor(i)));
    }
}

sf::Color WorldRenderer::darkenColor(sf::Color input)
{
    return sf::Color(input.r / 4, input.g / 4, input.b / 4);
}

Cell.h

#pragma once

#include <SFML/Graphics/Color.hpp>
#include <SFML/System/Vector2.hpp>

struct Cell
{
    sf::Vector2i position;
    sf::Color color;
};

CMakeLists.txt

# CMakeList.txt : CMake project for GameOfLife
#
cmake_minimum_required (VERSION 3.8)

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O3 -Werror -Wall -Wextra -Wshadow -Wwrite-strings -Wno-parentheses -Weffc++")

set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_EXTENSIONS OFF)

# Give the project a name
project(GameOfLife)

find_package(OpenMP)
find_package(SFML 2.5 COMPONENTS graphics REQUIRED)

set(SOURCES 
    src/Main.cpp
        src/GameOfLife.cpp
    src/GameOfLife.h
    src/WorldRenderer.cpp
    src/WorldRenderer.h
    src/Cell.h
)

add_executable(GameOfLife ${SOURCES})

target_link_libraries(GameOfLife sfml-graphics OpenMP::OpenMP_CXX)

Some minor changes I introduced while refactoring:

  • I changed the loop with the neighbours array to avoid the branch for the {0,0} case and to make it a single loop rather than nested loops. I think this is clearer, and it might be a tiny bit faster (but I didn't profile that).
  • I tend to prefer snake_case for identifiers, and that has crept into the code where I should have been consistent with the original camelCase - sorry about that! The same goes for spacing around operators and the & that indicates a reference variable. Being consistent is more important than any particular style, and I broke that rule because I was rushing.
\$\endgroup\$
  • \$\begingroup\$ When I try to build the CMake-generated Visual Studio project I'm getting this error: D8021 - invalid numeric argument '/Werror' And I had a couple questions but I don't know where to put them. The comment section doesn't allow enough characters... \$\endgroup\$ – Kyle V. Feb 20 at 16:22
  • 1
    \$\begingroup\$ There's probably a better CMake way to do that (I'm ignorant with CMake - I just added the minimum I could glean from SO and that works with GCC). Failing that, just put the required arguments for your compiler into the CMAKE_CXX_FLAGS line. \$\endgroup\$ – Toby Speight Feb 20 at 17:56
  • 1
    \$\begingroup\$ I believe my latest edit answers the other questions - if not, then let me know (reply may be tomorrow, as I'm reaching end of day here). \$\endgroup\$ – Toby Speight Feb 20 at 18:23
  • 1
    \$\begingroup\$ I found a useful blog entry about enabling warnings with CMake: foonathan.net/blog/2018/10/17/… Perhaps that helps (particularly the section referring to generator expressions)? \$\endgroup\$ – Toby Speight Feb 20 at 18:30
  • 1
    \$\begingroup\$ Perhaps it's a library linking problem - I'm able to use the functions from <omp.h> just by adding -fopenmp to my compile line, but maybe your platform needs linker options, too? Just a guess, and I'm heading AFK for a few days now, so I hope you manage to track that down (or find an answer over on Stack Overflow - remember to make a MCVE for that rather than posting the whole program!). \$\endgroup\$ – Toby Speight Feb 21 at 16:34
3
\$\begingroup\$

Don't make destructors if you don't need to. The default behavior is plenty for your use case.

Why is the destructor of GameOfLife virtual? You don't have a class that would need to inherit from it.

\$\endgroup\$
  • \$\begingroup\$ I think you're right about the destructors and I didn't mean to mark GameOfLife as virtual. Thanks! \$\endgroup\$ – Kyle V. Feb 19 at 20: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.