2D Platformer Collision Problems With Both Axes

Question

I'm working on a little 2D platformer/fighting game with C++ and SDL, and I'm having quite a bit of trouble with the collision detection.

The levels are made up of an array of tiles, and I use a for loop to go through each one (I know it may not be the best way to do it, and I may need help with that too). For each side of the character, I move it one pixel in that direction and check for a collision (I also check to see if the character is moving in that direction). If there is a collision, I set the velocity to 0 and move the player to the edge of the tile.

My problem is that if I check for horizontal collisions first, and the player moves vertically at more than one pixel per frame, it handles the horizontal collision and moves the character to the side of the tile even if the tile is below (or above) the character. If I handle vertical collision first, it does the same, except it does it for the horizontal axis.

How can I handle collisions on both axes without having those problems? Is there any better way to handle collision than how I'm doing it?

Answer 1

Yes. Vector based collision will be much better than tile based. Define each edge of a tile as lines (there are short cuts, but ignore them for now.) Now to see if a collision has occured, find the closest horizontal and vertical line. if you take the sign of lastPos.x * LineVector.y - lastPos.y * LineVector.x and compare that with thisTurnsPos.x * LineVector.y - ThisTurnsPos.y * LinePos.x. If the signs of those two values differ, you have crossed that line this tic. This doesn't check if you've crossed the end of a line segment though. You can form a dot product between the same lineVector and your curPosition (a little error here, but good enough probably) and it is either negative or greater than the line's magnitude squared, you aren't within that line segment and no collision has occured.

Now this is farily complex and you could probably get away with a simple grid check to see if you've crossed into another square's area. But! The advantage of doing it with vectors is it solves the moving faster than the size of the collision box problem and (more importantly), you can use non axis aligned lines for your collisions. This system works for any 2D vectors (and with a little massaging, 3D as well.) It also allows you slide your character along the edge of the collision box rather easily as well because you've already done 99% of the math needed to find where you are supposed to be after a collision.

I've glossed over a couple of implementation details, but I can tell that I've used the above method in countless commercial video games and it has worked like a charm. Good Luck!

Answer 2

XNA's 2D platformer example uses tile-based collision as well. The way they handle it there is pretty simple and may useful for you. Here's a stripped down explanation of what's in there (removing the specific-to-their-demo stuff):

1. After applying movement, it checks for collisions.
2. It determines the tiles the player overlaps based on the player's bounding box.
3. It iterates through all of those tiles...
   1. If the tile being checked isn't passable:
   2. It determines how far on the X and Y axes the player is overlapping the non-passable tile
   3. Collision is resolved only on the shallow axis:
      1. If Y is the shallow axis (abs(overlap.y) < abs(overlap.x)), position.y += overlap.y; likewise if X is the shallow axis.
      2. The bounding box is updated based on the position change
   4. Move on to the next tile...

It's in player.cs in the HandleCollisions() function if you grab the code and want to see what they specifically do there.