Custom ECS Storage

Wed Jan 8, 2020

Let's start with a super quick rundown of ECS (or Entity-Component-System) so that we are all speaking the same language. In ECS, you have a set of entities that have components attached to them to define their characteristics, which are then operated on by various systems.

In my mind, I tend to think of an entity as a noun -- it's a thing. And the components are like the adjectives describing it. So as a rough example, let's say that we have a ball entity. We may describe that ball as having a colour. So we attach a colour component to it. It may also be bouncy, so we also add a bouncy component. In code, those components store the data for us, so the colour may contain RED, and the bouncy component may contain a restition (bounciness) value of 0.5. Note that this is a poor example, but hopefully it makes it easy enough to understand.

The typical simple ECS implementation might have all components stored in a large array with booleans to denote the "has" part. As in the entity has that particular component attached. And the entities are simply integer indexes into those arrays.

That works really well for components that are attached to almost all entities. Like if you had a position or transform component, for example. But it wastes a lot of space for components that are only attached to a small handful of entities. Like if only one entity ever has a special component denoting it as The Player.

This is where some of the tricks of building a fast ECS framework comes in: not all components need to be allocated for all entities if they aren't using them. Less components means fewer loop iterations. Less memory means fewer cache misses.

Let's decide on a couple of container styles for our components.

First there's the format we already have, where there's a component for all entities. This is good for components that exist on most entities. Position for example. I've been referring to this one as Dense.

Second, we will want a container for components where only a few exist. This will be our Sparse container. This is implemented as two arrays, one containing the entity in a particular slot in the smaller array, rather than just using the entity integer as an array index directly. We will keep the small entity array sorted, to keep iteration order consistant with the dense container.

Third, we will have a special case for components that don't store any data. This is our Empty container. This only exists due to a quirk of C++, where every struct needs to be uniquely addressable, and therefore takes up 1 byte, even if it doesn't have any member fields. Don't believe me, try running the following for yourself.

struct Test {};
std::cout << sizeof(Test); // outputs 1

Lastly, we will add a generic, sort of reasonable medium if we aren't sure if we can make assumptions about the usage of the component. I've referred to this container as Unordered as the implementation of this is to use a hash map to map the entity to the component, and by using a hash map, we cannot make any guarantees of the iteration order.

So that is the basis for my goal API. Do be aware that there are many ECS frameworks where you don't have to specify the components upfront. Also note that actually having to specify the storage strategy for individuals components seems to be exceedingly rare. But Sometimes I Know Better™. Sometimes. Rarely. But in those moments, it's worth it. Right?

using MyRegistry = Registry<1024, Dense<Position>, Sparse<4, Player>, Empty<Gravity>>;
Registry registry;
Entity entity = registry.create();
Position& position = registry.add<Position>(entity);
Player& player = registry.add<Player>(entity);