Game Dev Log: Figuring out how to store objects in memory

There are varying degrees of processing that need to take place for objects within a level. For collision checks, if two objects have hit boxes that are axis-aligned then the trivial "axis-aligned bounding box" (AABB) routine would be sufficient. Otherwise, more computationally expensive routines, such as use of the "separating axis theorem", would instead be required. If there are many objects that are axis misaligned then needless consumption of frame budget would ensue by performing this kind of routine against distant objects or for objects that are far removed from the view port. In game development, limiting expensive processing to only the necessary objects can be achieved through the organisation of objects into "quadrants" where membership is determined by an object's coordinates in Cartesian space.

My game is a 2D side scrolling "auto runner". Unlike a game with a bird's eye view perspective, where a two dimensional grid of quadrants could be assumed, the quadrants can be set instead in a one dimensional arrangement; in other words, a quadrant is only anticipated to be beside another and never above or below. An object's quadrant membership could then be determined solely by it's x position, and the data structure that holds ownership of objects can be ordered based on ascending x positions. The data structure can then be segmented in a manner where the concept of quadrants emerges; the first five elements would comprise the first quadrant, the next five for the second, and so on. Since objects can move within a level, they can relocate to adjacent quadrants. This would require that the data structure be sorted per frame to ensure correct ordering prior to commencement of game logic routines.

To represent game objects, the architecture takes the object oriented approach of deriving concrete object types from an abstract interface; we shall call this interface ObjectBase. The object data structure holds pointers of type ObjectBase that refer to dynamically allocated concrete object instances, achieving runtime polymorphism. When writing C++ code, and if I'm not using my brain well enough ahead of time, I turn to std::vector as a catch-all container type until it is no longer sufficient, in this case the data structure initially being std::vector<ObjectBase*>. std::vector is C++'s standard library implementation of a dynamically resizable array where the stored elements are arranged contiguously in memory, that is, beside one another in the correct order and without gaps. The typical implementation of std::vector is a "raw" dynamically allocated array that may reallocated if the capacity of previously allocated memory has been exhausted. Despite reallocation, the contiguous contract of the data structure is beneficial for cache utilisation and we would enjoy an increased likelihood that the next object is already awaiting us in cache! Otherwise a cache miss would be encountered and an expensive round trip to main memory would then be required to obtain the next object.

std::list is C++'s standard library implementation of a doubly linked list. A linked list is a more flexible tool for managing its stored elements: reordering, removal and insertion of elements within arbitrary offsets is of constant complexity. A compelling cost for this flexibility is the loss in contract of contiguous memory, objects can be stored in disparate locations, and the runtime will be faced with an inevitable increase in cache misses upon traversal of the data structure.

A general rule of thumb when deciding between this fundamental trade off between an array and a linked list is to understand how the data structure is interacted with; this is the ratio of traversals over manipulations, or in other words, the dichotomy between iterating over the data structure and its manipulation. With the current state of things, the use of std::list<ObjectBase*> is an even more difficult proposition since two layers of indirection are required for accessing each object, firstly with accessing the underlying "node" of the list that stores the ObjectBase pointer, an the second being the dereferencing of the ObjectBase pointer itself. A very bad time for cache utilisation indeed! Using std::vector<ObjectBase*> removes a layer of indirection, and my thought at the time was that we would lose the flexibility of std::list, but during the write up of this post, I came realised that this was not the case.

Since pointers are stored in std::vector rather than the object instances themselves, reordering is as simple as swapping pointers around rather than relocating objects in memory. Furthermore, removal of objects from the play field does not necessitate the removal of objects in memory; the objects can simply be "disabled" and then "re-enabled" with their initial values should the player need to backtrack to an earlier location or even the beginning of the level. Insertion of new objects could result in reallocation which would involve an increase in complexity over the insertion of objects within std::list. I deem this cost to be acceptable, since we have established that only pointers will be copied, more specifically moved in the case of std::unique_ptr, and not their dereferenced contents. Furthermore, since the objects themselves are not relocated in memory, the pointers remain valid, thus avoiding the "dangling pointer problem". Although we generally avoid holding references of objects through pointers or C++ references and instead prefer to hold references to objects via. a unique identifier.

An avoidable shortcoming, that applies to both data structures, is the inefficiency of loading an entire object into cache just to query whether it is enabled or not. Since we are considering the prospect of keeping objects around in memory, we may perform a round trip to main memory just to obtain an object that is disabled and requires no further processing. This is an avoidable overhead during iteration of even a subset of the data structure. A workaround would be for the data structure to store "object entries" rather than ObjectBase pointers. An object entry might look something like this.

class ObjectEntryType
{
public:
  // Create an object with an upfront instance of std::unique_ptr<Object>
  ObjectEntryType(std::unique_ptr<ObjectBase> objectPtr);

public:
  // Enable object entry so that it is accounted for in game logic and rendering.
  void Enable();
  // Disable object entry so that it is ignored during game logic and rendering.
  void Disable();
  // I cannot bring myself to overload "operator bool" so you get this.
  bool IsEnabled() const;

public:
  // Pointer dereferencing semantics.
  const Object& operator*() const;
  const Object* operator->() const;
  Object& operator*();
  Object* operator->();

  // Access to the raw pointer so you can subvert the encapsulations if you dare. ;)
  const Object* GetPtr() const;
  Object* GetPtr();

private:
  bool m_Enabled;
  std::unique_ptr<Base> m_ObjectPtr;
};

So instead of having something like this, where each object needs to be cached to determine if it is currently enabled.

using ObjectArrayType = std::vector<std::unique_ptr<ObjectBase>>;
ObjectArrayType ObjectArray;

for (auto& objectPtr : ObjectArray)
{
  if (objectPtr->IsEnabled())
  {
  }
  else
  {
    // had to load an entire object for almost nothing! D:
  }
}

We would have something like this, including an almost identical calling convention which is great for managing what is becoming a medium sized code base. Hooray for encapsulation!

using ObjectArrayType = std::vector<ObjectEntryType>;
ObjectArrayType ObjectArray;

for (auto& objectEntry : ObjectArray)
{
  if (objectEntry.IsEnabled())
  {
    // do stuff with underlying object
  }
  else
  {
    // no need to dereference pointer in object entry
    // and needlessly need to cache and object.
  }
}

Moving forward, I have decided to proceed with using a std::vector instance for holding object entries as described. All of the above optimisations was not based on any measured observation or immediate necessity. It was a mixture of intuition and wanting to have fun with engine development, let's see in the future if it was right act on these impulses. :P