Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
add comment

4 Answers 4

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;
}
share|improve this answer
    
You don't handle d1 or d2 equalling zero. Beyond that, why did you do X math and assign it to Y? I don't think you're getting the data that you want to get, which could explain why you're seeing behavior you don't want. -- The "check against the diagonals" idea is clever, now you just need to implement it correctly. :) –  dash-tom-bang Sep 16 '10 at 17:44
add comment

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);
}
share|improve this answer
1  
This returns the same data that the OP's test does, it just computes it differently. (Note the divide-by-2 instead of a variable named 'double...') –  dash-tom-bang Sep 15 '10 at 18:52
    
My problem is that when my bigger box (32x32) collides with a smaller one (16x16) it moves on the y for a bit but also on the x, which is incorrect. –  knight666 Sep 15 '10 at 21:10
    
@dash-tom-bang Ah, I see it now! Very interesting... –  Ricket Sep 16 '10 at 2:10
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.