Making the most of ECS identifiers
The previous version of the blog was hopelessly outdated! I rewrote it to include all of the latest tips & tricks.
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. Something like this:
Position position_array[MAX_ENTITY_COUNT];
Velocity velocity_array[MAX_ENTITY_COUNT];unsigned int ent = world.entity();position_array[ent] = {10, 20};
velocity_array[ent] = {1, 1};
While this approach is very simple and can (literally) be implemented in less than 5 minutes, it’s also limiting the many cool things you can do with the bits in an entity identifier. In this blog I’ll go over some of the tricks I used in flecs to make the most of my ids.
Let’s start with …
Component ids are Entity ids
An ECS doesn’t just need a way to identify entities, it also needs to be able to uniquely identify components. There are a bunch of ways to do this, and they depend a lot on the language you’re implementing the ECS in, but chances are good that an ECS refers to components internally with integer identifiers.
One of the first “tricks” I implemented in flecs was to use regular entity identifiers for components. Not only does this save you from having to implement two separate id mechanisms, it also gives you a lot of flexibility with what you can do with your components. Just to mention a few things:
Runtime tagging. At some point you may want to tag your entities with something that’s only known at runtime. Say you have an RTS game with units that are grouped in platoons. The platoons are defined by the player at runtime. Ideally we’d like to be able to add a tag for each platoon we can add to the units, so we can easily query for them when necessary.
When components are entities, this is really easy to do. Just create a new entity for a platoon, and add it to the units:
entity Platoon_1 = world.entity();
unit_1.add(Platoon_1);
unit_2.add(Platoon_1);world.each(Platoon_1, [](flecs::entity unit) {
// unit is part of Platoon_1!
});
Reflection. Most games will end up implementing some kind of reflection system for their components. Say you’re building a function that visits all components from an entity, and you want to serialize them to JSON. How to get the reflection data from those components is not straightforward, and likely requires you to fiddle with a custom data structure.
When components are entities this becomes really simple, as you can just add the reflection data as a component to the component!
world.component<Position>()
.set<Struct>({
{"x", world.component<float>() }
{"y", world.component<float>() }
});Support for scripting languages. When components are entities, they aren’t tightly coupled with compile-time knowledge. This turns out to be ideal for scripting, as it enables you to define components at runtime directly from your scripting language runtime:
auto script_component = world.entity()
.set<flecs::Component>({ component_size, component_alignment });Tooling. If you’re building ECS tools, like editors or debugging utilities, at some point you’ll want to find all components in a world. Ideally these tools don’t have to know anything about your game, but this can be tricky if components can only be defined at compile time. When components are entities though, we can query for them just like we would any other entity:
world.each<flecs::Component>([](flecs::entity component) {
// found a component!
});Singletons. Unexpectedly, when components are entities, implementing singletons becomes trivial. A singleton component can simply be modeled as a component that is added to itself:
world.component<MySingleton>()
.set<MySingleton>({ ... });This is great, as it doesn’t require dedicated data structures or features from the ECS library to enable, and it reuses all of the functionality the ECS provides for regular components!
There are many more features that benefit from components as entities, such as automatic cross-binary component registration, component storage policies, and entity relationships. We’ll cover some of that later, but let’s first move to the next trick:
Entity Liveliness Tracking
A super useful feature in games is being able to tell whether an entity is still alive or not. Say you have a turret entity with a Target component that holds a reference to the entity the turret is targeting. Maybe by the time the turret evaluates the Target component, the target already got killed by another turret! In that case the reference could be pointing to a dead entity.
What would be nice is if the application can simply do target.is_alive() before attempting to do anything with it. This is what entity liveliness tracking enables us to do.
Say turretA was targeting entity 100, but turretB killed & deleted the entity from the world. We could now flag entity 100 as “not alive”, so that we can do the is_alive check. However, we run into a small problem here.
Most ECS implementations recycle ids, which means that after entity 100 is deleted, another system may have created an entity that reused id 100. Now when turretA does is_alive it returns true, even though the target was deleted! We get around this problem by adding a “generation count” to an entity. This is basically a counter for each id that increments when the id is deleted.
This however introduces another problem, which is how to quickly access this generation count. Having to do an additional lookup wouldn’t be great as it could slow down almost every ECS operation. Instead, we can encode the generation count directly into the entity id!
In flecs the generation count is encoded in the first 16 bits of the upper 32 bits of the entity identifier. This means an entity id can be recycled 65.535 times before the generation count resets, which should be more than enough for most games. It also means that whenever we pass an entity identifier around, the generation count is right there, so liveliness checks can be super fast.
The next trick is a big one:
Entity Relations
ECS relationships were first introduced by Flecs in version 2.4, and its introduction has since caused both game- and ECS developers to rethink what can be done with an ECS. In its most basic form ECS relationships let you create a graph with entity-to-entity relationships, for example:
entity Eats = world.entity();
entity Apples = world.entity();
entity Bob = world.entity();Bob.add(Eats, Apples); // Bob -(Eats)-> Apples
We can use entity relations in queries, for example:
world.each(world.pair(Eats, flecs::Wildcard),
[](flecs::entity e) {
// all entities that eat something!
});Entity relations has become a broad topic with lots of fun things you can do with them (such as adding components multiple times, hierarchies, prefabs), but going over them would require its own blogpost. If you’d like to learn more about relations, check out this article.
It does beg the question though how all of this can be efficiently implemented. Doesn’t this turn the ECS into a graph? What does this do to cache efficiency?! Is this going to blow up the complexity of an implementation?!!
The answer is unsurprisingly no, but perhaps surprising is that a large part of implementing relationships comes down to a simple id trick. Here’s how it is done in Flecs.
As we’ve learned, entity identifiers are 64 bit. Let’s take a look at what the entity identifier looks like with what we know so far:
We’ve also learned that components are entities, and that this means we can add entities to entities. Therefore there must be a list somewhere with 64 bit ids telling us which components an entity has. If you look closely however, a lot of those 64 bits are dead space. Entities should never have anything that’s not alive, so the entity generation isn’t used. 32 unused bits, how wasteful!
We could use those extra bits to effectively store two entities in a single component identifier. Because both entities must be alive, we don’t need the generation count, so 32 bits for either entity is enough. In flecs these combined ids are called “pairs”, and they allow us to store things like “Eats, Apples”, or “ChildOf, SpaceShip”. The two parts of a pair are called the “relation” and the “object” (terminology borrowed from graph dbs).
The kicker is that for an ECS storage, a component is nothing more than a unique id with some metadata, such as its size. That means that adding a component or a pair are the same for all the storage is concerned, it’s just a unique identifier (although the pair is quite a large id- which the storage must be able to handle).
This deserves extra emphasis: If components are modeled as entities, adding relationships to an ECS requires no changes to your storage.
Effectively what we’ve done here is add another way of interpreting the identifier. When it’s a regular entity, it has a generation count. When we add it to an entity, we use the upper 32 bits to store an additional entity. Flecs has two types for both, the first is flecs::entity, the second is flecs::id. When visualized, this is what they look like:
Of course this does not add full support for entity relationships to an ECS, as support for it will also have to be added to queries, serialization and lifecycle management (“deleting a parent should delete its children”). Still, it is neat that for all the storage is concerned, it comes down to a simple id trick.
The next one improves performance, and makes it easier to write multiplayer games!
Id Partitioning
32 bits is a lot. I doubt there will ever be a game with 4 billion entities, and while it is good to know that the ECS library provides some headroom, this seems a bit excessive. It turns out we can still make good use of our id space, even if our game doesn’t have millions (or billions) of entities.
In flecs you can partition your id space. Partitioning basically means walling of a part of your ids for a specific purpose. There are a few ways in which this is useful. The first one is component identifiers.
Low Component Identifiers. While it is great to use entity identifiers for components, it can pose some challenges. For example, you can optimize your data structures if you know that you’ll never have more than 64 components, and avoid resorting to expensive(ish) alternatives such as maps. When components are entities however, we can’t make assumptions about the id range of those components, which makes it harder to do such optimizations.
The answer to this solution is id partitioning. Flecs has a “low id partition” which is typically used for component ids. By default this partition is all the ids from 1..256. This doesn’t mean that you can’t have more than 256 components, but it does mean that the first 256 components use faster data structures.
Custom Entity Ranges. Flecs lets you set id ranges which configures the range in which ids are produced:
// Generate entities between 5000 and 6000
world.set_entity_range(5000, 6000);This is useful in multiplayer games, where you may want to reserve id ranges for different services of your architecture. You may for example reserve ids 1000..5000 for clients, and everything above that (5000..0) for entities from a server. This makes it possible to receive ids from a server that don’t have to be mapped to local ids, saving CPU cycles on the client!
Flecs also provides a range check, which makes sure a piece of your code doesn’t modify entities outside of the intended range. This is useful if you want to ensure that your networked code doesn’t accidentally overwrite the entities local to a client:
world.enable_range_check(true);An example of a custom id partitioning scheme could look like this:
Notice the “modules” gap between the component ids and client ids. This is typically done to leave space for entities imported by modules, such as tags, prefabs and systems, including those imported by the builtin flecs modules.
Our last trick will let us provide hints directly to the ECS storage!
Type flags
Type flags are a few bits we use at the end of an id that let us add features to an ECS that are orthogonal to everything we’ve talked about so far. That sounds abstract, so let’s make it concrete.
Suppose we want to add component enabling/disabling. Such a feature has been implemented by a number of ECS implementations, and it lets us temporarily disable a component and reenable it at a later point in time with its old value. In addition to this being a handy feature, it can also prevent expensive archetype swaps, depending on the ECS implementation.
On the storage level this can be implemented in any number of ways, but how do we actually let the storage know that we want to disable a component? This is where type flags come in handy. We can add a Disabled flag that we can combine with a component id using a bitwise OR, which will instruct the storage that the component is disable-able. In code this could look like:
ent.add(world.component<Position>() | flecs::Disabled);We’ll have to chip off a few bits at the end of the id to store the flags, which eats into the id space of the “relation” part of the id. That’s okay though, in Flecs type flags use up 4 bits, which leaves 28 bits, or 268,435,456 different kinds of relationship kinds. The flexibility that type flags provide, in addition to not having to write dedicated APIs for such storage features makes them more than worth it.
And that’s all of the tricks Flecs uses to make the most of ids! In summary the layout of an id looks like this when visualized:
You may notice the inconspicuous dead space of no less than 8 bits in the id space of an entity identifier. That is not an error, this is actual dead space in the entity identifier currently used to detect bad entity identifiers. It does leave open the possibilities for more exciting applications though, such as increasing the size of the generation count, or something else all together!
Anyway, that’s for another blog. I hope this gave you an idea or two about how you can get the most out of your entity ids, or gave you a better idea of the tricks Flecs uses to implement some of its features!
If you liked this blog, consider giving Flecs a star on GitHub or join the community on Discord! https://discord.gg/BEzP5Rgrrp
Further reading:
