Another Conway's Game of Life Simulation (With colored populations!)

Question

This is my near-final version of Conway's Game of Life, with inherited colors using PDCurses. Any new spawned cells take on the most frequent color surrounding it when it spawns. This leads to single-colored populations roaming around, and causes interesting "battles" between 2 populations; which usually end in one taking over the other.

I already had one review of it, which increased its speed considerably, but now I'm looking for more general feedback about best practices, and feedback regarding the following:

• An alternative to the struct NeighborData. It seems overkill to use a struct like this just to return 2 pieces of data at once (The most prevalent color, and the number of neighbors).
• If there's a more efficient way of counting the colors than consumeColorFreqs
• Anywhere else I can squeeze more speed out of.

Population.h:

#ifndef POPULATION_H
#define POPULATION_H

#include <set>
#include <vector>
#include <array>

#include "curses.h"

#define NCOLORS 16

typedef unsigned char Color;

struct NeighborData {
    unsigned int count = 0;
    Color color = COLOR_WHITE;
    NeighborData(unsigned int ct, Color cr);
};

class Population {
    //To hold the "finished" generation, and the generation
    // currently being constructed
    std::vector<Color> cells;
    std::vector<Color> newCells;

    int width = 0, height = 0;

public:
    Population(int newWidth, int newHeight);

    bool pointIsOccupied(int x, int y) const;

    void addPoint(int x, int y, Color color);
    void killPoint(int x, int y);

    Color getPointColor(int x, int y) const;

    NeighborData getNeighborData(int x, int y, int depth = 1) const;

    void decideLifeOf(int, int);

    int getIndexOf(int, int) const;

    void replacePopulation();

    Color consumeColorFrequencies(const Color colorFreqs[]) const;

};

Color randomColor(Color starting = 1);

#endif

Population.cpp:

#include "Population.h"

#include <cstdlib>
#include <algorithm>
#include <array>

#include "curses.h"

NeighborData::NeighborData(unsigned int ct, Color cr) {
    count = ct, color = cr;
}

Population::Population(int newWidth, int newHeight) {
    width = newWidth;
    height = newHeight;

    cells.resize(width * height);
    newCells.resize(width * height);
}

bool Population::pointIsOccupied(int x, int y) const {
    return cells[getIndexOf(x, y)] != '\0';
}

Color Population::getPointColor(int x, int y) const {
    return cells[getIndexOf(x, y)];
}

void Population::addPoint(int x, int y, Color color) {
    newCells[getIndexOf(x, y)] = color;
}

void Population::killPoint(int x, int y) {
    newCells[getIndexOf(x, y)] = '\0';
}

NeighborData Population::getNeighborData(int x, int y, int depth) const {
    //To temporarily hold frequencies of colors
    //Index is the color, value is the number of occurances
    Color colorFreqs[NCOLORS];

    int count = 0;
    for (int cY = y - depth; cY <= y + depth; cY++) {
        if (cY < 0 || cY >= height) continue;
        for (int cX = x - depth; cX <= x + depth; cX++) {
            if (cX < 0 || cX >= width || (cX == x && cY == y)) continue;
            Color color = getPointColor(cX, cY);

            if (color != '\0') {
                count += 1;
                colorFreqs[color] += 1;
            }

        }
    }
    Color c = consumeColorFrequencies(colorFreqs);
    return NeighborData(count,c);
}

void Population::decideLifeOf(int x, int y) {
    NeighborData nD = getNeighborData(x, y, 1);
    unsigned int ns = nD.count;
    Color color = nD.color;

    if (ns < 2 || ns > 3) killPoint(x, y);
    else if (ns == 3) addPoint(x, y, color);
}

int Population::getIndexOf(int x, int y) const {
    return y * width + x;
}

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

Color randomColor(Color starting) {
    return (rand() % (NCOLORS - starting)) + starting;
}

Color Population::consumeColorFrequencies(const Color colorFreqs[]) const {
    Color hIndex = 0, highest = 0;
    for (Color i = 0; i < NCOLORS; i++) {
        Color freq = colorFreqs[i];
        if (freq > highest) {
            hIndex = i, highest = freq;
        }
    }
    return hIndex;
}

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 = 0, worldHeight = 0;

public:

    World(int, int);

    void compileOutput(std::string disp = "#") const;

    void simGeneration();

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

};

#endif

World.cpp:

#include "World.h"

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

#include "curses.h"

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

void World::compileOutput(std::string disp) const {
    for (int cY = 0; cY < worldHeight; cY++) {
        for (int cX = 0; cX < worldWidth; cX++) {
            char c = pop.getPointColor(cX, cY);

            init_pair(c, c, COLOR_BLACK);   //(Pair number, fore color, back color)
            attron(COLOR_PAIR(c));
            mvprintw(cY, cX, (pop.pointIsOccupied(cX, cY) ? disp.c_str() : " ") );
            attroff(COLOR_PAIR(c));
        }
    }
}

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

void World::randomizeCells(double chanceOfLife, int newSeed) {
    if (newSeed > 0) srand(newSeed);
    for (int y = 0; y < worldHeight; y++) {
        for (int x = 0; x < worldWidth; x++) {
            if ((rand() % int(1.0 / chanceOfLife)) == 0) {
                unsigned char color = randomColor();
                pop.addPoint(x, y, color);
            }
        }
    }
    pop.replacePopulation();
}

Timer.h (Not entirely necessary for the program to run, but it's used in the main):

#ifndef TIMER_H
#define TIMER_H

#include <chrono>

class Timer {

    std::chrono::system_clock::time_point start;

public:
    Timer();

    void restart();

    std::chrono::system_clock::time_point now();

    double getMS();
    double getSecs();
};

#endif

Timer.cpp:

#include "Timer.h"

#include <ctime>


Timer::Timer() {
    start = now();
}

void Timer::restart() {
    start = now();
}

std::chrono::system_clock::time_point Timer::now() {
    return std::chrono::system_clock::now();
}

double Timer::getMS() {
    return (now() - start).count() / 10000.0;
}

double Timer::getSecs() {
    return getMS() / 1000.0;
}

Main.cpp:

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

#include <iostream>
#include <sstream>
#include <cstdlib>
#include <vector>
#include <chrono>
#include <thread>

#include "curses.h"

int strToInt(std::string str) {
    std::stringstream ss;
    int ret = 0;
    ss << str; ss >> ret;
    return ret;
}

void resetCin() {
    std::cin.clear();
    std::cin.ignore(255, '\n');
}

int main(int argc, char* argv[]) {
    using namespace std;

    //The input bit below is ugly and unsafe.

    string  inX = "10",
            inY = "10",
            tempSeed = "", inSeed = "-1";

    cout << "Board Dimensions? (2 space separated numbers): ";
    cin >> inX >> inY;
    resetCin();

    cout << "Random seed? (Leave blank for random): ";
    getline(cin, tempSeed);
    inSeed = tempSeed == "" ? inSeed : tempSeed;

    initscr();                    /* Start curses mode */
    start_color();

    noecho();                   // Don't echo any keypresses
    curs_set(FALSE);            // Don't display a cursor

    int maxX = strToInt(inX), maxY = strToInt(inY);

    World w(maxX, maxY);

    //w.randomizeCells(0.4, 10);
    w.randomizeCells(0.4, strToInt(inSeed));

    int updateDataEvery = 500;
    double lastDur = 0, lastOutput = updateDataEvery;
    Timer t;
    for (int gens = 0; gens < 100000; gens++) {

        //Clearing isn't necessary when using just updating pixels, because they're
        // constantly being overwritten
        //It causes areas outside the grid to "streak"
        clear();

        w.compileOutput("#");
        mvprintw(maxY + 1, 0, "Generation: %d", gens);

        w.simGeneration();

        //Update block every n milliseconds
        lastOutput += lastDur;
        if (lastOutput >= updateDataEvery) {

            lastDur = t.getMS();
            lastOutput = 0;

        }
        t.restart();
        mvprintw(maxY + 2, 0, "%0.1f fps", 1000.0 / lastDur);


        refresh();
        this_thread::sleep_for(chrono::milliseconds( 25 ) );
    }

    endwin();
}

Answer 1

I see a number of things that could probably help you improve your program.

Eliminate unused variables

In main(), argc and argv are unused. I'd recommend either eliminating them by changing the function to int main() or better yet, use them to pass in the required initialization variables for dimensions and seed value.

Use standard function where available

The code uses a custom strToInt function, but it would be better to simply use std::stoi.

Use const where practical

The values for maxX, maxY are set once and never changed which suggests that they should be const instead. I'd recommend eliminating inSeed, tempSeed, inX and inY and all of the associated clutter and instead using this:

if (argc < 3) {
    cout << "Usage: life xdim ydim seedvalue\n";
    return 0;
}
const int maxX = std::stoi(argv[1]);
const int maxY = std::stoi(argv[2]);
const int seed = std::stoi(argv[3]);

Have your constructor fully construct the object

The code currently has the equivalent to these lines:

World w(maxX, maxY);
w.randomizeCells(0.4, seed);

Instead, why not simply make a constructor that does the randomization?

World w(maxX, maxY, 0.4, seed);

Now the World object is fully instantiated and ready to use which should be the result of every constructor. One way to do that:

World::World(int xMax, int yMax, double chanceOfLife, int newSeed) :
    worldWidth(xMax), 
    worldHeight(yMax),
    pop(worldWidth, worldHeight)
{
    randomizeCells(chanceOfLife, newSeed);
}

Name parameters in constructors

At the moment, the constructor for the World object has this declaration inside the World.h header:

World(int, int);

Unfortunately, this is not sufficient for someone trying to use the World object. A very simple addition would be to simply name the parameters:

World(int xMax, int yMax);

This doesn't take the place of good documentation, but it's very useful for quick reference and costs you nearly nothing.

Never use an external parameter as a printf format string

The World::compileOutput() routine includes this line:

mvprintw(cY, cX, (pop.pointIsOccupied(cX, cY) ? disp.c_str() : " ") );

However disp is a std::string passed from outside the object. This is potentially dangerous because it could potentially be used for a format string attack. A better alternative would be this:

mvaddch(cY, cX, (pop.pointIsOccupied(cX, cY) ? disp : ' ') );

Now if you make the passed parameter a char, there is no longer any way to abuse it. Further, you avoid the overhead of having to create and destroy a string object every interation, which helps performance.

Avoid calling extra functions

In the World::compileOutput() routine, there there are calls to attron and attroff surrounding every output. However, these are not necessary. Instead, the could could look like this:

char c = pop.getPointColor(cX, cY);
init_pair(c, c, COLOR_BLACK);   //(Pair number, fore color, back color)
mvaddch(cY, cX, (pop.pointIsOccupied(cX, cY) ? disp|COLOR_PAIR(c) : ' ') );

By ORing the color value into the character value, you can avoid the two calls.

Use only required #includes

Your .h files are the interface for the class. For that reason, in those files, you should only include the #include files that are required for the interface. So in the case of World.h the file currently has the following includes:

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

#include "Population.h"

However, only Population.h is actually required for the interface. The others are required for the implementation but that is a detail that is not of concern to users of the interface, so those should be moved to the World.cpp file instead.

Use C++11 random number facilities

Consider this code in your World::randomizeCells() routine:

for (int y = 0; y < worldHeight; y++) {
    for (int x = 0; x < worldWidth; x++) {
        if ((rand() % int(1.0 / chanceOfLife)) == 0) {
            unsigned char color = randomColor();
            pop.addPoint(x, y, color);
        }
    }
}

What the code is attempting to do is to generate a boolean value distribution that is true with a probability of chanceOfLife. So if chanceOfLife has the value of 0.25 we would expect about 1 in 4 values to be true. That's called a Bernoulli distribution and C++11 has a much more direct and much more elegant way to achieve this.

std::random_device rd;
std::bernoulli_distribution alive(chanceOfLife);
for (int y = 0; y < worldHeight; y++) {
    for (int x = 0; x < worldWidth; x++) {
        if (alive(rd)) {
            pop.addPoint(x, y, randomColor());
        }
    }
}

You will need to #include <random> to use this facility.

Rethink your interfaces

The World and Population objects are closely intertwined. It appears that the World is essentially responsible for displaying the data and that Population is responsible for creating and updating the data. That's a fine and appropriate way to separate things, but there are redundancies. For example, the Population class definitely needs to know the height and width so it should have those member data items, but then they should be stored only there and the World class should get them from there rather than storing duplicates. I rewrote your program and removed the Timer and associated stuff. The Main.cpp now looks like this:

#include <iostream>
#include "World.h"

int main(int argc, char* argv[]) {
    if (argc < 2) {
        std::cout << "Usage: life maxX maxY\n";
        return 0;
    }
    int maxX = std::stoi(argv[1]);
    int maxY = std::stoi(argv[2]);

    constexpr unsigned maxgen = 10000;

    for (World w(maxX, maxY, 0.4); w.generation() < maxgen; ++w)
        w.display();
}

As you can see, the generation counter is delegatated to the World class. The constructor and destructor for the World class take care of all of the curses setup and teardown. I have also overloaded operator++ to advance to the next generation and changed the name from compileOutput which seemed rather vague to display which actually does what it says.

Use initializer list constructors by default

Here is a rewritten constructor for World:

World::World(int xMax, int yMax, double chanceOfLife) :
    worldWidth(xMax), 
    worldHeight{yMax},
    pop{worldWidth, worldHeight, chanceOfLife}
{
}

Note that all of the work is done inside the constructors for the objects. Also note that member data will be initalized in declaration order and not necessarily in the order listed in the constructor, so best practice is to make sure they match. In this case, it makes sense to list worldWidth and worldHeight before pop so they should also be declared in that order.

Use standard algorithms instead of indexing

We can greatly simplify code by using range for instead of indexing. For example, moving the randomizeCells to the Population class, it might be written like this:

void Population::randomizeCells(double chanceOfLife)
{
    std::random_device rd;
    std::bernoulli_distribution alive(chanceOfLife);
    for (auto &cell : newCells) {
        if (alive(rd)) {
            cell = randomColor();
        }
    }
    replacePopulation();
}

Even simpler, we could use a standard algorithm std::generate from <algorithm>:

void Population::randomizeCells(double chanceOfLife)
{
    std::random_device rd;
    std::bernoulli_distribution alive(chanceOfLife);
    std::generate(newCells.begin(), newCells.end(), 
        [&](){ return alive(rd) ? randomColor() : 0; }
    );
    replacePopulation();
}

This code uses a lambda to initialize each cell.

Streamline neighbor counting

The getNeighborData routine is more complex than it needs to be. An alternative approach would be to store relative offsets for each of the 8 neighbors in an array that is initialized by the constructor. If x is the width of the visible array, the offsets are these:

-x-1  -x+0  -x+1
  -1          +1
+x-1  +x+0  +x+1

For cells that are not near the edge, counting is now very simple. For ones that are at the edge, the current code makes sure to count only neighbors that are inside the actual rectangle. To keep the counting simple, but to maintain that same counting style, one simple way to accomodate that is to simply allocate a "dead band" of permanently dead cells around the periphery. This wastes a little space in the data structures (4+(2*width*height) cells) but greatly simplifies the calculation of neighbors. Since neighbor calculations are probably where your program spends much of its time, it's probably worthwhile to make that space/speed tradeoff if you wish to maximize speed.

To expand on that a bit, here is the routine I wrote to test the speed difference:

void Population::decideLifeMiddle(int x, int y) {
    int index = getIndexOf(x, y);
    Color *p = &cells[index];
    int count = 0;
    Color n[8];
    for (int i=0; i < 8; ++i) {
        if (p[neighbor[i]]) {
            n[count++] = p[neighbor[i]];
        }
    }
    // now point to new cell 
    p = &newCells[index];
    if (count < 2 || count > 3) {
        *p = 0;
    }
    else if (count == 3) {
        if (n[0] == n[1] || n[1] == n[2]) {
            *p = n[1];
        } else {
            *p = n[0];
        }
    }
}

A few comments about this code are in order. First, it is designed to be iterated through only the non-edge cells in the array. Second, it takes advantage of a neighbors array (not shown) which has the offsets mentioned above. Third, we only care about the color if there are exactly three neighbors, so what the code does is store non-zero colors in the array n[]. These values are not used except in the circumstance that there are exactly three neighbors. In that case, the only values are necessarily in n[0], n[1] and n[2]. If they are all three the same color, then we choose n[1] as the new color. If only two are the same color, and they are n[0] and n[1] or n[1] and n[2] we choose n[1] as the new color. Otherwise, either n[0] and n[2] are the same or they are all three different; in either case we choose n[0]. This eliminates a number of routines, the Neighbor structure and a lot of time. My tests showed a 3x improvement in speed.

Answer 2

Prefer to use initializer list in constructor

NeighborData::NeighborData(unsigned int ct, Color cr) {
    count = ct, color = cr;
}
// I would write it as
NeighborData::NeighborData(unsigned int count, Color color)
    : count(count)
    , color(color)
{}

If the members are non POD this will make a difference. So it is just a good habit to do it for all values (as types may change over time).

Interface Design:

This interface looks a bit leaky

bool pointIsOccupied(int x, int y) const;
void addPoint(int x, int y, Color color);
void killPoint(int x, int y);
Color getPointColor(int x, int y) const;
NeighborData getNeighborData(int x, int y, int depth = 1) const;
void decideLifeOf(int, int);
int getIndexOf(int, int) const;
void replacePopulation();
Color consumeColorFrequencies(const Color colorFreqs[]) const;

It basic looks like you use Population as a container then other classes just pull all the data from it and then manipulate it directly via the API. This leaks your implementation extraction.

I would reverse the design. The Population class knows how life is run. Then it updates the GUI via an interface that you provide.

 Population  pop(50, 50, display); // Display is an surface you can update.


 while(!finished)
 {
    pop.advanceIteration(1); // Advance 1 iteration and update Display.
 }

Use constructors when useful

int strToInt(std::string const& str)
{       //               ^^^^^^ pass by reference to avoid copy.
    std::stringstream ss(str); // Use constructor.
    int ret = 0;
    ss >> ret;                 // Did you want to check for errors?
    return ret;
}

Even easier if you use standard conversions:

int x = boost::lexical_cast<int>("56");

Or event the standard functions:

int x = std::atoi("56");

Remove unused code

Timer is defined but is not really used. You can remove all references and the code will work just as well.

Answer 3

NeighborData unnecessary

To answer your first question, I would get rid of NeighborData completely. Change:

NeighborData Population::getNeighborData(int x, int y, int depth) const {

To:

int Population::getNeighborData(int x, int y, int depth, Color *pColor) const {
    // ...
    *pColor = consumeColorFrequencies(colorFreqs);
    return count;
}

Faster color selection

For your second question, you could find the common color a tiny bit faster if you kept track of the most common color as you encountered each neighbor. Like this:

        Color maxColor = '\0';
        int   maxCount = 0;

        // ...

        if (color != '\0') {
            count += 1;
            if (++colorFreqs[color] > maxCount) {
                maxColor = color;
                maxCount = colorFreqs[color];
            }
        }

        // No need for the consume function any more, just return maxColor.

Since you have at most eight neighbors, you only do work 8 times max. With the consume function, you loop 16 times even if there were no neighbors.

Answer 4

I'd want to add to some exellent points outlined by other reviewers.

1. There is nothing wrong about NeighbourData. Even more, you should consider addition of Point structure to connect x and y coordinates.

2. You should really swap new and old cells in replacePopulation. It may not provide huge gain, but the copy is not really necessary, this is so low hunging fruit to take.