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.

http://dl.dropbox.com/u/3724424/Programming/Gifs/game6.gif

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: http://i.stack.imgur.com/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: http://i.stack.imgur.com/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.

share|improve this question
4  
There actually is nothing going wrong. The method I'm using pushes on the X axis first, then on the Y axis. That's why the player gets pushed horizontally even on the vertical spikes. I need to find a solution that avoids the "jumping problem" and pushes the player on the shallow axis (the axis with least penetration), but I can't find any. –  Vittorio Romeo Jul 4 '11 at 22:09
1  
You could detect which face of the obstruction the player is touching, and resolve that one –  Ioachim Jul 4 '11 at 23:41
25  
+1 for the animated .gif showing gameplay! –  Kevin Y Jul 5 '11 at 0:51
4  
@Johnathan Hobbs, read the question. Vee knows exactly what his code is doing, but doesn't know how to solve a certain problem. Stepping through the code will not help him in this situation. –  AttackingHobo Jul 5 '11 at 2:12
4  
@Maik @Jonathan: Nothing is "going wrong" with the program - he understands exactly where and why his algorithm doesn't do what he wants it to. He just doesn't know how to change the algorithm to do what he wants. So the debugger is not useful in this case. –  BlueRaja - Danny Pflughoeft Jul 5 '11 at 7:22
show 6 more comments

7 Answers

up vote 6 down vote accepted
+100

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.

share|improve this answer
    
This sounds interesting... Do you think that ordering everything by the Y coordinate before detecting collisions could solve all of my problems? Is there any catch? –  Vittorio Romeo Jul 10 '11 at 19:11
    
Aaaand I found the "catch". Using this method, the jumping bug is corrected, but if I set Velocity.Y to 0 after hitting a ceiling, it occurs again. –  Vittorio Romeo Jul 11 '11 at 11:29
    
@Vee: set Position = nextPosition immediately inside the for loop, otherwise the unwanted collision resolutions (setting onGround) still occur. The player should be pushed vertically down (and never up) when hitting the ceiling thus onGround should never be set. This is how the XNA demo does it, and I cannot repro the "ceiling" bug there. –  Leftium Jul 11 '11 at 12:25
    
pastebin.com/TLrQPeBU - this is my code: I actually work on the Position itself, without using a "nextPosition" variable. It should work as it does in the XNA demo, but if I keep the line that sets Velocity.Y to 0 (line 57) uncommented then the jumping bug occurs. If I remove it, the player keeps floating when jumping into a ceiling. Can this be fixed? –  Vittorio Romeo Jul 11 '11 at 14:34
    
@Vee: your code doesn't show how onGround is set, so I can't investigate why jumping is incorrectly allowed. The XNA demo updates its analogous isOnGround property inside HandleCollisions(). Also, after setting Velocity.Y to 0, why does gravity not starting moving the player down, again? My guess is the onGround property is improperly set. Take a look at how the XNA demo updates previousBottom and isOnGround (IsOnGround). –  Leftium Jul 11 '11 at 15:53
show 4 more comments

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.

share|improve this answer
1  
i.stack.imgur.com/NLg4j.png - this happens if I use the above method. –  Vittorio Romeo Jul 5 '11 at 8:02
1  
Maybe I'm not understading your code correctly, but let me explain the problem in the diagram: since the player is faster on the X axis, the X penetration is > than Y penetration. Collision chooses Y axis (because the penetration is smaller) and pushes the player vertically. This does not occur if the player is slow enough so that Y penetration is always > than X penetration. –  Vittorio Romeo Jul 5 '11 at 13:18
1  
@Vee Which pane of the diagram are you referring to, here, as giving an incorrect behaviour using this approach? I'm assuming pane 5, in which the player is clearly penetrating less in X than in Y, which would result in being pushed out along the X axis -- which is the correct behaviour. You only get the bad behaviour if you're selecting an axis for resolution based upon velocity (as in your image), and not based upon actual penetration (as I suggested). –  Trevor Powell Jul 5 '11 at 22:57
1  
@Trevor: Ah, I see what you're saying. In that case, you could simply make it if(fabs( yDistanceToResolve ) < fabs( xDistanceToResolve ) || xDistanceToResolve == 0) { object->Move( 0.f, yDistanceToResolve ); } else { object->Move( xDistanceToResolve, 0.f ); } –  BlueRaja - Danny Pflughoeft Jul 10 '11 at 5:51
1  
@BlueRaja Great point. I've edited my answer to use fewer conditionals, as you suggest. Thanks! –  Trevor Powell Jul 10 '11 at 8:22
show 4 more comments

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

share|improve this answer
    
I used to use this approach back in my Game Maker days. I can think of ways to speed it up/improve it with better searches (say a binary search on the space you traveled, although depending on the distance you went and the geometry, it maybe slower), but the main drawback of this approach is that instead of doing say one check against all possible collisions, you're doing up to whatever your change in position is checks. –  Jeff Jul 9 '11 at 18:03
    
"you're doing up to whatever your change in position is checks" Sorry but what exactly does than mean? BTW of course you will use space partitioning techniques (BSP, Octree, quadtree, Tilemap etc) to speed up the game but you'll Always need to do that anyway (if the map is big), the question is not about that however but about the algorithm used to move (correctly) the player. –  Valmond Jul 9 '11 at 19:22
    
@Valmond I think @Jeff means that if you player is moving 10 pixels left, you can have up to 10 different collision detections. –  Jonathan Connell Jul 11 '11 at 11:47
    
If that is what he is meaning then he is right and it should be that way (who can otherwise tell if we get stopped at +6 and not +7 ?). Computers are fast, I used this on the S40 (~200mhz and a not so fast kvm) and it worked like a charm. You can always try to optimize the initial algo but that will always give you corner cases like the one the OP have. –  Valmond Jul 11 '11 at 12:02
    
That's exactly what I meant –  Jeff Jul 15 '11 at 0:37
add comment

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.


share|improve this answer
    
I am kind of skeptical of that comment I made on it not working with thin platforms. I can't think of a reason why it wouldn't. Also if you want source, I can upload an XNA project for you –  Jeff Jul 9 '11 at 14:35
    
Yeah I was just testing this out some more and it goes back to your same problem of getting stuck in the wall. It's because where the two tiles line up with each other, it tells you to move up because of the lower one, and then out (right in your case) for the upper one, effectively negating the gravity movement if your y velocity is slow enough. I'll have to look into a solution for this, I seem to remember having this problem before. –  Jeff Jul 9 '11 at 17:11
    
Okay, I've come up with an extremely hacky way to get around your first problem. The solution involves finding the minimum penetration for each AABB, resolving only on the one with the largest X, then a second pass resolving only on the largest Y. It looks bad when you're being crushed, but lifts work and you can be pushed horizontally, and your original sticking problem is gone. It is hackey, and I have no idea how it would translate over to other shapes. Another possibility may be to weld the touching geometries, but I haven't even attempted that –  Jeff Jul 9 '11 at 18:34
    
Walls are made of 16x16 tiles. Spikes are a 16x16 tile. If I resolve on the minimum axis, the jumping bug occurs (look at the diagram). Would your "extremely hacky" solution work with the situation shown in the .gif? –  Vittorio Romeo Jul 9 '11 at 19:11
    
Yep, works in mine. What's your character's size? –  Jeff Jul 9 '11 at 20:54
show 5 more comments

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))

share|improve this answer
    
"(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)" this is the part I'm interested in. Can you elaborate? Does it succeed in the situation shown by the .gif and the diagram? –  Vittorio Romeo Jul 9 '11 at 22:59
    
I've yet to find a situation (other than high velocities) that this method does not work in. –  ultifinitus Jul 10 '11 at 6:00
    
Sounds good, but can you actually explain how do you resolve penetrations? Do you solve always on the smallest axis? Do you check the side of the collision? –  Vittorio Romeo Jul 10 '11 at 11:25
    
No as a matter of fact the smaller axis is not a good (primary) way to go. IMHO. I usually resolve based on which side was previously outside of the other object's side, it's the most common. When that fails, then I check based on velocity and depth. –  ultifinitus Jul 11 '11 at 2:51
add comment

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) ground collision

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

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

share|improve this answer
    
I tried your method (see my implementation: pastebin.com/HarnNnnp) but I don't know where to set the player's Velocity to 0. I tried setting it to 0 if encrY <= 0 but that lets the player stop in mid air while sliding along a wall and also lets him repeatedly wall-jump. –  Vittorio Romeo Jul 10 '11 at 11:40
    
However, this works correctly when the player interacts with the spikes (as shown in the .gif). I would really appreciate if you could help me solve the wall-jumping (also getting stuck in walls) problem. Keep in mind that my walls are made of several AABB tiles. –  Vittorio Romeo Jul 10 '11 at 11:46
    
Sorry for posting another comment, but after copy-pasting your code in a brand new project, changing sp to 5 and making the tiles spawn in a wall shape, the jumping bug happens (refer to this diagram: i.stack.imgur.com/NLg4j.png) –  Vittorio Romeo Jul 10 '11 at 12:03
    
Ok, try it now. –  bobobobo Jul 14 '11 at 0:38
    
+1 for working code sample (missing horizontally moving "spike" blocks, though :) –  Leftium Jul 14 '11 at 4:44
show 1 more comment

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.

share|improve this answer
    
in the extreme case where moveY fails to remove the intersection (because another wall is in the way) you can check again for intersection and either try moveX or just kill him. –  Chris Burt-Brown Jul 27 '11 at 11:33
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.