Nomad Game Engine: Part 4.1 — Generic Component Managers
Finally some implementation details!
This post is part of a series where I’m documenting my experience building an ECS game engine from scratch. Check out the homepage for this project for more posts, information, and source code.
This blog post is going to begin to tackle the the “Component Manager” both from a conceptual standpoint as well as a programming standpoint. This will be a 3-part blog post because there is a lot to cover as currently this is one of the more technically complex parts of the game engine. For the first post, we’re going to go over the implementation of the basic component manager, holding an array of generic components tightly packed within its memory. I’m going to do my best to explain my thinking behind each design decision, but if any of it doesn’t make sense please feel free to shoot me a message or leave a comment on this post, I’d be happy to clarify.
What is the Component Manager?
While my previous posts cover the need for a component manager, here’s a quick refresher on the purpose of the component manager:
A component can be attached to an entity to give it certain attributes. Instead of holding all of an entity’s components with the entity, it is more cache efficient to hold all components of a given type in the same place. In this way, when we run update methods on all components of a type, they are all held in contiguous memory.
What does the “generic” part mean and why do we need it?
The concept is pretty simple. Held within each component manager is an array of data that holds a bunch of structs (the components). Since it’s obvious that all of the component managers are going to do essentially the same thing, it follows naturally that we should be trying to write one set of code that will correctly handle all components. By creating this generic component manager, we can also do some really neat things, such as creating a generic “add component to entity” method that will be able to figure out which component manager needs to be called. All of these advantages are given to use through the power of C++ templates.
What does a component manager need to be able to do?
1. Add a component
2. Access a component from a specific entity
3. Remove a component from an entity
4. Iterate over all items
Let’s think for a second about what kind of data structures we would need to provide this functionality. The two requirements that point us to our storage choice are #2 and #4. Accessing a component given an entity ID screams hash map, where we have the entity ID point to the actual data for O(1) access. #4 provides us with the extra requirement of storing the data contiguously in a relatively opaque manner.
Our data structures will be a hash map on top (entityMap in the picture above), with an underlying array of data that can be iterated through (componentData). Now that we’ve figured that out, let’s take a look at what the outline for our new “generic component manager” might look like:
(if you’re viewing this on the iOS medium app, this will show up as a link. Open the blog post in safari to see the gists inline)
Notice that we’ve added this concept of a “ComponentInstance” — essentially just an int that denotes an index in the data array. Adding this gives us a bit more clarity and stops us from wondering “what does this unsigned int mean?”.
Contiguous array of data
The main reason we’re implementing a component manager is so that we can store our data in a contiguous array of data. Processors are great at iterating over fixed arrays of data, so putting all our data together means big performance increases on CPU-intensive game components. One important thing to add is that we’re going to pre-allocate this data. This means that this contiguous array won’t change size throughout the games running (as changing size would be an expensive operation that would involve copying a ton of data), so if we initialize the array with 1024 spots, it will remain at 1024. This means that we will also need to keep track of the “current size” of the array, since we can’t just poll array->size().
To accomplish this we’re going to wrap our array in a struct to make it a bit easier to read:
If we’re initializing the array with no components in it, why did we start the size at 1? This is a pretty sneaky trick that will allow us for much more robust error catching later on. By setting the size to 1, we know that any code that tries to access ComponentInstance = 0 probably has an issue, and we can catch it early on. If we didn’t have this check, we would accidentally be returning whatever component was stored there, making for a much more confusing bug to catch. In this way, index 0 becomes the equivalent of index -1 (if we were using ints instead of unsigned ints) — if we’re trying to access it or return it, something probably doesn’t exist or went wrong.
Side note: I’m actually considering switching over to ints from unsigned ints just so I’m using the same type all over and I can squelch compiler warnings without having to cast everything. For now I’ll leave the code in this post how it is to illustrate my points though.
You’ll notice that we’re using std::array instead of std::vector or std::list. Why is that?
Why aren’t we using std::vector?
Because we have a map on top of the array (referencing indices in the array), we need the map to remain mostly valid through a removal from the array. If we use std::vector and then need to remove our first component (vec.erase(vec.begin())), all our indices shift (vec becomes vec, etc.). This invalidates our entire map and would require a full update of the map.
Why aren’t we using std::list?
std::list is a linked list, and doesn’t really fit our requirements due to both how deletions work (similar to std::vector), and it’s not built for random access by index.
Thus, we end up with wanting C-style arrays, and std::array gives us that with a bit of syntactical sugar and bounds checking (via .at()). There isn’t really a performance difference between std::array and the regular C-style arrays, so there’s no harm in getting a bit of extra safety by using std::array.
My ignorance with C++ (this is my first real project in it) might be showing here, so if there’s a better way to do this, let me know in the comments :)
Adding a component
When adding a component, we just need to make sure that both of our data structures are correctly updated. We need to add the component to the end of our list, as well as adding a mapping from the Entity to the index in the list. That looks something like this:
Accessing a component
Since a lot of our design revolves around this, it should be pretty self evident how this works. To access a component from an entity, we first look up the entity in the hash map to find where in the array the component is held. Once we have the index, we simply return the component at that index in the array.
Removing a component
Removing a component might sound simple, but the implementation is more complex than just array.erase(). We have to remember we’re dealing with a static array and not a vector. Were we to simply erase indices from the array whenever they were removed, we would end up with holes as the engine ran and items were deleted. This not only ruins our idea of a “tightly packed array”, but will also eventually overflow our array and leave us in the dirt.
So how do we solve this? Well, whenever we remove an item, we simply take the last item in the list and move it to fill the space. In this way, we’re guaranteed to always have tightly packed data, at the cost of the slight overhead of copying a component and updating its index in the hashmap.
Here’s what that will look like:
And here’s the code to implement it:
Note that we don’t actually need to “clear out” the now replicated component at componentData[componentData.size - 1], since it will be overwritten by the next component to be added.
Also note that we’ve got this method
getEntityByComponentInstance. This is a necessity of this design — effectively we want a bidirectional map that allows us to query componentinstance by entity and entity by componentinstance. An example implementation can be found here.
Iterate over all items
Our final requirement is actually one that I added recently. For the most part, components interact with other components through systems, and we can therefore not just iterate over every component of a type willy nilly. For example, a HealthComponent might only decrease if the player is standing in an entity with the PoisonCloud component on it — we can’t just run over every HealthComponent and decrease it without also making sure that the Entity owning that HealthComponent is also standing in an Entity with a PoisonCloud component.
For this reason, most use cases don’t actually have the need to iterate over all items in order. Most use cases will simply make use of the component access method and call it a day. However, there are some components that have functionality that is relatively self contained. For example, the Motion component needs to update its position and velocity every tick, looking something like this:
component.position += component.velocity;
component.velocity += component.acceleration;
In this case, our functionality is very self contained — a Motion component only needs to access itself to update properly. This is going to happen every tick to every single Motion component, so this is code that will be run quite a bit. For uses like this, we provide a simple lambda function that allows for a method to be run on every component of a type, in order. Here’s what it looks like:
So to do what we have written above, we’d simply need to call:
c.position += c.velocity;
c.velocity += c.acceleration;
So now we’ve got a fully functional component manager. Not so bad, right? Well unfortunately, this is just the beginning. If you think this is over-optimized, just wait until you see the next two posts…
I’ve been in the midst of switching co-op jobs (I might make a post soon about how this process has gone for me) and been very busy and haven’t had much time to work on the game engine, but here’s a sneak preview of a more “game” looking demo that I’m calling “diablo” — essentially a hack n’ slash game where monsters spawn and you have to kill them as they run at you.
We have recently started to look into adding an entity/component system to the Bitsquid engine. You may be surprised to…bitsquid.blogspot.com