Jan 31 2024 Hello Relations

Parent-Child Hierarchies

One classical example are parent-child relations. In a standard ECS, we could technically add a Parent component to each entity, which would contain a reference to the parent entity. This way we could build hierarchies and easily discover the parent of an entity simply by accessing its Parent component.

cubos.system("print parents")
     .each([](Entity entity, const Parent& parent) {
         CUBOS_INFO("Entity {} has parent {}", entity, parent.entity);
     });

But what if we wanted to find all children of a given entity? There are two possible solutions:

• Query all entities with a Parent component and check if their parent is the entity you're looking for.
• Add a Children component to each entity, which contains a list of references to all of its children.

The first option is very slow and inefficient, as it requires a full scan of all entities with a Parent component. The second option means having to store a heap allocated list of references in the component, ruining any cache locality you might have had. Not only that, you would also have to keep the Children component in sync with the Parent component, which is a pain to do.

Physics Constraints

Another use case we had trouble with at Cubos was physics constraints. Eventually we will want to add support for adding constraints between entities such as springs, hinges, etc. Where do we store the data for these constraints? For example, a spring constraint needs to store the two entities it's connecting, as well as the spring constant and rest length. One possible solution would be to represent the constraint itself as a separate entity which stores this data, and the references to the two entities it's connecting. This isn't a bad solution, but we can do better!

Collision Pairs

This was kind of the tipping point for us. The collision plugins works in two phases: broadphase and narrowphase.

The broadphase is collision shape agnostic - it doesn't care whether the entities are spheres, boxes, or whatever. If finds pairs of entities whose AABBs intersect. The narrowphase, on the other hand, is collision shape aware. It takes the pairs generated by the broadphase, and checks if the real shapes are actually colliding.

On our original solution, we stored the pairs generated by the broadphase in a resource (used to share data between systems), which the narrowphase systems then read. This meant filtering the pairs generated by the broadphase by shape, which was not only inefficient but also a mess to implement. Lots of code duplication and boilerplate, which makes it hard to read and maintain.

How does it look like?

Creating and removing relations is very similar to creating and removing components. We just pass one extra argument, which is the second entity in the pair.

commands.relate(alice, bob, ChildOf{});   // Alice is now a child of Bob
commands.unrelate(alice, bob, ChildOf{}); // Alice is no longer a child of Bob

But the real power of relations comes from querying them. We can query all relations of a certain type, and apply filters on both entities in the pair.

cubos.system("access car wheels")
     .each([](const Wheel& wheel, const ChildOf&, const Car& car) {
         // Do something with the wheel and its parent car.
     });

The query above, for example, will match all pairs of entities where the first entity has a Wheel component, the second entity has a Car component, and the first entity is a child of the second entity.

This also allows us to write the narrowphase collision checks in a much more elegant manner:

cubos.system("box vs sphere")
     .each([](const Box& box, const PotentiallyCollidingWith&, const Sphere& sphere) {
        if (shapesIntersect(box, sphere))
        {
            // Do something with it.
        }
     });

We also allow the user to customize the behavior of relation types with two extra options:

• Symmetry: Whether the relation type is symmetric or not.
• Tree: Whether instances of the relation type should form a tree.

Symmetry is particularly important for collision relations. While the direction of some relations, such as ChildOf, matter, the direction of others, such as CollidingWith, should not. For example, a relation between foo and bar will also be identifiable through bar and foo.

Tree relations are used to specify that each entity can only have at most one outgoing instance of that relation type, and that cycles are not allowed. This is useful for parent-child relations: cmds.relate(a, b, ChildOf{}) would remove any previous relations of type ChildOf from a to other entity.

This is great, but how do we store these relations tightly in memory while also allowing for fast queries?

Sparse Relation Tables

Instead of touching the archetypes, we store relations in separate tables, which we call sparse relation tables. Each sparse relation table stores all relations of a given type whose entities belong to a given pair of archetypes

We store relations in separate tables. For each pair of archetypes and relation type, we create a table which stores all relations of that type between entities in those archetypes. With the entities of the previous example, we would get only two archetypes:

The relations would be stored in two separate tables: one for relations between archetype A and archetype B, and another for relations between archetype B and B.

This means that to query over a given relation, we just need to find all sparse relation tables for that relation type, and whose archetypes match the query filters. This result, once again, can be cached. Feel free to take a look at the code on GitHub if you're interested in the details!

Symmetric Relations

Implementing symmetric relations was actually really easy. On all operations, we simply sort the entities in the pair by their ID, such that the entity with the lowest ID is always the first one. This way, we can guarantee that the same relation will always be stored in the same table, regardless of the order in which the entities are passed to the operation.

It also took some tuning on the query side to look for both orders of the pair, but it didn't take much effort.

Tree Relations

Tree relations were a bit trickier to implement. The main issue was wanting to provide a fast way to perform BFS on the tree. Allowing traversal from top to bottom or bottom to top would allow us to easily implement parent-child transform updates, and I wanted to make sure that the components were laid out in memory in a way that would allow for fast traversal.

To achieve this, I changed the sparse relation tables to not only be indexed by type and archetype pair, but also by their depth. Relations are then stored in the table corresponding to the depth of their destination entity. For example, parent-child relations whose parent has no parent are stored at depth 0, and relations whose parent has a parent but no grandparent are stored at depth 1.

To traverse the tree from bottom to top or vice versa we just need to store the cached sparse relation tables by their depth, and voila!