Entity Component System

Summary

An archetype based ECS that was used in the last three group projects during my time at the Game Assembly. The entities are just a 64-bit ID and there is very little difference between them and components aside from some component ID:s being linked to data. ID:s are recycled on removal and are made up of multiple parts bit-shifted together. Tags, and even other entities, can be added as components and queried for akin to how you would query a database.
Heavily inspired by blog posts made by Sander Mertens, creator of Flecs.
The reasons why I chose to create an ECS:

It's cache efficient - You can iterate over the exact data that you require (or close to) for all entities with that data.
Easier to multi thread - All you need to do is check what systems don't share components; these can be run in parallel.
I had read that once the components and systems were in place, then, in theory, you could more easily create different types of entities by mixing and matching what components were attached to them, which sounded intriguing.

Component Storage

The storage is composed of a vector of columns, where each column is a type eased vector of a unique component type. The vector of columns are stored in an archetype.

This code has been over commented on purpose and does not represent my commenting style

Using this "structure of arrays"-like setup allows us to have fast look-ups and fast iterations over contiguous blocks of memory with no data fragmentation. I have also aligned the components by 16 bytes to allow for more vectorization opportunities by the compiler.

Queries

Queries are used to filter all existing entities for the ones you want to iterate over. A Query can contain components or tags and can be marked as "Has" or "Does not have" for advanced queries. In the next image is an example of a query that gets all entities with a local directional light component + in the selected scene + is not static. The entities are retrieved in the same order as they were found in the archetypes, so their components are guaranteed to be next to each other in memory.

Components can set what components they depend upon and this is used to more efficiently construct entities by adding the dependent components at the same time automatically if they don't already exist. It's also used to more efficiently navigate between archetype edges, as we don't need to jump between archetypes one at a time to get to the correct one, since when the components are added at the same time, they will go straight to the archetype with the component and its dependent components. This also means that, in the query above, we don't need to filter for the transform component, because the local directional light component has set it as a dependency and is therefore guaranteed to have it.

The Entity type, in the picture above, only contains an ID and is only an interface to more easily interact with a specific entity.

FVector, a.k.a. Frame Vector, is a regular vector that uses a custom allocator. It allocates from a pool of memory that is allocated at the beginning of the application. The memory is later reclaimed at the end of the frame to be reused during the next one. This is great for when you need a temporary vector, but want to avoid an expensive allocation from the OS, and queries are a perfect use case for them!

Relationships

Relationships are a type of tag whose ID consists of two parts; the relationship type, and the relationship target (usually an entity). For example: we can combine the ID of the tag "AttachedTo" and an entity ID and add it as a component to an entity. This allows us to make much more advanced queries, as we can not only query for "AttachedTo" + Entity, but also "AttachedTo" + wildcard and wildcard + Entity. The entity ID '0' is used to indicate an invalid ID, but for queries it acts as a wildcard by only matching to part of an ID.
During the initialization of an archetype; each component ID is added to a look up table as a key with the value being a pointer to another look up table of archetype IDs and pointers to their respective archetype. All we need to do to be able to query using wildcards is add three more entries into the first look up table with keys that have had either, and both parts replaced with wildcard.

Things that I'd like to improve

The most critical thing that I'd like to improve is to create some type of QueryIterator to be able to iterate over the components directly instead of having to get them one at a time. Right now, every time we get a component, we need to verify the entity and find its archetype. This time adds up and, as the world has more and more entities added to it, it becomes noticeable when we profile our games. I want to fix this, but I haven't been able to allocate time for it because it hasn't yet reached the point where it's our main bottleneck.

Here is a list of a few other things I would like to improve or features I'd like to add:

The syntax for querying. The goal is to remove bloat and make it as close as possible to reading a sentence of keywords that anyone could understand without any knowledge of C++.
The ability to toggle components so that we don't need to move the entity and all of its components back and forth between archetypes like we do now.
The ability to combine 'worlds', or in my case 'ComponentManagers'. This would allow us to safely load scenes on another thread by loading them into a separate world and then combining it with the main world.
Replace some of the unordered_maps with flat maps. I believe some of them don't get large enough to warrant an unordered_map vs searching a vector, and their data size is small enough to be able to cache any elements nearby instead of filling it with trash. Of course I would need to profile to make sure that its actually better.

Google Sites