2026-04-15
ECS or entity component systems are widely talked about in game dev. circles as well as many other data modelling problems in which the combinatory nature of OOP hierarchies becomes burdensome. It is lauded for its clean separation between data and behavior, its ability to maintain cache locality owing to SoA techniques, etc.
One thing ECS is not praised for, at least very loudly, is the
relative difficulty of expressing many-to-many or similar types of
relations. For binary relations it is possible. Say \(S\) is some binary relation, then an entity
may have a component L which is, say, a list of all
entities that are to the left of it under \(S\), and similarly for R. For
ternary relations, this already becomes unmanageable.
One solution to this comes by realizing that a component store, which
is essentially nothing more than a way of mapping entity IDs to the
component value they may or may not have, is in fact a subcase of
allowing values depend not on the entity ID itself, but an n-tuple of
entities. It’s is a T-valued (unary, in the case of
components) relation.
By building the appropriate indices, it is possible to iterate these
efficiently while keeping both the tuples and the values of
T contiguous. Moreover this affords us a richer query
ability, almost like a relational database.
A minimally thought out, thoroughly untested-and-unverified-but-compiling™ reference implementation follows, distributed under GPLv3 or later:
struct ID {
size_t index {0}, generation {0};
constexpr operator bool() const noexcept {return index != 0;}
constexpr auto operator <=>(ID const&) const noexcept = default;
};
template <typename T, size_t N>
class Relation {
public:
static constexpr size_t arity = N;
using index_t = std::array<ID, N>;
using value_t = T;
using p_set_t = std::unordered_set<size_t>;
using table_t = std::unordered_map<ID, p_set_t>;
struct Proj {
ID value;
size_t i;
};
private:
std::vector<index_t> m_indices;
std::vector<value_t> m_values;
std::array<table_t, N> m_tables;
std::set<size_t> m_free_slots;
template <typename IndexRange>
auto m_collect(IndexRange&& ir) const noexcept {
std::vector<index_t> list;
for (size_t index: ir) if (index < m_indices.size())
list.push_back({m_indices[index], m_values[index]});
return list;
}
template <size_t K>
p_set_t m_fiber(std::array<Proj, K> const& projs) const noexcept {
if constexpr (K == 0)
return p_set_t{};
std::vector<p_set_t const*> positions(K);
for (size_t i = 0; i < K; i++) {
auto [id, index] = projs[i];
if (m_tables[index].contains(id))
positions[i] = &m_tables[index].at(id);
else
return p_set_t{};
}
std::sort(positions.begin(), positions.end(), [](auto* lhs, auto* rhs){
if (lhs == nullptr)
return true;
if (rhs == nullptr)
return false;
if (lhs->size() < rhs.size())
return true;
else
return false;
});
p_set_t result = positions[0];
for (size_t i = 1; i < K; i++) {
if (result.empty()) break;
std::erase_if(result, [&](size_t offset){
return not positions[i]->contains(offset);
});
}
return result;
}
static T& nil() {
static T t {};
t = T{};
return t;
}
public:
auto items() const noexcept {
return m_collect(std::views::iota(0, m_indices.size()));
}
template <typename... Projs>
auto fiber(Projs&&... projs) const noexcept {
std::array<Proj, sizeof...(Projs)> _proj {
Proj(std::forward<Projs>(projs))...
};
return m_collect(m_fiber(_proj));
}
bool contains(index_t const& tpp) const noexcept {
std::array<Proj, N> projs;
for (size_t i = 0; i < N; i++)
projs[i] = Proj {.value = tpp[i], .i = i};
return m_fiber(projs).empty() == false;
}
T const& operator[](index_t const& tpp) const noexcept {
if (not contains(tpp))
return nil();
std::array<Proj, N> projs;
for (size_t i = 0; i < N; i++)
projs[i] = Proj {.value = tpp[i], .i = i};
auto this_fiber = m_fiber(projs);
assert(this_fiber.size() == 1);
size_t index = *this_fiber.begin();
return m_values[index];
}
T& operator[](index_t const& tpp) noexcept {
return const_cast<T&>(std::as_const(*this)[tpp]);
}
template <typename... Args>
T& set(index_t const& tpp, Args&&... args) {
if (contains(tpp))
return (*this)[tpp] = T(std::forward<Args>(args)...);
size_t slot;
if (not m_free_slots.empty()) {
slot = *m_free_slots.begin();
m_free_slots.erase(m_free_slots.begin());
m_indices[slot] = tpp;
m_values [slot] = T(std::forward<Args>(args)...);
} else {
slot = m_indices.size();
m_indices.push_back(tpp);
m_values.emplace_back(T(std::forward<Args>(args)...));
}
for (size_t i = 0; i < N; i++)
m_tables[i][tpp[i]].insert(slot);
return m_values[slot];
}
void del(index_t const& tpp) {
std::array<Proj, N> projs;
for (size_t i = 0; i < N; i++)
projs[i] = Proj {.value = tpp[i], .i = i};
auto fib = m_fiber(projs);
for (size_t i = 0; i < N; i++) for (auto p : fib) {
m_tables[i][tpp[i]].erase(p);
m_values[p] = T{};
m_free_slots.insert(p);
}
}
};
template <typename... Relations>
class Scene: Relations... {
template <typename Relation>
Relation const& as() const noexcept {
return static_cast<Relation const&>(*this);
}
template <typename Relation>
Relation& as() noexcept {
return static_cast<Relation&>(*this);
}
std::vector<std::function<void(void)>> m_pending;
std::vector<size_t> m_generations;
std::set<size_t> m_free_indices;
size_t m_next_id{0};
ID allocate_id() {
size_t index;
if (m_free_indices.empty()) {
index = m_generations.size();
m_generations.push_back(0);
} else {
index = *(m_free_indices.begin());
m_free_indices.erase(m_free_indices.begin());
}
return ID {index, m_generations[index]};
}
public:
ID sched_create() {
ID id = allocate_id();
m_pending.push_back([this]{
;
});
return id;
}
bool exists(ID id) const noexcept {
if (id.index >= m_generations.size())
return false;
return m_generations[id.index] == id.generation;
}
void sched_destroy(ID id) {
m_pending.push_back([this, id]{
if (not exists(id))
return;
m_generations[id.index] += 1;
m_free_indices.insert(id.index);
auto fn = [&,this]<typename Relation>{
auto& R = as<Relation>();
for (size_t i = 0; i < R.arity; i++) {
auto fiber = R.fiber({.value = id, .i = i});
for (auto& tpp : fiber)
R.del(tpp);
}
};
(..., fn.template operator()<Relations>());
});
}
template <typename Relation, typename... Args>
void set(Relation::index_t const& tpp, Args&&... args) {
using T = Relation::value_t;
m_pending.push_back([this, tpp, t = T(std::forward<Args>(args)...)]{
auto& R = as<Relation>();
R.set(tpp, std::move(t));
});
}
template <typename Relation>
void del(Relation::index_t const& tpp) {
m_pending.push_back([this, tpp]{
auto& R = as<Relation>();
R.del(tpp);
});
}
template <typename Relation>
auto const& get(Relation::index_t const& tpp) const noexcept {
return as<Relation>()[tpp];
}
template <typename Relation>
auto & get(Relation::index_t const& tpp) noexcept {
return as<Relation>()[tpp];
}
template <typename Relation>
bool contains(Relation::index_t const& tpp) const noexcept {
return as<Relation>().contains(tpp);
}
template <typename Relation, typename... Projs>
auto fiber(Projs&&... projs) const noexcept {
return as<Relation>().fiber(std::forward<Projs>(projs)...);
}
void update() {
auto pending = std::move(m_pending);
for (auto& fn: pending)
fn();
}
};
template <typename T>
using Component = Relation<T, 1>;A better implementation would probably include special case handling
for the IDs of index 0, by adding a nil conceptual object
and using it to guard against invalid access. We already have nil values
for relations, so adding the nil entity would be natural.
Other ideas would be adding support for fibers operations, like table joins/pullbacks. One thing I do think is interesting to note is that, being non-polymorphic, we can pass any relation-looking thing into a Scene type, including further specializations of that interface.
It’s not hard to imagine how to wrap a
Relation<T, 2> in a class
Bijection<T> or Symmetric<T>,
Transitive<T>, etc. All you need to do is to ensure
the invariants, and you don’t need polymorphism because the actual type
is being used, rather than inheritance.