Counting Colors in Conway's Game of Life

Question

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.addPoint(x, y, color);
            }
        }
    }
    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 <thread>

#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();
        this_thread::sleep_for(chrono::milliseconds( 50 ) );
    }


    endwin();
}

Answer 1

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.

Answer 2

@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;
  std::this_thread::sleep_for(50ms);
  

• 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;
  }