Counting Colors in Conway's Game of Life

I have a basic version of CGoL running with pdCurses. My goal was to have each newly spawned cell take on the dominant color of their neighbors (if a spawned cell is mostly surrounded by red, make it red). I managed to get a half-baked solution working, but it has a few problems, mainly:

• It requires another member vector to hold the frequency of colors
• It requires aforementioned vector to be marked as mutable so the constness of other functions isn't affected
• It required creating a struct to return duel results (the neighbor count, and the dominant color)
• The color frequency storage scheme is slightly confusing

If someone can think of a cleaner method of achieving this, I would appreciate it. I'll also take any other kind of critique you may have.

My main function to count the neighbors is:

NeighborData Population::getNeighborData(int x, int y, int depth) const {
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;

unsigned char color = getPointColor(cX, cY);

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

}
}
unsigned char c = consumeColorFrequencies();
return NeighborData(count,c);
}

• vector colorFreqs has a pre-allocated slot for each color (only 16 on my machine). Every time we check a color, we look up the color using the color as an index, and increment its count.
• consumeColorFrequenices() is the main function that I'm asking about. It "consumes" the frequency vector; returning the dominant color (or the first found color if more the one have an equal frequency)
• NeighborData is a small struct with 2 members: the count, and the dominant color. I needed a way to return both bits of data at once to my decideLifeOf() method.

consumeColorFrequencies():

unsigned char Population::consumeColorFrequencies() const {
int hIndex = 0, highest = 0;
for (unsigned int i = 0; i < colorFreqs.size(); i++) {
unsigned char freq = colorFreqs[i];
if (freq > highest) {
hIndex = i, highest = freq;
}
}
//Set all color frequencies to 0
std::fill(colorFreqs.begin(), colorFreqs.end(), 0);
return hIndex;
}


And, the target use:

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

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


Population.h:

#ifndef POPULATION_H
#define POPULATION_H

#include <set>
#include <vector>

#include "curses.h"

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

class Population {
//To hold the "finished" generation, and the generation
// currently being constructed
std::vector<unsigned char> cells;
std::vector<unsigned char> newCells;
//To temporarily hold frequencies of colors
//Index is the color, value is the number of occurances
mutable std::vector<unsigned int> colorFreqs;

int width = 0, height = 0;

public:
Population(int newWidth, int newHeight);

bool pointIsOccupied(int x, int y) const;

void addPoint(int x, int y, unsigned char color);
void killPoint(int x, int y);

unsigned char 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();

unsigned char consumeColorFrequencies() const;

};

unsigned char randomColor(unsigned char starting = 1);

#endif


Population.cpp:

#include "Population.h"

#include <cstdlib>
#include <algorithm>

#include "curses.h"

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

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

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

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

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

void Population::addPoint(int x, int y, unsigned char 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 {
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;
unsigned char color = getPointColor(cX, cY);

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

}
}
unsigned char c = consumeColorFrequencies();
return NeighborData(count,c);
}

void Population::decideLifeOf(int x, int y) {
NeighborData nD = getNeighborData(x, y, 1);
unsigned int ns = nD.count;
unsigned char 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;
}

unsigned char randomColor(unsigned char starting) {
return (rand() % (COLORS - starting)) + starting;
}

unsigned char Population::consumeColorFrequencies() const {
int hIndex = 0, highest = 0;
for (unsigned int i = 0; i < colorFreqs.size(); i++) {
unsigned char freq = colorFreqs[i];
if (freq > highest) {
hIndex = i, highest = freq;
}
}
//Set all color frequencies to 0
std::fill(colorFreqs.begin(), colorFreqs.end(), 0);
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.replacePopulation();
}


Timer.h:

#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 <cstdlib>
#include <vector>
#include <chrono>

#include "curses.h"

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

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

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

const long maxX = 60, maxY = 40;

World w(maxX, maxY);

w.randomizeCells(0.4, 10);

double lastDur = 1;
Timer t;
for (int rounds = 0; rounds < 5000; rounds++) {
clear();

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

w.simGeneration();

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

refresh();
}

endwin();
}

• If colorFreqs is a temporary, then why don't you convert it into a local variable in getNeighborData and pass it as a parameter to consumeColorFrequencies? – MikeMB Apr 9 '15 at 17:45
• @MikeMB I made it a member instead of a local so it wouldn't need to be constantly created/destroyed on every "scan". – Carcigenicate Apr 9 '15 at 17:50
• If the number of colors is fixed, just use a local std::array. The overhead for construction and destruction is zero. – MikeMB Apr 9 '15 at 18:12
• @MikeMB What does that give me? Fixing the mutable problem? Thanks, I'll try it. – Carcigenicate Apr 9 '15 at 18:15
• And it would allow you to parallelize your simGeneration method and possibly even increase your single threaded performance – MikeMB Apr 9 '15 at 19:38

I don't think there is anything wrong with your general approach (or at least I don't have a better suggestion).
On an implementation level I've a few suggestions

1. As mentioned before, I'd replace the class member mutable std::vector<unsigned int> colorFreqs; with a local std::array<size_t, COLORS> colorFreqs{}; in getNeighborData and pass the array as a const ref parameter to consumeColorFrequencies. This gets rid of the mutable problem and might even increase performance.
2. I'd write the getNeighborData function a little different:

NeighborData Population::getNeighborData(int x, int y, int depth) const {
std::array<unsigned char, COLORS> colorFreqs{};
int count = 0;
for (int cY = std::max(0, y - depth); cY <= std::min(height-1, y + depth); cY++) {
for (int cX = std::max(0, x - depth); cX <= std::min(width-1, x + depth); cX++) {
if (cX == x && cY == y) continue;
unsigned char color = getPointColor(cX, cY);
if (color != '\0') {
count++;
colorFreqs[color]++;
}
}
}
unsigned char c = consumeColorFrequencies(colorFreqs);
return NeighborData(count, c);
}


Whether that is easier to understand than your version is up for discussion, but it should be a little more efficient.

3. consumeColorFrequenciescan be simplified by using an STL algorithm:

unsigned char Population::consumeColorFrequencies(const std::array<unsigned char, COLORS>& colorFreqs) const {
auto it = std::max_element(std::begin(colorFreqs), std::end(colorFreqs));
return std::distance(std::begin(colorFreqs),it);
}

4. In response to the comment about multithreading: You can (more or less) trivially parallelize compileOutput by letting each thread generate the new cells for a slice of the world (e.g. a quarter of the rows on a 4-Core machine). There are many parallel loop implementations out there that can make that Task even easier. Obviously this is only sensible for very large grids.

• Awesome, thank you. It should be noted though, as I said in the comments that COLORS isn't actually a compile-time constant, so I ended up using a macro that defined NCOLORS as 16. I don't know what this will do on a machine with less than that many colors though. That'll probably be my next test. – Carcigenicate Apr 10 '15 at 0:18
• And is there a reason you use std::begin(colorFreqs) instead of colorFreqs.begin()? And I'm guessing the call to std::distance gives you the index number of the iterator? – Carcigenicate Apr 10 '15 at 0:22
• Amazingly, my version of consumeColorFrequencies is faster (29.748 vs 38.739 seconds). – Carcigenicate Apr 10 '15 at 0:33
• @Carcigenicate: You mean the version without STL-algorithm? If it has such a strong impact, then use your own version. About std::begin and end: No special reason just my personal preference. – MikeMB Apr 10 '15 at 7:48
• @Carcigenicate: I just realized I made a mistake: I wrote std::array<size_t, COLORS> when it should have been std::array<unsigned char, COLORS>. – MikeMB Apr 10 '15 at 8:00

@MikeMB answer already covers some interesting points, but there are still some more things that you could improve in your code:

• In your class Timer, you should const-qualify the methods now, getMS and getSecs since they don't modify the Timer instance when called. Whether you want now to be static or not is up to you.

• Also, it is useless to specify by yourself the seconds/milliseconds conversions, the standard library already does that for you:

double Timer::getMS() const {
std::chrono::duration_cast<std::chrono::milliseconds>(now() - start).count();
}

double Timer::getSecs() const {
std::chrono::duration_cast<std::chrono::seconds>(now() - start).count();
}


Actually, you could have only one function template that takes a type parameter for the seconds/milliseconds/etc... That would make a more flexible interface, while still abstracting away the std::chrono::duration_cast and the subtraction:

template<typename Duration>
double Timer::getElapsedTime() const {
std::chrono::duration_cast<Duration>(now() - start).count();
}

• At some point, you use the following piece of code:

this_thread::sleep_for(chrono::milliseconds( 50 ) );


It is fine, no problem. However, if you have access to a C++14 compiler, you might want to use the standard library user-defined literals to make it simpler:

using namespace std::chrono_literals;

• You could initialize every member of World in its constructor initialization list instead of initializing one member in the constructor initialization list and two members in the constructor body:

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

• The function consumeColorFrequencies can probably be written in terms of std::max_element and std::distance

unsigned char Population::consumeColorFrequencies() const {
// Find the index of the highest frequency
auto it = std::max_element(colorFreqs.begin(), colorFreqs.end());
auto hIndex = std::distance(colorFreqs.begin(), it);

//Set all color frequencies to 0
std::fill(colorFreqs.begin(), colorFreqs.end(), 0);
return hIndex;
}

• Thank you. I don't know if VS 2013 supports c++14; I haven't even looked into what goodies 14 brings. I'm glad they made times easier to enter though; the chrono class leads to some ugly code. And I don't know why I go back and forth between initialization lists and using the constructor body; i haven't found my preference yet. Your example is neater though. Thank you for the comments! – Carcigenicate Apr 10 '15 at 13:40
• @Carcigenicate When possible, always use constructor initialization list: it ensures that the object is constructed with the values you feed it. If you initialize in the constructor body, then the object will be constructed, then its fields will be modified. – Morwenn Apr 10 '15 at 13:45
• @Carcigenicate VS 2013 doesn't support user-defined literals, so the C++14 standard library one can't have been added. I guess that they will be present in VS 2015. – Morwenn Apr 10 '15 at 13:46
• Good point, thank you. And oh well. I survived this long writing long chrono namespace chains. That will be cool feature. They should just include implicits like Scala, then the user can just define such things with an implicit class. – Carcigenicate Apr 10 '15 at 13:53