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:
- Loop through every object in the MapData list
- Check Collision (Player, Object) return direction
- 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:
- Get the top, bottom, left and right boundaries of playerRect + gridDistance in pixels
- Convert these boundaries into grid form
- 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.
- Check Collision (Player, Object) return direction
- 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