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>likevector.push_back({"string", true});automatically instantiates a newpairobject.)
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()
{
}
