Problems with efficiency with the Game of Life

Question

To help prepare myself for my final exam, I wrote a simple Game of Life. I want to expand it to have each sub-population represented by a character, but before I do that, I want to make it more efficient; because right now it's running at about 1 fps, which is way too slow (I'd like at least 3 fps). What I want from a review, mainly is:

1. Any minor fixes that don't require a refactor.

2. Any larger fixes that I might need to move things around to implement.

3. Any other notable things regarding safety/style.

I appreciate any and all feedback that might help prepare me for my exam.

To represent a 2D point - StaticPoint.h

#ifndef STATICPOINT_H
#define STATICPOINT_H

#include <iostream>

class StaticPoint {
protected:
    double x = 0;
    double y = 0;

public:
    StaticPoint();
    StaticPoint(double, double);
    StaticPoint(const StaticPoint&);

    double getX() const;
    double getY() const;

    double distanceTo(const StaticPoint&) const;

    inline bool operator==(const StaticPoint&) const;
    inline bool operator!=(const StaticPoint&) const;
    inline bool operator<(const StaticPoint&) const;
    inline bool operator>(const StaticPoint&) const;
};

std::ostream& operator<<(std::ostream&, const StaticPoint&);

bool StaticPoint::operator==(const StaticPoint& oP) const {
    return x == oP.x && y == oP.y;
}

bool StaticPoint::operator!=(const StaticPoint& oP) const {
    return !(*this == oP);
}

bool StaticPoint::operator<(const StaticPoint& oP) const {
    return x < oP.x || (x == oP.x && y < oP.y);
}

bool StaticPoint::operator>(const StaticPoint& oP) const {
    return *this != oP && !(*this < oP);
}

#endif

StaticPoint.cpp

#include "StaticPoint.h"

StaticPoint::StaticPoint() {

}

StaticPoint::StaticPoint(double nX, double nY) {
    x = nX;
    y = nY;
}

StaticPoint::StaticPoint(const StaticPoint& oP) {
    x = oP.x;
    y = oP.y;
}

double StaticPoint::getX() const {
    return x;
}

double StaticPoint::getY() const {
    return y;
}

double StaticPoint::distanceTo(const StaticPoint& p) const {
    return sqrt( pow(x - p.x, 2) + pow(y - p.y, 2) );
}

std::ostream& operator<<(std::ostream& os, const StaticPoint& p) {
    os << "(" << p.getX() << ", " << p.getY() << ")";
    return os;
}

Represents the cells - Population.h

#ifndef POPULATION_H
#define POPULATION_H

#include <set>
#include <vector>

#include "StaticPoint.h"

class Population {
    std::set<StaticPoint> cells;
public:
    Population();

    static const StaticPoint badCell;

    void addCellToPop(const StaticPoint&);
    void removeCellFromPop(const StaticPoint&);

    void killPopulation();

    StaticPoint getCellAt(double, double) const;
    StaticPoint getCellAt(const StaticPoint&) const;

    bool pointIsOccupied(const StaticPoint&) const;

    int countNeighborsWithin(const StaticPoint&, int depth = 1) const;

    void decideLifeOf(const StaticPoint&);

};

bool cellIsValid(const StaticPoint& c);

std::vector<StaticPoint> getPointsAround(const StaticPoint&, int depth = 1);

#endif

Population.cpp

#include "Population.h"

Population::Population() {

}

const StaticPoint Population::badCell = StaticPoint(std::numeric_limits<double>::lowest(), std::numeric_limits<double>::lowest());

void Population::addCellToPop(const StaticPoint& c) {
    cells.insert(c);
}

void Population::removeCellFromPop(const StaticPoint& c) {
    cells.erase(c);
}

void Population::killPopulation() {
    cells.clear();
}

StaticPoint Population::getCellAt(const StaticPoint& p) const {
    auto cellIt = cells.find(p);
    //Find returns a iterator to the end if it's not found
    if (cellIt == cells.end()) {
        return badCell;
    }
    return *cellIt;
}

StaticPoint Population::getCellAt(double tX, double tY) const {
    return getCellAt(StaticPoint(tX,tY));
}

bool Population::pointIsOccupied(const StaticPoint& c) const {
    return cells.count(c) != 0;
}

int Population::countNeighborsWithin(const StaticPoint& p, int depth) const {
    int count = 0;
    for (const StaticPoint& n : getPointsAround(p, depth)) {
        if (pointIsOccupied(n)) {
            count += 1;
        }
    }
    return count;
}

void Population::decideLifeOf(const StaticPoint& centrePoint) {
    int ns = countNeighborsWithin(centrePoint, 1);

    if (ns < 2 || ns > 3) removeCellFromPop(centrePoint);
    else if (ns == 3) addCellToPop(centrePoint);
}

bool cellIsValid(const StaticPoint& c) {
    return c != Population::badCell;
}

std::vector<StaticPoint> getPointsAround(const StaticPoint& centrePoint, int depth) {
    std::vector<StaticPoint> surrounding;
    //Pre-reserve the number of cells
    surrounding.reserve( pow(depth * 2 + 1, 2) - 1 );
    for (int cY = centrePoint.getY() - depth; cY <= centrePoint.getY() + depth; cY++) {
        for (int cX = centrePoint.getX() - depth; cX <= centrePoint.getX() + depth; cX++) {
            StaticPoint p(cX, cY);
            if (p != centrePoint) {
                surrounding.push_back(p);
            }
        }
    }
    return surrounding;
}

Layer over a population to hold the world's dimensions and any relevant methods - World.h

#ifndef WORLD_H
#define WORLD_H

#include <set>
#include <sstream>
#include <limits>
#include <vector>

#include "StaticPoint.h"
#include "Population.h"

class World {

    Population pop;

    StaticPoint worldDims;

public:

    World(double, double);

    std::string compileOutput(int spacedAt = 2, std::string disp = "#") const;

    //Advances the generation
    void simGeneration();

    void randomizeCells(double chanceOfLife = 0.3, int newSeed = -1);

};

#endif

World.cpp

#include "World.h"

#include <iomanip>
#include <set>
#include <cstdlib>

#include "StaticPoint.h"

World::World(double xMax, double yMax) {
    worldDims = StaticPoint(xMax, yMax);
}

std::string World::compileOutput(int spacedAt, std::string disp) const {
    std::stringstream output;
    for (double cX = 0; cX < worldDims.getX(); cX++, output << '\n') {
        for (double cY = 0; cY < worldDims.getY(); cY++) {
            StaticPoint c = pop.getCellAt(cX, cY);
            output << (cellIsValid(c) ? disp : "") << std::setw(spacedAt);
        }
    }
    return output.str();
}

void World::simGeneration() {
    //We can't modify the population in place;
    // the entire generation needs to be updated at once
    Population newPop = pop;
    for (int y = 0; y < worldDims.getY(); y++) {
        for (int x = 0; x < worldDims.getX(); x++) {
            newPop.decideLifeOf(StaticPoint(x, y));
        }
    }
    //Copy the new Population over the old
    pop = newPop;
}

void World::randomizeCells(double chanceOfLife, int newSeed) {
    if (newSeed > 0) srand(newSeed);
    pop.killPopulation();
    for (int y = 0; y < worldDims.getY(); y++) {
        for (int x = 0; x < worldDims.getX(); x++) {
            if ((rand() % int(1.0 / chanceOfLife)) == 0) {
                pop.addCellToPop(StaticPoint(x, y));
            }
        }
    }
}

The main routine Main.cpp

#include <iostream>

#include <sstream>

#include "StaticPoint.h"
#include "World.h"
#include "Timer.h"

#include <cstdlib>
#include <vector>

bool getRandBool() {
    return bool(rand() % 2);
}

int main(int argc, char* argv[]) {
    using namespace std;
    const long maxX = 50, maxY = 50;

    World w(maxX, maxY);

    w.randomizeCells(0.5, 10);

    w.simGeneration();

    for (int rounds = 0; rounds < 150; rounds++) {

        cout << rounds << "\n" << w.compileOutput() << "\n\n";

        w.simGeneration();

    }    

}

At this point, it's the bare minimum. I'd like to speed it up before I begin expanding on it though.

---

After JS1's suggestions, for my standard test case (30x30 world, 40% spawn chance, seed of 10, and 150 rounds), the time required dropped from 35.502 seconds, to 17.742 seconds (with non-redirected output). That's a definite improvement.d

Answer 1

Bugs

As written, your program doesn't actually simulate the game of life. The problem is that when you create the new generation, you are modifying the cells as you go. This means that the changes you are making to the new generation are affecting the population counts for the rest of the cells yet to be determined. You tried to address this with a copy of the population:

Population newPop = pop;

However, the loop that follows only uses the new population:

for (int y = 0; y < worldDims.getY(); y++) {
    for (int x = 0; x < worldDims.getX(); x++) {
        newPop.decideLifeOf(StaticPoint(x, y));
    }
}

In order for this to work properly, you would have needed to pass in the old population as well:

for (int y = 0; y < worldDims.getY(); y++) {
    for (int x = 0; x < worldDims.getX(); x++) {
        newPop.decideLifeOf(pop, StaticPoint(x, y));
    }
}

The baseline speed

Disregarding the bug mentioned above, I built your code and ran it to see how fast it was. On my machine, I was able to run 5000 iterations in 13.74 seconds (redirecting output to /dev/null). So let 13.74 seconds be the baseline speed that we will try to improve upon.

Using ints instead of doubles

I modified your program to replace all doubles with ints, except for the random generation function. Doing this made the time go down to 11.80 seconds (16% faster).

Avoiding unnecessary vector creation

The function getPointsAround() is unnecessary. All it does is create a vector of points, which the caller countNeighborsWithin() iterates through. If you just put the logic of getPointsAround() directly into countNeighborsWithin(), you can count the neighbors without ever creating the intermediary vector. Doing this decreased the time from 11.80 to 9.65 (22% faster).

Using a vector instead of a set

You currently use a set to represent your cells. Using a set, it takes O(log N) time to retrieve whether or not a cell is occupied, where N is the number of items in the set. You can do better by using a vector of booleans. Each element of the vector represents whether one cell is occupied or not. A lookup into a vector takes O(1) time.

When I modified your program to use a vector instead of a set, the time went from 9.65 to 1.6 (6 times faster).

Removing StaticPoint

After changing the set to a vector, the use of StaticPoint became unnecessary. Indexing into the vector used this formula cells[y*width + x]. I removed all uses of StaticPoint and replaced them with x/y coordinates instead. At this point, I also fixed the bug mentioned above by using two vectors:

std::vector<bool> cells;
std::vector<bool> newCells;

At each generation, the newCells vector is created using the values from cells. Then I copy back to the old generation with:

cells = newCells;

The time went from 1.60 to 0.60 (2.6 times faster). In total, the last iteration was 23 times faster than the original.

Minor things

In World.cpp, it was printing the cells with X being the row number and Y being the column number. That seemed backwards, so I swapped the for loops so that Y would be the row and X would be the column.

Also, where you used std::setw(spacedAt) wasn't working for me. It kept cutting off the first character in each line. I'm not sure why that was but I changed that part just so I could test properly.

The new code

World.h

#ifndef WORLD_H
#define WORLD_H

#include <set>
#include <sstream>
#include <limits>
#include <vector>

#include "Population.h"

class World {

    Population pop;

    int worldWidth;
    int worldHeight;

public:

    World(int, int);

    std::string compileOutput(int spacedAt = 2, std::string disp = "#") const;

    //Advances the generation
    void simGeneration();

    void randomizeCells(double chanceOfLife = 0.3, int newSeed = -1);

};

#endif

World.cpp

#include "World.h"

#include <iomanip>
#include <set>
#include <cstdlib>

World::World(int xMax, int yMax) {
    worldWidth  = xMax;
    worldHeight = yMax;
}

std::string World::compileOutput(int spacedAt, std::string disp) const {
    std::stringstream output;
    for (int cY = 0; cY < worldHeight; cY++, output << '\n') {
        for (int cX = 0; cX < worldWidth; cX++) {
            bool isOccupied = pop.pointIsOccupied(cX, cY);
            // This seems to cut off the first character of each line.
            // output << (isOccupied ? disp : "") << std::setw(spacedAt);

            // I used this instead, which uses a spacing of only 1.
            if (isOccupied)
                output << disp;
            else
                output << " ";
        }
    }
    return output.str();
}

void World::simGeneration() {
    for (int y = 0; y < worldHeight; y++) {
        for (int x = 0; x < worldWidth; x++) {
            pop.decideLifeOf(x, y);
        }
    }
    pop.switchToNewgen();
}

void World::randomizeCells(double chanceOfLife, int newSeed) {
    if (newSeed > 0) srand(newSeed);
    pop.initPopulation(worldWidth, worldHeight);
    for (int y = 0; y < worldHeight; y++) {
        for (int x = 0; x < worldWidth; x++) {
            if ((rand() % int(1.0 / chanceOfLife)) == 0) {
                pop.setOccupied(x, y, true);
            }
        }
    }
    pop.switchToNewgen();
}

Population.h

#ifndef POPULATION_H
#define POPULATION_H

#include <set>
#include <vector>

class Population {
    std::vector<bool> cells;
    std::vector<bool> newCells;
    int width;
    int height;
public:
    Population();

    void setOccupied(int x, int y, bool occupied);
    void initPopulation(int newWidth, int newHeight);
    bool pointIsOccupied(int x, int y) const;
    int countNeighborsWithin(int x, int y, int depth = 1) const;
    void decideLifeOf(int x, int y);
    void switchToNewgen(void);
};

#endif

Population.cpp

#include "Population.h"
#include <limits>
#include <math.h>

Population::Population() {
}

void Population::initPopulation(int newWidth, int newHeight) {
    width  = newWidth;
    height = newHeight;
    cells.resize(width * height);
    newCells.resize(width * height);
}

void Population::setOccupied(int x, int y, bool occupied) {
    newCells[y * width + x] = occupied;
}

bool Population::pointIsOccupied(int x, int y) const {
    return cells[y * width + x];
}

int Population::countNeighborsWithin(int x0, int y0, int depth) const {
    int count = 0;
    int xEnd = x0 + depth;
    int yEnd = y0 + depth;

    for (int y = y0 - depth; y <= yEnd; y++) {
        if (y < 0 || y >= height)
            continue;
        for (int x = x0 - depth; x <= xEnd; x++) {
            if (x < 0 || x >= width)
                continue;
            if (pointIsOccupied(x, y))
                count++;
        }
    }
    // Subtract off the count of the point itself.
    if (pointIsOccupied(x0, y0))
        count--;
    return count;
}

void Population::decideLifeOf(int x, int y) {
    int ns = countNeighborsWithin(x, y, 1);

    if (ns < 2 || ns > 3)
        setOccupied(x, y, false);
    else if (ns == 3)
        setOccupied(x, y, true);
}

void Population::switchToNewgen(void) {
    cells = newCells;
}

Answer 2

I would encourage you to change StaticPoint to use int for its coordinates instead of double.

However, I have a hunch your program is getting killed by too many creations and deletions of std::vector<StaticPoint> in Population::countNeighborsWithin.

I would update the function to not create std::vector at all by moving the logic of Population::getPointsAround to Population::countNeighborsWithin.

int Population::countNeighborsWithin(const StaticPoint& p, int depth) const 
{
   int count = 0;
   for (int cY = centrePoint.getY() - depth; cY <= centrePoint.getY() + depth; cY++)
   {
      for (int cX = centrePoint.getX() - depth; cX <= centrePoint.getX() + depth; cX++)
      {
         StaticPoint p(cX, cY);
         if ( (p != centrePoint) && pointIsOccupied(p) )
         {
            count += 1;
         }
      }
   }
   return count;
}