Building an ECS #1: Types, Hierarchies and Prefabs
Flecs Discord: https://discord.gg/MRSAZqb
This article is outdated, and the data structures it describes have been replaced with more efficient ones! Go here for the more up to date article:
This is the first in a series of posts about the guts of Flecs, an Entity Component System for C and C++. Each post will cover a different part of the design and turn it inside out, so that at the end of each post you will have enough information to implement it yourself.
The blog is intended both for Flecs users as well as people interested in ECS and game design. I won’t explain ECS in great depth as there are many resources that already do a great job at this, such as the ECS FAQ or the ECS back & forth series.
In this first entry I will talk about two of the three fundamental building blocks of Flecs: entities and types (the 3rd one being systems), and how seemingly complex features like hierarchies and prefabs are implemented with a design simple enough to fit on the back of a napkin.
The Entity Index
Entities are unique “things” in your game, often represented as a unique integer value. A type in ECS (sometimes called an archetype) describes the components (datatypes) a specific entity has, which can be represented as a vector of component identifiers. For example, a first person shooter could have a “Player” entity that has components “Position” and “Health”. The type of this entity would be [Position, Health].
We can combine the entity and type concepts to build the first data structure of an ECS framework, which is the entity index:
using Type = vector<ComponentId>;
unordered_map<EntityId, Type> entity_index;The entity index lets us quickly query for a given entity id which components it has. Flecs uses a data structure very similar to the one described here for this exact purpose. With just the entity index, we can implement a rudimentary has_component function:
bool has_component(EntityId entity, ComponentId component) {
vector<ComponentId>& type = entity_index[entity];
for (auto c : type) {
if (c == component) return true;
}
return false;
}Let’s take a closer look at the types of EntityId and ComponentId. The EntityId is easy since it is just an integer. Flecs uses 64 bit ids, for reasons we will see later. For now that means we can simply define EntityId like this:
using EntityId = uint64_t;The component id is a little bit tricker. It needs to be a unique value for each datatype we add to entities, so Flecs knows what to do when we write:
Player.add<Position>();
Player.add<Health>();After these two operations, we want our entity index to contain a vector for “Player” that contains [Position, Health]. Because we can’t store types directly (C does not have a notion of a “type id” or otherwise) we need to come up with our own representation. A straightforward approach is to assign unique integers to each data type, which is exactly what Flecs does:
ComponentId Position_id = 1;
ComponentId Health_id = 2;With these ids, the type of Player can be stored like this:
[1, 2]This is exactly what happens in Flecs: a unique component id is assigned to a datatype whenever you do ECS_COMPONENT (in C) or flecs::component (in C++). Because this definition of a component id is exactly the same as that of the entity id (a unique integer value) they are the same in Flecs:
using ComponentId = EntityId;This is not just useless reductionism, it lets us do a lot of cool things that help implement many of Flecs’s unique features, as we will see in a bit. For now, this gives us a nice and concise way to describe our basic ECS design:
using EntityId = uint64_t;
using Type = vector<EntityId>;
unordered_map<EntityId, Type> entity_index;Or in plain text:
- An entity is represented by a unique integer
- A type is a vector of entity (component) ids
- The entity index stores entities and their type
We can use this design to describe our previous example. Let’s first start with assigning ids to all of our entities and components. Note that since ComponentId is the same as EntityId, we’ll just use EntityId from now on.
EntityId Position_id = 10;
EntityId Health_id = 20;
EntityId Player = 30;With these ids, the content of the entity index looks like this:
{
10: [],
20: [],
30: [10, 20]
}Note how not just Player (“30”) shows up in the entity index, but also the entities for Position and Health (“10”, “20”). This is great. We can store both entities and components in a single consistent data structure. It is not the whole story though, as entities that represent a component have a special component that describes the datatype it represents. In Flecs, this is the EcsComponent component. Let’s update our definitions to include this:
EntityId EcsComponent_id = 1;
EntityId Position_id = 10;
EntityId Health_id = 20;
EntityId Player = 30;Our entity index now looks like this:
{
1: [1],
10: [1],
20: [1],
30: [10, 20]
}Something funny happens here: since EcsComponent (“1”) is a component itself, it has itself in its type (“[1]”). The creation of EcsComponent happens during the Flecs bootstrap, when you call ecs_init or create your world.
Our entity index is becoming a bit unreadable though. This is not just a problem in this example, but also when writing applications and you want to inspect which components an entity has. Instead of a list of integers, it would be nice if we could see the component and entity names. For this reason, Flecs introduces the EcsId component:
EntityId EcsId_id = 2;Lets see what the entity index with EcsId looks like with plain numbers first:
{
1: [1, 2],
2: [1, 2],
10: [1, 2],
20: [1, 2],
30: [2, 10, 20]
}The same entity index with names instead of numbers then looks like this:
{
EcsComponent: [EcsComponent, EcsId],
EcsId: [EcsComponent, EcsId],
Position: [EcsComponent, EcsId],
Health: [EcsComponent, EcsID],
Player: [EcsId, Position, Health]
}This is pretty close to what an actual Flecs application looks like. Let’s now take a look at some of the more exciting things we can do with this design.
“One of the biggest implications of this design is that we can add entities to entities”
Hierarchies
So far we have described how this design lets us store entities and which components they have. One of the biggest implications of this design is that we can add entities to entities. Since a type is a vector of EntityId, it doesn’t matter for Flecs whether an application adds a component or a regular entity. In other words, it is possible to do this:
{
Foo: [],
Bar: [Foo]
}This might not seem like such a big deal, but this simple ability allows us to construct hierarchies (or more accurately, graphs but lets stick with hierarchies for now):
{
Parent: []
Child1: [Parent]
Child2: [Parent]
Child3: [Parent]
}There are ways we can improve upon this though. For example, right now it is kind of hard to see which element in the type represents a component and which one represents a parent. Suppose we can join a platoon in our game, in which case we add the platoon entity to the player as parent:
Player: [Position, Health, MyPlatoon]Even though we know that “MyPlatoon” is a parent, there is no way that we can see this just by looking at the type. For this purpose Flecs introduces “type flags”. Type flags are reserved bits in an entity id that describe the role an entity has in the type. “CHILDOF” is the type flag used to indicate that something is a parent. Let’s take a look at how we can use it to indicate that MyPlatoon is in fact a parent:
Player: [Position, Health, CHILDOF | MyPlatoon]The OR operator adds the CHILDOF bit to MyPlatoon. We could now write this code to quickly find the parents (there can be multiple) in a type:
Type type = entity_index[Player];
for (auto el : type) {
if (el & CHILDOF) {
// element is a parent
} else {
// element is not a parent
}
}Hierarchies are common in games, and sacrificing a single bit in the entity id for them is worthwhile. Of course we only described so far how to store the hierarchy, we haven’t actually talked about what the framework should do with this information, which a topic for a future blog.
Prefabs
Another feature that is also widely used in games and seems complex is the ability to create reusable assets, or prefabs. In Flecs, this functionality is implemented with another type flag, called INSTANCEOF. This flag lets entities share components with each other, which in combination with a few rules gives us the ability to create entity templates.
When using component sharing and INSTANCEOF, we talk about “base” entities, from which we share a component, and “instances” with whom the component is shared.
{
Base: [Color],
InstanceA: [Position, INSTANCEOF | Base]
InstanceB: [Position, INSTANCEOF | Base]
}Flecs interprets this as “InstanceA and InstanceB both share all components from Base”. When an application attempts to retrieve Color from either InstanceA or InstanceB, it will actually get the Color component from Base:
InstanceA.get<Color>(); // Returns Base.ColorHere we say that for InstanceA and InstanceB, “Color” is a shared component. The opposite of a shared component is an owned component. InstanceA and InstanceB both own Position, while Base owns Color.
Let’s use this functionality to create a reusable asset for a blue square, using the actual C++ Flecs API:
auto BlueSquare = flecs::entity()
.set<Color>({0, 0, 255})
.set<Square>({50});auto SquareA = flecs::entity()
.add_instanceof(BlueSquare)
.set<Position>({10, 20});auto SquareB = flecs::entity()
.add_instanceof(BlueSquare)
.set<Position>({30, 40});
This will result in the following entity index and types:
{
BlueSquare: [Color, Square],
SquareA: [INSTANCEOF | BlueSquare, Position]
SquareB: [INSTANCEOF | BlueSquare, Position]
}This design can be improved. What if SquareA wants to only update its own color? Right now changing the color of BlueSquare means changing the color for every instance of BlueSquare, and that may not be what we want. We want the ability to override components, and it turns out we can do that with just two additional rules:
- Adding a component to an instance will override the base
- When overriding a shared component, the value of the base will be copied to the instance
Let’s again take a look at what this looks like in C++ code:
auto BlueSquare = flecs::entity()
.set<Color>({0, 0, 255})
.set<Square>({50});auto SquareA = flecs::entity()
.add_instanceof(BlueSquare)
.add<Color>()
.set<Position>({10, 20});// Code for SquareB ...
Note how we do not provide a value when we add Color to SquareA, but because of the rules we just defined, the value of Color will be copied to its owned Color component. Here’s the entity index after running this code:
{
BlueSquare: [Color, Square],
SquareA: [INSTANCEOF | BlueSquare, Color, Position]
}This is pretty cool, but having to remember to add Color every time we create an instance of BlueSquare is annoying. Fortunately we can automate this by creating an explicit Flecs type that does the overriding for us:
auto BlueSquarePrefab = flecs::entity()
.set<Color>({0, 0, 255})
.set<Square>({50});auto BlueSquare = flecs::type()
.add_instanceof(BlueSquarePrefab)
.add<Color>();auto SquareA = flecs::entity()
.add(BlueSquare)
.set<Position>({10, 20});
This will result in the same entity index as the previous example, but note how we encapsulated overriding the Color component in the BlueSquare type.
Summary
That’s a lot of information, yet while hierarchies and prefabs can behave in intricate ways, the underlying data structure remains quite simple. Since type flags are just a bit that we set on an EntityId, we can include them in our existing design like this:
// Entities, types and entity index
using EntityId = uint64_t;
using Type = vector<EntityId>;
unordered_map<EntityId, Type> entity_index;// Type flags
const EntityId INSTANCEOF = 1 << 63;
const EntityId CHILDOF = 2 << 62;
I hope this gave you some insight into how to go about designing an ECS, and if you’re a Flecs user, a bit more background on how the framework stores things internally. If you liked what you read, consider checking out the Flecs repository (https://github.com/SanderMertens/flecs) and our Discord channel!
More reading:
