Doing a lot with a little: ECS identifiers

Image for post
Image for post

Disclaimer: I am the author of Flecs, an Entity Component System for C99. Discord: https://discord.gg/ZSSyqty

If you are writing your own ECS framework (or are about to), there is a good chance you are designing your entities as unique integer values. One of the simplest ways of implementing an ECS is to create an array for each component, and to use the entity identifier as index in each of these arrays (often combined with a bitset to test if the entity has the component). Other, more sophisticated approaches exist that also rely on plain integers, such as archetype- and sparse set based implementations.

Using a simple integer to identify your entities sounds simple enough. Yet they can be used to enable many advanced features, at very low cost. In this blog I’ll go over the tricks I used in Flecs to make the most out of my identifiers.

First, let’s start with:

If you saw any of my previous posts, you have probably read this a dozen times, but it is worth repeating, as much of what comes next depends on this simple rule.

An ECS framework needs not only a way to identify entities, but also to identify components. ECS frameworks (at least generic ones) cannot know at compile time which component types an application will use, and since they cannot rely on facilities of the programming language, they need their own mechanism to uniquely identify components. The most straight forward way to do this is is to generate a unique integer identifier per component id.

Whenever we want to add a component to an entity, we provide this unique identifier to an “add” operation, either directly or with the help of some meta-programming. Everything an entity “has” can then simply be described by a vector of integers. For example, if component Position has id 1, and component Velocity has id 2, the contents of an entity that has both components could simply be described with this vector:

[1, 2]

But why stop there? Why should an entity only be allowed to contain components? Indeed, many ECS frameworks support the notion of a “tag”. which is a component that is not associated with a datatype. A tag is nothing more than a simple unique identifier. We could have a tag called “Enemy” with id 3, and add it to our entity. The vector would now look like this:

[1, 2, 3]

We have to store somewhere what these identifiers mean, as we obviously do not just want to store what the entity has, but also the actual component values. We need to be able to attach some data to each of these unique identifiers, so that we know that 1 belongs to a value of type Position, and 3 does not point to anything but 3. Lets design a few data structures for what we have so far, without paying too much attention to performance:

using ComponentId = uint64_t;
using ComponentSize = map<ComponentId, size_t>;
using EntityId = uint64_t;
using EntityType = vector<ComponentId>;
using EntityContents = map<EntityId, EntityType>;

We store the size of the component type in the ComponentSize map, which is really all an ECS framework needs to know. For a tag we can simply store size 0. This seems to satisfy our requirements, yet doesn’t spark joy. There is a fair amount of repetition in the design, for no good reason. Let’s revisit what we are actually trying to accomplish here:

“We need to be able to attach some data to each of these unique identifiers”

That should sound eerily similar to the definition of components (“some data”) and entities (“unique identifiers”). Can we store our components as entities? It turns out we can, and it makes the design a lot simpler:

using EntityId = uint64_t;
using EntityType = vector<EntityId>;
using EntityContents = map<EntityId, EntityType>;
struct Component {
size_t size;
};

The size of a component is now simply stored as a component called “Component” (read that sentence three times), and we use entity identifiers to identify our components. To register a new component with our framework, we simply do:

EntityId position = ecs::new();
position.set<Component>({.size = sizeof(Position)});

After that, we could add our position component to an entity like this:

EntityId e = ecs::new();
e.add(position);

In a real framework we probably want to provide convenience functions to wrap this code, but in essence this is what would need to happen.

But wait, there is more. If components use entity identifiers, does that mean that we can also add entities to entities? There is no reason we cannot:

EntityId a = ecs::new();
EntityId b = ecs::new();
a.add(b);

This is a capability we got entirely for free, and one that as it turns out is extremely useful for creating different kinds of relationships between entities.

So far we haven’t done anything to the entity identifier itself yet besides expanding the scope of their applicability. In the next section we’ll look at how we can annotate identifiers to allow for expressive entity relationships.

At this point you may wonder: why. Can’t we just use a dedicated structure for components, not worry about strange recursive definitions and be done with it? Is adding entities to entities really that useful? I would forgive you for thinking the answer is no, as I haven’t done a great job yet at explaining why this is useful. As it turns out, adding an entities to entities by itself is meaningless, just another id in the entity type vector.

But, what if we could add meaning? That is where type roles come in.

A type role allows us to specify which role an entity plays in a type. Type roles can be anything, but I found two particularly useful applications for them, which are hierarchies and instancing. What if I could express that an entity is a parent of another entity? That would make it possible to store hierarchies in ECS, which in many frameworks requires developers to bend over backwards to implement something that still does not perform.

Imagine we have an entity for which the type looks like this. I’ll be using names instead of integer identifiers, since it makes for an easier read:

[Position, Velocity, CHILDOF parent_entity]

Here, CHILDOF is a type role that tells the ECS framework that parent_entity is not just an identifier that is added to the entity, but that it should be interpreted as the parent of the entity.

“Wait”, I hear you say, “isn’t a type just a vector of integers? How can you store this extra information?”. We would not want to complicate the element type of our EntityType with fields that most of the time are not used! To solve this, we need to reserve a few of the bits of our identifier to store the type role.

We can defineCHILDOF as 1 << 63, or in plain English, assign it a value in which we only set a single bit to 1 (in this case, the MSB). Now we can simply annotate an entity identifier with this role by applying a bitwise OR:

e.add(CHILDOF | parent_entity);

This of course does not provide us with full support for hierarchies, as there needs to be some code or feature that interprets the CHILDOF flag. However, we did create a mechanism that allows us to store entity hierarchies in an extremely simple data structure, which is no small feat.

To get back our parent id, we could define a constant, lets call it ENTITY_MASK, which sets all bits to 1, except the ones that can be used for type roles. We could now write this (psuedo) code to find the parent of an entity:

e.type().each((e) => {
if (e & CHILDOF) {
print "parent = " + e & ENTITY_MASK;
}
});

We can have as many type roles as the number of bits (64) in an entity identifier allows us, though we of course want to reserve some space for the actual entity / component identifiers. Instead of using a single bit per type role, we could use more efficient approaches, such as reserving the most significant byte for type roles, which could give us 256 different roles.

A benefit of type roles is that instead of limiting the addressing space of all entities, they only limit the addressing space of entities we can add to other entities, which is a small price to pay for the features they enable. It also doesn’t seem overly constraining, given that this still leaves us with 2⁴⁸ possible component / entity identifiers.

A hard constraint in ECS frameworks is that you can add a component only once. Often this is not really a limitation, as there rarely is a reason to add a component multiple times: why would you want to have an entity with two Positions? Turns out that while this is not common, it is not unthinkable.

Systems in ECS work because components have meaning. Position is not just a vec3, it means something: it is the position of an entity in the world. Perhaps Velocity is also a vec3, but it is a different vec3, with a different meaning. This is why ordinarily, entities don’t have multiple instance of the same component, even though component types can be very similar.

Adding a component multiple times seems like it would violate this core principle. If I were to add Position to an entity two times, what should a system do with this? Are the two Positions equivalent? It gets confusing quickly, and that is why adding components multiple times in the general sense is probably a bad idea (though there is a case to be made for components with collections, but that’s a separate topic).

If this makes no sense, then why are we talking about it? Well, in some cases adding a component multiple times does make sense, as long as it is clear what the meaning of those components is. This is as abstract as it gets, so let’s use a concrete example.

Imagine a “HealthBuff” component that must be automatically removed from an entity after a certain amount of time has passed. An elegant solution to this would be to create a “HealthBuffExpiry” component, in which I store the expiry time, and the time passed since I added the buff. I then increase time passed each frame and when it exceeds expiry_time, I remove HealthBuff.

Now, I have to preface what comes next by saying that there are many ways to tackle this problem, and I am just using it as a way to illustrate traits.

The obvious next question for this approach is, “what if I want to add a “StaminaBuff” component? What if I want to add a “ManaBuff” component? Etcetera. The easiest solution would be to create as many “Expiry” components and “Expiry” systems, but I can guarantee you that you will feel dirty when coding this out. All Expiry components and systems will be exactly the same but for their name. Surely there must be a better way to do this…

What we really want to express here is that we want to remove a component, any component, after a certain amount of time has expired. It really doesn’t matter (or rather: shouldn’t matter) for the systems which component is to be removed. If only we could write a single Expiry component and system, that we could simply apply to any Buff component. That’s where traits come in.

The problem is obvious: if we attempt to add the Expiry component for both HealthBuff and StaminaBuff, the second add would overwrite the first. After all, we can only add a component once per entity, and thus this doesn’t work.

Instead, we need to be able to add Expiry for a component. That is what a trait is. Here, we would define Expiry as our trait that we can apply to any component we added to our entity. Because it is a trait (and because we make up the rules for it) we can add a trait as many times as we want, as long as it is applied to a different component each time.

Hold on, adding components to components? That sounds like it is going to complicate the ECS implementation by a lot, and that added complexity is probably not worth it, considering that this is a pretty niche use case.

I wouldn’t have gone through all this trouble if it were actually that complex.

The key thing to realize is that for an ECS, it really doesn’t matter if you add a type more than once. Most ECS frameworks apply type erasure which means that the framework only has very basic knowledge about your component types. Typically it won’t need to know more than just the size of a type.

The limitation of only being able to add a component, or type multiple times is therefore self-imposed. We enforce that an EntityType vector can only contain exactly one instance of each identifier. Otherwise, operations such as add, get and remove would always need a qualifier: which one? But, as with all self-imposed rules, we can relax them if we have good reason to do so.

“an EntityType vector can only contain exactly one instance of each identifier”

This is what prevents us from adding the Expiry component multiple times. But what if we could use a different identifier for the Expiry component? That would solve one problem, in that we can now add it multiple times. But it only creates a new problem, which is: how do we generate those new identifiers?

It turns out that the answer to this problem is more straightforward. If we want to be able to add a trait to a component, why don’t we combine the component identifier with the trait identifier to generate a new id? After all, we have a 64 bit addressing space. What if we reserve the first 32 bit for the component id, and the second 24 bit for the trait id (the remaining 8 bit is for type roles)? That still leaves us with 4 billion component ids and 16 million traits, which is more than the number of components in any project to date.

In code, we can now do something like this, which combines the component ids of HealthBuff and Expiry in one id:

EntityId trait = health_buf_id;
trait |= expiry_id << 32;

We now need to be able to tell the framework that this is in fact a trait, and not just a regular entity id. To do this, we introduce an additional TRAIT type role, so that we can do this:

EntityId e = ecs::new();
e.add(TRAIT | trait);

When the framework encounters the TRAIT type role, it will know to split up the identifier into the trait id and component id. When matching systems with traits, we can do the same trick, where a system that matches with Expiry is invoked for each instance of Expiry on the entity (the exact implementation of this is interesting, but out of scope for this blog).

What’s best about this, is that we barely changed anything in our ECS framework. We still store entities with components, where a component is a unique identifier. It just so happens now that some of those unique identifiers point to the same type. If implemented well, this is only a very minor change, but comes with a great deal of benefits.

A feature that I haven’t implemented yet, but am planning to implement is entity generations. When an entity is deleted, it doesn’t mean that there are no more references to it. Especially since entities are regular integers, there is no weak-reference mechanism that magically nulls an identifier once deleted.

An answer to this problem is entity generations. A generation is a number that gets automatically increased every time an entity is deleted. With generations, an application can check if an entity is already deleted by simply comparing generations: if the active generation is different from the generation stored in the reference, the entity was deleted and the id should no longer be used.

A generation is yet another thing that can be encoded in the entity identifier. At this point you may be wondering if between type roles and traits we haven’t used up all of the available addressing space, and whether this isn’t going to put serious constraints on the total number of entities we can have.

The answer is no, for the simple reason that we can reuse the addressing space for type roles. Type roles are only used in the entity type, which means that they don’t eat into our regular addressing space. For this reason, we can use the same byte in our regular identifiers to store the entity generation. Then, when we do an operation on the entity we compare the generation in the handle with the last known generation, and if it doesn’t match, we throw an error.

But, the attentive reader may wonder, won’t this prevent us from keeping track of generations of entities that have been added to other entities? The answer is yes, but it doesn’t matter. Consider the things we can add to an entity (components, tags and parents):

  1. Components/tags will never increase in generation as they cannot be deleted (or should not, as this could cause undefined behavior)
  2. If a parent is deleted, its children should also be deleted, therefore it should never be possible to refer to a deleted parent in a type.

Other kinds of type roles, like instancing, have similar reasons for why this keeping track of generation in an entity type is not necessary. As a general rule of thumb, it seems reasonable to demand from an application that whatever is added to an entity, should not be deleted.

One remark about only using a single byte to store generation: it is not unthinkable that an entity is removed more than 256 times in the lifespan of an application. This could cause the generation to overflow and start again from 0. We can live with this however, since a generation still greatly reduces the chance of using a deleted entity as the generation of the identifier must match exactly with that of the actual entity generation. The worst case chance of accidentally using a deleted entity is therefore reduced to 1 / 256.

Lets finish with a topic that is a bit lighter:

If component identifiers are entity identifiers, that means that they can theoretically span the entire 64 bit addressing range (48 bit when using type roles, 32 bit when using traits). That is fine, but can be annoying as you can’t use a 64 bit address to index an array: anything above 32 bit, and probably much lower than that, will cause you to run out of memory. This is bad, as using component ids as array indices is one way to implement fast lookups.

Having our component identifiers potentially scattered across the entire addressing range is therefore not desirable. There is one simple solution to this, which is to reserve the first N identifiers for components. Reasonable values for N can vary from project to project, but some multiple of 256 is probably a good place to start.

Small component identifiers are one of the reasons that archetype traversal in Flecs is fast, as component identifiers are used to find the edge to traverse in an array of edges per archetype.

64 bit is not a lot of data to store, but can contain a lot of information about an entity. The greatest thing about it is that all of this information is at our fingertips the moment an id is passed into a function, and only requires a few cheap bitwise operations to retrieve. Furthermore, we have seen that features that previously seemed impossible to implement efficiently in ECS become almost trivial when encoded in an entity identifier.

This schematic shows the composition of an entity identifier with all of the techniques combined:

Image for post
Image for post

For an implementation of these concepts, check out the Flecs repository: https://github.com/SanderMertens/flecs

If you’re building an ECS, are using Flecs or would like to discuss more about ECS design in general, feel free to join the Flecs discord!

More reading:

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store