8
\$\begingroup\$

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.

Diagram #1

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.

Diagram #2

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.

\$\endgroup\$
  • \$\begingroup\$ You could just change the location of the player based on which tile came first in your check \$\endgroup\$ – Chachmu Jan 27 '14 at 16:18
6
\$\begingroup\$

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:

Collision bug

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();
}
\$\endgroup\$
  • \$\begingroup\$ Intriguing, but I still see a problem. In my second scenario, the sprite collides with a row of tiles. If I check X collisions first, there will be one incorrect detection in that scenario, and it would still be resolved to the left improperly. \$\endgroup\$ – Celarix Mar 1 '14 at 20:44
  • \$\begingroup\$ @Celarix The second scenario shouldn't happen because you aren't just checking the X axis first, you are moving along it first. The sprite would never be in a row of tiles, because the Y collision test from the previous movement would prevent you from colliding with a row of tiles like that. Just make sure that collisions are always resolved properly. I once had some problems being caused by the fact that I was using floats to store my coordinates. So it was causing shaking. The solution was to round the coords when I finished resolving collision. \$\endgroup\$ – Lysol Mar 2 '14 at 2:00
  • \$\begingroup\$ You're right, and I think this might be the solution to my problem of almost two years. (I'm a slow developer.) Thank you so much! \$\endgroup\$ – Celarix Mar 2 '14 at 3:14
  • \$\begingroup\$ There are some issues with my answer. It works for most situations, but note that there will be different outcomes depending on whether you check X collision first or Y collision first. Also keep in mind that tunneling is an issue; this will fail with high-velocity objects since they will skip over tiles. \$\endgroup\$ – Lysol Oct 10 '16 at 4:33
  • \$\begingroup\$ I think I went with X first so slopes would work right. Bullet-through-paper isn't really a problem in my platformer because nothing moves nearly fast enough to pass through tiles. Thanks for the further input! \$\endgroup\$ – Celarix Oct 11 '16 at 19:02
0
\$\begingroup\$

You're overthinking the problem and conflating a couple of issues. But that's okay because, as you said, this is a very solved problem with lots of great answers out there.

Let's break it down:

  1. Tilemaps. Your first example is of a sprite walking across a bunch of tiles laid out horizontally (or sliding down a wall of tiles laid out vertically, they're isomorphic). One very elegant solution to this is to simply not check the edges of tiles where we know a sprite can't get to, such as edges that are "underground" or edges that border another completely solid tile.

    You're right that the sprite would descend due to to gravity, then move laterally, then get stuck... but the answer is to not care about the left or right edges of the tiles that are underground. That way, your collision resolution routine only moves the sprite vertically — and your sprite can go on its merry way.

    Check out the Metanet tile tutorials for a step-by-step explanation of this. You say in your question that you're not using a traditional tilemap, but that's okay too: static tiles are in the tilemap and update as above, while moving platforms and such update as #2 below.

  2. Other AABBs. You'll only run into a problem if, in a single frame, your sprite can move a distance larger than the width/height of most AABBs in your game. If it can't, you're golden: resolve the collisions one-by-one and it'll work just fine.

    If the AABBs can move very fast in a single frame then you should "sweep" the movement when checking for collisions: chunk up the movement into tinier fractions and check for collisions at each step.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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