Connect Four in C++

Question

This is a library that implements the logic of Connect Four.

There's nothing related to graphics or user input here. This library is supposed to be integrated into any environment where one could run C++ (and play Connect Four). I want it to be easy and straightforward to use in virtually any platform, from Desktop to Arduino. Users of this library must be able to focus entirely on their implementation of user input and output, and leverage the logic to this library.

Given such focus on portability, I tried to make this code to be 100% ISO C++, and I chose C++11 because it is -- to the best of my admittedly limited knowledge -- available everywhere by now, and allows me to use "modern" language features such as range-based loops. C++11 looks like a good compromise.

The focus on portability also means that the code is supposed to run fast enough on resource-constrained devices, not waste memory, and not be unnecessarily large when compiled. (Although I admit that I don't know how large is "unnecessarily large")

I have very little experience in C++ so I put a substantial effort into researching good practices to apply on this code.

High-level explanation of the code: The Game class is the only class supposed to be used in the outside world. With Game::play the client informs that a player chose a column, and the Game instance uses an observer-like mechanism to notify the client that something happened. There are 2 events:

• CellFallThrough: Notifies the client that a cell is falling. This is supposed to allow the client to draw the animation.
• Win: Notifies the client that a player won the game.

Here are a few principles that I tried to follow:

• Aggressive compiler warnings
• No language extensions
• Warnings are errors
• Macros kept to a minimum
• Strong type safety
• Unit tests

Here are the reasoning for a few choices I made when writing the code:

• Using least types (uint_least8_t, int_least16_t): Those are more portable than fixed-length types (such as uint8_t) and the compiler is able to perform a few tricks to increase performance.
• Using uint_least8_t for board size: Board size can't be negative, so that's why it's unsigned. Also, typically the size is a single digit number, so 8 bits are more than enough.
• Using int_least16_t for position: It should to be possible to represent positions outside of the board. The board size is a 8-bit unsigned number, so a 16-bit, signed number is big enough for this.
• Using class enum: class enums offer better type safety over plain and old C enums.

As far as I know, the spirit of C++ is to write high-level code without compromising performance, so that's what I tried to get here.

All source files are attached below. The file system tree looks like this:

connect_four
|--- src
     |--- Board.cpp
     |--- Board.hpp
     |--- CellFallThroughEventData.hpp
     |--- Game.cpp
     |--- Game.hpp
     |--- Player.hpp
     |--- PlayResult.hpp
     |--- PlayResult.hpp
     |--- Position.hpp
     |--- WinEventData.hpp
|--- test
     |--- config_main.cpp
     |--- game_on_cell_fall_through.cpp
     |--- game_on_win.cpp
     |--- game_play.cpp
     |--- helper.hpp
|--- vendor
     |--- catch2
          |--- catch.hpp
|--- makefile

Once you have all the files you can run the tests with

make clean && make tests && ./run_tests

Note: vendor/catch2/catch.hpp isn't written by me, it's the unit test library. You can find it here.

---

src/Board.cpp

#include "Board.hpp"

#include <cstdint>

#include "Player.hpp"
#include "Position.hpp"

namespace connect_four
{
    #define at(position) (this->_cells[static_cast<std::size_t>(position.row)][static_cast<std::size_t>(position.col)])

    Board::Board(uint_least8_t const row_count, uint_least8_t const col_count)
    {
        this->_row_count = row_count;
        this->_col_count = col_count;

        auto empty = std::make_pair(Player::PLAYER_1, false);
        auto row = std::vector<std::pair<Player, bool>>(col_count, empty);

        this->_cells.resize(row_count, row);
    }

    bool Board::is_inside(Position const position)
    {
        return
            position.row >= 0 &&
            position.col >= 0 &&
            position.row < this->_row_count &&
            position.col < this->_col_count;
    }

    bool Board::is_empty(Position const position)
    {
        return this->is_inside(position) && !at(position).second;
    }

    bool Board::is_filled(Position const position, Player const player)
    {
        return
            this->is_inside(position) &&
            at(position).second &&
            at(position).first == player;
    }

    void Board::set(Position const position, Player const player)
    {
        at(position) = std::make_pair(player, true);
    }
}

src/Board.hpp

#pragma once

#include <cstdint>
#include <vector>

#include "Player.hpp"
#include "Position.hpp"

namespace connect_four
{
    class Board
    {
        uint_least8_t _row_count;
        uint_least8_t _col_count;
        std::vector<std::vector<std::pair<Player, bool>>> _cells;

        public:

        Board(uint_least8_t const row_count, uint_least8_t const col_count);

        bool is_inside(Position const position);
        bool is_empty(Position const position);
        bool is_filled(Position const position, Player const player);
        void set(Position const position, Player const player);
    };
}

src/CellFallThroughEventData.hpp

#pragma once

#include "Game.hpp"
#include "Player.hpp"

namespace connect_four
{
    struct CellFallThroughEventData
    {
        connect_four::Player const player;
        uint_least8_t const row;
        uint_least8_t const col;
        bool const is_final_position;
    };
}

src/Game.cpp

#include "Game.hpp"

#include <cstdint>
#include <functional>
#include <vector>

#include "Board.hpp"
#include "CellFallThroughEventData.hpp"
#include "WinEventData.hpp"
#include "Player.hpp"
#include "PlayResult.hpp"
#include "Position.hpp"

namespace connect_four
{
    Game::Game(uint_least8_t row_count, uint_least8_t col_count)
        : _board(row_count, col_count)
    {
        this->_player = Player::PLAYER_1;
        this->_ended = false;
    }

    PlayResult Game::play(uint_least8_t const col)
    {
        if (this->_ended)
        {
            return PlayResult::GAME_ALREADY_ENDED;
        }

        Position initial_position{0, col};

        if (!this->_board.is_inside(initial_position))
        {
            return PlayResult::COLUMN_IS_INVALID;
        }

        if (!this->_board.is_empty(initial_position))
        {
            return PlayResult::COLUMN_IS_FULL;
        }

        auto position = this->_fall_to_right_row(initial_position);

        this->_board.set(position, this->_player);

        if (this->_check_victory(position))
        {
            this->_ended = true;

            WinEventData event_data{this->_player};

            for (auto const & handler : this->_win_handlers)
            {
                handler(event_data);
            }
        }
        else
        {
            this->_player =
                this->_player == Player::PLAYER_1
                ? Player::PLAYER_2
                : Player::PLAYER_1;
        }

        return PlayResult::SUCCESS;
    }

    void Game::on_event(std::function<void (CellFallThroughEventData)> const handler)
    {
        this->_cell_fall_through_handlers.push_back(handler);
    }

    void Game::on_event(std::function<void (WinEventData)> const handler)
    {
        this->_win_handlers.push_back(handler);
    }

    Position Game::_fall_to_right_row(Position position)
    {
        Position next_pos{static_cast<int_least16_t>(position.row + 1), position.col};
        auto is_final = !this->_board.is_empty(next_pos);

        CellFallThroughEventData event_data{
            this->_player,
            static_cast<uint_least8_t>(position.row),
            static_cast<uint_least8_t>(position.col),
            is_final
        };

        for (auto const & handler : this->_cell_fall_through_handlers)
        {
            handler(event_data);
        }

        return
            is_final
            ? position
            : this->_fall_to_right_row(next_pos);
    }

    bool Game::_check_victory(Position position)
    {
        auto _check = [this, position](std::function<Position (Position, int_least16_t)> f)
        {
            auto counter = 1;
            int_least16_t i = 1;

            while (this->_board.is_filled(f(position, i), this->_player))
            {
                counter += 1;
                i += 1;
            }

            i = -1;

            while (this->_board.is_filled(f(position, i), this->_player))
            {
                counter += 1;
                i -= 1;
            }

            return counter >= 4;
        };

        #define make_lambda(row, col) [](Position pos, int_least16_t i) \
        {                                                               \
            return Position{                                            \
                static_cast<int_least16_t>(row),                        \
                static_cast<int_least16_t>(col)};                       \
        }                                                               \

        return
            _check(make_lambda(pos.row    , pos.col + i)) ||
            _check(make_lambda(pos.row + i, pos.col    )) ||
            _check(make_lambda(pos.row + i, pos.col + i)) ||
            _check(make_lambda(pos.row - i, pos.col + i));
    }
}

src/Game.hpp

#pragma once

#include <cstdint>
#include <functional>

#include "Board.hpp"
#include "CellFallThroughEventData.hpp"
#include "WinEventData.hpp"
#include "Player.hpp"
#include "PlayResult.hpp"
#include "Position.hpp"

namespace connect_four
{
    class Game
    {
        Player _player;
        Board _board;
        bool _ended;
        std::vector<std::function<void (CellFallThroughEventData)>> _cell_fall_through_handlers;
        std::vector<std::function<void (WinEventData)>> _win_handlers;

        bool _check_victory(Position position);
        Position _fall_to_right_row(Position current_position);

        public:

        Game(uint_least8_t const row_count, uint_least8_t const col_count);

        PlayResult play(uint_least8_t const col);
        void on_event(std::function<void (CellFallThroughEventData)> const handler);
        void on_event(std::function<void (WinEventData)> const handler);
    };
}

src/Player.hpp

#pragma once

namespace connect_four
{
    enum class Player
    {
        PLAYER_1,
        PLAYER_2,
    };
}

src/PlayResult.hpp

#pragma once

namespace connect_four
{
    enum class PlayResult
    {
        SUCCESS,
        GAME_ALREADY_ENDED,
        COLUMN_IS_FULL,
        COLUMN_IS_INVALID,
    };
}

src/Position.hpp

#pragma once

#include <cstdint>

namespace connect_four
{
    struct Position
    {
        int_least16_t const row;
        int_least16_t const col;
    };
}

src/WinEventData.hpp

#pragma once

#include "Game.hpp"
#include "Player.hpp"

namespace connect_four
{
    struct WinEventData
    {
        Player const winner;
    };
}

test/config_main.cpp

#define CATCH_CONFIG_MAIN

#include <catch2/catch.hpp>

test/game_on_cell_fall_through.cpp

#include <vector>

#include <catch2/catch.hpp>

#include "Game.hpp"

#include "helper.hpp"

using namespace connect_four;

SCENARIO("Cell fall through event happy path")
{
    GIVEN("An empty 6-row-per-7-column board")
    {
        Game game(6, 7);

        std::vector<CellFallThroughEventData> memo;

        game.on_event(create_handler<CellFallThroughEventData>(&memo));

        WHEN("The player chooses a valid column")
        {
            auto column = 4;

            game.play(column);

            THEN("6 events are emited")
            {
                REQUIRE(6 == memo.size());
            }

            THEN("All events report the chosen column")
            {
                for (auto event : memo)
                {
                    REQUIRE(column == event.col);
                }
            }

            THEN("All events report the 1st player")
            {
                for (auto event : memo)
                {
                    REQUIRE(Player::PLAYER_1 == event.player);
                }
            }

            THEN("The 1st event reports the 1st row")
            {
                REQUIRE(0 == memo[0].row);
            }

            THEN("The 6th event reports the 6th row")
            {
                REQUIRE(5 == memo[5].row);
            }

            THEN("The 1st event is not reported as final position")
            {
                REQUIRE(false == memo[0].is_final_position);
            }

            THEN("The 6th event is reported as final position")
            {
                REQUIRE(true == memo[5].is_final_position);
            }
        }
    }
}

test/game_on_win.cpp

#include <vector>

#include <catch2/catch.hpp>

#include "Game.hpp"

#include "helper.hpp"

using namespace connect_four;

SCENARIO("Win event not emited on normal, non-winning play")
{
    GIVEN("An empty 6-row-per-7-column board")
    {
        Game game(6, 7);

        std::vector<WinEventData> memo;

        game.on_event(create_handler<WinEventData>(&memo));

        WHEN("The player chooses a valid column")
        {
            game.play(0);

            THEN("No event is emited")
            {
                REQUIRE(0 == memo.size());
            }
        }
    }
}

SCENARIO("Win event emited on horizontal win")
{
    //
    //   : 1 : 2 : 3 : 4 : 5 : 6 : 7 :
    //   :---:---:---:---:---:---:---:
    // 1 :   :   :   :   :   :   :   :
    // 2 :   :   :   :   :   :   :   :
    // 3 :   :   :   :   :   :   :   :
    // 4 :   :   :   :   :   :   :   :
    // 5 : O : O : O :   :   :   :   :
    // 6 : X : X : X :   :   :   :   :
    //   :---------------------------:

    GIVEN("A 6-row-per-7-column board with state 112233")
    {
        Game game(6, 7);

        std::vector<WinEventData> memo;

        game.on_event(create_handler<WinEventData>(&memo));

        game.play(0);
        game.play(0);
        game.play(1);
        game.play(1);
        game.play(2);
        game.play(2);

        WHEN("The player chooses the 4th column")
        {
            game.play(3);

            THEN("1 event is emited for player 1")
            {
                REQUIRE(1 == memo.size());
                REQUIRE(Player::PLAYER_1 == memo[0].winner);
            }
        }
    }
}

SCENARIO("Win event emited on vertical win")
{
    //   : 1 : 2 : 3 : 4 : 5 : 6 : 7 :
    //   :---:---:---:---:---:---:---:
    // 1 :   :   :   :   :   :   :   :
    // 2 :   :   :   :   :   :   :   :
    // 3 :   :   :   :   :   :   :   :
    // 4 : X : O :   :   :   :   :   :
    // 5 : X : O :   :   :   :   :   :
    // 6 : X : O :   :   :   :   :   :
    //   :---------------------------:

    GIVEN("A 6-row-per-7-column board with state 121212")
    {
        Game game(6, 7);

        std::vector<WinEventData> memo;

        game.on_event(create_handler<WinEventData>(&memo));

        game.play(0);
        game.play(1);
        game.play(0);
        game.play(1);
        game.play(0);
        game.play(1);

        WHEN("The player chooses the 1th column")
        {
            game.play(0);

            THEN("1 event is emited for player 1")
            {
                REQUIRE(1 == memo.size());
                REQUIRE(Player::PLAYER_1 == memo[0].winner);
            }
        }
    }
}

SCENARIO("Win event emited on main diagonal win")
{
    //   : 1 : 2 : 3 : 4 : 5 : 6 : 7 :
    //   :---:---:---:---:---:---:---:
    // 1 :   :   :   :   :   :   :   :
    // 2 :   :   :   :   :   :   :   :
    // 3 : X :   :   :   :   :   :   :
    // 4 : O :   : O :   :   :   :   :
    // 5 : O : O : X :   :   :   :   :
    // 6 : X : X : O : X :   :   :   :
    //   :---------------------------:

    GIVEN("A 6-row-per-7-column board with state 1121124333")
    {
        Game game(6, 7);

        std::vector<WinEventData> memo;

        game.on_event(create_handler<WinEventData>(&memo));

        game.play(0);
        game.play(0);
        game.play(1);
        game.play(0);
        game.play(0);
        game.play(1);
        game.play(3);
        game.play(2);
        game.play(2);
        game.play(2);

        WHEN("The player chooses the 2nd column")
        {
            game.play(1);

            THEN("1 event is emited for player 1")
            {
                REQUIRE(1 == memo.size());
                REQUIRE(Player::PLAYER_1 == memo[0].winner);
            }
        }
    }
}

SCENARIO("Win event emited on secondary diagonal win")
{
    //   : 1 : 2 : 3 : 4 : 5 : 6 : 7 :
    //   :---:---:---:---:---:---:---:
    // 1 :   :   :   :   :   :   :   :
    // 2 :   :   :   :   :   :   :   :
    // 3 :   :   : O :   :   :   :   :
    // 4 :   :   : X : O :   :   :   :
    // 5 :   : X : X : O :   :   :   :
    // 6 : X : O : X : O :   :   :   :
    //   :---------------------------:

    GIVEN("A 6-row-per-7-column board with state 1234243433")
    {
        Game game(6, 7);

        std::vector<WinEventData> memo;

        game.on_event(create_handler<WinEventData>(&memo));

        game.play(0);
        game.play(1);
        game.play(2);
        game.play(3);
        game.play(1);
        game.play(3);
        game.play(2);
        game.play(3);
        game.play(2);
        game.play(2);

        WHEN("The player chooses the 4th column")
        {
            game.play(3);

            THEN("1 event is emited for player 1")
            {
                REQUIRE(1 == memo.size());
                REQUIRE(Player::PLAYER_1 == memo[0].winner);
            }
        }
    }
}

SCENARIO("Win event emited on win when last play at the middle")
{
    //   : 1 : 2 : 3 : 4 : 5 : 6 : 7 :
    //   :---:---:---:---:---:---:---:
    // 1 :   :   :   :   :   :   :   :
    // 2 :   :   :   :   :   :   :   :
    // 3 :   :   :   :   :   :   :   :
    // 4 :   :   :   :   :   :   :   :
    // 5 : O : O :   : O : O :   :   :
    // 6 : X : X :   : X : X :   :   :
    //   :---------------------------:

    GIVEN("A 6-row-per-7-column board with state 11224455")
    {
        Game game(6, 7);

        std::vector<WinEventData> memo;

        game.on_event(create_handler<WinEventData>(&memo));

        game.play(0);
        game.play(0);
        game.play(1);
        game.play(1);
        game.play(3);
        game.play(3);
        game.play(4);
        game.play(4);

        WHEN("The player chooses the 3rd column")
        {
            game.play(2);

            THEN("1 event is emited for player 1")
            {
                REQUIRE(1 == memo.size());
                REQUIRE(Player::PLAYER_1 == memo[0].winner);
            }
        }
    }
}

SCENARIO("Win event emited on player 2 win")
{
    //   : 1 : 2 : 3 : 4 : 5 : 6 : 7 :
    //   :---:---:---:---:---:---:---:
    // 1 :   :   :   :   :   :   :   :
    // 2 :   :   :   :   :   :   :   :
    // 3 :   :   :   :   :   :   :   :
    // 4 :   :   :   :   :   :   :   :
    // 5 : X : X : X :   :   :   :   :
    // 6 : O : O : O :   : X :   :   :
    //   :---------------------------:

    GIVEN("A 6-row-per-7-column board with state 5112233")
    {
        Game game(6, 7);

        std::vector<WinEventData> memo;

        game.on_event(create_handler<WinEventData>(&memo));

        game.play(4);
        game.play(0);
        game.play(0);
        game.play(1);
        game.play(1);
        game.play(2);
        game.play(2);

        WHEN("The player chooses the 4th column")
        {
            game.play(3);

            THEN("1 event is emited for player 2")
            {
                REQUIRE(1 == memo.size());
                REQUIRE(Player::PLAYER_2 == memo[0].winner);
            }
        }
    }
}

test/game_play.cpp

#include <catch2/catch.hpp>

#include "Game.hpp"

using namespace connect_four;

SCENARIO("Play happy path")
{
    GIVEN("An empty board")
    {
        Game game(6, 7);

        WHEN("The player chooses the first column")
        {
            auto play_result = game.play(0);

            THEN("The game accepts the play")
            {
                REQUIRE(PlayResult::SUCCESS == play_result);
            }
        }
    }
}

SCENARIO("A column that is full cannot accept any more plays")
{
    GIVEN("A board whose first column is full")
    {
        Game game(6, 7);

        game.play(0);
        game.play(0);
        game.play(0);
        game.play(0);
        game.play(0);
        game.play(0);

        WHEN("The player chooses the first column")
        {
            auto play_result = game.play(0);

            THEN("The game does not accept the play")
            {
                REQUIRE(PlayResult::COLUMN_IS_FULL == play_result);
            }
        }
    }
}

SCENARIO("The chosen column must be validated")
{
    GIVEN("A 6-row-per-7-column board")
    {
        Game game(6, 7);

        WHEN("The player chooses the 8th column")
        {
            auto play_result = game.play(7);

            THEN("The game does not accept the play")
            {
                REQUIRE(PlayResult::COLUMN_IS_INVALID == play_result);
            }
        }
    }
}

test/helper.hpp

#include <functional>
#include <vector>

template<typename T>
std::function<void (T)> create_handler(std::vector<T>* memo)
{
    return [memo](T event_data) mutable
    {
        memo->push_back(event_data);
    };
}

vendor/catch2/catch.hpp

https://raw.githubusercontent.com/catchorg/Catch2/v2.x/single_include/catch2/catch.hpp

Answer 1

Avoid macros whenever possible

As marcinj already mentioned in the comments, you can replace the macro at() with a regular function. Macros are problematic in many ways. Here the biggest problem is that while you think you defined it inside namespace connect_four, macros are not bound at all by namespaces. When you define this, you can no longer use any function named at(), like for example std::vector::at().

I strongly recommend you make this a member function that returns a reference to a cell:

std::pair<Player, bool>& Board::at(const Postion& position) {
    return _cells[position.row][position.col];
}

This should be a complete drop-in replacement for your macro.

The same goes for make_lambda(). Instead of passing a lambda to _check(), just pass extra parameters to _check() to encode the direction to check in. For example:

auto _check = [this, position](int dx, int dy)
{
    f = [dx, dy](Position pos, int i) {
        return Position{pos.row + dx * i, pos.col + dx * i};
    }
    ...
};

return _check(0, 1) || _check(1, 0) || _check(1, 1) || _check(-1, 1);

Create a struct Cell

Instead of using the add-hoc std::pair<Player, bool> for cells, create a struct that represents a cell. That makes the code simpler and easier to modify if you ever want to add more information to a cell:

class Board {
    struct Cell {
        Player player;
        bool filled = false;
    };

    std::vector<std::vector<Cell>> _cells;
    ...
};

You also no longer have to remember whether Player was first or second, and you don't have to use std::make_pair(). Using a default member initialier, you also don't have to explicitly define an empty cell, you can now just write:

_cells.resize(row_count, std::vector<Cell>(col_count));

Use a one-dimensional vector to store the cells of the board

A vector of vectors is a rather inefficient data structure, since the outer vector basically is just a bunch of pointers for every column. Following pointers is less efficient on the CPU than doing a multiplication and addition. Therefore, it's recommended that you do something like this:

std::vector<Cell> _cells;

Cell& Board::at(const Position& position) {
    return _cells[position.row * _col_count + position.col];
}

Board::Board(uint_least8_t const row_count, uint_least8_t const col_count) {
    _row_count = row_count;
    _col_count = col_count;
    _cells.resize(row_count * col_count);
}

Make use of default member intializers and member initializer lists

Initializing variables inside the body of a constructor has a few drawbacks. The order of initialization can be different from the order in which destructors are called, and it can be less efficient since for example first it will create an empty vector _cells, and then you are resizing it. While it's not wrong, it is better to use member initializer lists and/or default member intializers where possible. For example, using member initializer lists your constructor becomes:

Board::Board(uint_least8_t const row_count, uint_least8_t const col_count):
    _row_count(row_count),
    _col_count(col_count),
    _cells(row_count * col_count)
{
}

You have to use member initializer lists or initialization in the constructor body for those variables that depend directly on constructor parameters, like _row_count and _col_count. However, variables that do not depend on those parameters, like filled in struct Cell above, can be initialized using default member initializers.

Unnecessary use of this->

It is almost never necessary to write this-> in C++. I would remove it where possible, since that will make the code much easier to read.

Event handling

Using callbacks to signal events to the application that uses this library is not a bad idea. However, I would stop at just providing a single slot for each callback type. Adding vectors so multiple callbacks can be registered per event type is adding unnecessary complexity to your library. If the application really needs to have multiple callbacks registered, then it could install one callback that in turn has a vector of callbacks that it will call. This reduces the responsibilities of your library.

Alternatively, use another library to handle callback registration, like libsigc++.