A case for implementating relationships

[DaedieGit]

Hi,

I've been using entt to implement a development tool. My (currently hypothetical) users will interface with a thin layer that is built on top of entt (but is analogous in use). Overal I've been happy with how things are shaping up, with the exception of offering relationship support. Currently I use the approach that is recommended by entt (the one that uses linked list logic). Functionally, it works, but I have some issues with it:

1. Manual data-structure management. Because I'm pretty much implementing a data structure on top of a data structure, a lot of manual administration needs to be done from the user side. Additionally, because of the strong typing style of programming that is used, the user will either have to reïmplement the logic repeatedly, or I have to provide some scaffolding for them in the form of a template struct to wrap around their type and some interface. But neither of these are quite as smooth as I'd like.
2. By having to navigate the relationship structure through sibling/parent/child entities, a lot of unnecessary indirection is imposed.

My idea started as basically the linked list approach, but moving it into the storage. But after iterating on this for a while I came up with this:

I will be using relationship terminology like this: subject object

A regular component storage looks something like this:

{
    sparse_indices
    entity_array
    components
}

The most general implementation (many-to-many relationship) would look something like this:

{
    sparse_subject_indices
    subject_entity_array
    subject_nexts
    subject_prevs
    relationships
    object_entity_array
    object_nexts
    object_prevs
    sparse_object_indices
}

At first glance, this might seem like a lot, but all of the new arrays will have identical capacity and sizes to entity_array. Which means you can optimize for space usage very well. Also, you can have variations on this for one-to-one and one-to-many relationships that will be more compact. the nexts and prevs could also be combined into 1 data-structure. I'm not entirely sure what would be most efficient.

The way it works is that you can add the same "component" multiple times to the same (subject) entity but with multiple object entities. when the component is added for the first time, the corresponding entry in nexts and prevs is the null-index. Following components will add the index of the second component in the nexts-field corresponding to the first component, etc. The rest is analogous.

Iterating these requires some expansion of the view. Adding extra type lists for these newly introduced mechanisms, next to the included and excluded components. Due to template specialization, the current implementations can remain intact.

Iteration of one-to-one and one-to-many relationships would be identical to components, but instead of just passing in a reference to the data, you pass in a struct that contains a reference to the data and the "other" entity.

Iteration of many-to-one and many-to-many is a bit more complicated. My current idea is that the outer loop would acquire the regular components for each entity (like now) and there would be an inner-loop that iterates all the different relationships for that entity, the data of the regular components would be passed to the lambda repeatedly.
Dealing with multiple relationships in a single query is ambiguous I think. Currently, my idea is to allow only a single multi-entity query in a single view. one-to-one, one-to-many could remain multiple.

[skypjack]

Ehi, sorry for the late reply, I was out on vacation. 🙂

Currently I use the approach that is recommended by entt (the one that uses linked list logic)

🤔 EnTT doesn't recommend anything actually. This is one of the possible approaches to the problem though.
I'm not even sure I would use it nowadays. I mean, it works and it fits some cases. On the other hand, I feel like a more compact entityx-like storage also works and is probably a good compromise in many others. Maybe it's time to think about it and spawn a few specializations for the purpose in EnTT? 🤔

But after iterating on this for a while I came up with this:

I'm not sure about the goal of this discussion, sorry. Are you suggesting a possible implementation or asking for a feedback on this approach?
I've seen few ideas around relationships so far and none of them I liked. I don't think using relationships with no data or blowing up memory and number of jumps is really a solution. Have you already analyzed the complexity of this solution? Can you give me some data?
I can't get a very clear idea on the spot but it doesn't seem very different from the one suggested by EnTT, am I wrong?

[DaedieGit]

Ehi, sorry for the late reply, I was out on vacation. 🙂

Currently I use the approach that is recommended by entt (the one that uses linked list logic)
🤔 EnTT doesn't recommend anything actually. This is one of the possible approaches to the problem though. I'm not even sure I would use it nowadays. I mean, it works and it fits some cases. On the other hand, I feel like a more compact entityx-like storage also works and is probably a good compromise in many others. Maybe it's time to think about it and spawn a few specializations for the purpose in EnTT? 🤔

I was referring to the proposed solution for representing hierarchies on the wiki:
https://github.com/skypjack/entt/wiki/Crash-Course:-entity-component-system#hierarchies-and-the-like

Could you elaborate a little bit on the entityx-like aproach? I'm not familiar with the implementation details of the library.

But after iterating on this for a while I came up with this:

I'm not sure about the goal of this discussion, sorry. Are you suggesting a possible implementation or asking for a feedback on this approach?

It's meant as a pitch for a possible implementation of relationships inside entt. In a way that I felt could be a good fit for the library as it has very similar characteristics with regards to memory usage/layout and time complexity. Though feedback is very much appreciated as well.

I've seen few ideas around relationships so far and none of them I liked.

Same here, which was sort of the trigger for me to try and come up with some options.

I don't think using relationships with no data or blowing up memory and number of jumps is really a solution.

I would like to contest this notion. If we assume the linked list approach from the wiki is a sound solution using the regular component storage, my suggested implementation offers similar memory use and potentially improved performance due to internal optimizations (I say potentially , because I can only really know for sure by measuring an actual implementation).

I'm not sure what you mean by no data. This solution allows for arbitrary data to be associated with the relationship (including empty types), just like with regular components.

Have you already analyzed the complexity of this solution? Can you give me some data?

To some extent. Though there are some possibilities for trading some more memory for performance and vice versa.

This is based on a one-to-many implementation, as I feel it is the most useful variant.

Adding a new relationship is either O(n) where n is the number of relationships already assigned to an entity, or O(1) if you store the index of the last link as well (not currently in my aforementioned solution, but probably recommended?).
It is basically the same as a component, but we add 2 entities instead of one, emplace an element to the next/prev vector and change an entry in said vector(s).
Destroying a relationship is O(1).
To be fair, adding and destroying relationships is relatively expensive to adding and destroying a component, but still quite fast and the least common operations in an engine. additionally, if we use multiple components (2) to represent a relationship (see below), the difference becomes neglible.

Performing a get(Entity entity) (either subject or object) is identical to regular components.

Iteration:
For regular (in memory order) iteration, we iterate 3 vectors (Entity, Relationship, Entity) instead of 2 (Entity, Component), the same benefits of empty type optimization apply. Alternatively, you might want to support alternative means of iteration (ie. tree traversal), this will look somewhat similar to the approach on the wiki I referenced earlier, but faster because some optimization is possible here.

checking for the presence of an entity in a storage when iterating multiple types is identical to components.

I can't get a very clear idea on the spot but it doesn't seem very different from the one suggested by EnTT, am I wrong?

It is, which is sort of the premise of the solution. The difference is that it's integrated in the library which simplifies implementation for the user. For instance, if I have a relation for attacking (for combat between entities). I could have an Attacking component, which allows me to request entities that are attacking others, but if I want to know if entity x is being attacked without running through all my Attacking components, I need to implement a component for the reverse relationship as well and maintain the dual administration.

In my proposed solution, I only need something like an Attacking relationship and I can request the information from either side of the relationship at the same speed as I would a regular component.

I hope that made sense, my brain is only partially functional at this hour :P.

[skypjack]

Could you elaborate a little bit on the entityx-like aproach?

Oh, just something that's been buzzing in my head for a while and I'd like to try.

Adding a new relationship is either O(n) where n is the number of relationships already assigned to an entity,

How so? The gut feeling says O(1) if you prepend. Isn't it the case? 🤔

It is basically the same as a component, but we add 2 entities instead of one, emplace an element to the next/prev vector and change an entry in said vector(s).

Two entities, an element in a vector, an update who knows where in memory. It sounds... expensive, for the common case. Isn't it?

To be fair, adding and destroying relationships is relatively expensive to adding and destroying a component, but still quite fast and the least common operations in an engine.

Can you make a concrete example from a real world case of yours? Just to talk about something concrete.

For regular (in memory order) iteration, we iterate 3 vectors (Entity, Relationship, Entity) instead of 2 (Entity, Component)

This is the oddest part imho. Let's reset it for a moment and speak in these terms instead: how would you design it if you could specialize a storage? Because we can and it's likely easier to implement something that works better? Dunno, just thinking aloud, never really concerned about this problem so far to be honest, so bear with me. 🙂

In my proposed solution, I only need something like an Attacking relationship

As an user, how can you tell which one is a relationship here?

struct X {};
struct Y {};

I think I'm missing this part. I'm not a fan of an API that duplicates for the purpose (as in emplace_an_X and emplace_an_Y).
If you look at EnTT, everything is transparent at the end of the day. For example, you can enable pointer stability for a type at compile-time and forget about it. You don't have to invoke the right method all over because that's something special to remember about.
In this case (but take this with a grain of salt because I've no clue of the API you envision), it sounds as if we're going to add something special that needs its own API. Did I understand correctly?

[skypjack]

Nah, don't get me wrong, I see why you're suggesting this and why your solution works in you case.
My main concern/gut feeling is that there is a less invasive method to achieve the same but above all a method that allows us to have everything packed within a single chunk of memory, without many jumps around.
I'm trying to put it on paper at the moment since you triggered an idea but it may take a while because I just got back from vacation and have a few things to sort out first. 🙂

[DaedieGit]

Ok, cool. Looking forward to your idea. 😄

[skypjack]

Oh, it's nothing special but it's more on the let's customize a storage or let's write a dedicate storage for the purpose rather than trying to push a component on top of the existing implementation.
Have you ever tried to think in these terms? I mean, if you could add a storage to EnTT to solve your problem, wouldn't it be easier?

[DaedieGit]

I haven't, mostly because my focus was on the concept rather than the specifics. And also because the custom pool idea went completely over my head the first time I read it when going through the documentation.

I looked into it some yesterday and I do think it will indeed cover my needs.

Just to see if I'm getting it right:

I would implement a basic_storage specialization with the implementation above (or something better). Then I would use template instantiation for all my relationship types to make sure that the compiler picks up my custom storage instead of the default.

I would have an iterator that is the same as the one for the default storage, the extended iterator would have to add the "other" entity to the tuple that is returned by the operator*. Because I want to be able to iterate from both the subject and object pov, I would also need to mirror some of the api.

I'm not entirely sure how I need to handle views. Do I need to build my own thing or specialize a basic_view? Since it is used behind my query api, I'd be fine with either option really.

And I think the custom pool might actually also facilitate a solution to a different issue I have been wanting to address. Some of my components always exist together (by definition) and want to be organized a little differently from other components, so I was thinking about having them added as a "package" (all or none), but still exist in separate arrays.

The best example of this would be my LocalTransform and GlobalTransform components (which also might end up being split into their respective translation, rotation and scale components). Additionally, I'd want these to have fully contiguous (fully preallocated?) storages so I can use simd on them.

Groups + pagesize facilitates some of this, but not completely and they are also more expensive than necessary for the intended purpose. Having a separate api for group instead of just using view, was something I was willing to deal with, but it's not ideal.

I think making a storage that uses the same sparse_set logic as the default storage, but stores multiple vectors (1 for each component in the "pack"), could accomplish what I want here.

[skypjack]

Then I would use template instantiation for all my relationship types to make sure that the compiler picks up my custom storage instead of the default.

I guess a single specialization is enough. You can do something like this:

struct type {
    using type pick_me = void;
    // ...
};

Then specialize the storage type traits to match all types with a pick_me type member.
Same result, just less code probably. 🙂

I'm not entirely sure how I need to handle views. Do I need to build my own thing or specialize a basic_view? Since it is used behind my query api, I'd be fine with either option really.

It really depends on the storage specialization. It could also be that you don't touch the views at all.
Views rely on iterators and get_as_tuple functions. As long as these work as expected, they don't really care what your storage specialization does. You just need to know how to interpret the data you get.

Additionally, I'd want these to have fully contiguous (fully preallocated?) storages so I can use simd on them.

An entityx-like storage is probably the best approach here and yes, you can have it with a specialization. Feel free to reach out if you have problems. 👍