Imagine the following scenario with three hitboxes, before the collision detection & resolution occurs:

The green rectangle represents the player and is a rigid body. The blue rectangle represents a wall, and is also a rigid body. The red rectangle represents a collectible power-up, which disappears when the player picks it up and is not a rigid body. In this scenario, the player was to the left of the wall, is moving right, and collides with the wall. I've run into a problem where the order that the collision tests between the regions occurs is unpredictable and can result in incorrect behavior.

If the player and the wall collision is resolved first, the player is correctly re-positioned to the left of the wall, and will no longer be colliding with the power-up. However, if the collision test with the power-up is done first, the player would collect it, which is not the correct behavior. Naturally, the scene could also be mirrored, with the power-up to the left of the wall and the player to the right, moving left.

The only thing I can think of to deal with this problem is to do two passes for collection detection, one for collisions between rigid bodies only, and another for non-rigid bodies. This seems really inefficient though, so I'm wondering if there's a better way to address this. Any thoughts would be appreciated. Thanks!

Well, you could register the power up collision, but then only verify it's still colliding after all collisions resolved. Makes sense assuming number of trigger volumes is small in comparison to static / dynamic rigid bodies. (Related to pre/post updates mentioned here: https://www.gamedev.net/forums/topic/710310-generally-the-best-way-to-have-a-scenemanager-c/​ Some physics engines have their own pre/post callbacks as well.)

But i wonder how often this happens, and why at all? Player that fast and walls so thin? Could the level designer just be careful and place power ups at some distance to walls? Maybe the player box is just too large and some tighter capsule would do better in general?

Short answer: yes, you should run the collision detection twice.

Long answer: my advice would be to never allow the player and the wall to intersect in the first place. When it is time to move the player, before you actually do so, run a collision check where you would move the player. If there is a collision, adjust the player's movement vector, then run another collision check to check that you didn't mess up. Repeat as necessary. Only check for pick-ups after the player has actually moved, if the player has actually moved. Then do the same thing for every other entity that needs to move, one at a time.

Your goal isn't to write the fastest code possible. Your goal is to write resilient, glitch-free, correct code - and then optimize that code as much as necessary while maintaining correctness.

a light breeze said:
Long answer: my advice would be to never allow the player and the wall to intersect in the first place. When it is time to move the player, before you actually do so, run a collision check where you would move the player. If there is a collision, adjust the player's movement vector, then run another collision check to check that you didn't mess up. Repeat as necessary. Only check for pick-ups after the player has actually moved, if the player has actually moved. Then do the same thing for every other entity that needs to move, one at a time.

Just wanna mention this approach, while guaranteeing correctness, becomes extremely slow if we have islands of larger amounts of bodies. We constantly need to move them back in time while searching for the first collision, and re simulate form that moment to find the next collision in time. Really expensive from the perspective of doing simulation, and i don't think any of current physics engines work this way. The usual advise would be ‘take smaller timesteps / do more substeps’, which is still faster by avoiding worst cases within acceptable accuracy trade off.

Ofc. it works if multi body problems are kept on a minimum size, so really depends on the game an dhow it deals with physics.

JoeJ said:

But i wonder how often this happens, and why at all? Player that fast and walls so thin? Could the level designer just be careful and place power ups at some distance to walls? Maybe the player box is just too large and some tighter capsule would do better in general?

Well, this is just one hypothetical example to demonstrate the problem, it isn't necessarily always going to be a power-up and a wall. There could be any number of scenarios where a similar situation occurs. I like your suggestion of registering the collisions and doing a second check only on the ones that were valid, I will give that a try! Thanks!

You might also want to try ‘continuous collision detection’, which ensures fast objects do not tunnel through a wall (but still does not prevent simultaneous collisions). It's also quite costly, but usually can be enabled per body.

This issue indicates a general error in your collision-detection and the real solution might be, “Use an existing physics engine that is already robust and complete enough that this case never arises,” but let’s say you have valid reasons for not doing that. At this point you are basically working around issues rather than solving them, but if that’s fine with you, 2 efficient ways to handle this might be:
#1: If collision is found with an item, store only that item for later double-checking in a final pass. This keeps your 2nd pass as small and fast as possible.
#2: This could still lead to an error hypothetically if being pushed out of the wall results in a collision with an item that had already been checked, meaning it won’t be checked again after this and collision won’t be detected. So it’s probably better to sort the items ahead of time so that collisions with items are always the last checks being made, even in single passes.


L. Spiro

We constantly need to move them back in time while searching for the first collision,

If you use swept collision, you get the time already. And for a game, for MOST cases (character movement, environmental debris, even grenades and missiles) it's totally OK to just reflect the velocity, and stop the object at the collision, without re-simulating the rest of the time step. There are vehicle simulations where you need to either make the time step very small, or actually re-simulate the remainder, but those are the rare cases.

You could even, most of the time, get away with “if the movement finds a collision, just place the colliding object in the position it started at and reflect its velocity by restitution” and it'll be pretty good. Certainly for a field of thousands of items of debris, the player isn't going to notice. It also has nice stability properties once your bodies start to pile up.

hplus0603 said:
If you use swept collision, you get the time already.

But even if you find the first collision quickly, the outcome may affect that of other nearby bodies, so you need to invalidate and update the swept test results for a growing number of bodies in worst cases. It's not really stepping back then, but still the same effect on time complexity.
Let's take the example of the first ball hitting a triangle of billiard balls. To order all the collisions in time, we process a graph including all bodies for each collision. And the outcome is just chaos anyway, so treating the collisions as simultaneous and handling that is faster and more robust in practice too. That's what rigid body simulation engines usually do afaik, and the only way to increase temporal resolution is to do more substeps or using smaller timesteps where needed.

hplus0603 said:
You could even, most of the time, get away with “if the movement finds a collision, just place the colliding object in the position it started at and reflect its velocity by restitution” and it'll be pretty good. Certainly for a field of thousands of items of debris, the player isn't going to notice. It also has nice stability properties once your bodies start to pile up.

Oh, all those hacks like shock propagation, speculative contacts, etc. Solving one problem, introducing two new ones. I'd do such things for decorative special effects where performance is much more important than accuracy and robustness. For the important stuff, i'm just happy i switched to using a physics engine : )

Yeah, but what do you think the physics engine is doing under the covers? ;-)