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.

I am having some problems with collision detection, I have 2 types of objects excluding the player. Tiles and what I call MapObjects. The tiles are all 16x16, where the MapObjects can be any size, but in my case they are all 16x16. When my player runs along the mapobjects or tiles, it get verry jaggy. The player is unable to move right, and will get warped forward when moving left. I have found the problem, and that is 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, if you want to look that through. I think that my general approach might be wrong when i am working with small tiles, I have also be unable to find any good information on physics and collision detection in Platform games. http://dl.dropbox.com/u/3181816/Sogaard.Games.SuperMario.rar

share|improve this question
    
You can try disallowing movement in the first place if it results in a collision, that would probably allow you to avoid situations like this. –  Byte56 Mar 13 '12 at 23:46
    
I added an answer below. I noticed you're from Denmark, so am I, so if you need any help understanding, or need more explanations, feel free to contact me using the email on my profile. –  William 'MindWorX' Mariager Mar 16 '12 at 6:12
    
Thanks William, yes i am form Denmark, but i am currently living in San Diego, Ca :D –  DoomStone Mar 16 '12 at 7:54
    
@William 'MindWorX' Mariager Where are no email listed on your account! –  DoomStone Mar 17 '12 at 19:34
    
Oh, I see it isn't. Well, here it is: nikolaj dot mariager at gmail dot com –  William 'MindWorX' Mariager Mar 17 '12 at 21:56
add comment

2 Answers

up vote 7 down vote accepted
+100

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.

Tile walls

share|improve this answer
    
ill be honest, I didnt really read the question or answer, but +1 to take you into the thousands! –  Aralox Mar 17 '12 at 10:10
    
Hmm maby i am not understanding this correctly, but an't you doing the same as me, just without setting the position first? –  DoomStone Mar 17 '12 at 16:56
    
@DoomStone, Like I explain in the last paragraph, I'm fixing the velocity, rather than fixing the position. Also, I check corners separately. Added an image of how my walls are picked for collision checking. –  William 'MindWorX' Mariager Mar 17 '12 at 17:15
add comment

Diagrammatically

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

The problem collision

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.

share|improve this answer
    
This is a great way to look at it, and is also the reason I chose to treat tiles as walls and floors, as it allows me to treat it as a collision with one object, rather than multiple objects. –  William 'MindWorX' Mariager Mar 18 '12 at 16:00
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.