2D collision detection for a block game

Question

Background Knowledge:

The player can be freely transformed around the screen but each block is locked to a grid. This grid is 16x16 pixels and the players bounding box is 20x44 pixels. The blocks are stored in a List<MapObject> MapData where MapObject consists of three variables (X, Y, type).

Short Question

What is the best way to detect 2D collisions for a game that is made with thousands of blocks or is there a problem with what I am currently doing?

Problem

I started off with simple AABB collision detection and it worked fine until I started adding a large map with over 54,000 blocks. Currently the code goes like this:

1. Loop through every object in the MapData list
2. Check Collision (Player, Object) return direction
3. Move player next to the object in the opposite direction of the collision

However, the problem with this is that it has to loop through thousands of objects some of them being very far away.

So I came up with another solution where I would create a matrix of blocks around the player. This method

public List<Vector2> GetNearByGrids(Rectangle playerRect, int gridDistance)

This method works like this:

1. Get the top, bottom, left and right boundaries of playerRect + gridDistance in pixels
2. Convert these boundaries into grid form
3. Fill in each grid cell within these boundaries and add them to the grid matrix

or the code

public List<Vector2> GetNearByGrids(Rectangle playerRect, int gridDistance)
    {
        /*
         * Create a bounding box "gridDistance" around the player
         * Check if any of the points are negative and set a bool
         * Convert Pixels->Grid
         * Add them to the grid matrix
         * return grid matrix
        */

        List<Vector2> gridMatrix = new List<Vector2>();

        int pxTop = playerRect.Y - (gridDistance * gridY), 
            pxBottom = (playerRect.Y + playerRect.Height) + (gridDistance * 16), 
            pxLeft = playerRect.X - (gridDistance * gridX), 
            pxRight = (playerRect.X + playerRect.Width) + (gridDistance * 16);

        bool isTopNeg = pxTop < 0, 
            isBotNeg = pxBottom < 0, 
            isLeftNeg = pxLeft < 0, 
            isRightNeg = pxRight < 0;

        float top = 0, bottom = 0, left = 0, right = 0;

        #region Pixel->Grid Conversion If/Else
        if (isTopNeg)
        {
            if (-pxTop <= gridY)
                top = -1;
            else
            {
                float temp = (((float)pxTop) / gridY) - 1;
                top = (int)temp;
            }
        }
        else
        {
            if (pxTop <= gridY)
                top = 1;
            else
            {
                float temp = (((float)pxTop) / gridY) + 1;
                top = (int)temp;
            }
        }

        if (isBotNeg)
        {
            if (-pxBottom <= gridY)
                bottom = -1;
            else
            {
                float temp = (((float)pxBottom) / gridY) - 1;
                top = (int)temp;
            }
        }
        else
        {
            if (pxBottom <= gridY)
                bottom = 1;
            else
            {
                float temp = (((float)pxBottom) / gridY) + 1;
                bottom = (int)temp;
            }
        }

        if (isLeftNeg)
        {
            if (-pxLeft <= gridX)
                left = -1;
            else
            {
                float temp = (((float)pxLeft) / gridX) - 1;
                left = (int)temp;
            }
        }
        else
        {
            if (pxLeft <= gridX)
                left = 1;
            else
            {
                float temp = (((float)left) / gridX) + 1;
                left = (int)temp;
            }
        }

        if (isRightNeg)
        {
            if (-pxRight <= gridX)
                right = -1;
            else
            {
                float temp = (((float)pxRight) / gridX) - 1;
                right = (int)temp;
            }
        }
        else
        {
            if (pxRight <= gridX)
                right = 1;
            else
            {
                float temp = (((float)pxRight) / gridX) + 1;
                right = (int)temp;
            }
        }
        #endregion

        // Add each grid cell to the matrix
        for (float i = top; i < bottom; i += 1.0f)
        {
            for (float j = left; j < right; j += 1.0f)
            {
                gridMatrix.Add(new Vector2(j, i));
            }
        }

        return gridMatrix;
    }

With this grid matrix in a list I would then for loop through the list and check player collision with each object. For each item in the matrix I would use LINQ on the MapData list to check if there was an item in that grid space.

if (MapData.FindIndex(x => x.X == collisionMatrix[i].X) >= 0) { ...

Then inside of that if statement I would do steps 2 & 3 from the original collision detection.

2. Check Collision (Player, Object) return direction
3. Move player next to the object in the opposite direction of the collision

But this isn't working like I hoped it would. I was wondering if anyone picked up on something wrong with this that I didn't. Or if anyone had a solution to this problem that was completely different.

If you need more information I'll try my best to get it for you,

Solution

The map is loaded into chunks which contain a 4x4 grid of blocks. If the user collides with a chunk the collision detection function will go into more detail and check collision for each block in that chunk. The result of the collision detection function is this

class CollisionResult
{
    public CollisionResult(CollisionResultType result, MapObject obj)
    {
        this.result = result;
        this.obj = obj;
    }

    public CollisionResultType result { get; set; }
    public MapObject obj { get; set; }
}

// Collision Class
public List<CollisionResult> ChunkCollisionDetection(WCPlayer player, List<MapChunk> chunkData)
{

List<CollisionResult> collisionResults = new List<CollisionResult>();

foreach (MapChunk chunk in chunkData)
{
    int chunk_x = (chunk.X * 16) - 16, chunk_y = (chunk.Y * 16) - 16;

    if (
        player.Rect.X + player.Rect.Width >= chunk_x &&     // X-Axis: Player->Left, Object->Right
        chunk_x + 64 >= player.Rect.X &&                    // X-Axis: Player->Right, Object->Left
        player.Rect.Y + player.Rect.Height >= chunk_y &&    // Y-Axis: Player->Above, Object->Below
        chunk_y + 64 >= player.Rect.Y                       // Y-Axis: Player->Below, Object->Above)
    )
    {
        // Collision with chunk -> Check for collision with blocks inside of chunk
        foreach (MapObject obj in chunk.MapObjects)
        {
            int obj_x = (obj.X * gridX) - gridX, obj_y = (obj.Y * gridY) - gridY;

            if (
                player.Rect.X + player.Rect.Width >= obj_x &&       // X-Axis: Player->Left, Object->Right
                obj_x + gridX >= player.Rect.X &&                   // X-Axis: Player->Right, Object->Left
                player.Rect.Y + player.Rect.Height >= obj_y &&      // Y-Axis: Player->Above, Object->Below
                obj_y + gridY >= player.Rect.Y                      // Y-Axis: Player->Below, Object->Above)
            )
            {
                if (player.Rect.Y + player.Rect.Height >= obj_y && player.Rect.Y + player.Rect.Height <= obj_y + gridY)
                {
                    Vector2 newPos = new Vector2(player.Position.X, (obj.Y * GridY) - player.Height - GridY);
                    player.SetPosition(newPos, new Rectangle((int)newPos.X, (int)newPos.Y, player.Rect.Width, player.Rect.Height));

                    // Let the player jump again
                    player.Jumping = true;

                    collisionResults.Add(new CollisionResult(CollisionResultType.CollisionBelow, obj));
                }
                else if (player.Rect.X + player.Rect.Width >= obj_x && player.Rect.X + player.Rect.Width <= obj_x + (gridX / 2))
                {
                    Vector2 newPos = new Vector2((obj.X * GridX) - player.Width - GridX, player.Position.Y);
                    player.SetPosition(newPos, new Rectangle((int)newPos.X, (int)newPos.Y, player.Rect.Width, player.Rect.Height));

                    collisionResults.Add(new CollisionResult(CollisionResultType.CollisionRight, obj));
                }
                else if (obj_x + gridX >= player.Rect.X && obj_x + gridX <= player.Rect.X + (player.Rect.Width / 2))
                {
                    Vector2 newPos = new Vector2((obj.X * GridX), player.Position.Y);
                    player.SetPosition(newPos, new Rectangle((int)newPos.X, (int)newPos.Y, player.Rect.Width, player.Rect.Height));

                    collisionResults.Add(new CollisionResult(CollisionResultType.CollisionLeft, obj));
                }
                else if (obj_y + gridY >= player.Rect.Y) // Y-Axis: Player->Below, Object->Above
                {
                    Vector2 newPos = new Vector2(player.Position.X, obj.Y * GridY);
                    player.SetPosition(newPos, new Rectangle((int)newPos.X, (int)newPos.Y, player.Rect.Width, player.Rect.Height));

                    collisionResults.Add(new CollisionResult(CollisionResultType.CollisionAbove, obj));
                }
            }
        }
    }
}   

return collisionResults;
}

Thanks, Isaac

Answer 1

The first thing you should do is breaking up the terrain into chunks. This helps in both rendering and collision detection.

Using these chunks to do collision detection greatly reduces the complexity. If one of your chunks contains 20*20 "blocks" in it, then you need to check collision against 1/400th as many areas.

Here you should use the swept AABB algorithm to avoid fast moving projectiles going through solid objects.

After you assured you collide with one of the chunks, you need to check if the player collides with any of the blocks in that chunk. You should also use swept AABB for this.

You need to find the closest collision point and only do the collision after that

Swept AABB:

https://www.gamedev.net/resources/_/technical/game-programming/swept-aabb-collision-detection-and-response-r3084