How do I resolve a collision of a rectangle with two rectangular tiles at once?

Question

I am having some problems with collision detection between a player and the environment in a tile-based game. I have a player objects, Tiles and what I call MapObjects. The tiles are all 16×16. The MapObjects can be any size, but in my case they are all 16×16. The game jitters when the player runs along the MapObjects or tiles. The player is unable to move right, and will get warped forward when moving left. I have found the problem: My collision detection will move the player left/right if colliding the object from the side, and up/down if collision from up/down.

Now imagine that my player is sitting on 2 tiles, at (10,12) and (11,12), and the player is mostly standing on the (11,12) tile. The collision detection will first run on then (10,12) tile, it calculates the collision depth, and finds that is is a collision from the side, and therefore move the object to the right. After, it will do the collision detection with (11,12) and it will move the character up. So the player will not fall down, but are unable to move right. And when moving left, the same problem will make the player warp forward.

This problem have been bugging me for a few days now, and I just can't find a solution!

---

Here is my code that does the collision detection.

 public void ApplyObjectCollision(IPhysicsObject obj, List<IComponent> mapObjects, TileMap map)
        {
            PhysicsVariables physicsVars = GetPhysicsVariables();
            Rectangle bounds = ((IComponent)obj).GetBound();
            int leftTile = (int)Math.Floor((float)bounds.Left / map.GetTileSize());
            int rightTile = (int)Math.Ceiling(((float)bounds.Right / map.GetTileSize())) - 1;
            int topTile = (int)Math.Floor((float)bounds.Top / map.GetTileSize());
            int bottomTile = (int)Math.Ceiling(((float)bounds.Bottom / map.GetTileSize())) - 1;

            // Reset flag to search for ground collision.
            obj.IsOnGround = false;

            // For each potentially colliding tile,
            for (int y = topTile; y <= bottomTile; ++y)
            {
                for (int x = leftTile; x <= rightTile; ++x)
                {
                    IComponent tile = map.Get(x, y);
                    if (tile != null)
                    {
                        bounds = HandelCollision(obj, tile, bounds, physicsVars);
                    }
                }
            }

            // Handel collision for all Moving objects
            foreach (IComponent mo in mapObjects)
            {
                if (mo == obj)
                    continue;

                if (mo.GetBound().Intersects(((IComponent)obj).GetBound()))
                {
                    bounds = HandelCollision(obj, mo, bounds, physicsVars);
                }
            }
        }
        private Rectangle HandelCollision(IPhysicsObject obj, IComponent objb, Rectangle bounds, PhysicsVaraibales physicsVars)
        {
            // If this tile is collidable,
            SpriteCollision collision = ((IComponent)objb).GetCollisionType();

            if (collision != SpriteCollision.Passable)
            {
                // Determine collision depth (with direction) and magnitude.
                Rectangle tileBounds = ((IComponent)objb).GetBound();
                Vector2 depth = bounds.GetIntersectionDepth(tileBounds);
                if (depth != Vector2.Zero)
                {
                    float absDepthX = Math.Abs(depth.X);
                    float absDepthY = Math.Abs(depth.Y);

                    // Resolve the collision along the shallow axis.
                    if (absDepthY <= absDepthX || collision == SpriteCollision.Platform)
                    {
                        // If we crossed the top of a tile, we are on the ground.
                        if (obj.PreviousBound.Bottom <= tileBounds.Top)
                            obj.IsOnGround = true;

                        // Ignore platforms, unless we are on the ground.
                        if (collision == SpriteCollision.Impassable || obj.IsOnGround)
                        {
                            // Resolve the collision along the Y axis.
                            ((IComponent)obj).Position = new Vector2(((IComponent)obj).Position.X, ((IComponent)obj).Position.Y + depth.Y);

                            // If we hit something about us, remove all velosity upwards
                            if (depth.Y > 0 && obj.IsJumping)
                            {
                                obj.Velocity = new Vector2(obj.Velocity.X, 0);
                                obj.JumpTime = physicsVars.MaxJumpTime;
                            }

                            // Perform further collisions with the new bounds.
                            return ((IComponent)obj).GetBound();
                        }
                    }
                    else if (collision == SpriteCollision.Impassable) // Ignore platforms.
                    {
                        // Resolve the collision along the X axis.
                        ((IComponent)obj).Position = new Vector2(((IComponent)obj).Position.X + depth.X, ((IComponent)obj).Position.Y);

                        // Perform further collisions with the new bounds.
                        return ((IComponent)obj).GetBound();
                    }
                }
            }
            return bounds;
        }

Update: I have uploaded the source code here. I think my general approach might be wrong for working with small tiles.

Answer 1

Like Byte56 suggested, rather than fix the collision, you simply doesn't allow the collision to happen in the first place.

Here's a snippet of how my engine handles it

// Reset flags just like you do.
this.IsPushingLeft = false;  
this.IsPushingRight = false;

// verticalWall is just a struct containing all the common data for whatever wall of tiles the entity would hit in the next frame.
if (verticalWall.HasValue && verticalWall.Value.IsSolid)
{
    // If we're moving right and the next position (deltaPosition) would result in a collision, we fix it so the collision doesn't happen.
    if (this.IsMovingRight && deltaPosition.X + this.Width >= verticalWall.Value.BoundingBox.Left)
    {
        this.IsPushingRight = true;
        deltaVelocity.X = verticalWall.Value.BoundingBox.Left - this.Right - 1.00f;
    }
    // If we're moving left and the next position (deltaPosition) would result in a collision, we fix it so the collision doesn't happen.
    else if (this.IsMovingLeft && deltaPosition.X < verticalWall.Value.BoundingBox.Right)
    {
        this.IsPushingLeft = true;
        deltaVelocity.X = verticalWall.Value.BoundingBox.Right - this.Left;
    }
}

// Reset flags just like you do.
this.IsPushingDown = false;
this.IsPushingUp = false;
// verticalWall is just a struct containing all the common data for whatever ceiling or floor of tiles the entity would hit in the next frame.
if (horizontalWall.HasValue && horizontalWall.Value.IsSolid)
{
    // If we're moving down and the next position (deltaPosition) would result in a collision, we fix it so the collision doesn't happen.
    if (this.IsMovingDown && deltaPosition.Y + this.Height >= horizontalWall.Value.BoundingBox.Top)
    {
        this.ActiveFriction = horizontalWall.Value.Friction;
        this.IsPushingDown = true;
        deltaVelocity.Y = horizontalWall.Value.BoundingBox.Top - this.Bottom - 1.00f;
    }
    // If we're moving up and the next position (deltaPosition) would result in a collision, we fix it so the collision doesn't happen.
    else if (this.IsMovingUp && deltaPosition.Y < horizontalWall.Value.BoundingBox.Bottom)
    {
        this.IsPushingUp = true;
        deltaVelocity.Y = horizontalWall.Value.BoundingBox.Bottom - this.Top;
    }
}

This is a somewhat generic AABB collision type. Only thing that stands out is my approach to walls rather than individual tiles, but with individual tiles it's the same thing, you'd just do the check for each tile instead.

What I essentially do, is fix the velocity vector, so rather than moving speed * delta, I move speed * delta - collisionOffset, resulting in the entity ending just next to the wall, outside the potential collision.

Here's the walls I check collision against, depending on direction.

Answer 2

Diagrammatically

When I have collision problems, I draw. This is your problem, as I understand it:

Tiles A and B, considered separately, have their own ideas of where you should go to get out of each of their collisions. In this case, the displacement out of A is superfluous: The displacement out of B is already the minimum exit distance. However, in a corner between two tiles, the combination of both displacements may be necessary to get you out of the collision. Sometimes you need that extra information, sometimes you don't.

Essentially, sometimes some tiles' contributions to the collision resolution must be dropped in order to get resolution with minimal displacement.

Untested thrown-together algorithm which looks okay

On collision, go through all combinations of displacement suggestions received from tiles. Carry out the combined displacement that involves fewest tiles but still manages to get you out of the collision.

Example run:

In the particular case doodled above, The combinations would be: a, b or a+b, with a and b respecting the displacement vectors suggested by tiles A and B respectively.

Displacing by a would not get us out of the collision, so that's out.

Displacing by b would.

Displacing by a+b also would, but it involves two tiles.

Hence b wins out and we get minimum exit. If we always go in this order of least to most tiles involved, we could already return b before even checking a+b, as b involves only one tile and so would win regardless.

-

I hope this abstraction is useful.