Momentum and order of update problems in my physics engine

Question

This question is a "follow-up" question from my previous one, regarding collision detection and resolution, which you can find here.

---

If you don't want to read the previous question, here's a brief description on how my physics engine works:

Every physical entity is stored in a class called SSSPBody.

Only AABBs are supported.

Every SSSPBody is stored in a class called SSSPWorld, which updates every body and handles gravity.

Every frame, SSSPWorld updates every body.

Every updated body looks for nearby bodies in a spatial hash, checks if they need to detect collisions with them. If yes, they invoke a "collision" event and check if they need to resolve collisions with them. If yes, they calculate the penetration vector and directional overlap, then change their position in order to resolve the penetration.

When a body collides with another, it transfers its velocity to the other one by simply setting the body's velocity to its own.

A body is velocity is set to 0 when it hasn't changed position from the last frame. If it also collides with a moving body (such as a lift or a moving platforms) it calculates the movement difference of the lift to see if the body hasn't moved from its last position.

Also, a body invokes a "crushed" event when all its AABB corners overlapped something in a frame.

This is the FULL source code of my game. It's divided in three projects. SFMLStart is a simple library handling input, drawing and updating of entities. SFMLStartPhysics is the most important one, where the SSSPBody and SSSPWorld classes are. PlatformerPhysicsTest is the game project, containing all the game logic.

And this is the "update" method in the SSSPBody class, commented and simplified. You can take a look only at this if you don't feel like looking at the whole SFMLStartSimplePhysics project. (And even if you do, you should still take a look at this since it's commented.)

---

The .gif shows two problems.

1. If bodies are placed in a different order, different results happen. The crates on the left are identical to the crates on the right, only placed in the inverse order (in the editor).
2. Both crates should be propelled towards the top of the screen. In the situation on the left, no crates are propelled. On the right, only one of them is. Both situations are unintended.

---

First problem: order of update

This is fairly simple to understand. In the situation on the left, the topmost crate is updated before the other one. Even if the crate on the bottom "transfers" velocity to the other one, it needs to wait the next frame to move. Since it didn't move, the bottom crate's velocity is set to 0.

I don't have any idea how to fix this. I'd prefer the solution to not be dependent on "sorting" the update list, because I feel I'm doing something wrong in the whole physics engine design.

How do the major physics engines (Box2D, Bullet, Chipmunk) handle the update order?

---

Second problem: only one crate is propelled towards the ceiling

I yet don't understand why this happens. What the "spring" entity does is set the body's velocity to -4000 and re-position it on top of the spring itself. Even if I disable the re-positioning code, the problem still occurs.

My idea is that when the bottom crate collides with the top crate, its velocity is set to 0. I'm not sure why this happens.

---

Despite the chance of looking like someone who gives up at the first problem, I posted the whole project source code above. I don't have anything to prove it, but believe me, I tried hard to fix this but I just couldn't find a solution and I don't have any previous experience with physics and collisions. I've been trying to solve these two problems for more than a week and now I'm desperate.

I don't think I can find a solution on my own without stripping many features out of the game (velocity transfer and springs, for example).

Thanks a lot for the time spent reading this question, and thanks even more if you even try coming up with a solution or a suggestion.

Answer 1

Actually, order of update problems are quite common for normal impulse physics engines, you can't just delay applying the force as Vigil suggests, you'd end up breaking energy preservation when an object simultaneously collides with 2 other. Usually they do though manage to make something that seems pretty real, even though a different order of update would have made a significantly different outcome.

In any case, for your purpose there is enough hiccups in an impulse system that I'd suggest you instead build a mass-spring model.

The basic idea is that instead of trying to resolve a collision in one step you apply a force to the objects colliding, this force should be equivalent to the amount of overlap between the objects, this is comparable to how real objects during a collision transform their movement energy into deformation and then back into movement, the great thing about this system is that it allows force to travel through an object without that object having to bounce back and forth, and it can reasonably be done completely order of update independent.

In order for objects to come to a halt rather than bounce around indefinitely you will have to apply some form of dampening, you can greatly affect the style and feel of your game depending on how you do it, but a very basic approach would be to apply a force to two touching objects equivalent to their internal movement, you may choose to apply it only when they are moving towards one another, or also when they move away from one another, the latter can be used to completely prevent objects from bouncing back when they hit the ground, but will also make them a little sticky.

You can also make a friction effect by braking an object in the perpendicular direction of a collision, the amount of braking should be equivalent to the amount of overlap.

You could get around the concept of mass pretty easily by making all objects have the same mass, and immovable objects will work like having infinite mass if you simply neglect accelerating them.

Some pseudo-code, just in case the above wasn't clear enough:

//Presuming that you have done collision checks between two objects and now have  
//numbers for how much they overlap in each direction.
overlapX
overlapY
if(overlapX<overlapY){ //Do collision in direction X
    if(obj1.X>obj2.X){
        swap(obj1,obj2)
    }
    //Spring effect:
    obj1.addXvelocity-=overlapX*0.1 //Constant, the lower this is set the softer the  
                                    //collision will be.
    obj2.addXvelocity+=overlapX*0.1
    //Dampener effect:
    velocityDifference=obj2.Xvelocity-obj1.Xvelocity
    //velocityDifference=min(velocityDifference,0) //Uncomment to only dampen when  
                                                   //objects move towards each other.
    obj1.addXvelocity+=velocityDifference*0.1 //Constant, higher for more dampening.
    obj2.addXvelocity-=velocityDifference*0.1
    //Friction effect:
    if(obj1.Yvelocity>obj2.Yvelocity){
        swap(obj1,obj2)
    }
    friction=overlapX*0.01
    if(2*friction>obj2.Yvelocity-obj1.Yvelocity){
        obj1.addYvelocity+=(obj2.Yvelocity-obj1.Yvelocity)/2
        obj2.addYvelocity-=(obj2.Yvelocity-obj1.Yvelocity)/2
    }
    else{
        obj1.addYvelocity+=friction
        obj2.addYvelocity-=friction
    }
}
else{ //Do collision in direction Y

}

The point of the addXvelocity and addYvelocity properties is that these are added to their object's velocity after all collision handling is done.

Edit:
You could do stuff in the following order, where each bullet must be performed on all elements before the next is performed:

• Detect collisions, they may be resolved as soon as they are detected.
• Add the addVelocity values to the velocity values, add gravity Yvelocity, reset the addVelocity values to 0, move objects according to their velocity.
• Render the scene.

Also, I realize that the following might not be completely clear in my initial post, under the influence of gravity objects will overlap when resting on top of one another, this suggests that their collision box should be slightly higher than their graphical representation to avoid overlapping visually. This problem will be lesser if the physics is run at a higher update rate. I suggest you try running at 120Hz for a reasonable compromise between CPU time and physics accuracy.

Edit2:
Very basic physics engine flow:

• Collisions and gravity produce force/acceleration. acceleration = [Complicated formulas]
• Force/acceleration are added to velocity. velocity += acceleration
• Velocity is added to position. position += velocity

Answer 2

Well, you're obviously not a someone who gives up easily, you're a real man of iron, I would have thrown my hands in the air much earlier, since this project bears a strong resemblance to a kelp forest :)

First of all, positions and velocities are set all over the place, from a viewpoint of physics subsystem it's a recipe for a disaster. Also, when changing integral things by various subsystems, create a private methods like "ChangeVelocityByPhysicsEngine", "ChangeVelocityBySpring", "LimitVelocity", "TransferVelocity" or something like that. It will add an ability of checking changes made by a specific part of logic and provide an additional meaning to these velocity changes. That way debugging would be easier.

First problem.

Onto the question itself. Now you're just applying position and velocities fixes "as they go" in order of appearance and game logic. That won't work for complex interactions without carefully hard-coding the physics of each complex thing. A separate physics engine is not needed then.

In order to do complex interactions without hacks, you need to add an additional step between detecting collisions based on positions which were changed by initial velocities and final changes of positions based on "after-velocity". I imagine it would go like this:

• integrate velocity using the all the forces acting on bodies (you're applying velocity fixes directly now, leave velocity calculations to your physics engine and use forces to move things instead), then use the new velocity to integrate positions.
• detect collisions, then restore velocity and positions,
• then process collisions (using impulses without immediate position update, ofc, only velocity is changed until the final step)
• integrate new velocity again and process all collisions using impulses again, except now collisions are inelastic.
• make final integration of positions using resulting velocity.

Additional things may pop up, like dealing with jerking, refusal to stack up when FPS is small, or other things like that, be prepared :)

Second problem

Vertical velocity of both those "deadweight" crates never changes from zero. Strangely, in PhysSpring's Update loop you assign velocity, but in PhysCrate's Update loop it's already zero. It's possible to find a line where velocity goes wrong, but I stopped debugging here since it's "Reap What You Sew" situation. It's time to stop coding and start rethinking everything when debugging becomes hard. But if it comes to a point where it's impossible even for code's author to understand what's going on in the code, then your code base is already dead without you realizing it :)

Third problem

I think that something is off when you need to recreate a portion of Farseer to do a simple tile-based platformer. Personally, I would think of your current engine as of tremendous experience, and then ditch it completely for more simple and straightforward tile-based physics. While doing so, it would be wise to pick up on things like Debug.Assert and maybe even, oh the horror, unit tests, since it would be possible to catch unexpected things earlier.

Answer 3

When a body collides with another, it transfers its velocity to the other one by simply setting the body's velocity to its own.

Your problem is that these are fundamentally wrong assumptions about motion, so what you're getting doesn't resemble motion as you're familiar with it.

When a body collides with another, momentum is conserved. To think of this as "A hits B" versus "B hits A" is to apply a transitive verb to an intransitive situation. A and B collide; the resulting momentum must be equal to the initial momentum. That is, if A and B are equal mass, they are now both traveling with the mean of their original velocities.

You will also likely need some collision slop and an iterative solver, or you'll run into stability issues. You should probably read through some of Erin Catto's GDC presentations.

Answer 4

I think you have made a really noble effort, but it seems there are fundamental problems with how the code is structured. As other have suggested, it may help to separate the operations into discreet parts, eg:

1. Broad phase: Loop through all the objects - do a quick test (eg, AABB) to determine which objects may be colliding - discard those that aren't.
2. Narrow phase: Loop through all the colliding objects - calculate a penetration vector for the collision (eg, using SAT).
3. Collision response: Loop through the list of collision vectors - calculate a force vector based on the mass, then use this to calculate an acceleration vector.
4. Integration: Loop through all the acceleration vectors and integrate position (and rotation if needed).
5. Rendering: Loop through all the calculated positions and render each object.

By separating the phases all objects are updated progressively in sync and you won't have the order dependencies you are currently struggling with. The code also generally turns out to be simpler and easier to change. Each of these phases is fairly generic, and it's often possible to substitute better algorithms after you have a working system.

That said, each of these parts is a science in itself, and can occupy a great deal of time trying to find the optimal solution. It may be better to start with some of the most commonly used algorithms:

• Broad phase collision detection: Spatial hashing.
• Narrow phase collision detection: For simple tile physics, you can just apply Axis Aligned Bounding Box (AABB) intersection tests. For more complicated shapes you can use Separating Axis Theorem. Whatever algorithm you use, it should return the direction and depth of an intersection between two objects (called the penetration vector).
• Collision response: Use Projection to resolve inter-penetration.
• Integration: The integrator is the largest determinant of the engine's stability and speed. Two popular options are Verlet (fast but simple) or RK4 (accurate but slow) integration. Using verlet integration can lead to an extremely simple design as most physical behaviours (bounce, rotation) just work without too much effort. One of the best references I have seen for learning RK4 integration is Glen Fiedler's series on physics for games.

A good (and obvious) place to start is with Newton's laws of motion.