Introduction
This is the translation of my article about ECS. Original (in Russian)
ECS (Entity Component System) is an architectural pattern used in game development.
In this article, I am going to describe some of the general principles of ECS frameworks' inner workings and some of the problems I have faced during the development of my own.
When I first started learning about ECS everything seemed wonderful, but only in theory. I needed some real practice to make sure that all that they were saying about ECS was true.
I’ve tried different frameworks with different engines and programming languages. Mostly it was the gorgeous EnTT framework that I used with the Godot engine and LeoECS with Unity. I haven’t tried Unity’s native ECS from DOTS because it was rather unpolished at the time I was starting.
After a while, I got enough practical experience with ECS but it was still unclear to me how all this magic works under the hood. There are a few good blogs about ECS development (https://skypjack.github.io/ from the author of EnTT and https://ajmmertens.medium.com/ from the author of Flecs) but none of them gave me enough understanding about how they are implemented. So eventually, following Bender’s example, I decided that I’m gonna make my own ECS =)
For implementation, I chose C# and Unity since that’s what I’m using for my pet game project.
There are lots of articles and explanation videos all over the Internet about what ECS is and how to make games using it (for example the blogs mentioned above or this really good presentation from the developers of Overwatch: https://www.youtube.com/watch?v=zrIY0eIyqmI) but almost nothing about its inner workings. And that will be the subject of this article.
Data access
The main problem of the ECS architecture is data access. If we had only one component type, entities could be just indices into an array of these components, but there is always more than one component type in real-world scenarios. And if one group of entities all had one component, another group of entities had another component, and the third one had them both, then it would be really bad for CPU cache locality with a naive array-based approach. And thus we need some smart data access arrangement. From the information found on the internet, I’ve learned that there are two major approaches: archetypes and sparse sets. The first one is used in Flecs and (as far as I know) Unity’s DOTS. The second one is in frameworks such as EnTT and LeoEcs. I went with the approach of the sparse set for implementing my framework.
Archetypes
First, I’ll briefly explain how archetypes work, or at least my understanding of it. An archetype is a collection of entities with exactly the same set of components. When you add or remove components from an entity it is moved to another archetype, with all its components. Each archetype contains arrays of entities and components with corresponding indices, so they are perfectly aligned with each other. The main advantage of this architecture is that entity processing can be parallelized more easily, but it comes with a downside: it is quite costly to add/remove components from entities. So I gave up on that approach in favor of sparse sets because the game I am working on uses tags extensively. A tag is a no-data component that only describes some aspects of the entity that it belongs to. For example, DeadTag on an entity indicates that this entity is dead and therefore should not be processed by systems where only alive entities are processed. And usually, such tags are added only for a couple of frames and then removed.
Sparse sets
The second approach. A sparse set is a tricky data structure that allows indirect access to data. In its basic form, it consists of two arrays: an outer sparse array of indices and an inner dense array of values. In such sets, we refer to elements by outer indices. Using that index we first get the inner index from the sparse array, and then using this inner index we get the value we need. If the inner index is -1 or the outer index is outside of the range of the sparse array then there is no value with that outer index. Thus we can store data continuously without gaps. The only gaps we’ll have are the regions filled with -1’s in the outer indices.
Overall structure
The main class of my framework is EcsWorld, which holds an array of entities, a collection of systems, and component pools.
An entity is just an integer that stores the entity’s index and generation using bit shift operations. The generation is incremented every time an entity is recycled and is used to check whether the entity represented by this integer is still valid, i.e. it hasn’t been destroyed and recreated.
A Component pool in my case is just a class implementing the IComponentsPool interface. So I can store pools of components of different types in one collection.
There are two implementations of IComponentsPool: ComponentsPool (based on sparse sets) and TagsPool, which is implemented as a dynamic bitmask and only stores whether the tag is present or absent on the entity.
Component registration
Each component is registered and gets its index via this trick with a static constructor that I came across in LeoECS:
static class ComponentIdCounter
{
internal static int Counter = -1;
}
public static class ComponentMeta<T>
{
public static int Id
{
get;
private set;
}
static ComponentMeta()
{
Id = ComponentIdCounter.Counter++;
}
}In other words, we have a static counter that is incremented each time a new component appears. It’s then used as the index of the components pool for this component.
Naive implementation
This is what the first iteration of data organization looked like. Every system had a filter consisting of two masks: includes, or the components that entity should have, and excludes, the components that it shouldn't.
Every tick the system iterates over all the entities and checks the components on the entity against its filter. But the performance of that approach was unsatisfying and I had to think about some kind of optimization.
Optimization
The idea of optimization is that every filter should have not only include/exclude masks but also an array of filtered entities which should be updated every time an add/remove happens. Somewhat resembling the archetypes approach mentioned above.
For this, we create two (one for includes and one for excludes) helper structures of type Dictionary<int, HashSet<int>> which will contain sets of indices of all filters with a given component, accessible by the id of that component.
Every time we add a component, we get the registered ID of that component, get all the filters by that ID from our helper structure for excludes, and remove the entity from all these filters. Then we add the component to the pool and add the entity to all the corresponding filters in the helper structure for includes. And when we remove a component, we go through all this in reverse: add an entity to the exclude filters and remove it from the include ones.
However, the fact that an entity has a specific component doesn’t guarantee that this entity satisfies all the filter conditions. That's why I added an array of bitmasks that corresponds to the array of entities to the EcsWorld and check against the mask when adding or removing a component.
The rest is easy: each system registers a filter (or you may have several filters) in EcsWorld by two masks and gets the index of the corresponding filter. Then it iterates over the collection of filtered entities obtained from the world by that index.
class MySystem : EcsSytem
{
int filterId;
public MySystem(EcsWorld world)
{
filterId = world.RegisterFilter(
new BitMask(Component1.Id, Component2.Id),
new BitMask(Component3.Id, Component4.Id));
}
public override void Tick()
{
world.GetFilter(filterId).Iterate((entities, count) =>
{
for (int i = 0; i < count; i++)
{
//do stuff
}
});
}
}(the code is slightly simplified for the sake of readability)
Epilogue
There are many nuances of implementation left outside of the scope but the main purpose of this article is to show key ideas of ECS implementation, the main problems I have faced during development, and solutions to them.
I have plans to implement a system of sorted groups in the future, like in EnTT. In it you can sort sets of components according to certain filters so that the entities and components that meet the criteria go in strict order. But in general, even without sorting, there is a performance gain.
I also plan to write an ECS based on archetypes. Maybe someday I will write about it here.
Well, in the end, I want to clarify that my project was created solely for educational purposes and although I’m making a game with it, I advise you to use one of the popular frameworks: for example, LeoECS or, if you need rollbacks just like me, ME.ECS. Also, Unity’s DOTS has been long in development and could be ready enough to be worth a try.