leblog

Summary

This was a project that I’ve itterated mutiple times without event trying to go further that the first rendering. This is my ways on improving a simple game of life editor but with plenty of editing features.

Core ideas & application:

The first things that I wanned to add on the basic project is a setting and a pause/play option.

In order to do this, I used dearImGUI on top of raylib rendering, the whole project is implemented in C++.

This is what I’ve implemented so far.

The following steps are what will take me a lot of brain process. In order to add more advanced features, I need to optimize this base.

As for now, the grid is stored in a vector of booleans, this causes an issue of memory as we can set the current cells sizes really small. The first topic I will bring here for now is the data compression. This will allow me to create saves of the current grid in a memory efficient way.

Optimisation & patern reproduction

I wanned to implement a way to start from an initial state and step forward & backward. This means storing an history. If done like it is implemented right now (as vectors of booleans), this will take too much space in memory. Here is my though on the improvments.

Data compression :

Packed data:

• The initial state (to reduce load time or file size).
• Undo/redo snapshots (for compact state history) with history buffer of packed data.
• Any export/serialization (like RLE or bitstream).

Unpacked data:

• Only once, when loading the initial grid to GPU.
• When restoring an undo/redo state.

RLE(Lossless compression) :

The first type of compression that I've implemented was the RLE and it just compacts the data that is represented multiple times into a shorter representation.

As the game of life contains only 2 types, it is easier to implement.

There could be multiple dead or alive cells that are stored into a 1D array.

To achieve my goal, I want to compressed any grid sizes to have a shorter representation.

Here is my first iteration on this.

<grid_width>.<grid_height>.<initial_state>.<nbr>.<nbr>.<…>

// _data is a vector of bool that contains each cell states
std::string World::getCompressed() {
  if (!_data || _data->empty()) {
    return {};
  }
  bool previous_state = (*_data)[0];
  std::vector<uint32_t> compressed_out;
  compressed_out.push_back(_width);
  compressed_out.push_back(_height);
  compressed_out.push_back((previous_state) ? 1 : 0);
  unsigned int count = 0;
  for (auto state : *_data) {
    if (previous_state != state) {
      compressed_out.push_back(count++);
      previous_state = state;
      count = 1;
      continue;
    }
    count++;
  }
  compressed_out.push_back(count);
  return compressed_out;
}

// Ex for a grid of 33 x 18
// std vector<bool> _data = {true, true, true, false, false, true, true, false, true, <false until the end>};
// the compressed method results in 33.18.1.3.2.2.1.1.585

This seems easy enough, now the decompression algorythm.

void World::loadCompressed(const std::vector<uint32_t> &compressed) {
  if (compressed.empty()) {
    return;
  }
  auto it = compressed.begin();
  int width = *it++;
  int height = *it++;
  bool actual_state = (*it++ == 1);
  auto new_data = new std::vector<bool>(width * height, false);
  while (it != compressed.end()) {
    unsigned int count = *it++;
    for (unsigned int i = 0; i < count; ++i) {
      new_data->push_back(actual_state);
    }
    actual_state = !actual_state;
  }
  delete this->_data;
  this->_data = new_data;
  this->_width = width;
  this->_height = height;
}