Checking collision in an array - is there a better way?

Question

MSDN suggested this, but I'm worried about it slowing down the game when there are a lot of objects to check:

for (int i = 0; i < enemy.Length; i++)
{
   if (enemy[i].isActive)
   {
      BoundingSphere enemySphere =
         new BoundingSphere(enemy[i].position,
         enemy[i].Model.Meshes[0].BoundingSphere.Radius *
         enemy[i].modelBoundingConstant);
      for (int j = 0; j < bulletList.Length; j++)
      {
          if (bulletList[j].isActive)
          {
             BoundingSphere bulletSphere = new BoundingSphere(
                bulletList[j].position,
                bulletModel.Meshes[0].BoundingSphere.Radius);
             if (enemySphere.Intersects(bulletSphere))
             {
                enemy[i].health -= 10;
                bulletList[j].isActive = false;

                break; //no need to check other bullets
             }
          }
       }
   }
}

Nested looping like this just doesn't seem like the most efficient way to check if a bullet connects with an enemy. Is there a better way?

Answer 1

My first suggestion is that you begin with the approach that you have posted, because it might be fast enough, and it's trivial to implement. Then if you identify a problem, move over to a more complex solution

The simple approach suggested by MSDN is is basically just linearly iterating over every bullet and enemy, and checking every possible combination once:

foreach(var enemy in enemies)
    foreach(var bullet in bullets)
        CheckCollision(enemy, bullet);

If it turns out that you have too many bullets and enemies that it will slowdown, there are certainly many ways to do it more efficiently. These techniques usually require you to implement a space partitioning data structure, such as a quadtree, octree, or even a simple grid.

I've talked about space partitioning data structures in a few answers before, so I'll link the two most relevant ones:

• How to find all entities within a radius efficiently?
• Space partitioning bibliography

Answer 2

Plants vs Zombies just uses the N^2 algorithm, and they get quite a lot on the screen (on cell phones too...), so you are probably fine with just iterating. The absolute fastest would be using sweep and prune. The bullet physics library has a good implementation for reference. This is a good algorithm to just have in your toolbox if you make a lot of games.