Why does my collision detection code cause my framerate to drop?

I have this code:

foreach (CollisionTiles tile in map.CollisionTiles)
{
player.CollisionBox(tile);
foreach (Enemy enemy in enemys)
enemy.CollisionBox(tile);
}

This is the CollisionBox() function:

public void CollisionBox(CollisionTiles tile)
{
int x = rectangle.X / Map.Size;
int y = rectangle.Y / Map.Size;
int tileX = (int)tile.Position.X;
int tileY = (int)tile.Position.Y;

if (tileX >= x - 1 && tileX <= x + 2 && tileY >= y - 1 && tileY <= y + 3)
{
Collision(tile.Rectangle, Map.Width, Map.Height);
tile.Collide = true;
}
}

These two lines appear to be the problem:

int x = rectangle.X / Map.Size;
int y = rectangle.Y / Map.Size;

I guess because it loops through them on every tile...

The Collision() function just check the face's of the two triangles (both player/enemy and the tiles) with these functions:

public static bool TouchTopOf(this Rectangle r1, Rectangle r2)
{
return (r1.Bottom >= r2.Top && r1.Bottom <= r2.Top + (r2.Height / 2));
}

public static bool TouchBottomOf(this Rectangle r1, Rectangle r2)
{
return (r1.Top >= r2.Bottom - (r2.Height / 2));
}

public static bool TouchLeftOf(this Rectangle r1, Rectangle r2)
{
return (r1.Top <= r2.Bottom - (r2.Height / 2) &&
r1.Bottom >= r2.Top + (r2.Height / 2) &&
r1.Right >= r2.Left &&
r1.Right <= r2.Left + (r2.Width / 4));
}

public static bool TouchRightOf(this Rectangle r1, Rectangle r2)
{
return (r1.Top <= r2.Bottom - (r2.Height / 2) &&
r1.Bottom >= r2.Top + (r2.Height / 2) &&
r1.Left >= r2.Right - (r2.Width / 4) &&
r1.Left <= r2.Right);
}

When there is more then one monster with the player I get a massive FPSdrop, and it's getting worse when more monsters get added. What should I do to fix that problem?

• Use a profiler, identify bottlenecks, correct bottlenecks.
– user1430
Mar 24 '14 at 15:16
• How can i use a profiler? I don't actually know what it is can you direct me to a guide? Mar 24 '14 at 15:19
• Try searching for "C# profiler" to find one and some guides for using them.
– user1430
Mar 24 '14 at 15:47

You are checking each object against each collision tile, even when those are too far away to have a chance to affect it. That's inefficient, because the computational cost increases quadratical with the amount of objects. Divide your map into zones and keep track of which zones each mobile object touches. Then only check for collisions inside each zone.

Keeping track of which zones each object touches can be done whenever that object is moved. Compare its old coordinates with the new ones to find out from which zones the object needs to be removed and to which zones the object is added. Each map zone would have a HashSet<MobileObject> representing its current inhabitants. Note that when an object is on the border of two zones, it can be in multiple zones at the same time.

When you check for collisions, you only check for collision of objects and tiles which are in the same zone (you might have to check adjacent zones too, when objects are large enought to span multiple zones).

I also assume (but might assume wrong), that you have a lot more collision tiles than mobile objects. When that assumption is right, most zones will always contain collision tiles, but will often not contain any mobile objects. In that case it would be better to iterate all objects and check them against the tiles in their zone instead of the other way like you are doing right now (iterate tiles and check them against mobile objects).

Regarding how to define zones: The most straight-forward way would be to use square-shaped zones of uniform size. This has the advantage that finding out the zone a point is in is trivial: Put the zones in a two-dimensional array. To get the array-indexes of the zone a point is in, just divide the x- and y-coordinate of the point by the zone-size and you have them.

The ideal zone-size depends on your object-density and object-mobility. You will need to find a compromise between keeping the zones small enough so their population is small and large enough to avoid too frequent zone-changes.

When you have areas which are always much more densely-populated than others, it might make sense to divide these areas into smaller zones.

• How can i divide the map into zones when all my tiles are in List? And check which zone the monster in Mar 24 '14 at 15:41
• @NaorHadar Don't put your tiles into a list. Put them into a two-dimensional array or similar data-structure. When you really want to stay true to your lists, have an individual list of tiles for each zone. I edited my answer to explain how to find the zone an object is in. Mar 24 '14 at 15:59