What are the ways to implement many-to-many relations?

[definability]

I started trying EnTT and quickly got stuck on this question.

The problems:

1. Given a binary relation R and an entity a, traverse all such b that aRb (get all b related to a via R).
2. Given entities a and b, find out whether aRb (whether they are related via relation R).
3. Given two binary relations, X and Y, and an entity a, traverse all such b that aXb and all such c that bYc.

Examples:

1. Fetch all friends of a to generate a phone book or fetch all skills of a to create a CV.
2. Entities a and b meet on the game field. Decide whether they are enemies or not to determine whether we need to initiate a fight.
3. A company a employs contractors through relationship X, and contractors have skills defined by Y. To assign suitable jobs, fetch contractors b via aXb and fetch their skills c via bYc.

The problem may be that I am trying to address ECS as a relational database, which is evidently wrong. Should I reimagine the application architecture or use another ECS paradigm?

Below, I share the potential solutions I found.

Relations as Components

To my understanding, the most efficient and idiomatically correct way to represent relations is through components. Nonetheless, I am unsure how to use this method correctly for relations generated at runtime, so I need help with the questions below.

Storage

There are multiple discussions concerning this matter, and this approach seems to be the most promising:

• Emplace/view components with the same type BUT with different id in runtime. #475
• Runtime Tag #607
• Multiple components of the same type as separate #869
• One entity with multiple 'same' type components #961

After reading ECS back and forth, Wiki on entt::storage, and discussions, I did not understand some details. It appears I should read Beam me up, registry about entt::registry::storage template member function instead. As I understand, storage is a sparse set, like any other row in the registry, so adding another one is the same as adding another component.

Is it okay to make a Component with entt::storage as a member? This implies a scarier question: Is having multiple storage units for each entity involved in many-to-many relations alright?
Here is an example (you can try it at https://godbolt.org/z/jnE95noxn):

#include <entt/entt.hpp>
#include <iostream>
#include <string>

using entt::operator ""_hs;

template<typename Component>
struct Multiple
{
    entt::storage<Component>& storage;
};

struct Friend
{
};

// Create specific entities and their relations
void create(entt::registry& registry)
{
    auto&& pc = registry.create();
    auto&& person = registry.create();
    auto&& cat = registry.create();

    registry.emplace<std::string>(pc, "PC");
    registry.emplace<std::string>(person, "Person");
    registry.emplace<std::string>(cat, "Cat");

    auto&& personFriendship = registry.emplace< Multiple<Friend> >(person, registry.storage<Friend>("Person friends"_hs));
    personFriendship.storage.emplace(pc);
    personFriendship.storage.emplace(cat);

    auto&& pcFriendship = registry.emplace< Multiple<Friend> >(pc, registry.storage<Friend>("PC friends"_hs));
    pcFriendship.storage.emplace(person);

    auto&& catFriendship = registry.emplace< Multiple<Friend> >(cat, registry.storage<Friend>("Cat friends"_hs));
    catFriendship.storage.emplace(cat); // what did you expect?
}

int main()
{
    entt::registry registry;
    create(registry);
    registry.view< Multiple<Friend> >().each([&](auto&& entity, auto&& friends) {
        entt::basic_view view{friends.storage};
        view.each([&](auto&& friendlyEntity, auto&& relation) {
            std::cout << registry.get<std::string>(entity) << " befriends " << registry.get<std::string>(friendlyEntity) << '\n';
        });
    });
    return 0;
}

Pros:

• the approach only uses EnTT data structures;
• for any a, we can find all related b efficiently;
• for given a and b, we can easily check whether aRb;
• traversing all pairs that belong to aRb is efficient: view< Multiple<Friend> > and go through the friends container;
• traversing a composition of relations seems to be easy as well (mind the contractors example):
  • fetch all entities having Multiple< Employee > component — we will treat the entities as companies;
  • for each company, go through the list of employees just like we traversed the list of friends in the example above;
  • for each employee, go through the list of skills they have;
  • for each skill, check whether it is required for the current building task;
  • profit!

Cons:

• finding all a for b in aRb relations needs storing the reverse edges, which may multiply the memory use by two;
• higher chances of container key collision (consider birthday paradox, entity amount, and hash size);
• performance concerns: Is EnTT designed to handle so many components?

Tags

Sometimes, compile-time tags can remove some b in aRb relations.

For example, if R is a mastery with a specific type of materials, use template<auto... item> Skill { int level; };.
Hence, an entity may have a lot of skills like Skill<SkillType::cut, Material::wood, WoodSpecies::pine, Colour::red>, Skill<SkillType::cook, Material::eggs>, Skill<SkillType::sing, SongGenre::opera, OperaStyle::loudly>.

Pros:

• each component is unique;
• comonent access is quick;
• unused components do not use space.

Cons:

• the management may be complicated because of template syntax;
• some relations cannot be implemented this way — for example, usually, friendship is a many-to-many relationship between entities.

Relations as Entities

SQL-like approach, where relations are modelled as joining links. However, we can find elements efficiently by indexed fields in SQL, which does not seem to be the case in generic EnTT. Or am I missing something?

Also, as I understand, you should implement a listener for registry.on_destroy<entt::entity> to handle the relations associated with the recycled entities.
This issue is also true for Fleks (another ECS framework), which provides an API for relations, but

[...] archetypes aren’t cleaned up when an entity used in a pair is deleted.

https://ajmmertens.medium.com/a-roadmap-to-entity-relationships-5b1d11ebb4eb#5d41

Linked list

The idea is described in https://skypjack.github.io/2019-06-25-ecs-baf-part-4.
Its application of traversing chains of entities is discussed in #1056.

The general idea is to store the pointers to the other relations in the relation.

struct R
{
  entt::entity a;
  entt::entity b;

  // previous relation in the relation list of a
  entt::entity previous_a{entt::null};
  // previous relation in the relation list of b
  entt::entity previous_b{entt::null};
  // next relation in the relation list of a
  entt::entity next_a{entt::null};
  // next relation in relation list of b
  entt::entity next_a{entt::null};
}

Also, store a pointer to the last relation in the entities.
For example, through a component

struct HasR
{
    entt::entity relation{entt::null};
}

Thus, by multiplying twice the storage required by relations, we achieve a zero overhead in terms of the get operations needed to traverse the relations.

If we want to find out whether aRb exists, we should go through all relations of a``, which is inefficient.

Mark and Propagate

A mix of ideas from Part 4, insights - Hierarchies and beyond and #1062 for fetching chains of entities through relations.

Implement simple relations:

struct R
{
    entt::entity a;
    entt::entity b;
};

1. Create two tag classes: Dirty and StillDirty.
2. Go through all relations X and add component Dirty to all suitable entities b.
3. Go through all relations Y and add component StillDirty only to such b that have Dirty.
4. Repeat for as many relations as needed.
5. Remove the penultimately assigned tag. In the case of two relations, do registry.clear<Dirty>().
6. Visit all entities you need via registry.view<StillDirty>().each.
7. Remove the left tag: registry.clear<StillDirty>().

Becomes less and less efficient if there are more relations than dirty entities.

Sort and Binary Search

Implement simple relations:

struct R
{
    entt::entity a;
    entt::entity b;
};

Use the tutorial, sections Sorting: is it possible? and Iterators:

1. Sort the required relations when they change:

   registry.sort<R>([](const R &lhs, const R &rhs) {
     return lhs.a < rhs.a or lhs.b < rhs.b;
   });

2. Use std::lower_bound to find the first relation that contains the required entity in log N.
3. Go through the relations containing the required element until you meet the relation containing the unsuitable a.

Pros:

• minimum memory overhead: you have a single component for each type of relation;
• custom N-ary relation is possible;
• far more efficient than linear search in an unordered storage (brute force).

Cons:

• slower than "reverse" brute force when the relations are added or removed frequently.

Is there an efficient (O(log N)) method of inserting an entity into sorted entt::storage that preserves the sorting?

Brute Force

Implement simple relations:

struct R
{
    entt::entity a;
    entt::entity b;
};

Naïve solution. Just for prototyping:

void f(entt::entity a)
{
    registry.view<R>.each([&](auto r)
    {
        if (r.a == a) process(a, r);
    });
}

Reverse Brute Force

Discussed in #1062.

Implement simple relations:

struct R
{
    entt::entity a;
    entt::entity b;
};

If you use ECS, you probably want to process multiple entities with shared traits.
Thus, a may not be the only entity related by R we want to process:

registry.view<R>.each([&](auto r)
{
    if (predicate(r.a)) process(r.a, r);
    if (predicate(r.b)) process(r.b, r);
});

[skypjack]

Yet another option, which is the closest one to the good old OOP design, is to enable pointer stability for the relation type.
In this case, you can have a reltype* parent member for a link to the root, and an std::vector<reltype *> children for the list of children.
Unless you have a measurable performance hit around it (and this is unlikely to happen, especially if compared to the other solutions), this is a pretty handy approach imho.
If it looks like a typical tree now, similar to a scene tree or something like that, that's because it is. Have you considered it already?

[definability]

@skypjack, I am currently only planning to use them, so my question may seem theoretical. The use cases I am curious about are:

1. Linear iterations: Given a binary relation R and an entity a, traverse all such b that aRb (get all b related to a via R).
2. Random access: Given entities a and b, find out whether aRb (whether they are related via relation R).
3. Folded linear iterations: Given two binary relations, X and Y, and an entity a, traverse all such b that aXb and all such c that bYc.

I plan to have more linear iterations than random access.

[skypjack]

All this talk about relationships makes me think of pointer stability. Why not just enable it and simply keep cross-references between items of interest? I don't think there's a faster way to establish relationships, and work with them too (check, traverse, and so on). Have you considered this option already?

[definability]

just enable it and simply keep cross-references between items of interest

Do you mean adding components that hold STL/Abseil containers with pointers to related entities and check their existence on each access? Yes.
I was unsure whether this was an idiomatically correct approach because I am totally new to the ECS paradigm, which is why I thought about trickery with registries.
It looks like using ordinary containers, checking entities they point to manually, and destroying containers when their hosting entities are destroyed is indeed a clean solution. Thanks!

[skypjack]

I was talking about enabling pointer stability for certain components in EnTT (it's a feature of the ECS layer).
You can have something like this at the end of the day:

struct tree_node {
    tree_node *parent;
    std::vector<tree_node *> children;
    // ...
};

And with the right destructor(s), it's easy to keep things in sync and cleanup them eventually.
In this way, an entity points to its companions and their components directly.