Conway's Game of Life In C++17

Question

I implemented Conway's Game of Life in C++17. To make it easy to copy paste. I have merged my .h and .cpp files. Any improvements or any C++20 features that I can leverage are greatly appreciated.

To run the code build it using cmake and run the following command

cat .<Path_to_life_file>/life.txt | .<Path_to_bin_dir>/Conway 

The game is paused at boot. Press p to toggle play-pause. Left-click adds a new live cell. Right-click kills a cell.

src/main.cpp

// ------------ position.h ---------------------- //

#include <cstddef>
#include <cstdint>
#include <boost/functional/hash.hpp>

using Distance = int;

struct Position {
    Distance x;
    Distance y;
};

bool operator==(Position const & p1, Position const & p2){
    return (p1.x == p2.x) && (p1.y == p2.y);
}

std::ostream& operator<<(std::ostream & os, Position const & p){
    os << "[" << p.x << ", " << p.y << "]";
    return os;
}

template <>
struct std::hash<Position>
{
    std::size_t operator()(const Position& p) const noexcept {
        auto seed = std::size_t{};

        boost::hash_combine(seed, p.x);
        boost::hash_combine(seed, p.y);

        return seed;
    }
};

[[nodiscard]]
std::array<Position, 8> get_neigbhors(Position const & position) noexcept {
    return {{
        {position.x - 1, position.y + 1},
        {position.x - 0, position.y - 1},
        {position.x + 1, position.y - 1},
        {position.x + 1, position.y - 0},
        {position.x + 1, position.y + 1},
        {position.x + 0, position.y + 1},
        {position.x - 1, position.y - 1},
        {position.x - 1, position.y - 0},
    }};
}

// ------------ game_of_life.h ---------------------- //

#include <algorithm>
#include <unordered_set>
#include <vector>

class GameOfLife {
public:

    GameOfLife(std::vector<Position> const & live_cells)
    : m_live_cells{cbegin(live_cells), cend(live_cells)} {}

    void step(){
        auto kill_set = std::unordered_set<Position>{};
        for(auto const & cell : m_live_cells){
            if(should_die(cell)){
                kill_set.insert(cell);                
            }
        }

        auto born_set = std::unordered_set<Position>{};
        for(auto const &  cell : m_live_cells){
            
            auto neighbors = get_neigbhors(cell);
            for(auto const & neighbor : neighbors){
                if(should_be_born(neighbor)){
                    born_set.insert(neighbor);
                }
            }
        }

        for(auto const & cell : kill_set){
            m_live_cells.erase(cell);
        }

        for(auto const & cell : born_set){
            m_live_cells.insert(cell);
        }
    }
    [[nodiscard]]
    std::unordered_set<Position> const & get_live_cells() const noexcept {
        return m_live_cells;
    }

    void add_cell(Position position){
        m_live_cells.insert(position);
    }

    void remove_cell(Position position){
        m_live_cells.erase(position);
    }

    [[nodiscard]]
    bool should_die(Position const & position) const noexcept {

        auto const neighbors = get_neigbhors(position);
        auto num_alive_neighbors = std::count_if(
            cbegin(neighbors), cend(neighbors),
            [&](auto const & neighbor) { return m_live_cells.count(neighbor); }
        );
        
        return num_alive_neighbors < 2 || num_alive_neighbors > 3;
    }
    
    [[nodiscard]]
    bool should_be_born(Position const & position) const noexcept {
        auto const neighbors = get_neigbhors(position);
        auto num_alive_neighbors = std::count_if(
            cbegin(neighbors), cend(neighbors),
            [&](auto const & neighbor) { return m_live_cells.count(neighbor); }
        );
        
        return num_alive_neighbors == 3;
    }

    std::unordered_set<Position> m_live_cells;
};


// ------------ ui.h ---------------------- //

#include <SFML/Graphics.hpp>

template<typename AddCellCallback, typename RemoveCellCallback>
class UI {
public:
    UI(AddCellCallback add_cell_callback, RemoveCellCallback remove_cell_callback)
    : m_window{ { 1920u, 1080u }, "Conway Game Of Life" }
    , m_add_cell_callback(add_cell_callback)
    , m_remove_cell_callback(remove_cell_callback)
    {
        m_window.setFramerateLimit(144);
        m_window.setKeyRepeatEnabled(false);
    }

    void handle_user_input(){
        for (auto event = sf::Event{}; m_window.pollEvent(event);)
        {
            switch (event.type)
            {
            case sf::Event::Closed:
                m_window.close();
                break;
            case sf::Event::KeyPressed:
                if(sf::Keyboard::isKeyPressed(sf::Keyboard::P)){
                    m_is_playing = !m_is_playing;
                }
            case sf::Event::MouseButtonPressed:
            {
                auto click_position = sf::Mouse::getPosition(m_window);
                auto game_position = Position{
                    static_cast<Distance>(click_position.x / m_scale),
                    static_cast<Distance>(click_position.y / m_scale)
                };

                if(sf::Mouse::isButtonPressed(sf::Mouse::Left)){
                    m_add_cell_callback(game_position);
                } else if(sf::Mouse::isButtonPressed(sf::Mouse::Right)){
                    m_remove_cell_callback(game_position);
                }
                break;
            }
            default:
                break;
            } 
        }
    }
    
    [[nodiscard]]
    bool is_running() const noexcept {
        return m_window.isOpen();
    }

    [[nodiscard]]
    bool is_playing() const noexcept {
        return m_is_playing;
    }

    void draw(std::unordered_set<Position> live_cells){
        m_window.clear();
        for(auto const & cell : live_cells){

            auto rect = sf::RectangleShape{{m_scale, m_scale}};

            rect.setFillColor({150, 150, 150});
            rect.setPosition({
                m_scale*cell.x,
                m_scale*cell.y
            });

            m_window.draw(rect);
        }

        m_window.display();
    }

private:

    bool m_is_playing = false;
    sf::RenderWindow m_window; 
    AddCellCallback m_add_cell_callback;
    RemoveCellCallback m_remove_cell_callback;

    static constexpr float m_scale = float{10.0};

};

// ------------ main.cpp ---------------------- //

#include <iostream>
#include <sstream>
#include <chrono>

int main()
{
    auto game = std::invoke([](){
        auto live_cells = std::vector<Position>{};
        auto line = std::string{};
        for(auto x = int{0}; std::getline(std::cin, line); ++x){            
            for(auto y = int{0}; y < line.size(); ++y){
                if(line[y] == 'O'){
                    live_cells.push_back({x, y});
                }
            }
        }

        return GameOfLife{live_cells};
    });

    auto ui = UI{
        [&](auto const & p) { game.add_cell(p); },
        [&](auto const & p) { game.remove_cell(p); }
    };

    auto last_update_time = std::chrono::steady_clock::now();
    
    while (ui.is_running())
    {
        ui.handle_user_input();

        auto now = std::chrono::steady_clock::now();
        if(now - last_update_time > std::chrono::milliseconds{100}){
            last_update_time = now;            

            ui.draw(game.get_live_cells());

            if(ui.is_playing()){
                game.step();
            } 
            
        }
    }
}

CMakeList.txt

cmake_minimum_required(VERSION 3.16)
project(Conway LANGUAGES CXX)

set(CMAKE_RUNTIME_OUTPUT_DIRECTORY ${CMAKE_BINARY_DIR}/bin)
option(BUILD_SHARED_LIBS "Build shared libraries" OFF)

set(CMAKE_EXPORT_COMPILE_COMMANDS ON)

include(FetchContent)
FetchContent_Declare(SFML
    GIT_REPOSITORY https://github.com/SFML/SFML.git
    GIT_TAG 2.6.x)
FetchContent_MakeAvailable(SFML)

find_package(Boost)

add_executable(Conway src/main.cpp)
target_link_libraries(Conway PRIVATE sfml-graphics)
target_compile_features(Conway PRIVATE cxx_std_17)

if(WIN32)
    add_custom_command(
        TARGET Conway
        COMMENT "Copy OpenAL DLL"
        PRE_BUILD COMMAND ${CMAKE_COMMAND} -E copy ${SFML_SOURCE_DIR}/extlibs/bin/$<IF:$<EQUAL:${CMAKE_SIZEOF_VOID_P},8>,x64,x86>/openal32.dll $<TARGET_FILE_DIR:Conway>
        VERBATIM)
endif()

install(TARGETS Conway)

life.txt

.O.
OO.
O.O
..
..
..
.......O.
......OO.
......O.O
..
..
..
..
..
..
..
..
..
...................O.
..................OO.
..................O.O
..
..
..
.........................O.
........................OO.
........................O.O
..
..
..................O....................
.................O.OO..........O.......
.................O.OO.........OO.......
..................OO..........O.O......
.......................................
.......OO............OO................
.......OO............OO................
.....................................O.
....................................OO.
......O.O...........................O.O
.....O..................OO....
OO..O....O..........OO.O..O.OO
OO.O..O.OO..........OO..O....O
....OO...................O....
..........................O.O.

Answer 1

Consider using a library for vector math

You created your own 2D vector type Position. This is much better than passing x and y indiviually everywhere. However, consider using a library that provides such a type, because those libraries typically supply much more helpful functions and operator overloads for those types.

Container types

You store the positions of the live cells in a std::unordered_set. It has the advantage of being simple and handling a very sparse field efficiently, and you don't have to know the size of the grid beforehand. There are other ways to store the state with different trade-offs, but for this simple implementation it's fine.

However, there are other choices for containers that are not so great. For example, the kill_set should probably just be a std::vector<Position>s: there is no possibility of adding duplicates to them, and std::vector is much more efficient here. You could also consider using this for the born_set; while it might add some duplicates, this doesn't affect m_live_cells in the end.

In the constructor of GameOfLife you require the initial set of live cells to be passed as a std::vector. But what if you have the initial set in a different container? Consider making this a template so it accepts any type of range:

class GameOfLife {
public:
    template<typename T>
    GameOfLife(const T& live_cells)
    : m_live_cells{std::begin(live_cells), std::end(live_cells)} {}
    …
};

Avoid unnecessary copies

UI::draw() takes the set of live cells by value, which is unnecessary. Just pass a const reference.

Avoid unnecessarily looping over the data

In step() you visit every live cell twice; once to check if it needs to be killed, and once to check if neighbors need to be born. Consider looping only once and handle both cases at the same time. Related to this:

Avoid code duplication

should_die() and should_be_born() are the same, except for the condition in the return statement. Consider writing a single function that calculates the number of live neighbors.

Avoid busy loops

You have a busy loop in main() waiting for 100 milliseconds to pass before calling ui.draw(). This will use 100% of one CPU core for no good reason. Unfortunately, SFML doesn't have the concept of timer events. The next best thing is to ensure vsync is enabled using:

m_window.setVerticalSyncEnabled(true);

This way, a call to m_window.display() will automatically wait until the next frame can be displayed on the screen. That will still not be ideal, since framerates vary depending on the monitor, and you might not want the game of life to run so fast. Still, you can just call ui.draw() unconditionally and only do a step if 100 milliseconds expired:

using clock = std::chrono::steady_clock;
auto interval = std::chrono::milliseconds{100};
auto last_update_time = clock::now();

while (ui.is_running()) {
    ui.handle_user_input();
    ui.draw();

    auto now = clock::now();
    if(now - last_update_time > interval) {
            last_update_time += interval;
            if(ui.is_playing()) {
                game.step();
            }
    }
}

Questionable choices

I'm not sure why you use a lambda to create game inside main(). I would rather create a function that reads the input and returns a container of live cells, so that it looks like:

static auto read_live_cells() {
    auto live_cells = std::vector<Position>{};
    …
    return live_cells;
}

int main() {
    auto game = GameOfLive(read_live_cells());
    …
}

You also don't need to use std::invoke() to directly invoke a lambda function, you can write [](){…}() instead. Although with that many brackets perhaps the explicit std::invoke() makes it more clear what is going on here.

Instead of making UI a template to handle the callbacks, consider using std::function instead.