# Efficient Tile-based collision detection for a lot of squares?

currently I am working on my own take of a tile-based game (think Terraria, but less fantastical (I think that's a word? Sorry if it isn't)).

Anyway, I currently have collision detection working (for corner cases even!) which was a big step for me. There is something extremely gratifying about seeing a sprite not run through a block. But then I had the idea to benchmark. Bad idea.

1,000 squares, no problem. 10,000 squares, for 3 characters was kind of laggy. 100,000 squares (really huge map), for 3 characters was unplayable.

I'm having the issue where I don't want to even consider the blocks that are too far from the player, characters, items, etc., but I don't want to load those in-out of memory constantly.

Here's my algorithm so far, feel free to criticize.

``````foreach (Block in level)
{
if (distance from block to player > a specified amount)
ignore this block;
else
{
get the intersection depth between the two bounding boxes
if (depth of intersection != Zero-vector)
{
check y size vs x size
resolve on smallest axis
}
}
}
``````

As you will note, when the level size get's bigger, the Order of this algorithm grows by N blocks. I would like to not even consider blocks that aren't even near the player.

I'm thinking maybe use a (0,0) to (mapWidth,mapHeight) double-array of blocks instead of a list, calculating a danger-zone depending on the person's position e.g., if player's position is at (10, 20) it will look from (0, 10) to (20, 30), or so on.

Any thoughts and considerations are awesome, thank you.

-
And welcome to stackexchange! :-) Don't forget to read the FAQ if you're unaware of how the whole QA and reputation system works. – David Gouveia Dec 30 '11 at 13:34
Surely these tiles are larger than 16 by 16 pixels, at 1920 by 1080 that's 8,100 tiles. Surely you know where the moveable entities are, and you can only check tiles on the grid that can possibly be in range (if one is 160*160 and the center is in tile (12,12) you need only check between tiles (6,6) and (18,18) for a total of ~150 possible tiles.). Surely tiles under gravity only fall down, and so you need only look for the next tile below it. – DampeS8N Dec 30 '11 at 14:58
Do you think 16x16 is too small? It wouldn't be hard for me to change the size of the tiles, since anything that references tilewidth/height is a static constant. All I would have to do is enlarge them in Paint.NET, which is nice because it adds more detail. – Ross Dec 30 '11 at 17:36
Would you mind sharing your collision code? :/ – ashes999 Dec 6 '12 at 4:02

Yes, you're thinking correctly. You should be using a 2D array of tiles since that allows you to index tiles by position.

``````Block[,] level = new Block[width, height];
``````

And since the player can only collide with its surrounding tiles, the number of collision checks you need to do is very small. This of course depends on the size of the player. The Platformer sample does it like this:

``````int leftTile = (int)Math.Floor((float)characterBounds.Left / tileWidth);
int rightTile = (int)Math.Ceiling(((float)characterBounds.Right / tileWidth)) - 1;
int topTile = (int)Math.Floor((float)characterBounds.Top / tileHeight);
int bottomTile = (int)Math.Ceiling(((float)characterBounds.Bottom / tileHeight)) - 1;

for (int y = topTile; y <= bottomTile; ++y)
{
for (int x = leftTile; x <= rightTile; ++x)
{
// Handle collisions with the tile level[x,y] just like you were doing!
}
}
``````

Check the sample if you still have any problems.

-
This is a very nice little algorithm, I hadn't even heard of the Platformer sample (I should have, but I claim ignorance). Thank you! – Ross Dec 30 '11 at 13:27
@Ross Really? You'd be surprised at how similar your solution is to the sample. :-) Minus the list part, everything else is pretty much identical (intersect bounding boxes, get intersection depth, resolve on smallest axis). – David Gouveia Dec 30 '11 at 13:30
Oh man, I just looked at it. >.< Wish I knew this 2 days ago!! Well, I'm new to XNA but I've delved with 2D graphics (just OpenGL, not very much game programming). I guess I should check more resources first before I go head-first into coding. – Ross Dec 30 '11 at 13:47

When dealing with a large number of collisions, you usually want to adopt a more advanced structure, such as a Quadtree or Hashmap to check for those collisions.

Since tiles are static I would suggest using a Quadtree. A quad tree is made up of quads. Each quad is made up of four rectangles and each of those rectangles are quads. This continues recursively up to a specified size. Each quad can contain a list of tiles which inhabit that area of the screen. That way, when you're checking for collisions you can

1. Restrict the checks to those in the immediate vicinity
2. Restrict checks to only objects which are moving

Now if you don't want to even look at tiles off screen then you could do something like

``````public bool CheckCollision(myPosition) {
// This is not a leaf, keep checking
if(node.Position is insideViewport && nearPlayer)
// Continue recursion
}
}
}
else {
// This is a leaf, do checks
foreach(Tile tile in tileList) {
if(collision)
return true;
}
return false;
}
}
``````
-
Hmm, I've heard of Octrees in 3D collision detection but never seen an advanced Data Structure being used for 2D collision detection. Thank you very much! – Ross Dec 30 '11 at 13:01
Since his game (assuming Terraria) is made up of evenly spaced tiles, using a grid would be both a lot easier and faster than a quadtree. A quadtree works better for more complex worlds where a grid would be hard to fit and everything has arbitrary size. – David Gouveia Dec 30 '11 at 13:05
You're right if it is a purely grid-based game, even down to the character sizes. I know that in Terraria they also have monsters which do not readily fit in to a grid format. I was running under the assumption that the basic world is made of tiles but other objects would be different and they could store them in a similar structure to avoid building another one. I suppose they could use a grid for tiles then a different structure (if needed) for other arbitrary objects. – Mike C Dec 30 '11 at 13:13
That's what I was about to suggest :) The grid should be used to handle collisions with the terrain, while a quadtree could be used to handle inter-object collisions. – David Gouveia Dec 30 '11 at 13:20
True. Right now every bounding box has 2^power dimensions. This makes it much easier I find for collision detection. A grid would fit my needs for now. – Ross Dec 30 '11 at 13:25