5
\$\begingroup\$

This is a very simple version of Conway's game of life. It treats the edge of the grid as dead cells and uses a very basic algorithm. Despite this it works fine.
As people might not have the SFML library installed here's a picture of what it looks like when running: Game of Life

It can be paused with p and updated one step at a time with u (only while paused). Reset is possible by pressing r.

Testing has shown that the performance bottleneck is the drawing itself. I'm using slightly modified code from an SFML example for this. I would appreciate input on this issue from someone with experience in rendering as I'm new to this.
I'm also concerned with the coupling between the Gol class and the render engine. Any ideas on how to decouple this are very welcome.

gol.h:

#include <SFML/Graphics.hpp>

#include <random>
#include <vector>

class Gol {
public:
    Gol(int width_, int height_);

    void display_grid(sf::RenderWindow& window) const;
    void update();
    void reset();

private:
    void init_visuals();
    void seed_grid();
    int count_neighbors(int m_origin, int n_origin) const;
    void apply_rules(int neighbors, int m, int n);

    int width;
    int height;
    std::vector<std::vector<bool>> grid_current;
    std::vector<std::vector<bool>> grid_next;
    std::vector<sf::Vertex> grid_visual;
    std::mt19937 rng;
    sf::Color visual_alive = sf::Color::White;
    sf::Color visual_dead = sf::Color::Black;
};

gol.cpp:

#include "gol.h"

#include <SFML/Graphics.hpp>

#include <cstddef>
#include <ctime>
#include <random>
#include <vector>

Gol::Gol(int width_, int height_)
    : width{width_}
    , height{height_}
    , grid_current{}
    , grid_next{}
    , grid_visual{}
    , rng{}
{
    std::random_device rd;
    rng.seed(rd());

    reset();
}

void Gol::display_grid(sf::RenderWindow& window) const {
    window.draw(&grid_visual[0], grid_visual.size(), sf::Points);
}

void Gol::update() {
    grid_current.swap(grid_next);
    for (int m = 0; m < height; ++m) {
        for (int n = 0; n < width; ++n) {
            apply_rules(count_neighbors(m, n), m, n);
        }
    }
}

void Gol::reset() {
    grid_current.clear();
    grid_current.resize(static_cast<std::size_t>(height),
        std::vector<bool>(width));
    grid_next.clear();
    grid_next.resize(static_cast<std::size_t>(height),
        std::vector<bool>(width));
    init_visuals();
    seed_grid();
}

void Gol::init_visuals() {
    grid_visual.clear();
    grid_visual.resize(width * height);

    int pos = 0;
    for (int y = 0; y < height; ++y) {
        for (int x = 0; x < width; ++x) {
            grid_visual[pos].position =
                sf::Vector2f(static_cast<float>(x), static_cast<float>(y));
            // postfix intended
            grid_visual[pos++].color = visual_dead;
        }
    }
}

void Gol::seed_grid() {
    std::uniform_int_distribution<int> m_axis(0, height - 1);
    std::uniform_int_distribution<int> n_axis(0, width - 1);
    std::uniform_int_distribution<int> cells(width * height / 2, 
                                             width * height);

    int initial_cell_nr = cells(rng);
    while (initial_cell_nr > 0) {
        std::size_t m = m_axis(rng);
        std::size_t n = n_axis(rng);
        if (!grid_next[m][n]) {
            grid_next[m][n] = true;
            grid_visual[m * width + n].color = visual_alive;
            --initial_cell_nr;
        }
    }
}

int Gol::count_neighbors(int m_origin, int n_origin) const {
    int neighbors = 0;
    for (int m_current = m_origin - 1; m_current <= m_origin + 1; ++m_current) {
        for (int n_current = n_origin - 1; n_current <= n_origin + 1; ++n_current) {
            if (m_current < 0 || m_current >= height ||
                n_current < 0 || n_current >= width) {
                continue;
            }

            if (m_current == m_origin && n_current == n_origin) {
                continue;
            }

            if (grid_current[m_current][n_current]) {
                if (++neighbors > 3) {
                    return neighbors;
                }
            }
        }
    }
    return neighbors;
}

void Gol::apply_rules(int neighbors, int m, int n) {
    grid_next[m][n] = grid_current[m][n];

    // Any live cell with fewer than two live neighbors dies,
    // as if caused by under population.
    if (grid_current[m][n] && neighbors < 2) {
        grid_next[m][n] = false;
        grid_visual[m * width + n].color = visual_dead;
    }

    // Any live cell with two or three live neighbors lives on
    if (grid_current[m][n] && (neighbors == 2 || neighbors == 3)) {
        grid_next[m][n] = true;
        grid_visual[m * width + n].color = visual_alive;
    }

    // Any live cell with more than three live neighbors dies,
    // as if by overpopulation.
    if (grid_current[m][n] && neighbors > 3) {
        grid_next[m][n] = false;
        grid_visual[m * width + n].color = visual_dead;
    }

    // Any dead cell with exactly three live neighbors becomes a live cell,
    // as if by reproduction.
    if (!grid_current[m][n] && neighbors == 3) {
        grid_next[m][n] = true;
        grid_visual[m * width + n].color = visual_alive;
    }
}

main.cpp:

#include "gol.h"

#include <SFML/Graphics.hpp>

#include <string>

int main() {
    constexpr int width = 1440;
    constexpr int height = 900;
    Gol gol{width, height};

    sf::RenderWindow window(sf::VideoMode(width, height), "0",
                            sf::Style::Titlebar | sf::Style::Close);
    window.setFramerateLimit(60);

    constexpr float update_delay = .5;
    bool is_active = false;
    int iteration = 0;
    sf::Clock clock;
    clock.restart();
    while (window.isOpen()) {
        sf::Event event;
        while (window.pollEvent(event)) {
            switch (event.type) {
                case sf::Event::Closed:
                    window.close();
                    break;

                case sf::Event::KeyPressed:
                    if (event.key.code == sf::Keyboard::P) {
                        is_active = !is_active;
                    }

                    if (!is_active && event.key.code == sf::Keyboard::U) {
                        window.setTitle(std::to_string(++iteration));
                        gol.update();
                    }

                    if (event.key.code == sf::Keyboard::R) {
                        is_active = false;
                        iteration = 0;
                        window.setTitle("0");
                        gol.reset();
                    }
                    break;

                default:
                    break;
            }
        }

        window.clear();

        if (is_active && 
            clock.getElapsedTime().asSeconds() >= update_delta) {
            window.setTitle(std::to_string(++iteration));
            gol.update();
            clock.restart();
        }

        gol.display_grid(window);

        window.display();
    }
}
\$\endgroup\$
  • \$\begingroup\$ Make the grid an sf::Drawable and use an sf::VertexArray not a std::vector<sf::Vertex> as I'm pretty sure the vector won't be stored in the video memory. Not certain however. \$\endgroup\$ – pointerless May 3 '18 at 10:35
  • \$\begingroup\$ @pointerless The linked tutorial explicitly mentions that a sf::VertexArray is just a std::vector<sf::Vertex> so it should make no difference unless it changed in recent versions. \$\endgroup\$ – yuri May 3 '18 at 10:38
  • \$\begingroup\$ A very good point. Still make it a drawable and provide the draw method, it may not improve performance but it is more logical. Also what is your compile command? Maybe add some optimiser flags? \$\endgroup\$ – pointerless May 3 '18 at 11:10
  • \$\begingroup\$ @pointerless I always compile with -O2 in this case I also tried -O3 and -Ofast neither of which changed the rather high CPU usage. \$\endgroup\$ – yuri May 3 '18 at 11:37
  • \$\begingroup\$ I would rather simulate the game in a separate thread, store the results (or changes) in a container and use sfml for playback. This would also allow you to go to previous steps. \$\endgroup\$ – Timo May 3 '18 at 11:48
3
\$\begingroup\$

I think that you are correct to be concerned about the coupling. I also think that decoupling your program would make it easy to test, debug, and profile for performance issues. With that in mind I suggest you use the MVC Pattern or closely related MVVM or MVP and the Game Loop.

The way I would implement the Update Method would be to build your GOL class as an application level class. At its core this pattern boils down to:

while(app.isRunning())
{
    // handle all input from user (in your case p, u, and r)
    // update all entities (here you would scan the neighbors and change your cells
    // draw (here render your vertex array)
}

The MVC is what will help you decouple though. try to think of it this way. What if you wanted to switch libraries. Try to write your code so that the underlying data structure doesn't know or care how it is presented. Then you could theoretically switch from say SFML to SDL or some hand-rolled library or anything you'd like. You'd have to define your Cells in abstract manner. Maybe a 2d Matrix or a flattened matrix. The update method here would run your check_neighbors() or apply_rules functions and update all your cells accordingly.


It's also worth mentioning you have a good use of a double-buffer.


Now to build your View and Controller. In this case because its the same library and the Controller is so small I personally would make them the same class. Just shove your three user events into the input() function and move on. You will want to pass the Model as a reference to the View so it can know what to present. Here you will keep your sf::RenderWindow as well as your std::vector<sf::Vertex>.


This might seem like over-engineering and for such a small project it very well may be. However, you are having a performance issue that you can't narrow down and a little further abstraction will make that easier. Once you have a render() function you can profile and test it. You can do the same with an update() function.

\$\endgroup\$
2
\$\begingroup\$

This is not an actual answer but rather an investigation that doesn't fit into the comment section.

I just tested your code with VS2017 and let the profiler do its work.

Build config { c++17, sfml 2.4.2, release (O2), x64 }

Rig:

  • OS: Windows 10 x64 (1709, 16299.371)
  • CPU: i7-6800K (6 cores @ 4.1GHz)
  • GPU: GTX 1080 Ti
  • RAM: 32 GB DDR4

I'm aware that the rig is probably above average but this shouldn't matter that much when profiling the code and this is what the profiler gave me (don't mind the C.exe, that's the project name):

performance profile

As you can see, drawing is indeed not the problem, but updating the logic is the actual bottleneck. Your Gol::update function takes 30% of the entire execution time.

Note

Your game runs kinda fluent on my system (update cycles need 270ms, you limited it to 500ms).

\$\endgroup\$
  • \$\begingroup\$ This is rather odd. After spending hours setting up microsoft bloat studio and testing this the display_grid function takes the top spot. I'm not familiar with using the MS profiler or VS in general so maybe I did something wrong when measuring? \$\endgroup\$ – yuri May 3 '18 at 18:47
  • 2
    \$\begingroup\$ That's indeed interesting. Did you compile debug or release? \$\endgroup\$ – Timo May 3 '18 at 20:27

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.