What is the correct order of operations for collision detection and response?

Question

I am trying to make a 2D game engine, but I can't seem to get collisions to work all the time (Often times things get stuck or pass through each other). Without getting into the code too much, here is the order in which I am updating.

1. Get user input and update the player velocity
2. Save the position for each entity, then move the velocity / update interval units
3. Check each movable entity for collisions against all other entities. If the entity collides with something, it is moved to its old position and the new velocities are set for both colliding entities.

The collision impulse is calculated in this function:

private static void CollisionImpulse(PhysicsEntity a, PhysicsEntity b)
    {
        var relative = b.Velocity.Vector - a.Velocity.Vector;
        var normal = Vector2.Normalize(relative);
        var e = Math.Min(a.Material.Elasticity, b.Material.Elasticity);
        var j = (-(1 + e) * Vector2.Dot(relative, normal)) /
                (Vector2.Dot(normal, normal) * (a.InverseMass + b.InverseMass));
        if (double.IsNaN(j)) return;

        var velocityA = normal * (float) (j / a.Mass);
        var velocityB = normal * (float) (j / b.Mass);

        a.Velocity.X -= velocityA.X;
        a.Velocity.Y -= velocityA.Y;

        if (!b.Movable) return;
        b.Velocity.X += velocityB.X;
        b.Velocity.Y += velocityB.Y;
        b.Position = b.OldPosition;
    }

and this is the function to check for the collisions:

public override void Update()
        {
            foreach (var entity in Universe.PhysicsEntities)
            {
                if (entity.Equals(this) || entity.Collided) continue;
                CollisionResolution.ResolveCollision(this, entity);
                if (!Collided) continue;
                Position = OldPosition;
                break;
            }
        }

I have been trying to tweak the code for a few days, but I cannot figure out what is wrong. I was hoping some fresh eyes could shed some light on my dilemma.

Answer 1

There is a fundamental issue with step 3 "If the entity collides with something, it is moved to its old position..." - because you are now moving this entity again, you need to re-run the collision detection for all previous entities against this entity, otherwise you might cause an overlap.

E.g. if you had 3 pool balls (A,B,C), you move all 3 to their desired new positions to A',B',C' (in your step 2). Now for step 3 you check and A'B' and A'C' don't collide, and they don't, but then you check B'C' and they do collide, so in your solution you move B',C' back to B,C - BUT now technically you may have moved B and/or C so it's now intersecting with A.

To make your step 3 work you either need to:

1) Ensure that no objects overlap at the start, and whenever you detect a collision in your step 3 either (a) re-run the collision on every previous object that we'd previously said didn't collide with these objects, OR keep rerunning the whole of step 3 until no objects were reset on the last loop. This can become expensive if you have a lot of objects and they all start resetting each other.

or:

2) Instead of resetting objects to their last frame's "safe" position each time, the resultant force (so acceleration, not velocity) is related to how much the objects interpenetrate. This is common in 3D physics engines, and can result in objects exploding if they interpenetrate too much.

Also note that if you ever move an object very far in 1 frame (e.g. further than half it's size), it could potentially pass through another object without the collision overlap detection firing. This is often known as the bullet-through-paper problem