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
}