How to detect and prevent the resolution of fake collisions?

Question

I'm creating my own physics engine and I came across a small inconvenience. Here how it goes: when a body tries to push into something it really can't push, it gets pushed back (which is completly fine). But when it tries to push that solid plus another simple box, the box gets pushed as if the body has really moved even if it can't.

Here's a visual explanation:

My current collision resolver is solving collisions by altering position of bodies. Here is its pseudo code simplified for the question.

/**
 * Resolves the collision by pushing a body or another
 *
 */
void resolve(Collision collision) {
    float weightA = getWeight(collision.world, collision.bodyA, -collision.normal);
    float weightB = getWeight(collision.world, collision.bodyB, collision.normal);

    //This resolves who gets to push who in a collision
    DynamicBody toPush = weightA > weightB ? collision.bodyB : collision.bodyA

    Vector normal = toPush == collision.bodyA ? -collision.normal : collision.normal;

    float replaceX = normal.x * pene;
    float replaceY = normal.y * pene;

    if(replaceX != 0f) {
        //getCollisionShifting() is the total shifting done by collisions in this frame. 
        //When this resolver will be done, it will be added to the position

        float dirX = signum(toPush.getCollisionShifting().x);

        if(!original || dirX != signum(replaceX))
            toPush.getCollisionShifting().x += replaceX;
        else if(dirX == 0 || replaceX * dirX > toPush.getCollisionShifting().x * dirX)
            toPush.getCollisionShifting().x = replaceX;
    }

    /* Here, exactly the same thing is done with Y */
    //...
}

/**
 * This finds the weight of a body based on his own weight plus all the bodies its colliding with in a direction
 *
 * Uses a recursive method
 * This method might not be the best but it works and only becames inefficient for really big stacks of objects
 * Since my game won't include giant stacks, its viable for now
 */
float getWeight(World world, Body body, Vector normal) {
    float weight = body.getWeight();

    for(Collision collision : world.getCollisions()) {
        if(collision.bodyB == body)
            collision = Collision.swap(collision); //turns the collision around so bodyB becomes bodyA

        if(collision.bodyA == body && collision.normal.dot(normal) == 1f)
                weight += getWeight(world, collision.bodyB, normal);
    }

    return weight;
}

I included this code for you to have a better look at my current approach but I do not ask anyone to write the solution into that code. A theoric explanation of a working solution is what I'm looking for.

Currently, collisions aren't solved in any particular order. Will I have to sort the collisions ? I hope not since it would slow down the whole thing just for this. So, how can I fix this issue ?

P.S. : Please note that this physics engine is open source and you can access the original code of this example here.

Answer 1

You can fix this specific problem by performing collision detection and resolution against immovable objects first, then doing the same against movable objects in a second pass.

But in the general case, you have a multi-body collision problem, which is in a different class of difficulty than the two-body collision. As you've found, you run into situations where you've calculated the collision between the first pair, but then realise that collision between the second pair affects the first pair's results, so you go back to re-do the first pair, which might lead you to re-do the second pair... and so on, until you run out of energy and collisions.

One example is where B is against a wall C, and A collides into B. What happens? Well, A pushes B, but B is against a wall so all the force is reflected back, which should transfer back into A.

Lots of physics engines deal with this using multiple iterations, which nevertheless produces jittering in edge cases. And to prevent this from getting out of hand, there are lots of hacks, like slop.