Entt: How to speed up event system for proximity-based events?

[Yzrsah]

Hello.

I am using a custom event system currently, dispatching events and looping to check each subscribed entity for proximity to the emitter. This allows events to be in range or out of range. I also use a raytracer to emit events to traceable objects. Proximity helps cut down on a lot of checks and signaling.

I would like to use entt's event system, but it seems the event and dispatcher are hard-coded to update all connected listeners only. This kinda assumes a heavy load of all listeners checking the event on arrival.

I thought of first doing a distance search, then creating a bunch of listeners with triggers, but that is far too costly.

Can you imagine a better way to dispatch and emit conditionally based upon what is contained in component values without sending the message to every single connection? (possible hundreds of thousands of entities).

Perhaps there could be a kind of "dispatch condition component"

I thought about modifying entt to make some special support for the position component, with some kind of support for distance balanced nodes (to avoid looping over all entities). But there maybe a better way.

What would you recommend is the fastest way to do this with entt?

[Milerius]

I think that you should recheck the code of the event system, it use family type as index, it's really fast, it's will be almost impossible to do something more optimised

[Yzrsah]

Thank you for your response. I agree that the implementation is fast. This is a different issue / consideration - optimizing for intrusive views into entity component data as filters for dispatch/emit operations. The event family is for type, but not data.

[skypjack]

I'm not sure I got what your goal is. Are you trying to find entities close to a specific entity? You can just use an external data structure like an octree for that.
A _dispatch condition component_ sounds good if you look at the client code, but you still have to visit all the entities potentially interested by the event and see if they match the condition internally. Therefore I don't see how this could mitigate the cost of an iteration.
The other way around is to consistently keep up-to-date a list of listeners for each entity, but this just moves the performance hit on another place and the impact is much higher, mainly because most of the operation are useless in case of no events.

[Yzrsah]

The goal is to dispatch events to entities close to a specific entity without maintaining a separate octree. The entities fly across the scene with dynamic positions, causing the octree to shrink & expand frequently. I have tested this approach with a special allocator for the octree but it is still heavy. Because of this reason I've opted for a simpler data structure. It seems that the brute force approach of visiting all of the entities can work, as long as the dispatch condition resolution is made perfect without much generated code in between. It may seem like a non-issue, but that overhead becomes the main thing when there's millions of spam messages going back and forth. There's also various other dispatch conditions that depend on entity component data, this is one example. Making that dispatch condition resolution perfect is why I have posted here about potentially supporting this generically in entt.

[Kerndog73]

Maybe instead of an octree, you could use a grid. Once you have it set up, there are almost no further allocations unless you have lots of entities close together and you have to grow some grid-cells. That's my two cents.

[skypjack]

To be honest I've never had such an issue, therefore I don't fully get the impact.
What is not clear to me yet is how you intend to solve it. I mean, you said you don't want to use an octree but you suggest to use _another data structure_, that is more or less the same thing (granted, pick the most optimized one for your case, but you still have to _spend_ time to keep it up-to-date, right?).
Otherwise, I don't see how the library could know what are the entities close to another one without iterating all of them. This is slower than using an octree, but it uses less memory and has no impact when you move things around, of course.
What's the best solution? Well, it mostly depends on you specific case, so it's also hard to define a generic approach that is _always good_. Am I wrong?

[vblanco20-1]

There is even a better way than just a grid. You could use the morton code (its a 3d index) and keep stuff sorted. You could also use a hash map. I detail both of those in my ECS experiment. http://victor.madtriangles.com/code%20experiment/2018/06/11/post-ecs-battle-huge.html
Using an ECS that works in arrays doesnt mean you cant have other data structures beside it, and just keep a "handle" to that data structure in the ECS registry.

[skypjack]

@Zyrsha Are the answer you received satisfying? I'm not sure we can do much more on this, so I'm tempted to close the issue. What about?

[Yzrsah]

Thank you to everyone for the help and ideas.

@skypjack For a small test, you might consider throwing together a thing like I have mentioned which allows proximity filtering via events with hundreds of thousands of objects - in doing so you may run into some of the ideas for building in the dispatcher components