2D AABB collision response

Question

I'm making a simple platformer, and I wanted simple collision handling. So I gave all my objects an AABB hitbox and tried to resolve collisions. However, I can't get it to work.

My main character has a 32x32 hitbox and my walls have a 16x16 hitbox. I've used the separating axes solution to resolve the collision, like so (unoptimized):

Vec2 Box::Collides(Box* a_Other)
{
    Vec2 sum_extents;
    sum_extents.x = (m_Max.x - m_Min.x) + (a_Other->GetMax().x - a_Other->GetMin().x);
    sum_extents.y = (m_Max.y - m_Min.y) + (a_Other->GetMax().y - a_Other->GetMin().y);

    Vec2 double_center_to_center;
    double_center_to_center.x = (a_Other->GetMin().x + a_Other->GetMax().x) - (m_Min.x + m_Max.x);
    double_center_to_center.y = (a_Other->GetMin().y + a_Other->GetMax().y) - (m_Min.y + m_Max.y);

    bool result = (fabsf(double_center_to_center.x) < sum_extents.x) && (fabsf(double_center_to_center.y) < sum_extents.y);

    if (result)
    {
        return (
            Vec2(
                ((sum_extents).x - (double_center_to_center).x) / 2.f, 
                ((sum_extents).y - (double_center_to_center).y) / 2.f
            )
        );  
    }

    return (Vec2(0.f, 0.f));
}

My character just falls down onto the floor. I check the object I want to check against every other object and just see which one has the smallest intersection area.

Object* Scene::Collides(Object* a_Test, Vec2& a_Difference)
{
    float smallest_area = 10000.f;
    Object* closest = NULL;
    Vec2 final;

    std::vector<Vec2> check;

    for (uint32 i = 0; i < s_ObjectTotal; i++)
    {
        if (a_Test == s_Objects[i]) { continue; }

        Vec2 test = a_Test->GetCollision()->Collides(s_Objects[i]->GetCollision());
        float area = test.x * test.y;
        if (area > 0.f)
        {
            check.push_back(test);

            if (area < smallest_area)
            {
                smallest_area = area;
                final = test; 
                closest = s_Objects[i];
            }
        }
    }

    if (closest) 
    { 
        a_Difference = final;
    }

    return closest;
}

The hitbox for the player is (32, 229.999995)(64, 261.999994) and the hitbox for the floor is (48, 256)(64, 272). So, the resulting movement (to resolve the collision) is (16, 5.9999930). The y is correct, the x is not. As a result, the player character hits the floor, stays above it and slides to the right very fast.

How do I resolve this collision?

Answer 1

This is how I solved it.

I already knew when it collides. There is lots of stuff on the interwebz about the separating axis theorem. Google that and you're halfway there.

Now the hard part: resolving the collision. After a good hard discussion with a teacher, we came up with the following. A collision can be resolved in four ways:

• Box A moves left to resolve collision with Box B
• Box A moves right to resolve collision with Box B
• Box A moves up to resolve collision with Box B
• Box A moves down to resolve collision with Box B

And if you take the diagonals of Box B and determine on which side of the line the other box's center is... tadaa! It still has a tiny problem though: even though logic says it should resolve a collision from the bottom, it wants to resolve it to the right. I don't know what's up with that.

uint8 Box::Resolve(Box* a_Other)
{
    Vec2 diff, perp;

    diff = m_Pivot - a_Other->m_Pivot;

    perp.x = -a_Other->m_Min.y + a_Other->m_Pivot.y;
    perp.y = a_Other->m_Min.x - a_Other->m_Pivot.x;
    float d1 = perp.GetDotProduct(diff);

    perp.x = -a_Other->m_Min.y + a_Other->m_Pivot.y;
    perp.y = a_Other->m_Max.x - a_Other->m_Pivot.x;
    float d2 = perp.GetDotProduct(diff);

    // left
    if (d1 < 0 && d2 < 0)
    {
        m_Pos.x = a_Other->m_Min.x - (m_HalfHeight * 2);
        Compute();

        return BOX_LEFT;
    }
    // right
    if (d1 > 0 && d2 > 0)
    {
        m_Pos.x = a_Other->m_Max.x;
        Compute();

        return BOX_RIGHT;
    }
    // down (and right?!)
    if (d1 < 0 && d2 > 0)
    {
        m_Pos.x = a_Other->m_Max.x;
        Compute();

        return BOX_RIGHT;
    }
    // up
    if (d1 > 0 && d2 < 0)
    {
        m_Pos.y = a_Other->m_Min.y - (m_HalfHeight * 2);
        Compute();

        return BOX_UP;
    }

    return BOX_NONE;
}

Answer 2

I'm not sure about your Scene collision. But it looks to me like your box collision has a problem. I've seen this mistake before; it looks to me like you're finding the centers of the boxes, and calculating distance between the centers. That's not box collision; that's sphere collision. Think about it for a moment.

Honestly your algorithm is entirely unclear to me, when AABB collision is pretty simple (especially in 2 dimensions, which is essentially AAS (Axis-Aligned Square) collision).

You can use the process of elimination:

• Let's say box A is to the left of box B. Then if the right side of A is left of the left side of box B, there can be no collision.
• Now suppose box A is to the right of box B. If the right side of B is left of the left side of A, there can be no collision.
• If neither of the above two cases were true, then the boxes are overlapping in some way in this dimension.
• Now do the same in the Y dimension (the two steps, but with above/below). If neither of the Y dimension cases were true, the boxes overlap in some way in the Y dimension.
• So if the boxes overlap in the X dimension and and in the Y dimension, then they overlap. Otherwise, if they overlap in only one dimension, then they are just above/below each other, or left/right of each other, but not touching.

---

So your algorithm should look something like this:

Vec2 Box::Collides(Box* a_Other)
{
    final Vec2 nullResult(0.0f, 0.0f);

    float xOverlap = 0.0f, yOverlap = 0.0f;

    /* test the X direction */
    if(m_Max.x < a_Other->GetMin().x || a_Other->GetMax().x < m_Min.x) {
        return nullResult;
    } else {
        // get center X's of this and other box
        float thisCenterX = (m_Min.x + m_Max.x) / 2.0f;
        float otherCenterX = (a_Other->GetMin().x + a_Other->GetMax().x) / 2.0f;

        if(thisCenterX < otherCenterX) {
            xOverlap = m_Max.x - a_Other->GetMin().x;
        } else {
            xOverlap = a_Other->GetMax().x - m_Min.x;
        }
    }

    /* test the Y direction */
    // (repeat the above but with Y instead of X)

    // if necessary, do the same in the Z direction

    return Vec2(xOverlap, yOverlap);
}

Answer 3

In my opinion, you should move your player only by smaller part of the result movement. In this case (5.9..)

Answer 4

The problem with your solution (I think) is that you're resolving the axes independently in the case of a collision; even though the boxes are only touching in the Y, they are overlapping in the X so this algorithm is going to try to push them apart in that axis as well. I'm not sure if there's an "easy" solution to this problem and suspect that the most straight forward way to deal with it would be to split your collision detection into four "modes," which is bottom, left, right, and top collision with the player. Actually, Kaemon's answer would do this, sort of, since it'll only move along the axis that is least-penetrating.

The problem with general collision resolution is that it requires a lot more state than you're passing in. What direction are the bodies moving relative to one another? If you know that, then you can figure out what direction to push them away from one another when a collision is triggered. You could also resolve the corners against the other box's faces, which would allow you to spin the box if you wanted to (e.g. one corner is overlapping so it stops while the other corner keeps moving) (although if you want to keep things simple this would be undesirable).

The easiest way to detect collision in AA bodies is something like this:

for axis in [x, y, etc...]:
   if (body1.axis.min > body2.axis.max) or (body1.axis.max < body2.axis.min):
      # can't possibly be colliding
      return false

   # must be colliding if we got here
   return true

However, this only tells you that the bodies are colliding, not what to do. Again, the decision about what to do requires more information.