0
\$\begingroup\$

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.

  1. Check Collision (Player, Object) return direction
  2. 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

\$\endgroup\$
  • \$\begingroup\$ IMHO your problem is not a collision detection but rendering instead. From what I've understood you're making 2D tile based game so my suggestion would be : make a 2 dimensional array of "visible" tiles and based on these tiles make your collision detection. So instead of iterating all of the tiles you only iterate let's say ` { camera.x-10, camera.y - 10, camera.x + 10, camera.t + 10 }`. \$\endgroup\$ – Mateusz Feb 13 '17 at 11:00
  • \$\begingroup\$ I haven't yet got a camera set up but I will note this down for when it is ready. Instead of an array for the tiles I will probably make one of the chunks as suggested in Bálint answer. @m.rogalski \$\endgroup\$ – Isaac Skelton Feb 14 '17 at 5:01
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Really interesting webpage, I have put the blocks into chunks now and it seems to be working (from reading data) but I need to fix my player physics before I can actually see the results. Is four by four blocks enough for a chunk or should I go larger (player < 3 blocks). \$\endgroup\$ – Isaac Skelton Feb 14 '17 at 4:56
  • \$\begingroup\$ @Isaac Again, you should decide that yourself. If they aren't big enough, it doesn't increase performance that much, if they're too big, then you need to check for a lot of blocks inside it in case the player collides with it \$\endgroup\$ – Bálint Feb 14 '17 at 7:40

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.