Collision Detection Errors and Lagging movement

Question

this is my first time doing this and im sorry if im doing this wrong but for the last couple of weeks i've been working on a little project with xna and c# while following a book i made a simple platformer game with enemies and collectibales and traps but i ran into an issue...

You see i have struggled to find (and to write) a good collision detection function to use. I ultimately used one from the Microsoft platformer project in addition to the function found in the book i was reading everything was fine but i noticed that the game character was lagging (sort of moving in bursts instead of smooth motion) while moving. The frame rate was stable and well above 400 (i turned off fixed time step).

So my question is if someone can take a look at my code and tell me whats the problem.. i think the main problem is in the HandleCollisons function or the horizontal and vertical collision detecting functions

ps: english is not my first language as you might have noticed so sorry for the bad grammer :D/> anyway thanks in advance

this is the class that does the collision Detection :

    public override void Update(GameTime gameTime)
    {
        float elapsed = (float)gameTime.ElapsedGameTime.TotalSeconds;

        Vector2 prevLocation = worldLocation;

        if (useGravity) { speed.Y += Gravity.Y * elapsed; }

        Vector2 moveAmount;
        moveAmount.X = speed.X * elapsed;
        moveAmount.Y = speed.Y * elapsed;

        if (isPlayer)
        {
            moveAmount = horizontalCollisionTest(moveAmount);
            moveAmount = verticalCollisionTest(moveAmount);
        }
        if (moveAmount == Vector2.Zero)
        {
            worldLocation = prevLocation;
        }
        else
        {
            worldLocation.X += moveAmount.X;
            worldLocation.Y += moveAmount.Y;
        }

        HandleCollisions();

        if (limitSpeed)
        {
            if (speed.X > maxSpeed.X) speed.X = maxSpeed.X;
            if (speed.X < -maxSpeed.X) speed.X = -maxSpeed.X;
            if (speed.Y > maxSpeed.Y) speed.Y = maxSpeed.Y;
            if (speed.Y < -maxSpeed.Y) speed.Y = -maxSpeed.Y;
        }

        if ((speed.Y > MaxSpeed.Y / 20))
        {
            onGround = false;
            jumping = true;
        }

        if (!beingMoved)
        {
            if (speed.X < 0) speed.X += deaccelerationX * elapsed;
            if (speed.X > 0) speed.X -= deaccelerationX * elapsed;

            if (speed.X > 0 && speed.X < (deaccelerationX * elapsed)) speed.X = 0;
            if (speed.X < 0 && speed.X > (-deaccelerationX * elapsed)) speed.X = 0;
        }

        if (worldLocation.X <= 0)
        {
            worldLocation.X = 0;
            speed.X = 0;
        }
        if (worldLocation.X >= (Camera.WorldRectangle.Width - FrameWidth))
        {
            worldLocation.X = Camera.WorldRectangle.Width - FrameWidth;
            speed.X = 0;
        }

        base.Update(gameTime);
    }

    private void HandleCollisions()
    {
        Rectangle bounds = CollisionRectangle;
        int left = (int)((bounds.Left / TileMap.TileWidth)) * TileMap.TileWidth;
        int right = (int)((bounds.Right / TileMap.TileWidth)) * TileMap.TileWidth;

        int top = (int)((bounds.Top / TileMap.TileHeight)) * TileMap.TileHeight;
        int bottom = (int)((bounds.Bottom / TileMap.TileHeight)) * TileMap.TileHeight;

        for (int i = left; i <= right; i += TileMap.TileWidth)
        {
            for (int j = top; j <= bottom; j += TileMap.TileHeight)
            {
                Rectangle tile = TileMap.CellWorldRectangle(i / TileMap.TileWidth, j / TileMap.TileHeight);

                if (!TileMap.CellIsPassable(TileMap.GetCellByPixel(new Vector2(i, j))))
                {
                    Rectangle tileRect = new Rectangle(i, j, TileMap.TileWidth, TileMap.TileHeight);
                    Vector2 depth = RectangleExtensions.GetIntersectionDepth(bounds, tileRect);

                    if (depth != Vector2.Zero)
                    {
                        float absDepthX = Math.Abs(depth.X);
                        float absDepthY = Math.Abs(depth.Y);

                        if (absDepthY <= absDepthX)
                        {
                            if (preBottom <= tileRect.Top)
                            {
                                onGround = true;
                                jumping = false;
                            }
                            if (onGround)
                            {
                                worldLocation = new Vector2(worldLocation.X, worldLocation.Y + depth.Y + 1);
                                bounds = CollisionRectangle;
                                speed.Y = 0;
                            }
                        }
                        else
                        {
                            worldLocation = new Vector2(worldLocation.X + depth.X, worldLocation.Y);
                            bounds = CollisionRectangle;
                            speed.X = 0;
                        }
                    }
                }
            }
        }
        preBottom = bounds.Bottom;
    }

    private Vector2 horizontalCollisionTest(Vector2 moveAmount)
    {
        if (moveAmount.X == 0)
            return moveAmount;

        Rectangle afterMoveRect = CollisionRectangle;
        afterMoveRect.Offset((int)moveAmount.X, -5);
        Vector2 corner1, corner2;

        if (moveAmount.X < 0)
        {
            corner1 = new Vector2(afterMoveRect.Left,
                                  afterMoveRect.Top + 1);
            corner2 = new Vector2(afterMoveRect.Left,
                                  afterMoveRect.Bottom - 1);
        }
        else
        {
            corner1 = new Vector2(afterMoveRect.Right,
                                  afterMoveRect.Top + 1);
            corner2 = new Vector2(afterMoveRect.Right,
                                  afterMoveRect.Bottom - 1);
        }

        Vector2 mapCell1 = TileMap.GetCellByPixel(corner1);
        Vector2 mapCell2 = TileMap.GetCellByPixel(corner2);

        if (!TileMap.CellIsPassable(mapCell1) ||
            !TileMap.CellIsPassable(mapCell2))
        {
            moveAmount.X = 0;
            speed.X = 0;
        }

        return moveAmount;
    }

    private Vector2 verticalCollisionTest(Vector2 moveAmount)
    {
        if (moveAmount.Y == 0)
            return moveAmount;

        Rectangle afterMoveRect = CollisionRectangle;
        afterMoveRect.Offset((int)moveAmount.X, (int)moveAmount.Y + 1);
        Vector2 corner1, corner2;

        if (moveAmount.Y < 0)
        {
            corner1 = new Vector2(afterMoveRect.Left + 1,
                                  afterMoveRect.Top);
            corner2 = new Vector2(afterMoveRect.Right - 1,
                                  afterMoveRect.Top);
        }
        else
        {
            corner1 = new Vector2(afterMoveRect.Left + 1,
                                  afterMoveRect.Bottom);
            corner2 = new Vector2(afterMoveRect.Right - 1,
                                  afterMoveRect.Bottom);
        }

        Vector2 mapCell1 = TileMap.GetCellByPixel(corner1);
        Vector2 mapCell2 = TileMap.GetCellByPixel(corner2);

        if (!TileMap.CellIsPassable(mapCell1) ||
            !TileMap.CellIsPassable(mapCell2))
        {
            if (moveAmount.Y > 0)
            {
                onGround = true; 
            }
            moveAmount.Y = 0;
            speed.Y = 0;
        }            

        return moveAmount;
    }

    public override void Draw(SpriteBatch spriteBatch)
    {
        base.Draw(spriteBatch);
    }
}

}

and the code for the rectangle intersection depth is :

public static Vector2 GetIntersectionDepth(this Rectangle rectA, Rectangle rectB)
    {
        // Calculate half sizes.
        float halfWidthA = rectA.Width / 2.0f;
        float halfHeightA = rectA.Height / 2.0f;
        float halfWidthB = rectB.Width / 2.0f;
        float halfHeightB = rectB.Height / 2.0f;

        // Calculate centers.
        Vector2 centerA = new Vector2(rectA.Left + halfWidthA, rectA.Top + halfHeightA);
        Vector2 centerB = new Vector2(rectB.Left + halfWidthB, rectB.Top + halfHeightB);

        // Calculate current and minimum-non-intersecting distances between centers.
        float distanceX = centerA.X - centerB.X;
        float distanceY = centerA.Y - centerB.Y;
        float minDistanceX = halfWidthA + halfWidthB;
        float minDistanceY = halfHeightA + halfHeightB;

        // If we are not intersecting at all, return (0, 0).
        if (Math.Abs(distanceX) >= minDistanceX || Math.Abs(distanceY) >= minDistanceY)
            return Vector2.Zero;

        // Calculate and return intersection depths.
        float depthX = distanceX > 0 ? minDistanceX - distanceX : -minDistanceX - distanceX;
        float depthY = distanceY > 0 ? minDistanceY - distanceY : -minDistanceY - distanceY;
        return new Vector2(depthX, depthY);
    }

Answer 1

I disabled all collisions and left only movement player was still jittering. SO! I have started to dig into movement and found that the player speed is stable at maximum speed and do not vary it means no cause jitter again. SO! Next my step was digging around a camera and I think i have found what are you looking for! Seems you are calculating a camera reposition at player input before all other code movement calculation etc. and it cause jitter. I did reposition() method after base.Update() ( after all code of movement being processed) and I think it works! Here is a little change of a code in the Player.cs Update method. Watch at repositionCamera(); placement at the code:

    public class Player : MovingGameObject
    {
    ...
    public override void Update(GameTime gameTime)
    {
        float elapsed = (float)gameTime.ElapsedGameTime.TotalSeconds;
        this.beingMoved = false;

        if (canBeDameged)
        {
            if (!canTakeDamage)
            {
                timeSinceDamage += (float)gameTime.ElapsedGameTime.Milliseconds;
                if (timeSinceDamage >= damegeDelay)
                {
                    canTakeDamage = true;
                    timeSinceDamage = 0;
                }
            }
        }

        if (hasInput)
        {
            string newAnimation = "Stand";

            if (Input.KeyDown(leftKey0) ||
                Input.KeyDown(leftKey1))
            {
                speed.X -= accelerationX * elapsed;
                beingMoved = true;
                flipped = true;
                newAnimation = "Walk";
            }
            if (Input.KeyDown(rightKey0) ||
                Input.KeyDown(rightKey1))
            {
                speed.X += accelerationX * elapsed;
                beingMoved = true;
                flipped = false;
                newAnimation = "Walk";
            }
            if ((Input.KeyPressed(jumpKey0) ||
                Input.KeyPressed(jumpKey1) ||
                Input.KeyPressed(jumpKey2)))
            {
                Jump();
                newAnimation = "Jump";
            }
            if ((Input.KeyDown(downKey0) ||
                Input.KeyDown(downKey1)))
            {
                speed.Y += Gravity.Y * 3 * elapsed;
            }
            HandelAnimations(newAnimation);

            //repositionCamera(); --> replace it after base.Update(gameTime)
        }

        base.Update(gameTime);

        repositionCamera(); // place here!
    }
    ...
    }

Answer 2

Your collision detection is awesome. In my 2d game I use simple XNA rectangles (bounds of a texture). The world has many different blocks (64x64 textures with rectangles) and I use simple wrapping textures to increase the size of a block then I check whether the rectangle of a character was intersected with any world rectangle by calling character.rectangle.Intersects(world.rectangles[i]) into the loop of world rectangles.

Seems your loops are expensive for your game Update() method:

        for (int i = left; i <= right; i += TileMap.TileWidth)
        {
           for (int j = top; j <= bottom; j += TileMap.TileHeight)
           {
              ...
           }
        }

To optimize this LARGE loop which probably cause FPS drops I use QuadTree.

Read this about quadtree which optimize collision detection

You can use different algorithms such as Octree, BinaryTree, BSP etc. but quadtree is the best choise for 2d space.