Separate axis theorem applied to AABB misunderstood

Question

I'm trying to implement a collision system for a 2D platformer using the SAT algorithm. For what I need, my implementation only handles AABB's, I followed the instructions given here. It works, there is only a little something I'm having trouble solving, let me explain.

In this scenario I expect the player to swing along the left side of the wall. From what I understand of the SAT algorithm, in this case, when the player reaches the bottom of one of the static entities constituting the wall, a collision on Y would happens.

To illustrate, that's what I'm trying to do in the picture, at some point, the overlap on the Y axis will become lower than the one on the X axis. Regarding the linked tutorial, the overlap on Y should then be used to create the projection vector.

It's what's happening in my implementation, I only accept collisions on X pushing away the player to the left, but it's not the case. Collision on Y happens when my player reaches the bottom of an entity resulting to an odd feeling.

Am I misunderstanding the SAT algorithm, should this case never happen? Or is there a way to avoid it?.

Here is the SAT part of my collision system implementation:

    private Vector2 testCollision(SATAABB box1, SATAABB box2, Vector2 velocity) {
        float ox = (box1.wx.len() + box2.wx.len())
                - box1.getDistanceBetweenCentersOnX(box2);
        if (ox <= 0) //no overlap on X, no collision
            return null;
        float oy = (box1.wy.len() + box2.wy.len())
                - box1.getDistanceBetweenCentersOnY(box2);
        if (oy <= 0) //no overlap on Y, no collision
            return null;

        if (ox < oy) { 
            projectionVector.set((box1.center.x > box2.center.x) ? ox : -ox, 0);
            velocity.x = 0;
        } else {
            projectionVector.set(0, (box1.center.y > box2.center.y) ? oy : -oy);
            velocity.y = 0;
        }
        return projectionVector;

The SATAABB is a simple class holding half width vectors on both axis and a center position.

---

EDIT: After using time equations, it's way better, still a case remains I'm having trouble with. The player is moving on the ground with a positive X velocity and a positive Y velocity (gravity). Here is the equations for that particular case:

timeCollisionX = (player.topright.x - wall.topleft.x) / velocity.x;
timeCollisionY = (player.bottomright.y - wall.topleft.y) / velocity.y;

And I come in a situation where those equations are equal to:

timeCollisionX = (324,000000 - 320,000000) / 5,000000 = 0,800000
timeCollisionY = (448,200012 - 448,000000) / 0,200000 = 1,000061

Which results to a X collision where only Y collisions should occur because the difference between the player top right corner and the wall top left corner on X is lower than the actual velocity on X. Any idea on how to deal with this?

Answer 1

You're not misunderstanding the SAT algorithm, but you're confusing collision detection with collision resolution. The SAT algorithm just detects collisions; it doesn't tell you what to do about them.

The projection vector that you can generate with SAT is not necessarily useful for collision resolution; people commonly want to use this vector to push apart the colliding objects, but that causes problems like the one you're seeing, where the direction of the push can suddenly change in undesirable ways.

Basically the way to fix it is to look for the earliest collision along the trajectory of the moving object(s), rather than looking for the minimum vector to push them apart. There are some other questions here that touch on this issue: Finding the contact point with SAT and How to deal with corner collisions in 2D. You may also want to google about "continuous collision detection". It's not a simple problem to solve in general, though.

When you have multiple objects in the world, you might detect a collision with several objects in the same frame. When this happens, again you need to look for the earliest collision across all of them. So you can't just stop with the first object where you find a collision; you have to calculate the collision time for all colliding objects and choose the earliest.

Once the earliest collision has been resolved (i.e. you changed the position so that the objects no longer collide) you should re-run the whole collision detection algorithm with the new position, since there could be another collision you need to handle. For instance if the character is running along the ground and hits a wall, you first resolve the collision with the ground and prevent him falling through it, but then his modified position still hits the wall, so you need to re-run the algorithm to detect and resolve that as well.

For a 2D platformer with rectangular objects, running it twice is probably enough. In general you might need to run it many times, which gets expensive fast, and can cause all sorts of problems when multiple moving objects hit each other. Algorithms for resolving multiple collisions robustly and fast are a subject of intense research, and this is where a lot of the complexity of a physics engine is.