What is the most efficient container to store dynamic game objects in? [closed]

Question

I am making a first person shooter and I know about about a lot of different container types but I would like to find the container that is the most efficient for storing dynamic objects that will be added and deleted from the game quite frequently. EX-Bullets.

I think in that case it would be a list so that the memory is not contiguous and there is never any re sizing that is going on. But then I am also contemplating using a map or set. If anyone has any helpful information I would appreciate it.

I am writing this in c++ by the way.

Also I came up with a solution that I think will work.

To start off I am going to allocate a vector of a big size.. say 1000 objects. I am going to keep track of the last added index in this vector so that I know where the end of the objects are. Then I will also create a queue that will hold the indices of all objects that are "deleted" from the vector. (No actual deleting will be done, I will just know that that slot it free). So if the queue is empty I will add to the last added index in the vector + 1, else I add to the index of the vector that was at the front of the queue.

Answer 1

The answer is always to use an array or std::vector. Types like a linked list or a std::map are usually absolutely horrendous in games, and that definitely includes cases like collections of game objects.

You should store the objects themselves (not pointers to them) in the array/vector.

You want contiguous memory. You really really want it. Iterating over any data in non-contiguous memory imposes a lot of cache misses in general and removes the ability for the compiler and CPU to do effective cache prefetching. This alone can kill performance.

You also want to avoid memory allocations and deallocations. They are very slow, even with a fast memory allocator. I've seen games get a 10x FPS bump by just removing a few hundred memory allocations each frame. Doesn't seem like it should be that bad, but it can be.

Lastly, most data structures that you care about for managing game objects can be far more efficiently implemeted on an array or a vector than they can with a tree or a list.

For instance, for removing game objects, you can use swap-and-pop. Easily implemented with something like:

std::swap(objects[index], objects.back());
objects.pop_back();

You could also just mark objects as deleted and put their index on a free list for the next time you need to create a new object, but doing the swap-and-pop is better. It lets you do a simple for loop over all live objects with no branching aside from the loop itself. For bullet physics integration and the like, this can be a significant performance boost.

More importantly, you can find objects with a simple pair of table lookups from a stable unique is using the slot map structure.

Your game objects have an index in their main array. They can be very efficiently looked up with just this index (much faster than a map or even a hash table). However, the index is not stable due to the swap and pop when removing objects.

A slot map requires two layers of indirection, but both are simple array lookups with constant indices. They are fast. Really fast.

The basic idea is that you have three arrays: your main object list, your indirection list, and a free list for the indirection list. Your main object list contains your actual objects, where each object knows its own unique ID. The unique ID is composed of an index and a version tag. The indirection list is simply an array of indices to the main object list. The free list is a stack of indices into the indirection list.

When you create an object in the main list, you find an unused entry in the indirection list (using the free list). The entry in the indirection list points to an unused entry in the main list. You initialize your object in that location, and set its unique ID to the index of the indirection list entry you chose and the existing version tag in the main list element, plus one.

When you destroy an object, you do the swap-and-pop as normal, but you also increment the version number. You then also add the indirection list index (part of the object's unique ID) to the free list. When moving an object as part of the swap-and-pop, you also update its entry in the indirection list to its new location.

Example pseudo-code:

Object:
  int index
  int version
  other data

SlotMap:
  Object objects[]
  int slots[]
  int freelist[]
  int count

  Get(id):
    index = indirection[id.index]
    if objects[index].version = id.version:
      return &objects[index]
    else:
      return null

  CreateObject():
    index = freelist.pop()

    objects[count].index = id
    objects[count].version += 1

    indirection[index] = count

    Object* object = &objects[count].object
    object.initialize()

    count += 1

    return object

  Remove(id):
    index = indirection[id.index]
    if objects[index].version = id.version:
      objects[index].version += 1
      objects[count - 1].version += 1

      swap(objects[index].data, objects[count - 1].data)

The indirection layer allows you to have a stable identifier (the index into the indirection layer, where entries do not move) for a resource that can move during compaction (the main object list).

The version tag allows you to store an ID to an object that might be deleted. For example, you have the id (10,1). The object with index 10 is deleted (say, your bullet hits an object and is destroyed). The object in that location of memory in the main object list then has its version number bumped, giving it (10,2). If you try to look up (10,1) again from a stale ID, the lookup returns that object through index 10, but can see that the version number has changed, so the ID is no longer valid.

This is the absolute fastest data structure you can have with a stable ID that allows objects to move in memory, which is important for data locality and cache coherence. This is faster than any implementation of a hash table possible; a hash table at the very least needs to calculate a hash (more instructions than a table lookup) and then has to follow the hash chain (either a linked list in the horrible case of std::unordered_map, or an open-addressed list in any not-stupid implementation of a hash table), and then has to do a value compare on each key (no more expensive, but possible less expensive, than the version tag check). A very good hash table (not the one in any implementation of the STL, as the STL mandates a hash table that optimizes for different use cases than you game about for a game object list) might save on one indirection, but wil be a larger bloated structure that you can't iterate over at maximum efficiency, and loses out in real-world performance for use cases like this one.

There are various improvements you can make to the base algorithm. Using something like a std::deque for the main object list, for instance; one extra layer of indirection, but allows objects to be inserted into a full list without invalidating any temporary pointers you've acquired from the slotmap.

You can also avoid storing the index inside the object, as the index can be calculated from the object's memory address (this - objects), and even better is only needed when removing the object in which case you already have the object's id (and hence index) as a parameter.

Apologies for the write-up; I don't feel it's the clearest description it could be. It's late and it's difficult to explain without spending more time than I have on code samples.

Answer 2

fixed size array (linear memory)
with internal free list (O(1) alloc/free, stable indicies)
with weak reference keys (reuse of slot invalidates key)
zero overhead dereferences (when known-valid)

struct DataArray<T>
{
  void Init(int count); // allocs items (max 64k), then Clear()
  void Dispose();       // frees items
  void Clear();         // resets data members, (runs destructors* on outstanding items, *optional)

  T &Alloc();           // alloc (memclear* and/or construct*, *optional) an item from freeList or items[maxUsed++], sets id to (nextKey++ << 16) | index
  void Free(T &);       // puts entry on free list (uses id to store next)

  int GetID(T &);       // accessor to the id part if Item

  T &Get(id)            // return item[id & 0xFFFF]; 
  T *TryToGet(id);      // validates id, then returns item, returns null if invalid.  for cases like AI references and others where 'the thing might have been deleted out from under me'

  bool Next(T *&);      // return next item where id & 0xFFFF0000 != 0 (ie items not on free list)

  struct Item {
    T item;
    int id;             // (key << 16 | index) for alloced entries, (0 | nextFreeIndex) for free list entries
  };

  Item *items;
  int maxSize;          // total size
  int maxUsed;          // highest index ever alloced
  int count;            // num alloced items
  int nextKey;          // [1..2^16] (don't let == 0)
  int freeHead;         // index of first free entry
};

Handles everything from bullets to monsters to textures to particles, etc. This is the best data structure for video games. I think it came from Bungie (back in the marathon/myth days), I learned about it at Blizzard, and I think it was in a game programming gems back in the day. It's probably all over the games industry at this point.

Q: "Why not use a dynamic array?" A: Dynamic arrays cause crashes. Simple example:

foreach(Foo *foo in array)
  if (ShouldSpawnBaby(*foo))
    Foo &baby = array.Alloc();
    foo->numBabies++; // crash!

You can imagine cases with more complication (like deep callstacks). This is true for all array like containers. When making games, we have enough understanding of our problem to force sizes and budgets on everything in exchange for performance.

And I can't say it enough: Really, this is the best thing ever. (If you don't agree, post your better solution! Caveat - must address the issues listed at the top of this post: linear memory/iteration, O(1) alloc/free, stable indices, weak references, zero overhead derefs or have an amazing reason why you don't need one of those ;)

Answer 3

There is no right answer to this. It all depends on the implementation of your algorithms. Just go with one you think is best. Don't try to optimize at this early stage.

If you are often deleting objects and recreate them, I suggest you look at how object-pools are implemented.

Edit: Why complicate things with slots and what not. Why not just use a stack and pop the last item off and reuse it? So when you add one, you will do ++, when you pop one you do -- to keep track of your end index.

Answer 4

It depends on your game. The containers are different in how fast the access to a specific element is, how quickly a element is removed and how quickly a element is added.

---

• std::vector - Fast access and removing and adding to the end is fast. Removing from the beginning and the middle is slow.
• std::list - Iterating over the list is not much slower than a vector but accessing a specific point of the list is slow (because iterating is basically the only thing you can do with a list). Adding and Removing items anywhere is fast. Most memory overhead. Non-continous.
• std::deque - Fast access and removing/adding to the end and beginning is fast but slow in the middle.

---

Usually you want to use a list if you want your object list sorted in a different way than chronocially and thus have to insert new objects rather then append, a deque otherwise. A deque has increased flexiblity over a vector but doesn't really have much of a downside.

If you have really a lot entities you should take a look at Space Partitioning.