Building an ECS #1: Where are my Entities and Components

The Entity Index

Entities are unique “things” in your game, often represented as a unique integer value. Entities can have components, which can be represented as a vector of component identifiers. The total set of components is the entity’s type (sometimes called an archetype).

using Type = vector<ComponentId>;
unordered_map<EntityId, Type> entity_index;
bool has_component(EntityId entity, ComponentId component) {
vector<ComponentId>& type = entity_index[entity];
for (auto c : type) {
if (c == component) return true;
}
return false;
}

The Archetype

First, we need to get rid of storing a vector per entity, and one way to do that is to introduce a new data structure called an “archetype”. An archetype is something that stores all the entities that have the same components. Because of this, all entities stored in an archetype can share the same component id vector which reduces memory overhead by a lot. Let’s add the archetype to the data structures for our ECS:

using Type = vector<ComponentId>;struct Archetype {
Type type;
};
unordered_map<EntityId, Archetype&> entity_index;
unordered_map<Type, Archetype> archetype_index;

The Component Index

Having a vector of component ids is good if we want to iterate through all the components of an entity, but having to loop through the vector if we want to test if an archetype has a specific component is not ideal. One thing we could do is add a set to the archetype that has an entry for each component id:

struct Archetype {
Type type;
unordered_set<ComponentId> type_set;
};
bool has_component(EntityId entity, ComponentId component) {
Archetype& archetype = entity_index[entity];
return archetype->type_set.count(component) != 0;
}
struct Archetype {
ArchetypeId id; // unique integer identifier for an archetype
Type type;
};
using ArchetypeSet = unordered_set<ArchetypeId>;
unordered_map<ComponentId, ArchetypeSet> component_index;
bool has_component(EntityId entity, ComponentId component) {
Archetype& archetype = entity_index[entity];
ArchetypeSet& archetype_set = component_index[component];
return archetype_set.count(archetype.id) != 0;
}
ArchetypeSet& position_archetypes = component_index[Position];for (auto& archetype : position_archetypes) {
// archetype has Position component!
}
ArchetypeSet& position_archetypes = component_index[Position];
ArchetypeSet& velocity_archetypes = component_index[Velocity];
for (auto& archetype : position_archetypes) {
if (velocity_archetypes.count(archetype.id) != 0) {
// archetype has Position and Velocity!
}
}

Summary

Our ECS is starting to shape up nicely:

  • We can keep track of entities in the entity_index
  • We can inspect the components of an entity by looking at its Archetype
  • We can check if an entity has a component with the component_index
  • We can quickly find all archetypes for a set of components
// A list of component ids
using Type = vector<ComponentId>;
// Type used to store each unique component list only once
struct Archetype {
ArchetypeId id;
Type type;
};
// Find an archetype by its list of component ids
unordered_map<Type, Archetype> archetype_index;
// Find the archetype for an entity
unordered_map<EntityId, Archetype&> entity_index;
// Find the archetypes for a component
using ArchetypeSet = unordered_set<ArchetypeId>;
unordered_map<ComponentId, ArchetypeSet> component_index;
  • How to store components
  • How to add/remove components from an entity

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store