Skip to content

Instantly share code, notes, and snippets.

@SanderMertens
Last active March 29, 2022 21:06
Show Gist options
  • Save SanderMertens/18be89a5cfdf7faa6aef8adfa19a1869 to your computer and use it in GitHub Desktop.
Save SanderMertens/18be89a5cfdf7faa6aef8adfa19a1869 to your computer and use it in GitHub Desktop.
// Summary of Flecs data structures
// This is a non-exhaustive overview of flecs datastructures. Things have been ommitted/have different names for clarity.
// --- DATASTRUCTURES
// A sparse set is a map-like structure that guarantees O(1) lookup times (as opposed to O(1) on average for maps) at the cost of
// requiring more RAM (more info on the general idea of sparse sets: https://www.geeksforgeeks.org/sparse-set/)
struct ecs_sparse_t { };
// A map is a structure that allows for O(1) lookups on average (similar to an std::unordered_map). The map only supports
// uint64_t keys and uses a bitshift as hashing function.
struct ecs_map_t { };
// --- CORE TYPES
// An entity id is a 64 bit id
typedef uint64_t ecs_entity_t;
// An ecs_id_t encodes an id that can be added to an entity. For regular components this is the same as the entity id for
// that component, for relations the id can encode up to 2 component ids.
typedef uint64_t ecs_id_t;
// --- TABLE (ARCHETYPE) TYPES
// A storage contains the array with component data. The component data array is type erased, as the ECS cannot know
// about application types beforehand.
struct ecs_storage_t {
vector<T> component_data;
};
// Edge in the table graph that allows for finding the next table in an add/remove operation in constant time
struct ecs_table_edge_t {
ecs_table_t *add; // The table with the component added
ecs_table_t *remove; // The table with the component removed
};
// A table is the Flecs implementation of an archetype. It stores component data for all entities with a certain combination
// of components.
struct ecs_table_t {
int32_t table_id;
vector<ecs_id_t> type; // Array with component ids
vector<ecs_entity_t> entities; // Array with entity ids in table
vector<ecs_storage_t> columns; // Component data. Each component has its own array (SoA)
map<ecs_id_t, ecs_table_edge_t> edges; // Traverse to the next table by adding/removing a component
};
// --- ENTITY LOOKUP STRUCTURES
// This type is used to keep track of where an entity is stored
struct ecs_record_t {
ecs_table_t *table; // The table where the entity is stored
int32_t row; // The row (index in the component arrays) where the entity's data is
};
// The entity index makes it possible to find where an entity is stored from its entity id
ecs_sparse_t<ecs_entity_t, ecs_record_t> entity_index;
// --- TABLE LOOKUP STRUCTURES
// An id record stores a map with all tables for a specific component id
struct ecs_id_record_t {
map<table_id, ecs_table_record_t> table_index;
};
// A table record is used to find where in a table a component is stored
struct ecs_table_record_t {
int32_t column; // The column of the id (component) in the table
};
// The id index enables finding all tables for a given component id
map<ecs_id_t, ecs_id_record_t> id_index;
// --- COMMON OPERATIONS
// Test if entity "e" has component "comp"
ecs_record_t *r = entity_index[e];
ecs_id_record_t *idr = id_index[comp];
ecs_table_record_t *tr = idr->table_index[r->table->id];
return tr != NULL;
// Get component "comp" for entity "e"
ecs_record_t *r = entity_index[e];
ecs_id_record_t *idr = id_index[comp];
ecs_table_record_t *tr = idr->table_index[r->table->id];
return r->table->columns[tr->column].component_data[r->row];
// Test if entity "e" has pair (Likes, Apples)
ecs_id_t pair = ecs_pair(Likes, Apples);
ecs_record_t *r = entity_index[e];
ecs_id_record_t *idr = id_index[pair];
ecs_table_record_t *tr = idr->table_index[r->table->id];
return tr != NULL;
// Test if entity "e" has pair (Likes, *)
ecs_id_t pair = ecs_pair(Likes, EcsWildcard);
ecs_record_t *r = entity_index[e];
ecs_id_record_t *idr = id_index[pair];
ecs_table_record_t *tr = idr->table_index[r->table->id];
return tr != NULL;
// Find all instances of pair (Likes, *) for entity "e"
ecs_id_t pair = ecs_pair(Likes, EcsWildcard);
ecs_record_t *r = entity_index[e];
ecs_id_record_t *idr = id_index[pair];
ecs_table_record_t *tr = idr->table_index[r->table->id];
for (i = tr->column; i < (tr->column + tr->count); i ++) {
yield r->table->type[i];
}
// Find all entities for component "comp"
ecs_id_record_t *idr = id_index[comp];
for (table : idr->table_index) {
for (e : table->entities) {
yield e;
}
}
// Find all entities for components "pos, vel"
ecs_id_record_t *idr_pos = id_index[pos];
ecs_id_record_t *idr_vel = id_index[vel];
for (table : idr_pos->table_index) {
if (!idr_vel->table_index.has(table->id)) {
continue;
}
for (e : table->entities) {
yield e;
}
}
// Find all entities for wildcard (Likes, *), (Eats, Apples)
ecs_id_t pair_likes = ecs_pair(Likes, EcsWildcard);
ecs_id_t pair_eats = ecs_pair(Eats, Apples);
ecs_id_record_t *idr_likes = id_index[pair_likes];
ecs_id_record_t *idr_eats = id_index[pair_eats];
for (table : idr_likes->table_index) {
if (!idr_eats->table_index.has(table->id)) {
continue;
}
for (e : table->entities) {
yield e;
}
}
// Delete all entities with (ChildOf, parent)
ecs_id_t pair_childof = ecs_pair(EcsChildOf, parent);
ecs_id_record_t *idr_childof = id_index[pair_childof];
for (table : idr_childof->table_index) {
delete(table);
}
id_index.erase(pair_childof);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment