Question How to handle many-to-many relationships with computed values?

I've been toying with ECS for some time now, and I think I understand it conceptually, but I'm struggling to find a good way to architect components for a feature of my game and am stuck with a many-to-many setup I'm just lost on.

In short, some entities in the game have "influences" applied to them, which can represent many things about said entity. Additionally, these entities may have a list of other entities which they are "influenced by": that is, the influences of those entities which share the same type are additively merged to the entity's own influences to create an "effective" list. Further still, this can be a few entities deep before reaching the "root".

For example, a structure on a map may have a "temperature" influence: it may have a base temperature of its own as well as the temperature from the tile it sits on. The tile's temperature is, in turn, computed from its map, maybe the biome it's in, and also from a number of potential other nearby structures which can raise/lower it.

The trick is, I can't figure out a good solution to achieve this goal!

I spent some time digging through how the built-in LocalToWorldSystem and ParentSystem work, since they perform a similar-ish task, but I think they're too different to help me. Despite that, this is what I've come up with so far:

I have my Influence type that looks like this:

Code (CSharp):

1. public struct Influence
2. {
3.     public FixedString32Bytes Type;
4.     public float Value;
5. }

When merging, two Influences with the same Type should have their Weight summed up to create the final weight.

My initial thinking has me with three IBufferElementData components:

• InfluenceItem which represents the influences on this particular entity
• InfluenceSource which represents all the entities this entity will pull influences from, populated by other system(s)
• EffectiveInfluenceItem which holds the computed influences

In theory, these could instead just be components with a NativeHashMap of influences, but it sounds like it makes no functional difference.

This all gets me stuck on a few points:

• What happens if an entity in the sources is destroyed? AFAIK that does not update the change version of the source buffer, so I would need a way to remove it from the sources too.
  • I could also have a buffer of InfluenceTarget or similar as a back-link which is also a cleanup component, but now what happens when the entity with the sources list is destroyed? Do I need another cleanup buffer there, too?
• If I wanted to do the simplest thing of combining a source's effective influences rather than walking the whole tree, how can I know those are even up-to-date? Iteration order of entities from queries is not guaranteed, especially with parallel iteration.
• What if a source's influences change? How do I propagate that change update downward?
  • I could tag entities with some sort of "I need to be updated" tag, but that means maintaining a back-list for targets of sources, like above, that I can iterate to mark them. This also runs into the same problems as above, though.
• If I added some sort of relationship entity (like in relational DBs), how could it be kept track of such that an update or destruction of either end notifies the other?
  • Wouldn't this also cause a bunch of structural changes when said entities are created/destroyed?
• Could something be done with events that isn't incompatible with the job system?

If anybody has any ideas on the best pattern to implement this, that would be greatly appreciated!

I've tried reading through the docs best I can but I'm not familiar with all the (anti)patterns yet. If there's a better approach entirely than what I've come up with, I'm all ears.

 

If you want exceptional performance with many-to-many problems, the trick is to constrain the problem as tightly as possible.

Does each individual data change infrequently relative to the number of times it is read? Then use a receiver cache.

Are the relationships static or infrequently changing? Cache the receivers in the providers.

Is the data flow unidirectional (like a DAG) and the relationships are static or infrequently changing? Use shared components to order dependencies.

Is the data infrequently changing on average and can be stored spatially, but needs to be read a lot in Entity Queries? Double-buffer both in components and the spatial structure and only sync deltas.

If you want to get very specific about the problem you are trying to solve, then I can provide some very specific ideas for how to solve it. And don't forget to profile!

One last thing, I would not use the transform system as an example of how to do many-to-many relationships in ECS. It isn't that performant and is full of race conditions that just so happen to not effect the common use case so most people don't notice.

 

While there are many options, simplest I've found for this specific case is something like:

Code (CSharp):

1. public struct Influence : IComponentData {
2.     public float Base; // Value of *this* base cell without modifiers
3.     public float Combined; // Combined value of this cell + nearby cell values
4. }

Store references to the nearby Influences in a separate buffer / component.
Lookup structure (like your map) would also work. As long as you've got Entity to read from - its good.

1. Iterate over all entities with Influence;
2. Grab data via ComponentLookup & process nearby cells Combined value.
3. Write Combined value of nearby cells and base value to this cell Combined value
[based on the rules needed to be applied];
4. If Entity is no longer valid - clean it up from the nearby buffer.

What happens is - over multiple frames you'll get proper "stabilized" value in cells.
Not the most accurate, but over time computations usually less intensive.
And with temperature you'd probably tick over time anyway.
Just make sure you're using proper initial default value and you're good to go.
Most games do not need 1 frame precision so you might get away with it as well.

In any case - ComponentLookup for Read / Writes from / to other entities is what you're looking for.

Edit: Also, check out Boids example.
It might give you some ideas on how to propagate values over nearby entities as well.

 

I wouldn't say the relationships change incredibly often, but they're certainly not static and probably not infrequent either. In most cases, relationship changes will be in response to player actions, and the number of actions which do will vary depending on what exactly the player is doing. Placing or removing structures, for example, may update influences around it, but also the player can adjust settings on the wider environment in a few places too and those are also influences, just higher up the "tree".

I'm unsure if it's unidirectional or not. Influences don't propagate back "up" to their sources, only flow "downward" and shouldn't form loops in any way, but the sources the influences flow from kinda form a tree "upward" so to speak.

Absolute best performance isn't super critical, as the number of entities with influences will be in the thousands to tens of thousands rather than millions.

I did consider a sort of "eventual consistency" approach like you suggested here, where I just assume all the sources were up to date since they will be eventually (usually after a few frames). The game doesn't need frame precision and the "source tree" of influences will probably be at most three entities deep, so I was leaning toward just doing this.

I'm wondering, though, if it's not going to be too painful on performance to be always doing this for every frame rather than trying to detect changes, but I guess I won't know for sure without trying and profiling it.

I'll dig through the boids example as well. Sounds like it has quite a few other useful things in it, too, for other parts of my game.

Sounds like I've got some work and testing to do. Cheers to you both!

 

Those are "infrequent". Infrequent being on average less than 10% changes per frame. Honestly, your use case sounds like it would benefit from most of the optimization strategies I hinted at. I don't have a good way of explaining the strategies abstractly though. But if you come up with a concrete case, I can walk you through the design process. These aren't techniques I see discussed much on these forums or other Unity ECS resources. But once you know them, you'll find you'll be way less dependent on ComponentLookup and friends and everything will be a lot cleaner.