A few questions regarding collision detection orer of operations and world orientation

TooOld2rock-nRoll wrote:

what is the practical order to move the game objects and detect collisions between them?

Most game physics engines use the following order of operations:

1. Zero the force and torque vectors for all objects.

2. Apply forces (e.g. gravity, springs, aerodynamics, etc.)

3. Integrate force and torque vectors to produce pseudovelocities: v' = v + F*(dt/m). This the velocity that the objects would have if they don't collide with anything.

4. Detect collisions between all objects, and put the results in a big array of (object pair, contact information). This allows use of acceleration structures (grids, spatial hash, BVH, sweep and prune) to reduce the time complexity of the collision detection from O(N^2) to O(N*log(N)) or O(N). Using your approach would be slow O(N^2), not practical for more than about 500 objects.

   For engines that support continuous collision detection, the pseudovelocities can be used to determine the potential trajectory and calculate a more accurate time of collision to avoid tunneling problems.

5. Update the contact constraints using the collision results. This involves building a "contact manifold", a small collection of contact points between each object pair. For 3D, usually it is 4 points, for 2D 2 points would be enough. I use a hash map to quickly lookup the manifold for each collision point produced from the collision detection. This is the stage where you can call callback functions to report collision results to external systems.

6. Solve the constraints between all objects using the pseudovelocities and contact manifolds. For games this is usually done using the "sequential impulse method", which involves iteratively applying impulses at each contact point to shrink the velocity error. For example, a contact constraint must ensure the relative velocity at every contact is >= 0 (objects must be in stationary contact or separating). More iterations produce more accurate results. This is effectively an approximate solution to a system of equations of all constraints in the simulation.

7. Use the now legal velocities to calculate the new positions at the end of the time step: p' = p + v*dt.

Aressera wrote:

Detect collisions between all objects, and put the results in a big array of (object pair, contact information). This allows use of acceleration structures (grids, spatial hash, BVH, sweep and prune) to reduce the time complexity of the collision detection from O(N^2) to O(N*log(N)) or O(N). Using your approach would be slow O(N^2), not practical for more than about 500 objects.

It would be VERY acceptable than!

A fighting game or even a platformer will not have more than 500 valid objects to check.

I have always avoided studding this part of gamedev, physics is ok, I can follow the theory and implement good solutions, but algebra makes no sense to my brain. It will be good to start simple and stupid hahaha

Just a quick follow up question than, if ALL the moving and collisions are computed "at once", how do you solve cases with multiple collisions? What is the priority reasoning in this case?

PS: I keep making these basic and confusing questions just because I like to check my own instinctive solutions against real world solutions.

I don´t keep idle waiting for answers, I'm actively reading reference materials (articles and books) and trying to implement something that works. Most of the times, I have a good but naive guess of what would work and it helps me understand the proper solutions and what are the practical problems it is trying to circumvent.

For instance, I really liked the impulse method! Didn't knew it was a thing, but was already implementing "forces" using that logic.

It made much more sense than trying to use force vectors, specially since we agreed in my last post that contact time is zero and acceleration formulas would not work.

TooOld2rock-nRoll wrote:

if ALL the moving and collisions are computed "at once", how do you solve cases with multiple collisions? What is the priority reasoning in this case?

That's partly what continuous collision detection is for, to calculate accurate time of collision, but I doubt that any game physics engines are ensuring 100% accurate ordering of collisions and response, it's just not compatible with good performance. The compromise is to accept some slop in the collision detection, so that objects can penetrate each other, and that penetration is resolved over time ("baumgarte stabilization"). If multiple objects collide within a time step, it's treated as if all collisions happened simultaneously.

To do better, you need to do "conservative advancement" so that you calculate the minimum time until the next collision across all objects, then integrate time forward for that substep for all objects, then repeat until the end of the time step is reached. As you can imagine, this is very slow. Calculating the time until next collision is a hard geometry problem, especially with rotation and even worse in 3D. A cheaper version of CCD is to do a ray cast (or swept sphere) along the velocity vector to identify the approximate time of collision, then maybe refine from there. This at least handles tunneling problems. This is what I plan to implement in my physics engine.

TooOld2rock-nRoll wrote:

What would you suggest?

Anything goes. But i can add some context, initially assuming we aim for realism.

I see your thoughts mainly circle around the order in which to resolve one collision after another.
But your considered options are formulated from implementation details, not so much from a general understanding of the problem itself, which i'll try to improve.

The first option i'd mention is to get our order from the time at which the collisions happen.
The algorithm is to project all bodies for one time step, then detecting collisions and their moment in time, keeping track of the collision happening first. After that, We move all bodies to the time of first collision, and change the velocities of the affected pair.
Then we repeat this process, finding one collision after another until we arrive at the desired time, and the physics update is completed.
Notice we avoid a question about order here, but you can imagine this is prohibitively expensive if we have many bodies colliding with each other within a single timestep. So the method is practical only for a small number of bodies.
Also, it does not help with bodies in contact, e.g. a stack of boxes. Contact happens over a duration of time, likely over the whole timestep, so we don't get any order from looking at time.
However, the method is very practical if we only care about collision with a static world. E.g. Breakout or Quake, where the player body is projected along velocity direction against the world, and finding the closest intersection is equivalent to finding the first collision in time.

In this case, collisions with other dynamic characters brings back the question of order of coarse, so let's see what's our options regarding the resolution of multiple collisions across multiple dynamic bodies, treating them to happen at the same time.
Lets say we have 3 balls left to right, ball 1 intersects ball 2 and ball 2 intersects ball 3.

The first option is to make the order irrelevant.
The algorithm is: For each ball, sum op all the collisions responses affecting it (could be forces, velocities or displacements), then move all balls by their summed up displacement.
For ball 2 in the middle, the displacement from 1 and 3 would cancel each other out, so it would not move.
The other two bodies each move outwards one half of the penetration.
We can then repeat the process for a few iterations to reduce the error further.
As said, the order in which we process collisions does not matter, the outcome is the same with any.

The second option is to use some roughly consistent order. Usually our algorithm detects collisions int same order every frame, and we can just resolve the collision for each pair as we go.
E.g., ball 1 and 2 resolve first, moving ball 2 to the right, increasing its penetration with ball 3. We resolve this pair next, so ball 2 now penetrates ball 1 again. But not as much as before.
Again we do some iterations to reduce this error further.
In the end, we have balls all separated well enough from each other. But the outcome is a little different depending on the order we used. Which is a downside compared to the former option, but iirc the upside is that the total error reduces faster.

A third option is to randomize the order each time, to minimize the effects of order dependency over time.
But i can't say much about that. When i've tried quickly, the jitter got worse so i settled at the first option. But others get good results i've heard.

I've also tried some other more creative options, e.g. sorting by height for easy stacks, or sorting by penetration depth. But nothing of this worked - for me at least.

TooOld2rock-nRoll wrote:

What I'm thinking now is to let the Level itself control the procedure and for each obj that moved on the previous loop, check for collisions. So it would be:

Reminds me on the Super Mario example from last post, where boxes are parented by other boxes, moving with them instead of falling into each other from gravity.
It usually means less realism but more control from game design.

Either way has its strengths and problems. If you're not sure, maybe just choose what feels most intuitive to you and see where you get. You can always change your mind or extend later.

TooOld2rock-nRoll wrote:

Should I just ditch all this and just focus on pure 2D????

Yeah why not. It's hard enough.

But i think, similar to the choice of realism vs. design, you make it harder to yourself by aiming for an engine the can do any game, if i recall.
It's actually easier to focus on just one game, but trying to keep the code modular and reusable so after a second or third game the code base becomes an engine.
But you've heard that before i guess.

Just a quick follow up question than, if ALL the moving and collisions are computed "at once", how do you solve cases with multiple collisions? What is the priority reasoning in this case?

In proper physics engines, 2D or 3D, collision resolution is treated as an error minimization problem. The overall process goes something like this, within a single timestep:

1. At the start, calculate new positions for each body based on their current positions, forces, torques, velocities. Detect and collect pairs of bodies that are intersecting.

2. For all collisions that occur based on the positions you've projected, measure the degree of penetration (somehow). This penetration value is the "error" you've measured.

3. Walk through each collision pair, applying a force to correct the penetration in the next step. Calculate and store the projected new position for the colliding bodies, as well as a value representing the overall correction itself over multiple iterations (called the Lagrange multiplier or similar).

4. Repeat 2 - 3 for some set number of iterations.

The basic idea is that each iteration minimizes the "error" observed in each collision pair by a certain amount. The biggest correction takes place in the first iteration, each successive iteration making smaller and smaller adjustments. Beyond some number of iterations, the corrections are negligible, and so are the corresponding errors in each collision.

There's some complicated math driving this method, but the implementations tend to look much simpler.

Honestly though, if you aren't shooting for an all-round physics engine, I'd take JoeJ's advice:

But i think, similar to the choice of realism vs. design, you make it harder to yourself by aiming for an engine the can do any game, if i recall.
It's actually easier to focus on just one game, but trying to keep the code modular and reusable so after a second or third game the code base becomes an engine.

As for ditching 3D and going for 2D, you're still going to run into the same problem. How much more gameplay can your engine enable for the least amount of effort is what you'll want to look for. It's fine to hard-code magic physics that's specific to your game if the generic thing will take too long to flesh out.

JoeJ wrote:

The first option i'd mention is to get our order from the time at which the collisions happen.

Oh I actually have no clue how to achieve that! In the sense that it never crossed my mind it could be done :P

I will not try that right now, but it's something to keep in mind.

JoeJ wrote:

But i think, similar to the choice of realism vs. design, you make it harder to yourself by aiming for an engine the can do any game, if i recall.

I thought I could get that for free, a little awareness from the user and it was just a matter of messing with the perspective of the tiles.

Separating mechanics from behavior is not as clear cut as I hoped for, but this is the first time spatial orientation plays a big role on the world behavior. Even if my target is 2D fighting games, I'm confident it is possible to build any platformer from what I'm designing as the engine.

I will accept your suggestion and specialize in pure 2D for the time being, this is the exact moment to avoid future me a lot more unnecessary headache!