# Fastest way to look up an entity with a set of components?

I'm currently trying to implement an ECS system, but I've sort of ran into a problem trying to fetch all of my entities that have a specific set of components. I currently have a Dictionary that maps a component name to a list of Guids (entities), so I have no problem fetching a list of entities if I were to query for just one component. But if I were to query entities for more than one component (e.g. all entities that have Render and Transform component), I run into a problem where it's no longer a constant time lookup.

I could probably loop through the entities to see if they contain that set of component names (they are stored in a dictionary that maps Guid to a list of strings), but I was thinking that there could be a faster way of doing this?

• First thing to do is measure (profile) and see if it's fast enough. :-) You're taking the intersection of several sets. Relational databases have some optimizations for this situation. If your sets are large, you can represent them as sorted arrays of guids and then calculate the intersection similar to the way merge sort iterates through sorted arrays. If at least one set is small, you can use hash tables of guids. Start with the smallest one, test each of those elements against the other sets (probably the smallest first). – amitp Jul 15 '19 at 23:09

## Update

I have wrote Theraot.ECS inspired by this answer. It allows you to use Guid, int or whatever for the entities. It will allow you specify how sets of component kinds are handled. Two implementation provided: one uses a binary flag array, the other is based on hash sets.

Some lessons learned:

• QueryCheck (see original answer) should return one of three cases: add, remove, nothing to do. I created an enum for this.
• BitArray, not very good for this. I rolled my own FlagArray type.
• With the design proposed in this answer getting the entities from a query yields a view, not a snaptshot. It was very easy to make it a custom type that also provide events among other things.

I decided to merge creating the query and getting the entities for the query. This means that the call can only expensive the first time (if there are already entities). Subsequent calls are O(1).

I also decided to change the phrase "component type" to "component kind" to avoid confusion with actual System.Type types.

The project is free and open source software, feel free to study it, use it, whatever. MIT license.

I want to suggest is to maintain a set for entities for each query.

When a system starts, it will report the queries it needs (I assume it is usually a single one, yet, multiple could be supported).

The engine will create (and populate) new sets for those queries. By doing this, you would only need to go over every entity to populate the dictionary when a system is created. By creating all necesary systems before the entities, you do not need to populate the sets on creation at all.

Instead, when a component is attached to an entity, you will add it to the sets according to the queries. Alright, that is not trivial... we need to figure out what queries could change their result depending on the attached component. Similarly when removing.

So, if we express a query as a list of components that must be present, we can also create a dictionary that give you queries based on components. In fact, it is relatively easy to extend to have negative queries (as in "the entity must not have this component").

The process when a component is attached or removed is as follows:

1. Use the component to get the list of active queries that could apply
2. For each query:

2.1 See if the entity passes or not.

2.2 If it passes: Add it to the set for the query (if it was not already there)

2.3 If it does not pass: Remove it from the set for the query (if it was already there)

Then the system can simply get the set for the query it wants. Of course, the query would not exist if it was not created first.

We need something like the following:

Dictionary<ComponentType, HashSet<Query>> QueriesByComponentType;
Dictionary<Query, HashSet<Entity>> EntitiesByQuery;
Dictionary<Entity, HashSet<Component>> ComponentsByEntity;


Of course, you can use GUID for your entities, and I do not know if you want ConcurrentDictionary, and you would need a good hash for the HashSet, in fact a good hash for the Components is a good idea.

What follows is the same idea translated to code (some assumptions where made).

When the component is added or removed:

// O(n) where n = number of affected queries
var entity = this_entity;
// The code below should probably be extracted to another method:
// Try to update ComponentsByEntity, if no update you can return
if (QueriesByComponentType.TryGetValue(componentType, out var queries))
{
foreach (var query in queries)
{
var set = EntitiesByQuery[query];
if (query.CheckQuery(entity)) // Uses ComponentsByEntity
{
}
else
{
set.Remove(entity);
}
}
}


Note: the remove case can be optimized futher if we know that all queries are positive (they only ask for a component to be present, but never for a component to not be present), which is the way entity-component-system is meant to be. If that is the case, you separete this code in a version for adding and another for removing, and the removing case does not need CheckQuery. You might also be interested in creating a version that takes multiple components to add at once (computing the union of the queries sets).

When the system is created:

// O(n) where n = number of components
var componentTypes = new []{componentTypeA, componentTypeB /*,...*/};
var query = QueryManager.GetFrom(componentTypes);
// The code below should probably be extracted to another method:
{
foreach (var componentType in componentTypes)
{
if (!QueriesByComponentType.TryGetValue(componentType, out var set))
{
set = new HashSet<Entity>();
}
}
}


When the system wants to query:

// O(1)
var entities = EntitiesByQuery[query];


I said twice in comments that code should be extracted to another method. That is because that code would be the same for all entities and systems. In fact, I think it is wise to not expose the dictionaries directly. I suggest a Façade.

How many components do you have? There is a change you can represet the list of components that make up a query as a bit array. Which would also be useful to represent the list of components an entity has... and then, checking is bit wise and.

In fact ComponentType does not need to be a class, nor Query. And you already know Entity does not have to be a class either. I wrote it that way to not get into the specifics of how they are represented. In fact, you might as well take advantage of using alias directive plus extension methods.

Addendum on the order of component types

This can work even without having a strict order for the components types of a query (and yes, even for negative queries).

With that said, if you want to use a bit array to represent a set of component types, the component types would need consecutive numeric codes that also act as the indexes for the bits in the bit array.

You could use an enum and flags, such that only the bit that represents the component type is set and the rest are not set. That makes doing that bit wise and very easy, and give give you the best performance. However, it would also limit the number of possible component types to 64, since the base type would be at best a ulong which has 64 bits.

You can carry on with that idea beyond the 64 component types by using a BitArray instead.

If you start with the enum and then for whatever reason you need a large number of component types, you would have to change that. Please notice I consider the bit array an optimization. You can still do the same with a set of component types and iterating.

In fact the advice would be the opposite: - Start with sets, but keep them isolated from the rest of the code. - If they are affecting your performance, and you have already settled on the number of component types for your game, then optimize accordingly.

If you are creating a generic ECS, you could offer different strategies, and let the developer decide. Keep the same façade so most of the code is unaware of the difference, and use dependency injection to pass the strategy the developer wants.

Addendum on the idea of negative component queries

Sometimes it is useful to have a system that must run on entities that do not have a particular component. For example, you could have the system detect these entities, do some computation on then, and then add the componet so it does not run on it anymore.

How to do it? The idea is go back to the initial algorithm I proposed, before any optimization. Realize it is the same for adding and removing, it has symmetry. We can exploit that symmetry... if you remove a component, perhaps you should add the entity to the set of a query that requires to not have that component. Similarly when adding a component, perhaps you want to remove the entity from the set of a query that do not wants that component.

We, of course, have the problem of how to represent these negative queries. We need a concept of the negation of a component type. That way you can have queries that say "must have componentA and no componentB".

So a query can contain a component type, its negative or neither (a query with a component type and its negative should be rejected, as it makes no sense for an entity to have a component and not have it). And yes, for the bit array, that would mean two bits per component. Which for the enum approach means you could only have half the ammount of possible component types. Again, this is a trade-off.

Disjuntions are another kind of query that is missing (an "Any" query instead of an "All" query).

You got to treat them separately (have queries marked as disjuntion). The base algorithm continues to be the same (when you add or remove, you check the queries that has the component type that is being added or removed and check if the query is satisfied and add or remove the entity on the set of the query accordingly), but the optimizations are different.

Addendum on the idea of entities with multiple of the same component type

It usually does not make sense, and in the cases it does, you probably want a hierarchy of components, such that an aggregation of components of a given type can also act as a component.

However if you want to allow entities with multiple components of the same type, then ComponentsByEntity would not use HashSet, but some sort of list... which also makes the system code more complex, because it has to deal with a variable number of components.

Then, in that case, being able to use a sorted list would allow a faster algorithm for checking a query than a regular list. If the list of components is large, a binary search will be good, otherwise, simply iterating in order will allow to discard soon. How large? Test.

By allowing an entity to have multiple of the same component type, checking if it satiesfies a query is slower. Alternatively, you could have another level of dictionaries. Which means more indirection, which means more overhead. As you can see, this idea comes with a trade-off, as usual there is price for versatility.

• First of all, thank you for the answer. I had few questions regarding the queries. If I were to save a query (any structure with a list of components) and map that to a list of entities, how would the negative queries work (not having specific components). Would a specific query that says this is a negative query have to be added as a key to the dictionary? I assume that components would have to be added in the same order for a specific query for this to work. As for the bit array to work like this, would I need a pre-determined enum to map the list of components? Thank you again! – jj232 Jul 16 '19 at 3:44
• @jj232 see addendums. – Theraot Jul 16 '19 at 6:51
• @jj232 thiking about this, I realized that an special "has no components" query would solve most - if not all - cases where a negative query would be used. And those are few to begin with. – Theraot Jul 16 '19 at 7:00

The way ECS implementations like the new one in Unity work is to use the concept of Archetypes.

An Archetype is the description of the components in a particular entity. Given sets of components, like {position,rotation,mesh} and {position,rotation,particles}, you have two different Archetypes. Both of them contain {position,rotation}, but the first Archetype also contains mesh while the second one instead additionally contains particles.

Every entity belongs to one and exactly one Archetypes. If components are added or removes, the entity then belongs to a new Archetype. By itself, this should make it easy to see how to find entities matching a query. Iterate through the Archetypes and find all matching ones. Then just iterate the entities in each matching Archetype. This is considerably faster than searching all entities because many entities will have the same archetype (e.g., every single static prop in your game world will be in {position,rotation,mesh} or some such). Some entities will be "unique" but those will be the exceptional case in any large populated game scene.

Within the Archetype, you keep the components in nice linear arrays. For example, for the {position,rotation,mesh} Archetype, its Chunk "layout" might look like:

| entity   | entity   | ... | entity   |
| position | position | ... | position |
| rotation | rotation | ... | rotation |
| mesh     | mesh     | ... | mesh     |


The advantage to this is that now you can correlate components together very efficiently. When processing all the entities in an Archetype, just look at the arrays, and you know that for a given index all the components in each array corresponds to the same entity.

Since each Archetype has its own arrays, each archetype will have an entity at index 0, and will its own array of position components at index 0. Your processing code then looks something like (in simplified code):

foreach archetype:
if archetype matches query:
for index in 0..archetype.entities:
draw(archetype.positions[index], archetype.rotations[index])


With some generics you can factor all that away into a utility and your C# user code will probably look more like:

world.Query((int count, Position[] pos, Rotation[] rot) => {
Parallel.For(0, count, () => {
renderer.Draw(pos[i], rot[i]);
}
});


That not only makes it very easy to correlate components, it also means the data is laid out nicely in the CPU cache which reduces cache misses and pipeline stalls. As a bonus, notice the use of Parallel.For in the above - if your actual update logic can use it, this approach makes multi-threading updates almost trivial. The other kinds of approaches out there using sets makes this incredibly difficult to do efficiently.

Note that Unity ECS (and other Archetype-based ECS) typically additionally have the concept of a Chunk, which is essentially the idea that the components in an Archetype are split up into fixed-sized blocks of memory (which fit a variable-size number of entities, based on the sizes of the components in that Archetype). That helps avoid memory fragmentation/bloat and makes multi-threading a bit easier in some cases, but isn't necessary for a simple implementation.

The damning part of an Archetype approach is that modifying entities is much harder. When a component is added to an entity, the entity changes Archetypes. This necessarily means that all the existing components must be copied from the storage of the original Archetype into the storage of the new Archetype. Further, these modifications can't be performed while the Archetypes' arrays are being iterated, so changes incurred during a world query have to be queued up and applied later. That's not all that tricky to write, and it performs better than you might think (so long as you perform changes in bulk), but it is extra implementation.

That said, of the handful of games I'm aware of that using actual shipping ECS architecture (and not some other or hybrid component model), most of them are using the Archetype approach. Minecraft (Bedrock/C++ edition) is the only exception as it uses EnTT, a C++ sparse-set ECS framework.

Which, if you're not keen on the Archetype approach, EnTT is probably a good place to look for implementation strategies (though again, it's C++, not C#). As mentioned, it uses the concept of sparse sets so that it mostly just iterates lists of components and uses basic set operation logic to find matches. Unlike the Archetype approach, it is neither data-oriented (doesn't guarantee contiguous/linear cache access patterns) nor especially multi-thread friendly (because underlying sets can be mutated) but it is otherwise relatively quick compared to the vast majority of other open-source ECS frameworks out there (and it's good enough for Minecraft, in any case).