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

Question

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?

Answer 1

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.