The ObjectStore - BOUNCE iT log #2

In this devlog, I will discuss how I implemented an ObjectStore that keeps track of all of my game objects. It provides an API for adding and removing objects, as well as running all the necessary game-loop functions for each of these objects.

But before we proceed, here is an important disclaimer:

I am by no means an experienced game developer. In fact, this is the first time I try to develop a game/engine.

In addition, the way I like to approach projects like that (i.e. projects that are meant to be for learning) is that I try to avoid watching or reading any tutorials that do something similar to what I am trying to do. I prefer to attempt to solve the problem on my own and only look for help when I get stuck on specific issues. I personally find that this maximises the learning outcomes for me.

However, this means that none of what I am showcasing here is presented as a tutorial on what should you do if you are embarking on a similar project. I am just discussing how I solved the problem in my specific case. I am sure there are a lot of mistakes that I have made that would be very obvious for someone with more experience.

With this out of the way, let’s begin.

Why do I even need an ObjectStore?

If you recall from the previous devlog, I said that rather than trying to build an engine that I can reuse for many games, I am going to focus on building things that I need for this game and only generalise when it makes sense.

This might lead someone to question the need for having an ObjectStore. Based on what I shared so far about the game, BOUNCE iT seems like a very simple game. It only has a ball and a paddle, doesn’t it?

Well, the answer is no. It is true that the beta only has the ball and the paddle, but I have always known that the game will include other things. Currently, the game has UI elements, pickups and simple particles.

I also knew that some structure that manages creating and destroying objects would come in handy for future games.

For these two reasons, I decided that it makes sense to create a generic structure that takes care of managing the game objects.

How I implemented my ObjectStore?

Before I discuss the implementation of the ObjectStore, I just want to mention one quick thing. The “engine” part of the game is implemented in plain old C, rather than C++. When I started working on the game, I wanted to use it as an opportunity to learn more about C. Therefore, I thought it would be good to implement the “engine” parts of the game in C and use C++ for the game itself.

The game-loop functions

Each object in the game can have one or more of three functions, an event handler, an update function and a rendering function. These functions will be registered when adding the object to the ObjectStore, and the engine will run them automatically every frame.

Each of these functions has a specific signature:

typedef void (*EventHandlerPtr)(void *object,
                                const SDL_Event *event);
typedef void (*UpdateFuncPtr)(void *object, f32 delta);
typedef void (*RenderFuncPtr)(void *object);

As you can see, each of the functions expect a void * to the object. This makes it possible to add an object of any data type to the store. The specific implementation of each function for an object should handle casting the void * to a pointer to the correct data type of the object.

void pointers, of course, can be very dangerous, as C allows you to cast them to a pointer of any type. However, in this case, since each function will be implemented at the same time as the object, there wasn’t any danger of me making the mistake of casting the void * to a pointer of the wrong type. So, unless I was going out of my way to make this mistake, there wasn’t really any reasons to be concerned here.

The ObjectStore struct

The ObjectStore type itself is declared as follows:

typedef struct object_store ObjectStore;

The struct itself is implemented in the source file. This keeps the implementation details hidden from the user, since the members of the struct shouldn’t be modified manually.

#define MAX_OBJ_COUNT 10000 // Defined in a constants.h file

/* ObjectID is an alias to int32_t */

struct object_store {
  uint64_t count;
  uint64_t deleted_count;
  void *object_ptrs[MAX_OBJ_COUNT];
  EventHandlerPtr event_handlers[MAX_OBJ_COUNT];
  UpdateFuncPtr update_funcs[MAX_OBJ_COUNT];
  RenderFuncPtr render_funcs[MAX_OBJ_COUNT];
  ObjectID reusable_ids[MAX_OBJ_COUNT];
};

As you can see, the ObjectStore keeps track of the count of both the active and the deleted objects. It then uses five fixed-size arrays. The reusable_ids array stores the IDs of any deleted objects, so they can be reused. The other four store the object pointers, event handlers, update functions and render functions respectively.

When an object is added to the store, the generated ID is used as the index to the object_ptrs, event_handlers, update_funcs and render_funcs arrays. So, an object and all of its functions are stored in the same position in their respective arrays. This makes it very simple to call the right functions for the correct object.

Why fixed-size arrays

Short answer: to simplify memory management.

I could have easily used dynamically allocated arrays. However, that would have meant that I will need to allocate and deallocate the memory for each of them. This isn’t a complicated task or anything, but it could lead to memory issues, since there are a lot of heap allocations that need to be managed. Therefore, it made more sense to just use fixed-size arrays in this case.

The fixed-size arrays would have been a problem if the following two conditions were met:

1. The ObjectStore could be allocated on the stack.
2. The MAX_OBJ_COUNT was very high.

Meeting both of these conditions could potentially lead to Stack Overflow problems, depending on the stack size assigned to the program by the operating system.

However, in my case, the ObjectStore can only be allocated on the heap, since it is declared as an incomplete type. Therefore, using fixed-size arrays can’t lead to Stack Overflow problems, even if MAX_OBJ_COUNT was greater than it currently is.

The ObjectStore API

The ObjectStore exposes the following functions:

ObjectStore *create_object_store();

ObjectID add_object_to_store(ObjectStore *os, void *object,
                             EventHandlerPtr eh,
                             UpdateFuncPtr uf,
                             RenderFuncPtr rf);

void remove_object_from_store(ObjectStore *os, ObjectID *id_ptr);

void handle_all_objects_events(ObjectStore *os,
                               const SDL_Event *event);
void update_all_objects(ObjectStore *os, float delta);
void render_all_objects(ObjectStore *os);

void destroy_object_store(ObjectStore **os);

It is very clear, of course, what each of these functions do, so let’s discuss how each of them is implemented.

ObjectStore *create_object_store() {
  ObjectStore *os = (ObjectStore *)malloc(sizeof(ObjectStore));
  if (!os) {
    return NULL;
  }

  os->count = 0;
  os->deleted_count = 0;
  memset(os->object_ptrs, 0, sizeof(os->object_ptrs));
  memset(os->event_handlers, 0,
         sizeof(os->event_handlers));
  memset(os->update_funcs, 0, sizeof(os->update_funcs));
  memset(os->render_funcs, 0, sizeof(os->render_funcs));
  memset(os->reusable_ids, 0, sizeof(os->reusable_ids));

  return os;
}

create_object_store attempts to dynamically allocate memory for an instance of ObjectStore. If the allocation fails, it just returns NULL. Otherwise, it initialises all the members of the struct to 0 and returns the pointer.

void destroy_object_store(ObjectStore **os) {
  if (!(*os)) {
    return;
  }

  memset((*os)->object_ptrs, 0, sizeof((*os)->object_ptrs));
  memset((*os)->event_handlers, 0,
         sizeof((*os)->event_handlers));
  memset((*os)->update_funcs, 0, sizeof((*os)->update_funcs));
  memset((*os)->render_funcs, 0, sizeof((*os)->render_funcs));
  memset((*os)->reusable_ids, 0, sizeof((*os)->reusable_ids));

  (*os)->count = 0;
  (*os)->deleted_count = 0;

  free(*os);
  *os = NULL;
}

destroy_object_store performs the opposite operation. It clears all variables, frees the memory that was allocated by create_object_store and sets the pointer to NULL to make sure that it can’t be used after the memory is freed.

The handle_all_objects_events, update_all_objects, and render_all_objects functions are very simple. They just loop over the added objects, and run their respective functions if they exist.

void handle_all_objects_events(ObjectStore *os,
                               const SDL_Event *event) {
  if (!os || os->count == 0) {
    return;
  }

  for (int i = 0; i < os->count; ++i) {
    if (os->event_handlers[i]) {
      void *object = os->object_ptrs[i];
      (os->event_handlers[i])(object, event);
    }
  }
}

void update_all_objects(ObjectStore *os, float delta) {
  if (!os || os->count == 0) {
    return;
  }

  for (int i = 0; i < os->count; ++i) {
    if (os->update_funcs[i]) {
      void *object = os->object_ptrs[i];
      (os->update_funcs[i])(object, delta);
    }
  }
}

void render_all_objects(ObjectStore *os) {
  if (!os || os->count == 0) {
    return;
  }

  for (int i = 0; i < os->count; ++i) {
    if (os->render_funcs[i]) {
      void *object = os->object_ptrs[i];
      (os->render_funcs[i])(object);
    }
  }
}

Adding an object

The most interesting part of the ObjectStore is the function that adds an object.

#define INVALID_ID -1 // Defined in reusable_ids.h

int32_t reuse_id(int32_t *ids, uint64_t count) {
  int32_t id = ids[0];

  for (size_t i = 0; i < count; ++i) {
    // Remove the first id and make sure
    // the remaining ones are packed
    ids[i] = ids[i + 1];
  }

  ids[count - 1] = INVALID_ID;

  return id;
}

ObjectID add_object_to_store(ObjectStore *os, void *object,
                             EventHandlerPtr eh,
                             UpdateFuncPtr uf,
                             RenderFuncPtr rf) {
  // If all function pointers are NULL, no point of
  // adding the object to the store
  bool no_funcs_passed = !eh && !uf && !rf;

  if (!os || !object || object_exists(os, object) ||
      no_funcs_passed ||
      (os->count + 1 == MAX_OBJ_COUNT &&
       os->deleted_count == 0)) {
    return INVALID_ID;
  }

  ObjectID id;

  if (os->deleted_count > 0) {
    id = (ObjectID)reuse_id(
            (int32_t *)os->reusable_ids,
            os->deleted_count
         );
    
    os->deleted_count -= 1;

    if (id == os->count) {
      os->count += 1;
    }
  } else {
    id = (os->count)++;
  }

  os->object_ptrs[id] = object;
  os->event_handlers[id] = eh;
  os->update_funcs[id] = uf;
  os->render_funcs[id] = rf;

  return id;
}

As you can see, the add_object_to_store function performs some checks first to see if adding the object would be possible. If these checks fail, then it returns an INVALID_ID. Otherwise, it checks to see whether there are IDs that were previously freed or not.

If there are no available IDs in the resuable_ids array, it just uses the count as the new ID and increments the count of objects in the store.

However, if there are IDs that can be resued, then the add_object_to_store function relies on the reuse_id function, which takes the reusable_ids array, pops the first element and moves any remaining IDs to the previous index in the array. You can think of the reusable_ids array as more of a queue which uses the FIFO method.

The function then decrements the deleted_count, but it only increments the count if the ID equals count. I will explain the reason after discussing the function that removes an object from the store.

Deleting an object

void remove_object_from_store(ObjectStore *os, ObjectID *id_ptr) {
  ObjectID id = *id_ptr;

  if (!os || os->count == 0 || id == INVALID_ID ||
      !(os->object_ptrs[id])) {
    return;
  }

  *id_ptr = INVALID_ID;

  os->object_ptrs[id] = NULL;
  os->event_handlers[id] = NULL;
  os->update_funcs[id] = NULL;
  os->render_funcs[id] = NULL;

  os->reusable_ids[(os->deleted_count)++] = id;

  if (id == (os->count - 1)) {
    // Only decrement the count if the last object is deleted.
    // Otherwise, the count shouldn't be decremented since the
    // deleted object would be in the middle, which means that
    // the functions that loop over all objects in the store
    // will not actually loop over all active objects

    uint64_t new_count = 0;

    // Figure out how much we need to decrement the count.
    // Since, a lot of objects may have been removed, the
    // count should equal the last active object.
    for (size_t i = id - 1; i >= 0; --i) {
      if (os->object_ptrs[i]) {
        new_count = i + 1;
        break;
      }
    }

    os->count = new_count;
  }
}

As you can see, the remove_object_from_store function is a lot simpler. Once it validates the arguments passed to it, it sets the ID to INVALID_ID, removes the object and all its functions and adds the ID to the reusable_ids array. It then does something similar to what we saw with the add_object_to_store function, where it only decrements the count if the object being removed has an ID that is equal to count - 1.

However, it doesn’t just decrement by 1. It goes backward checking the store to find the last active object and then uses its index to set the current count.

Example to explain the logic of adding and removing objects

Imagine that you have added 3 objects to the store and haven’t deleted any of them yet.

/*
The ObjectStore will look something like this
 -----------
| x | x | x |
 -----------

count => 3

deleted_count => 0
*/

If you then, decide to remove the second object, the ObjectStore will look something like this:

/*
 -----------
| x |   | x |
 -----------
*/

You now have a gap in the middle. If the count were to be decremented at this point, then the last object in the store will be ignored. Therefore, in this instance, the count will remain 3 and only the deleted_count will be incremented to 1.

If you try to add a new object now, this object will occupy the slot that is already free. This is why, in this case, the add_object_to_store function will not increment the count.

However, if you remove the third object immediately after removing the second object, the number of active objects in the store is now only 1. However, the count will still be equal to 3. This means that, if the count is only decremented by 1, you will be looping over an inactive object. This is why the remove_object_from_store function performs this loop:

void remove_object_from_store(ObjectStore *os, ObjectID *id_ptr) {
  /* ... */
  /* Rest of the function removed for brevity */

  if (id == (os->count - 1)) {
    uint64_t new_count = 0;

    for (size_t i = id - 1; i >= 0; --i) {
      if (os->object_ptrs[i]) {
        new_count = i + 1;
        break;
      }
    }

    os->count = new_count;
  }
}

And this is basically it. This is the complete implementation of the ObjectStore that I use for my game. In the next installment of this series, I will discuss how I implemented the AssetManager which handles loading assets such as images, audio files and fonts.