2D Platformer AABB collision problems

Question

I have a problem with AABB collision resolution.

---

I resolve AABB intersection by resolving the X axis first, then the Y axis. This is done to prevent this bug: https://i.sstatic.net/NLg4j.png

---

The current method works fine when an object moves into the player and the player has to be pushed horizontally. As you can see in the .gif, the horizontal spikes push the player correctly.

---

When the vertical spikes move into the player, however, the X axis is still resolved first. This makes "using the spikes as a lift" impossible.

When the player moves into the vertical spikes (affected by gravity, falls into them), he's pushed on the Y axis, because there was no overlap on the X axis to begin with.

---

Something I tried was the method described in the first answer of this link: 2D rectangular object collision detection

However the spikes and moving objects move by having their position changed, not velocity, and I don't calculate their next predicted position until their Update() method is called. Needless to say this solution didn't work either. :(

---

I need to solve AABB collision in a way that both of the cases described above work as intended.

This is my current collision source code: http://pastebin.com/MiCi3nA1

I'd be really grateful if someone could look into this, since this bug has been present in the engine all the way back from the beginning, and I've been struggling to find a good solution, without any success. This is seriously making me spend nights looking at the collision code and preventing me from getting to the "fun part" and coding the game logic :(

---

I tried implementing the same collision system as in the XNA AppHub platformer demo (by copy-pasting most of the stuff). However the "jumping" bug occurs in my game, while it doesn't occur in the AppHub demo. [ jumping bug: https://i.sstatic.net/NLg4j.png ]

To jump I check if the player is "onGround", then add -5 to Velocity.Y.

Since the player's Velocity.X is higher than Velocity.Y (refer to the fourth panel in the diagram), onGround is set to true when it shouldn't be, and thus lets the player jump in mid-air.

I believe this doesn't happen in the AppHub demo because the player's Velocity.X will never be higher than Velocity.Y, but I may be mistaken.

I solved this before by resolving on the X axis first, then on the Y axis. But that screws up the collision with the spikes as I stated above.

Answer 1

OK, I figured out why the XNA AppHub platformer demo doesn't have the "jumping" bug: the demo tests the collision tiles from top to bottom. When up against a "wall" the player may be overlapping multiple tiles. The resolution order is important because resolving one collision may also resolve other collisions (but in a different direction). The onGround property is only set when the collision is resolved by pushing the player up on the y-axis. This resolution will not occur if the previous resolutions pushed the player down and/or horizontally.

I was able to reproduce the "jumping" bug in the XNA demo by changing this line:

for (int y = topTile; y <= bottomTile; ++y)

to this:

for (int y = bottomTile; y >= topTile; --y)

(I also tweaked some of the physics-related constants, but this should not matter.)

Perhaps sorting bodiesToCheck on the y-axis before resolving the the collisions in your game will fix the "jumping" bug. I suggest resolving the collision on the "shallow" axis of penetration, as the XNA demo does and Trevor suggests. Also note the XNA demo player is twice as tall as the collide-able tiles, making the multiple collision case more likely.

Answer 2

The simplest solution for you will be to check both collision directions against every object in the world before resolving any collisions, and just resolve the smaller of the two resulting "compound collisions". This means that you resolve by the smallest amount possible, instead of always resolving x first, or always resolving y first.

Your code would look something like this:

// This loop repeats, until our object has been fully pushed outside of all
// collision objects
while ( StillCollidingWithSomething(object) )
{
  float xDistanceToResolve = XDistanceToMoveToResolveCollisions( object );
  float yDistanceToResolve = YDistanceToMoveToResolveCollisions( object );
  bool xIsColliding = (xDistanceToResolve != 0.f);

  // if we aren't colliding on x (not possible for normal solid collision 
  // shapes, but can happen for unidirectional collision objects, such as 
  // platforms which can be jumped up through, but support the player from 
  // above), or if a correction along y would simply require a smaller move 
  // than one along x, then resolve our collision by moving along y.

  if ( !xIsColliding || fabs( yDistanceToResolve ) < fabs( xDistanceToResolve ) )
  {
    object->Move( 0.f, yDistanceToResolve );
  }
  else // otherwise, resolve the collision by moving along x
  {
    object->Move( xDistanceToResolve, 0.f );
  }
}

big revision: From reading commentary on other answers, I think I've finally noticed an unstated assumption, which will cause this approach not to work (and which explains why I couldn't understand the problems that some -- but not all -- people saw with this approach). To elaborate, here is some more pseudocode, showing more explicitly what the functions I referenced before are supposed to actually be doing:

bool StillCollidingWithSomething( MovingObject object )
{
  // loop over every collision object in the world.  (Implementation detail:
  // don't test 'object' against itself!)
  for( int i = 0; i < collisionObjectCount; i++ )
  {
    // if the moving object overlaps any collision object in the world, then
    // it's colliding
    if ( Overlaps( collisionObject[i], object ) )
      return true;
  }
  return false;
}

float XDistanceToMoveToResolveCollisions( MovingObject object )
{
  // check how far we'd have to move left or right to stop colliding with anything
  // return whichever move is smaller
  float moveOutLeft = FindDistanceToEmptySpaceAlongNegativeX(object->GetPosition());
  float moveOutRight = FindDistanceToEmptySpaceAlongX(object->GetPosition());
  float bestMoveOut = min( fabs(moveOutLeft), fabs(moveOutRight) );

  return minimumMove;
}

float FindDistanceToEmptySpaceAlongX( Vector2D position )
{
  Vector2D cursor = position;
  bool colliding = true;
  // until we stop colliding...
  while ( colliding )
  {
    colliding = false;
    // loop over all collision objects...
    for( int i = 0; i < collisionObjectCount; i++ )
    {
      // and if we hit an object...
      if ( Overlaps( collisionObject[i], cursor ) )
      {
        // move outside of the object, and repeat.
        cursor.x = collisionObject[i].rightSide;
        colliding = true;

        // break back to the 'while' loop, to re-test collisions with
        // our new cursor position
        break;
      }
    }
  }
  // return how far we had to move, to reach empty space
  return cursor.x - position.x;  
}

This is not a "per object pair" test; it doesn't work by testing and resolving the moving object against each tile of a world map individually (that approach will never work reliably, and fails in increasingly catastrophic ways as tile sizes decrease). Instead, it is testing the moving object against every object in the world map simultaneously, and then resolving based upon collisions against the whole world map.

This is how you ensure that (for example) individual wall tiles within a wall never bounce the player up and down between two adjacent tiles, resulting in the player being trapped in some non-existant space 'between' them; the collision resolution distances are always calculated all the way to empty space in the world, not merely to the boundary of a single tile which might then have another solid tile on top of it.

Answer 3

Edit

I have improved it

It seems the key thing I changed is classifying the intersections.

Intersections are either:

• Ceiling bumps
• Ground hits (push out of the floor)
• Mid-air wall collisions
• Grounded wall collisions

and I resolve them in that order

Define a ground collision as player being at least 1/4 way on the tile

So this is a ground collision and the player (blue) will sit on top of the tile (black)

But this is NOT a ground collision and the player will "slip" on the right side of the tile when he lands on it

By this method the player will no longer get caught on the sides of walls

Answer 4

Forenote:
My engine uses a collision detection class that checks collisions with all objects real time, only when an object moves, and only in the grid squares it currently occupies.

My Solution:

When I ran against problems like this in my 2d platformer, I did something like the following :

-(engine detects possible collisions, quickly)
-(game informs engine to check exact collisions for particular object)[returns vector of object*]
-(object looks at depth of penetration, as well as previous position relative to other object's previous position, to determine which side to slide out of)
-(object moves, and averages it's velocity with object's velocity (if the object is moving))

Answer 5

In video games I have programmed the approach was to have a function telling if your position is valid, ie. bool ValidPos(int x,int y, int wi,int he);

The function checks the bounding box (x,y,wi,he) against all geometry in the game and returns false if there is any intersection.

If you want to move, say to the right, take the player position, add 4 to x and check if the position is valid, if not, check with +3,+2 etc until it is.

If you also need to have gravity you need a variable that grows as long as you dont hit the ground (hitting ground: ValidPos(x,y+1, wi,he) == true, y is positive downwards here). if you can move that distance (ie. ValidPos(x,y+gravity,wi,he) returns true) you are falling, useful sometimes when you shouldn't be able to control you character when falling.

Now, your problem is that you have objects in your world that moves so first of all you need to check if your old position is still valid!

If it is not, you need to find a position that is. If objects ingame can't move faster than say 2 pixels per game revolution, you would need to check if position (x,y-1) is valid, then (x,y-2) then (x+1,y) etc etc. the whole space between (x-2,y-2) to (x+2,y+2) should be checked. If there are no valid position then it means you have been 'crushed'.

HTH

Valmond

Answer 6

I have a few questions before I start answering this. First, in the original bug in which you got stuck in the walls, were those tiles on the left individual tiles as opposed to one large tile? And if they were, was the player getting stuck in between them? If yes to both those questions, just make sure your new position is valid. That means you'll have to check if there's a collision on where your telling the player to move. So solve the minimum displacement as described below, and then move your player based on that only if he can move there. Almost too under the nose :P This will actually introduce another bug, which I call "corner cases". Essentially in terms of corners (like the bottom left where the horizontal spikes come out in your .gif, but if there were no spikes) would not resolve a collision, because it would think that none of the resolutions you generate lead to a valid position. To solve this, simply keep a bool of whether the collision has been resolved, as well as a list of all the minimum penetration resolutions. Afterwards, if the collision has not been resolved, loop over every resolution you generated, and keep track of the maximum X and maximum Y resolutions (the maximums don't have to come from the same resolution). Then resolve the collision on those maximums. This seems to solve all your problems as well as the ones I've encountered. Here's the code I use in my update:

    List<Vector2> collisions = new List<Vector2>();
        bool resolved = false;
        foreach (Platform p in testPlat)
        {
            Vector2 dif = p.resolveCollision(player.getCollisionMask());

            RectangleF newPos = player.getCollisionMask();

            newPos.X -= dif.X;
            newPos.Y -= dif.Y;


            if (!PlatformCollision(newPos)) //This checks if there's a collision (ie if we're entering an invalid space)
            {
                if (dif.X != 0)
                    player.velocity.X = 0; //Do whatever you want here, I like to stop my player on collisions
                if (dif.Y != 0)
                    player.velocity.Y = 0;

                player.MoveY(-dif.Y);
                player.MoveX(-dif.X);
                resolved = true;
            }
            collisions.Add(dif);
        }

        if (!resolved)
        {
            Vector2 max = Vector2.Zero;

            foreach (Vector2 v in collisions)
            {
                if (Math.Abs(v.X) > Math.Abs(max.X))
                {
                    max.X = v.X;
                }
                if (Math.Abs(v.Y) > Math.Abs(max.Y))
                {
                    max.Y = v.Y;
                }
            }

            player.MoveY(-max.Y);

            if (max.Y != 0)
                player.velocity.Y = 0;
            player.MoveX(-max.X);

            if (max.X != 0)
                player.velocity.X = 0;
        }

Another question, are the spikes you show one tile, or individual tiles? If they are individual thin tiles, you may have to use a different approach for the horizontal ones and vertical ones than what I describe below. But if they're whole tiles this should work.

---

Alright, so basically this is what @Trevor Powell was describing. Since you're using only AABBs, all you have to do is find how much one rectangle penetrates the other. This will give you a quantity in the X axis and the Y. Choose the minimum out of the two, and move your colliding object along that axis that amount. That is all you need to resolve an AABB collision. You will NEVER need to move along more than one axis in such a collision, so you should never be confused about what one to move first, as you will only be moving the minimum.

Metanet software has a classic tutorial on an approach here. It also goes into other shapes as well.

Here's an XNA function I made to find the overlap vector of two rectangles:

    public Point resolveCollision(Rectangle otherRect)
    {
        if (!isCollision(otherRect))
        {
            return Point.Zero;
        }

        int minOtherX = otherRect.X;
        int maxOtherX = otherRect.X + otherRect.Width;

        int minMyX = collisionMask.X;
        int maxMyX = collisionMask.X + collisionMask.Width;

        int minOtherY = otherRect.Y;
        int maxOtherY = otherRect.Y + otherRect.Height;

        int minMyY = collisionMask.Y;
        int maxMyY = collisionMask.Y + collisionMask.Height;

        int dx, dy;

        if (maxOtherX - minMyX < maxMyX - minOtherX)
        {
            dx = (maxOtherX - minMyX);
        }
        else
        {
            dx = -(maxMyX - minOtherX);
        }

        if (maxOtherY - minMyY < maxMyY - minOtherY)
        {
            dy = (maxOtherY - minMyY);
        }
        else
        {
            dy = -(maxMyY - minOtherY);
        }

        if (Math.Abs(dx) < Math.Abs(dy))
            return new Point(dx, 0);
        else
            return new Point(0, dy);
    }

(I hope it's simple to follow, because I'm sure there are better ways to implement it...)

isCollision(Rectangle) is literally just a call to XNA's Rectangle.Intersects(Rectangle).

I've tested this with moving platforms and it seems to work fine. I'll do some more tests more similar to your .gif to make sure and report back if it doesn't work.

---

Answer 7

It's simple.

Rewrite the spikes. It's the spikes' fault.

Your collisions should happen in discrete, tangible units. The problem as far as I can see it is:

1. Player is outside spikes
2. Spikes move into intersection position with the player
3. Player resolves incorrectly

The problem is with step 2, not 3!!

If you're trying to get things to feel solid, you should not let items slide into each other like that. Once you are in a position of intersection, if you lose your place, the problem becomes harder to solve.

The spikes should ideally check for the existence of the player and, when they move, they should push him as necessary.

An easy way to achieve this is for the Player to have moveX and moveY functions which understand the landscape and will shove the player by a certain delta or as far as they can without hitting an obstacle.

Normally they will be called by the event loop. However they can also be called by objects in order to push the player.

function spikes going up:

    move spikes up

    if intersecting player:
        d = player bottom edge + spikes top edge

        player.moveY(-d)
    end if

end function

Obviously the player still needs to react to the spikes if he goes into them.

The overarching rule is, after any object moves, it should end in a position without intersection. This way, it's impossible to get the glitches you are seeing.