c# - 2D AABBs and resolving multiple collisions

Okay, so this is a problem I've been trying to figure out for quite some time. Mine is a 2D platformer game with a world made up of (usually) immobile tiles and mobile sprites, both of which use AABBs to represent their hitboxes. This game is NOT grid-based due to some complications with moving layers of tiles.

I can detect collisions and easily figure out the depth of the collision. I use the "shallowest axis method" to determine which way to resolve a collision between the sprite and the tile. If the sprite is deeper horizontally than vertically, the direction to resolve is either up or down. If the sprite is deeper vertically than horizontally, the direction to resolve is either left or right.

This is simple enough, and it works pretty well. That is, until you have a sprite colliding with more than one tile. As, by their nature, each collision has to be checked separately, different collisions may have different direction to resolve in. For example, if a sprite is trying to walk across a row of tiles, for one frame they will intersect the next tile such that the horizontal depth is shorter than the vertical depth. As the collision says "resolve left", it will be pushed back and will be stuck on the corner.

I've been mulling this problem over, on and off, for quite some time, and several solutions have come to me, but all have flaws. I could mark certain sides as unreachable, but without a grid-based engine, determining "unreachability" is remarkably complex, especially with moving layers of tiles always a possibility.

Another possible method would be to predict collisions before they happen and "work back" the movement to the point of the collision, I suppose, but I'm not sure how the math on that works.

I feel that I'm missing something incredibly obvious, especially since games from the 80s have already solved this problem.

Answer

The problem

The problem lies in your method of collision resolution. Your method goes as follows:

1. Move the player.


2. Check for collision.



3. Determine the shortest collision depth.


4. Resolve collision.

The problem with this, is that it can easily move the player in the wrong direction. You can see how this might happen in the image below:

Because the player is moving down to the right, and is above the ground, you would expect the player to land on top of the ground (by the green box). But instead, it gets pushed out of the ground to the left (represented by the red box). This can be a problem if the player is trying to jump from one platform to another, because the player may end up falling to his death due to bad collision code.

The solution

The solution to this problem is actually pretty simple. Instead of using the above method, you resolve collision like so:

1. Move the player along the X axis.



2. Check for colliding tiles.


3. Resolve X collision.


4. Move the player along the Y axis.


5. Check for colliding tiles.


6. Resolve Y collision.

Now I hope that you didn't throw your depth check code away, because you are still going to need it for steps 3 and 6.

To resolve collision between tiles on either of the two axes (after moving the player), you first get the depth of the collision. You then take the depth of the collision, and subtract that from the axes that you are currently checking for collision. Note that the depth should be negative if you are moving to the left, so that the player moves in the right direction.

Using this method, you will not only not have to worry about collision bugs like the one in the scenario in the above image, but this method also can handle collision with multiple tiles.

Example code:

void move(velocity)
{
    top = player.y / TILE_HEIGHT;
    bottom = top + (player.height / TILE_HEIGHT);
    left = player.x / TILE_WIDTH;
    right = left + (player.width / TILE_WIDTH);

    // Check X

    player.x += velocity.x;

    player.updateAABB();
    for(int tx = left - 1; tx <= right + 1; tx++)
    {
        for(int ty = top - 1; ty <= bottom + 1; ty++)
        {
            aabb = world.getTileAABB(tx, ty);
            if(aabb.collidesWith(player.aabb))
            {
                depth = player.aabb.getXDepth(aabb);
                player.x -= depth;

            }
        }
    }

    // Now check Y

    player.y += velocity.y;
    player.updateAABB();
    for(int tx = left - 1; tx <= right + 1; tx++)
    {

        for(int ty = top - 1; ty <= bottom + 1; ty++)
        {
            aabb = world.getTileAABB(tx, ty);
            if(aabb.collidesWith(player.aabb))
            {
                depth = player.aabb.getYDepth(aabb);
                player.y -= depth;
            }
        }
    }


    player.updateAABB();
}