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

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].modelBoundingConstant);
for (int j = 0; j < bulletList.Length; j++)
{
if (bulletList[j].isActive)
{
BoundingSphere bulletSphere = new BoundingSphere(
bulletList[j].position,
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?

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:

• The game I'm working on is a bullet hell game, so it does worry me that I'll eventually get to that point. I'll take your advice and go with the simple solution for now, but thanks for the alternatives. Aug 4 '12 at 9:34
• @Fibericon Your concern is justified then. For a bullet hell game I think I'd probably go with a grid system, which is also very simple to implement. Basically divide the screen or world into an evenly spaced grid, and for each cell in the grid keep a list of the enemies which are currently intersecting the area of that cell. This way, if you have a bullet with position (x,y) you can easily calculate which cell it's currently in, and then only check for collision with the enemies intersecting that cell. Most of the time, the cells will be empty, so no check will even need to be done. Aug 4 '12 at 10:18

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.

• May I ask where you found that bit of info about the Plants vs Zombies implementation? :) Aug 4 '12 at 13:12
• If this is the Jeff Gates I'm thinking of, he was actually involved in the game's development. Aug 4 '12 at 14:21
• Tod's (the PvZ programmer) told me many times. In fact, I think the first time was after the 2006 GDC when I found out about the SAP algorithm, heh. Aug 4 '12 at 20:33
• As an aside, the major advantage you have with strict iteration is memory access coherency. To really get that advantage having things in flat arrays helps a lot. Aug 4 '12 at 20:34