Entity-entity relations 🌈

[alice-i-cecile]

Overview

Inspired by flecs, relations are a first-class graph primitive for the ECS: useful for modelling generalized hierarchies, graphs and so on in a safe, fast and ergonomic way by working with the ECS, rather than fighting it.

These have three main categories of benefits:

• Ergonomics: query for entities with specific relation types and iterate over the various relations
• Correctness: enforce critical logic invariants (such as "each child must have a parent" or "each child can only have at most one parent")
• Performance: operate more quickly, especially compared to naive hand-rolled implementations

Challenges

There are several critical challenges that need to be addressed by any design:

1. Performance: ECS is designed for random-order linear iteration
2. Serialization: entity ids are opaque and ephemeral
3. Ergonomics: there's a lot of interesting and important things you may want to do
4. Graph structure: how do you ensure that the rules of the graph that you want to represent are enforced upon creation, and stay correct as components and entities are added and removed. Some graphs may be directed, some may be symmetric, some may have edge weights, some may be acyclic, some may be trees, some may be forests...
5. Multiple edges from / to the same entity: this is an essential use case, but entities can (currently) only have one of each component type.

Possible paths forward

Essential universal tasks:

• Thoroughly benchmark existing tools and strategies for working with graphs of entities

Optional universal tasks:

• Allow entities to store multiple components with the same type #1527
• Investigate further optimizations for query.get()
• Allow Option<Entity> to use memory layout optimization #3022

Index-driven approaches:

• Create one or more reasonably performant graph-storing indexes
• Implement a complete, ergonomic indexes solution (see Fast Component Lookup-by-Value with Indexes #1205)

Broadly speaking, there are two paths to this design:

1. Index-based: Store the graph in a resource, keep that resource up to date. Use that resource to ensure constraints aren't broken, and enable fast look-up.
2. Baked-in: Reframe components as relations with no targets. Reshape the ECS to support relations as the first-class primitives.

In both cases, these implementations details would be hidden to the end user.
Ultimately, we want to build an API that broadly follows the one outlined in bevyengine/rfcs#18 if at all possible.

Atomic indexes

• Make the schedule less of a nightmare using Stageless: a complete scheduling overhaul rfcs#45
• Implement atomic groups ala Atomic schedule groups rfcs#46
• Implement a full indexing solution, using the automatically scheduled cleanup systems seen in Fast Component Lookup-by-Value with Indexes #1205.

Permissions and hook indexes

• Create a permissions and hooks framework, which only allows certain components to be accessed with the appropriate components, and can do cleanup work on component removal (see this early design doc)

Non-fragmenting relations

• Revive Entity Relations #1627
• Alter the internals so the indexes no longer fragment archetypes by default
• As a result, remove the ability to quickly filter by target

Related work and issues

This topic was discussed at great length in bevyengine/rfcs#18. The consensus there was that the feature was incredibly useful and desired, but the specific approach taken in #1627 was challenging to implement and review, and had serious non-local performance impacts due to the archetype fragmentation created.

Entity groups (#1592) reflects one possible use case of this feature.

#2572 covers a broad laundry list of complaints and limitations of the current frustrations with Parent-Child hierarchies, especially in the context of UI.

Kinded entities (#1634) are a very useful correctness feature when working with relations extensively, to help verify that you're pointing to the flavor of entity you think you are. They are probably blocked on #1481.

[nicopap]

This is relevant to bevyengine/rfcs#41 since the navigation system builds on a DAG stored in the ECS.

It might be an interesting starting point for discussions around the topic. Implementation can be a clue at what a system that relies heavily on relationships can look like https://github.com/nicopap/ui-navigation

I think relations could contribute to improving the ui-nav lib, for example:

• Enforce at compile-time DAG invariants that currently can only be explicited through doc strings and runtime asserts 😬
• Enforce that child/parents have specific components
• etc.

[TheRawMeatball]

The atomic indexes solution is not as viable as the other options because &mut World based editing could still trivially get broken state. While that could be acceptable for some use cases, I don't think it is for most.

[SanderMertens]

Was discussing an approach to relations in Bevy with @alice-i-cecile yesterday. Thought I'd post it here as it's not very complicated, and could be a quick way to get relations support.

Pros:

• doesn't create/fragment archetypes
• no overhead outside of relation API (no indices to keep in sync)
• supports constant time bidirectional lookups
• no linear searches in any of the operations
• could reuse same code for dynamic (runtime) tags

Limitations / TODOs:

• doesn't integrate with queries
• doesn't support relationships with data (tho possible to add with some effort)
• set/map lookups are constant time, but more expensive than regular components

The idea (in pseudo, I don't know Rust well enough):

// Simple relation implementation that uses entities to represent relation
// pairs like (Bevy, Bluebird).

// -- The data structures

// Builtin component type to store pair on pair entity
struct Pair {
  relation: entity, 
  target: entity 
};     

type pair = entity;     // For readability
type relation = entity; // For readability

map<pair, set<entity>> entities_for_pair;            
map<entity, map<relation, set<pair>>> pairs_for_entity;         
map<relation, map<entity, pair>> pairs_for_relation;
map<entity, map<relation, pair>> pairs_for_target;  

// -- Usage

fn find_or_create_pair(relation r, entity t) -> pair {
  let pair = pairs_for_relation[r][t];
  if (!pair) {
    pair = world.spawn().assign<Pair>(relation: r, target: t);
    pairs_for_target[t][r] = pair;
    pairs_for_relation[r][t] = pair;
  }
  return pair;
}

fn add_pair(entity e, relation r, entity t) {
  let pair = find_or_create_pair(r, t);
  entities_for_pair[pair].insert(e);
  pairs_for_entity[e][r].insert(pair);
}

fn has_pair(entity e, relation r, entity t) -> bool {
  let pair = find_or_create_pair(r, t);
  return pairs_for_entity[e][r].has(pair);
}

fn get_target(entity e, relation r, i32 index) -> entity {
  let pair = pairs_for_entity[e][r][index];
  if (!pair) return 0;
  return pair.get<Pair>().target;
}

fn find_for_pair(relation r, entity t) {
  let pair = find_or_create_pair(r, t);
  for e in entities_for_pair[pair] {
    // yield e
  }
}

fn find_for_relation(relation r) {
  for pair in pairs_for_relation[r] {
    let target = pair.get<Pair>().target;
    // yield find_for_pair(pair), target
  }
}

fn despawn_for_target(entity t) {
  // despawn children when despawning parent etc
  for pair in pairs_for_target[t] {
    for e in entities_for_pair[pair] {
      pairs_for_entity.erase(e);
      despawn_for_target(e);
      world.despawn(e);
    }

    // if target of pair is despawned, pair is
    // no longer valid, so delete it everywhere
    let pv = pair.get<Pair>();
    pairs_for_relation[pv.relation].erase(t);
    entities_for_pair.erase(pair);
  }
  pairs_for_target.erase(t);
}

fn remove_for_target(entity t) {
  // remove all pairs with target t
  for pair in pairs_for_target[t] {
    let pv = pair.get<Pair>();

    for e in entities_for_pair[pair] {
      pairs_for_entity[e][pv.relation].erase(pair);
    }

    pairs_for_relation[pv.relation].erase(t);
    entities_for_pair.erase(pair);
  }
  pairs_for_target.erase(t);
}

fn despawn_entity(entity e) {
  for pairs in pairs_for_entity[e] {
    for pair in pairs {
      entity_for_pairs[pair].erase(e);
    }
  }
  pairs_for_entity.erase(e);

  despawn_for_target(e);
  // or: remove_for_target(e) depending on what the
  // cleanup behavior of the relationship should be
}

[DrewRidley]

I think this post here provides a good reference as to why relationships would be important.
It also provides some implementation details that could be useful.

https://ajmmertens.medium.com/building-games-in-ecs-with-entity-relationships-657275ba2c6c

[Diddykonga]

Psuedo-Impl for Relations, as One Kind Struct, and Two (Entity/Component/System/Relation) Refs:

trait RelationKind;
struct RelationID(usize);
struct RelationRowID(usize);

enum ECSRRef {
    Entity(Entity),
    Component((Entity, ComponentID)),
    System(SystemID),
    Relation(RelationID, RelationRowID),
}

enum RelationRef {
    In(ECSRRef),
    Out(ECSRRef),
}

struct Relation<T : RelationKind> {
    kind: Option<T>,
    in: Option<ECSRRef>,
    out: Option<ECSRRef>,
}

struct RelationColumn {
    data: BlobVec, // Stores Relation<T : RelationKind>
    ticks: Vec<UnsafeCell<ComponentTicks>>, // Could be replaced with "Changed<T>" Relation
    refs: Vec<RelationRef>, // Lookup for all RelationRefs stored on this RelationColumn
}

struct RelationStorage {
    relations: SparseSet<RelationId, RelationColumn>, // RelationID is the T : RelationKind Type, which the user registers
    kind_index: HashMap<Blob, SparseSet<RelationID, Vec<RelationRowID>>>, // Index for RelationKind values
    ref_index: HashMap<Option<RelationRef>, SparseSet<RelationID, Vec<RelationRowID>>>, // Index for RelationRef values
}

Example:

fn foo() {
    let relation = RelationQuery<ChildOf>::in(in: Entity(specific_entity)).get_single();
    print!(relation.out); // Print specific_entity's Parent entity
}

fn main() {
    let app = ...
    let system = ...
    let system_two = ...
    let entity = ... 
    let entity_two = ...
    let component_type = ... // TypeOf: Name

    app.insert_relation<Changed<Name>>(kind: Changed<Name>::new(old_value: Name::new("old_name"), new_value: Name::new("new_name")), in: Component((entity_two, component_type)), out: None); // Insert an Changed<T> Relation that could allow change detection
    app.insert_relation<After>(kind: None, in: System(system), out: System(system_two)); // Insert an After Relation that can be used by the executor to run an System after another

    
    let relation : ECSRRef = app.insert_relation<Component<Name>>(kind: Name::new("Player"), in: Entity(entity), out: None); // Insert an Component<T> Relation that could allow an Entity to store Components
    app.insert_relation<Component<Name>>(kind: Name::new("Bevy"), in: relation, out: None); // Insert an Component<T> Relation that could allow an Entity to store an chain/graph of Components
    app.insert_relation<Shares>(kind: None, in: Entity(entity), out: Entity(entity_two)); // Insert an Shares Relation that could allow an Entity to share another Entity's Components
}

There are clear issues with this impl, but is still useful to convey the ideas of what relations can be.

[Zeenobit]

I've been working on an alternative implementation of entity relations as a product of trying to solve Kinded Entities:

#1634 (comment)

The comment provides more details. In summary, I believe entity relations and kinded entities are two interwoven solutions to the same set of problems (i.e. expressing relationships between entities in a safe and readable way).
I've solved this breaking the problem into two main chunks:

Component Links: https://gist.github.com/Zeenobit/c57e238aebcd4ec3c4c9b537e858e0df
Connections and the relation! macro: https://gist.github.com/Zeenobit/ce1f24f5230258d0cf5663dc64dc8f2b

[Zeenobit]

Using the implementation above, I think we can express entity relations in this way:

Some permutations that I think are possible:

1. relation! { * as Contained -> 1 Container }
2. relation! { 1 Container -> * as Contained }
3. relation! { 1 Container <-> * as Contained }
4. relation! { * Containable as Contained -> 1 Container }
5. relation! { 1 Container -> * Containable as Contained }
6. relation! { 1 Container <-> * Containable as Contained }

In English:

1. Many Entities (of any kind) may be Contained with respect to A Container. Each Contained Entity references its Container (Unidirectional).
2. Many Entities (of any kind) may be Contained with respect to A Container. Each Container references its Contained Entities (Unidirectional Reversed).
3. Many Entities (of any kind) may be Contained with respect to A Container. Both Container and Contained Entities reference each other (Bidirectional).
4. Many Containable Entities may be Contained with respect to A Container (Unidirectional).
5. Many Containable Entities may be Contained with respect to A Container (Unidirectional Reversed).
6. Many Containable Entities may be Contained with respect to A Container (Bidirectional).

So far, I've managed to get 3 and 6 working as a proof of concept.

Using the same logic, we could express 1-to-1 and many-to-many relationships as well:

1. relation! { 1 as Contained -> 1 Container }
2. relation! { 1 as Contained <-> 1 Container }
3. relation! { * as Contained <-> * Container }
4. ...

I suspect 1-to-1 and many-to-many relationships are a little more tricky though, just because I can't specialize an impl where two generic A and B are not the same, so Rust might get confused in trying to figure out which type is connectable to which other type.

[Zeenobit]

I've managed to get all of the following permutations functional:

    { 1 Container -> * Containable as Contained } DONE
    { 1 Container -> * as Contained } DONE
    { 1 Container -> * } DONE
    { * Containable as Contained -> 1 Container } DONE
    { * as Contained -> 1 Container } DONE
    { * -> 1 Container } IMPOSSIBLE
    { 1 Container <-> * Containable as Contained } DONE
    { 1 Container <-> * as Contained } DONE
    { 1 Container <-> * } IMPOSSIBLE
    { * Containable as Contained <-> 1 Container } DONE
    { * as Contained <-> 1 Container } DONE
    { * <-> 1 Container } IMPOSSIBLE

Full gist with examples/tests at the bottom for each case:
https://gist.github.com/Zeenobit/ce1f24f5230258d0cf5663dc64dc8f2b

Note: I haven't included any examples of how systems would use these relations. This is because everything is just components. Any system can query any term in a "relation clause" as a regular component. The user can also further extend each component to serve their specialized needs.

The implementation looks complicated, but it's mostly a lot of copy-pasted macro logic. I'm putting this here with the hopes that someone more experienced with macros can help with simplification and solving the 1-to-1, many-to-many and potentially even fixed capacity (i.e. 1-to-N) relations.

In the meantime, I'm planning to release Component Links and Entity Relations as separate crates. While I think integrating them into Bevy actual could make things more ergonomic, I also see benefits in having it be proven in the wild as a separate crate.

@alice-i-cecile Are there any objections to me using bevy_ecs_relation and bevy_ecs_link as crate names?

[alice-i-cecile]

In the meantime, I'm planning to release Component Links and Entity Relations as separate crates. While I think integrating them into Bevy actual could make things more ergonomic, I also see benefits in having it be proven in the wild as a separate crate.

I'm looking forward to seeing these experiments!

Are there any objections to me using bevy_ecs_relation and bevy_ecs_link as crate names?

Generally speaking, it's nicer to avoid using bevy in your crate names here, especially at the start. For example, my input crate is leafwing_input_manager. It's better to make it clear that it's for Bevy, not by Bevy.

[iiYese]

I think the items from this discussion would be appropriate to add under "universal tasks"?

[LegNeato]

TL;DR:

• Components are currently a special form of Entities (or, Entities are a base case of Components).
• Merge components and entities as a concept. Entities should have 0-N fields and be queryable.
• ECS users should create their own logical entity / node and edge / connection types that all have the same underlying structural/higher-kinded type.

---

When designing relations it is probably useful to learn from the most successful graph-based product in the world: Facebook. Here is an old paper with their TAO system: https://engineering.fb.com/2013/06/25/core-data/tao-the-power-of-the-graph/. And a blog post: https://engineering.fb.com/2013/06/25/core-data/tao-the-power-of-the-graph/. This API literally has not changed in over 10 years and powers all FB's products. It has been flexible enough to keep up with FB's product, storage, and query needs as they changed.

I think TAO's model maps well to Bevy concepts. The only difference is bevy is currently "decomposed" where instead of fields stored on an entity/object, the are stored on the component:

• Bevy
  • Entity --[Points to]--> Component --[Stores]--> Data
    • Example: Person Entity --[Points to]--> Name Component --[Stores]--> Name(String)
• TAO
  • Object --[Stores]--> Data
    • Example: Person Object --[Stores]--> Name(String)

But, FB's TAO has the concept of "Associations". In TAO you can selectively decompose object fields via associations (and most TAO objects do):

• TAO Object with field (before)
  • Object --[Stores]--> Data
    • Example: Person Object --[Stores]--> Name(String)
• TAO Object with association pointing to object with field (after)
  • Object --[Points to]--> Association --[Points to]--> Object --[Stores]--> Data
    • Example: Person Object --[Points to]--> Name Association --[Points to]--> Name Object --[Stores]--> Name(String)

There is an extra level of indirection in there vs bevy! Bevy's components are structurally the same as TAO Objects with fields:

• TAO Object with field
  • Object --[Stores]--> Data
    • Example: Person Object --[Stores]--> Name(String)
• Bevy Component
  • Component --[Stores]--> Data
  • Example: Name Component --[Stores]--> Name(String)

And TAO Objects are structurally similar to bevy Entities. So bevy components are entities with some data attached. They are a node, not an edge in the graph. They only act like an edge in bevy because they are hardcoded in the engine and the storage and query system encourages this thinking.

TAO's Associations as pointers between data are strictly more powerful than Bevy's Components as you can create your own connection types (and those can have data too!). Conversely, in bevy pointers between data (components) are a closed data model / type system.

So I think Bevy should step back and stop making Components "special" and instead have two types: Entities and Edges (name can be bikeshed here). ECS users can create typed Entities and typed Edges. And they are all nodes to the query and storage system.

[alice-i-cecile]

The dynamic queries API in #9774 will be a useful building block for relations.

[benfrankel]

The flecs link at the top of this issue is broken. I think the new link is https://www.flecs.dev/flecs/md_docs_2Relationships.html.

[ryo33]

I'd like to share my thoughts about entity relation, which I cannot find someone had mentioned. (I prefer "triple" for the term, and used it below.)

If using entity relation for representation of ai agents' knowledge, there are cases relation could also be an target of other relation. For example "my teammates
knows that I know the last position of the enemy". Notice, in this case, the know can target both objects and relations. To support the use-case, we need to keep the relation types also being a first class component in design. Although that, it's still convenient to have relation-kind in components.

Supporting both directional and bidirectional relation may lead extra complexity in implementation. Even If we don't support it, if the cost of using relations are cheap, we can express a bidirectional relation by a pair of directional relation like: "a key is linked to a door, and a door is linked to a key."

Wildcard querying can help garbage collection like things. For example, I'd like to record the reference frequency for triples and remove triples in less frequent access. It can emulate "forgetting". It can be done in a similar way as transform propagation. Instead, since I know all types that will be used in my game, I can maintain a pile of generics systems like forgetting<Know>, forgetting<Love>, forgetting<HasName>, but it's painful.

I'm staring to design queries and relation management systems, for my game and also for a library for general use. To me, the current design/implementation of Bevy ECS looks like already super powerful and beautiful, so I'm trying to figure a way to workaround the build-in relation feature. It might help designing of built-in one.

[SanderMertens]

@ryo33 These things have been discussed before:

1. is mentioned briefly at the end of https://ajmmertens.medium.com/why-it-is-time-to-start-thinking-of-games-as-databases-e7971da33ac3 (search for "theory of mind") and has been discussed on the Flecs Discord. There are a few proposed designs to support this. One is to have an entity with Relationship, Target and Source pairs that point to the different bits of information + some query syntactic sugar to make it nice.

2. Is the Symmetric relationship property: https://www.flecs.dev/flecs/md_docs_2Relationships.html#symmetric-property

3. Wildcard queries are a fundamental part of how relationship/hierarchy cleanup works.