Best approach for handling collisions

[roo-oliv]

Hi, I've just started with DefaultECS (great framework by the way!) and ECS in general. I've read a lot about how to handle collisions in different ways but I'm still unsure how to approach it and keep ECS benefits of reduced cache misses and less code branch mispredictions. I wonder if anyone can help me here, I also think that this might be a valuable future reference for other devs in similar situations.

Important Premisses

• The game has a player entity and multiple collidable entities like static blocks (floor, wall, etc) and dynamic things (enemies, platforms, etc). This implies that we'll have to resolve a single entity colliding with multiple other entities in the same frame.
• There is no physics engine for simulations going on, interactions are simple enough to code/handle manually and I want to be able to tweak bits of it (just like Celeste is permissive for near-miss collisions and etc). This implies that we have full control on how to detect and report collisions.

The Problem

Say we've collision detection worked out (in my case I've implemented a Swept AABB Collision Detection - reference video). Now our CollisionDetectionSystem is able to get us all entities which are colliding with each other alongside the time of the collision, the point of collision, collision direction and the normal vector to the collision point for each collision. To correctly resolve collisions we need to resolve them in order by the time they occurred. So, how do we do this?

Considerations

As far as I understand, DefaultECS and other ECS frameworks works with the concept of only one component of each type per entity (or world). So we can't just register a set of CollisionComponents for an entity.

Approaches

# 1

Add a CollisionQueueComponent to each colliding entity which will store all collisions happening to that entity.

This way we can easily have collisions properly sorted in a queue.

But is this good practice? Is this efficient? If we create components with queues/arrays/stacks of variable size won't we lose all the memory management benefits of storing components adjacent in memory?

# 2

Create "collision entities", each with a CollisionComponent referencing a single collision (which references the two colliding entities).

This way we do not need to manage queues/arrays, our CollisionComponent struct has fixed size in memory and it may be more readable and clear to understand code dealing with each component referring one collision instead of a queue of collisions.

But how can we resolve collisions in order? Maybe we can have our CollisionDetectionSystem sort all collisions and after that create entities in the correct order so we can latter process then in the same order? I don't know if DefaultECS guarantees any sort of order when processing entities... (most probably not so I would have to figure this out too) Also, is it efficient to always need to use references to the two colliding entities? Won't it eventually be slow to loop through an entity set just to have to get references for the two other actual entities?

# 3

Resolve collisions in the same system where we detect'em, effectively creating a big CollisionSystem.

This way all we need to do is to sort collisions and resolve them.

But isn't this a bad pattern? Collision can happen between solid bodies, dynamic bodies, a player can collide with a wall but also with a coin, each will have different rules for collision resolution, we no longer can have specialized collision systems. We could divide the code in order not to end with a massive, monstrous CollisionSystem class but wouldn't we lose the benefits of less code branch mispredictions? For each collision we would need to check the type of the colliding entity to them decide which set of collision resolution rules (each implemented in its own class) to use.

---

I'm leaning towards approach number # 2 since it looks more readable, clearer and easier to understand and seems not to violate basic principles of ECS but I'm unsure if I'm losing something that way or even if I will effectively be able to resolve these collisions in order without having to fight the DefaultECS framework.

[Doraku]

Hey, thanks for you kind words :) I will try to comment as best as I can your different approaches:

# 1

Adding storage as component seems indeed a little too memory hungry. You could always use a pool of queues but I feel it complexifies too much for too little gain. I do have an idea I want to explore to allow storing multiple components of the same type on an entity, maybe it could help with this scenario in the futur but it is not there yet ^^"

# 2

I have seen this approach in a lot of other framework, using entities as messages. In DefaultEcs I would actually advise against doing this. Changing an entity composition is not free, using the full inner storage of entities and components just to store a single component that live only one frame seems a little too much when you can easily just store the messages to be processed directly later on.
This is actually what I am using in my game: my collision system checks for collisions in multithread and send collision messages when one occur (it's a simple shooter game with bullet and ennemies but I think the strategy could be used for more complex check), those message are received by a subscription (kinda like this but directly inside the collision system and with a thread safe queue specifically made for this) and the collision message processing occurs in the PostUpdate method that way the costly check can still be processed in multithread (with just a little branching to send the collision message or not) and after that the actual effect of the collisions are processed. This is important for me as some collisions that were detected could no longer be valid because an other collision that was processed before could have removed one of the two colliding entities.
If order is really important for you, you could use some sorting rules before processing the collision messages (or even use multiple collision message types if you have different kind of collisions that should be processed in a specific order), as no order is guaranteed in DefaultEcs, entities are swapped as they are added/removed from sets, same for component (so those operations are always o(1) in most cases), keeping collision detection and collision processing separated seems crucial either way so...

# 3

This look like a bad idea:

• you can't use multithread for anything
• the processing order (at least in DefaultEcs) is not guaranteed
• you would end up with a god system doing too much with if/else everywhere

---

At least this is where I am at now, I am all ears for other ideas on this problem :)

[roo-oliv]

Hi, @Doraku! Thanks for the quick reply, and again, congrats on the excellent work in this open-source framework!

Being able to store multiple components of the same type on an entity sounds exciting as a user of the framework, though it also looks very delicate to implement correctly or even to reason if this is the right way to go. I look forward to seeing how this will evolve in the future.

Events do come to mind when thinking about this problem but my current understanding of events in games is that we should avoid using them in hot-paths like collision resolution. I confess though that I do not fully understand why and I only have this simplistic pre-concept of management of subscriptions and message delivery being, to some extent, less efficient than direct imperative flows. I assume being wrong here given that you're using this approach without any problems. If that is the case I'll go this way I really liked it!

Also, about multi-threading, I understand that it is common practice to use it for handling heavy I/O operations, such as textures loading and network communication, but is it recommended to use it in the core processing of the game? Coming from a software engineering background it seems natural to use multi-threading in ECS since I believe I can declare ParallelSystems inside SequentialSystems and vice-versa. Am I encouraged to do this? Should I beware of anything?

[Doraku]

Messages (and thus events) are indeed a little less performant than direct calls (negligibly so compared to actual demanding operations), but it's always a question of tradeoff between performance and coupling/complexity. You could directly add messages to the delayed queue. DefaultEcs use events everywhere to notify changes in entities to update containers anyway so whatever you do it would be better than to use entities as single frame event ^^

For multi-threading, it is actually one of the main goal of ECS. As systems operate on separated entity data it is a perfect candidate to be processed in parallel. In DefaultEcs I expose two strategies:

• ParallelSystem allows you to run multiple systems in parallel, each systems should be completely independent from one another data (component) they use (if System A update the value of Component 1 and System B read the value of Component 1, obviously we can't run them in parallel). In practice I think this behavior is kinda rare and not optimal (it's probably rare that two independent systems would take the same time to process, making one thread hang waiting for the other to finish)
• AEntitySetSystem can take a IParallelRunner to balance all the entities that need to be processed across all the available threads. Since it is the same system running on almost the same number of entities in parallel it has much more chance for everything to finish at the same time, reducing hanging time, and you are assured that entity states are updated for the next system that may be dependent to the modified component data. As stated in the readme you can't do entity composition modification in multithread (adding a new component, removing one) as those are not thread safe and you need to use an EntityCommandRecorder for that which while optimized for it, induce an extra cost.

As always for multithread, splitting processing on multiple threads and synching the end has a cost that may be greater than the time it takes to process everything in a single thread. That's up to you, AEntitySetSystem can also take a parameter which is the minimum number of entities per thread required for it to run in multithread to give a little more control over it.

[roo-oliv]

Nice! Thanks for such a through explanation! I'll go and use events for handling this :) Also I'll give parallel systems a try 🚀