Data Structures
Introduction
This page contains highlights of some data structures that I've implemented that has seen extended usage due to their many useful applications. They have been used in, for example, optimized scene culling with octree, cache-based component system with free vector, and more. All the highlighted data structures here were implemented and applied in our own custom game engine R.O.S.E. developed at The Game Assembly.
​
You can check out other utilities I've made here:
https://github.com/Daikalos/CommonUtilities/tree/main/CommonUtilities
​
I've uploaded a PDF file for each structure for those that are interested in how exactly they work.
Free Vector
FreeVector is, as the name implies, just a plain standard vector container, but with modified functionality to handle fast insertion and removal. The idea is to keep track of the latest available position in the vector that can be safely overwritten, and fill that slot whenever a new element is inserted. This is done by each element also being able to track the previously available slot, and using that data to know which element is free. This structure is extremely useful for improving cache efficiency while also having O(1) insertion and removal. It also means that an element's position will always remain the same and won't get shifted around which makes indexing safe. The downside is that it is harder to iterate through the FreeVector, and if the FreeVector is managed poorly with many gaps in the structure, the spatial locality is hurt and therefore not as benifical.
​
Static Vector
StaticVector is quite simple, it provides the interface of the standard vector, while being much faster due to simply not having to allocate memory on the heap. The drawback is that the capacity of the structure must be explicitly set by the user, and if the capacity is reached, no further elements can be added. The StaticVector is different from a normal array because it is instead an array of bytes, and elements are constructed onto the array via placement new.
​​
Octree
The Octree is a structure used for accelerating lookups in the world, where each node has at most 8 children. The highlight of the implementation is that it focuses on improving cache locality by utilizing FreeVector as much as possible to store and iterate through its nodes and inserted elements.
​
Blackboard
Blackboard is a structure that has a familiar syntax with unordered map, but with the greatly added benefit of being able to store any kind of value in it. This enables for it to be commonly used wherever data dependencies are complex or difficult to express between different objects, e.g., behavior tree.
​
Event
Event enables for registering multiple function callbacks that can later be called all at once. This structure has been widely used for event-driven programming to loosen dependencies between objects. For example, if a particular enemy wishes to react to the player's death, all they have to do is retrieve the player and register their own callback for that event, which the player then calls internally when they die (instead of the enemy listening every frame).
To make sure that events does not leak, for example, so that the callback the enemy registered is automatically removed when the enemy is destroyed, I created the EventID class which removes the callback when the destructor is called. The reverse scenario is also handled where the event may have been destructed but not the EventID, this is solved by the EventID being able to check the lifetime of the Event through a simple void weak_ptr.
​​