Arduino Conways Game of Life using FastLED

Question

So I attempted to write Conway's game of life on an Arduino and display using the FastLED library. I use a custom bitset class to manage the game board state. I'm looking for feedback on performance, and general code style towards embedded systems.

I should note that my led strip is a little bit weird see diagram below to show how 4 rows work in it, and 4 columns. It kind of snakes back and forth, with zero being in the top right. My actual grid has 8 columns on it, and can be daisy chained to get more rows.

+----+----+----+----+
| 3  | 2  | 1  | 0  |
+----+----+----+----+
| 4  | 5  | 6  | 7  |
+----+----+----+----+
| 11 | 10 | 9  | 8  |
+----+----+----+----+
| 12 | 13 | 14 | 15 |
+----+----+----+----+

/**
   Game of Life with LEDS and variable HUE

   Assumes a square grid of leds on a 8x8 led matrix.

   Controlled with WS2812B led controller.
*/

#include <FastLED.h>

/**
 * How long should each frame be displayed roughly
 */
#define FRAME_TIME 500


/**
 * Should we draw the red border. If so we reduce the playfield by one on each side.
 * Undefine this if we should not draw it
 */
#define DRAW_BORDER
//#undef DRAW_BORDER

/**
 * The width of the grid
 */
#define WIDTH 8
/** 
 * The height of the grid
 */
#define HEIGHT 32

/**
 * The initial number of live cells in the grid. They are randomly placed.
 */
#define NUMBER_OF_INITIAL_LIVE_CELLS 16

/**
 * WS2812B Data pin
 */
#define DATA_PIN 3



/*
 * Computed Values based on above constants
 */
#ifdef DRAW_BORDER
  // We provide a spot for the border to go.
  #define GRID_X_START 1
  #define GRID_X_END (WIDTH - 1)
  #define GRID_Y_START 1
  #define GRID_Y_END (HEIGHT - 1)
#else
  #define GRID_X_START 0
  #define GRID_X_END WIDTH
  #define GRID_Y_START 0
  #define GRID_Y_END HEIGHT
#endif // DRAW_BORDER

#define NUM_LEDS (WIDTH * HEIGHT)

/**************************************************
 * Begin Main Code Below
 **************************************************/

int computeBitNumber(byte x, byte y) {
  return y * WIDTH + x;
}

template<size_t N>
class MyBitset {
public:
  MyBitset& operator=(const MyBitset& b) {
    memcpy(this->data, b.data, N/8);
  }

  void setBit(size_t idx, byte val) {
    size_t idx2 = idx / 8;
    int bit2 = idx % 8;
    bitWrite(data[idx2], bit2, val);
  }

  void zeroArray() {
    memset(data, 0, N/8);
  }

  byte getBit(size_t idx) const {
    size_t idx2 = idx / 8;
    return bitRead(data[idx2], idx % 8);
  }
private:
  byte data[N/8];
};

const CRGB BORDER_COLOR = CRGB(255, 25, 25);
const CRGB WAS_LIVE_COLOR = CHSV(115, 82, 60);
const CRGB LIVE_COLOR = CHSV(115, 82, 100);
const CRGB LIVE_AND_WAS_COLOR = CHSV(115, 82, 140);

CRGB leds[NUM_LEDS];
MyBitset<NUM_LEDS> current, prev;

CRGB& getLed(byte x, byte y) {
  int xOffset = y & 1 ? (WIDTH - 1) - x : x;
  return leds[y * WIDTH + xOffset];
}

void setup() {
  // put your setup code here, to run once:
  Serial.begin(9600);

  FastLED.setBrightness(100);
  FastLED.addLeds<WS2812B, DATA_PIN, GRB>(leds, NUM_LEDS);

  // Randomize the initial grid everytime on start up
  setupBorder();
  generateRandomGame();

  prev = current;
  FastLED.show();
}

void loop() {
  int startTime = millis();  
  setupBorder();
  current.zeroArray();

  for (int x = GRID_X_START; x < GRID_X_END; ++x) {
    for (int y = GRID_Y_START; y < GRID_Y_END; ++y) {
      int count = countNeighbors(x, y);
      int index = computeBitNumber(x, y);

      CRGB& targetLed = getLed(x, y);
      if (count == 2 || count == 3) {
        current.setBit(index, 1);
        targetLed = prev.getBit(index) ? LIVE_AND_WAS_COLOR : LIVE_COLOR;
      } else {
        current.setBit(index, 0);
        targetLed = prev.getBit(index) ? WAS_LIVE_COLOR : CRGB::Black;
      }
    }
  }
  prev = current;
  int finishTime = millis();
  Serial.println(finishTime - startTime);

  FastLED.show();
  FastLED.delay(FRAME_TIME - (finishTime - startTime));
}

int countNeighbors(byte xCenter, byte yCenter) {
  int sum = 0;
  for (int x = xCenter - 1; x < xCenter + 2; ++x) {
    for (int y = yCenter - 1; y < yCenter + 2; ++y) {
      if (x >= GRID_X_END || x < GRID_X_START || y < GRID_Y_START || y >= GRID_Y_END)
        continue;
      sum += prev.getBit(computeBitNumber(x,y));
    }
  }
  return sum - prev.getBit(computeBitNumber(xCenter, yCenter));
}

/**
 * Clears the LED array to black using memset.
 */
void setupBorder() {
  memset(leds, 0, sizeof(leds));
#ifdef DRAW_BORDER
  for (int i = 0; i < WIDTH; ++i) {
    getLed(i, 0) = BORDER_COLOR;
    getLed(i, GRID_Y_END) = BORDER_COLOR;
  }
  for (int i = GRID_Y_START; i < HEIGHT; ++i) {
    getLed(0, i) = BORDER_COLOR;
    getLed(GRID_X_END, i) = BORDER_COLOR;
  }
#endif // DRAW_BORDER
}


void generateRandomGame() {
  for (int i = 0; i < NUMBER_OF_INITIAL_LIVE_CELLS; ++i) {
    int x, y, v;
    do {
      x = random(GRID_X_START, GRID_X_END);
      y = random(GRID_Y_START, GRID_Y_END);
      v = computeBitNumber(x, y);
    } while(current.getBit(v) > 0);
    current.setBit(v, 1);
    getLed(x, y) = LIVE_COLOR;
  }
}

Answer 1

First, given that this is C++, it's surprising that you're still using C-style #defines when you could be using constexpr variables, e.g.

/**
 * WS2812B Data pin
 */
#define DATA_PIN 3

could have been done in one line as

constexpr int ws2812b_data_pin = 3;

---

One place it does still make sense to use #defines is when you have things that could conceivably be configured at build time. For example,

/**
 * Should we draw the red border. If so we reduce the playfield by one on each side.
 * Undefine this if we should not draw it
 */
#define DRAW_BORDER
//#undef DRAW_BORDER

seems like a reasonable use of the preprocessor. However, it would be much more conventional, and useful, if you permitted the build system to control the border via -DDRAW_BORDER=1 and -DDRAW_BORDER=0, rather than -DDRAW_BORDER and -UDRAW_BORDER. That is, the traditional way to write a macro like this is:

// Should we draw the red border?
// Default to "yes", but let the build system override it with -DDRAW_BORDER=0.
#ifndef DRAW_BORDER
 #define DRAW_BORDER 1
#endif

#if DRAW_BORDER
 constexpr int grid_x_start = ...
#endif

---

  MyBitset& operator=(const MyBitset& b) {
    memcpy(this->data, b.data, N/8);
  }

C++20 deprecated providing a user-defined operator= without a user-declared copy constructor. If you provide one, you should provide all three of the "Rule of Three" operations. Fortunately, in this case, you don't need a customized operator= at all. Just eliminate these three useless lines of code.

Also, it should have been four useless lines of code! Did you not receive a warning from your compiler about the missing return *this?

---

You never define the identifier byte, which makes me a little nervous. Is it just a typedef for unsigned char?

---

const CRGB WAS_LIVE_COLOR = CHSV(115, 82, 60);
const CRGB LIVE_COLOR = CHSV(115, 82, 100);
const CRGB LIVE_AND_WAS_COLOR = CHSV(115, 82, 140);

You forgot THE_WAS_AND_THE_LIVE_TOKYO_DRIFT...

IIUC, these constants are meant to be the colors of cells that were "live in the previous generation but not now," "live in this generation but not the previous one," and "live in both." For some reason you provide constants for these three, but then hard-code the fourth option ("live in neither generation") as CRGB::Black. I would much prefer to see this as a pure function of the two inputs:

static CRGB computeCellColor(bool prev, bool curr) {
    switch (2*prev + 1*curr) {
        case 0: return CRGB::Black;
        case 1: return CHSV(115, 82, 100);
        case 2: return CHSV(115, 82, 60);
        case 3: return CHSV(115, 82, 140);
    }
    __builtin_unreachable();
}

Then you can write your main loop more simply:

  for (int x = GRID_X_START; x < GRID_X_END; ++x) {
    for (int y = GRID_Y_START; y < GRID_Y_END; ++y) {
      int index = computeBitNumber(x, y);
      bool isLive = computeLiveness(x, y);
      bool wasLive = prev.getBit(index);

      current.setBit(index, isLive);
      getLed(x, y) = computeCellColor(wasLive, isLive);
    }
  }

I replaced your countNeighbors function with a computeLiveness function that does exactly what you need it to do — no more. Our main loop does not care about the exact number of neighbors involved; all it wants to know is a single bit of information. So that's all it should be asking for.

It is almost correct to say leds[index] = computeCellColor(...) instead of having to do that weird "assign to the result of a function call" thing. I would suggest looking for a way to eliminate the "assign to function call." For example,

setLed(x, y, computeCellColor(wasLive, isLive));

or

leds[computeLedIndex(x, y)] = computeCellColor(wasLive, isLive);

---

/**
 * Clears the LED array to black using memset.
 */
void setupBorder() {
  memset(leds, 0, sizeof(leds));
}

I can write that code in half the number of lines:

void clearLedsToBlack() {
  memset(leds, 0, sizeof(leds));
}

Also, I don't even see why you're clearing the LEDs to black on each iteration through the loop. Don't you end up overwriting all of the LEDs' values in the main loop anyway? And who says 0 means "black"? Elsewhere, when you want to set an LED to black, you use the symbolic constant CRGB::Black. You should try to be consistent — if you know black is 0, then just say 0, and if you don't know it, then don't write setupBorders to rely on it.

C++ does also allow you to assert that black is 0 at compile-time:

static_assert(CRGB::Black == 0);