# My grid based collision detection is slow

Something about my implementation of a basic 2x4 grid for collision detection is slow - so slow in fact, that it's actually faster to simply check every bullet from every enemy to see if the BoundingSphere intersects with that of my ship. It becomes noticeably slow when I have approximately 1000 bullets on the screen (36 enemies shooting 3 bullets every .5 seconds). By commenting it out bit by bit, I've determined that the code used to add them to the grid is what's slowest.

Here's how I add them to the grid:

for (int i = 0; i < enemy[x].gun.NumBullets; i++)
{
if (enemy[x].gun.bulletList[i].isActive)
{
enemy[x].gun.bulletList[i].Update(timeDelta);

int bulletPosition = 0;
if (enemy[x].gun.bulletList[i].position.Y < 0)
{
bulletPosition = (int)Math.Floor((enemy[x].gun.bulletList[i].position.X + 900) / 450);
}
else
{
bulletPosition = (int)Math.Floor((enemy[x].gun.bulletList[i].position.X + 900) / 450) + 4;
}

GridItem bulletItem = new GridItem();
bulletItem.index = i;
bulletItem.type = 5;
bulletItem.parentIndex = x;

if (bulletPosition > -1 && bulletPosition < 8)
{
if (!grid[bulletPosition].Contains(bulletItem))
{
for (int j = 0; j < grid.Length; j++)
{
grid[j].Remove(bulletItem);
}
}
}

}
}


And here's how I check if it collides with the ship:

if (ship.isActive && !ship.invincible)
{
BoundingSphere shipSphere = new BoundingSphere(
for (int i = 0; i < grid.Length; i++)
{
if (grid[i].Contains(shipItem))
{
for (int j = 0; j < grid[i].Count; j++)
{
//Other collision types omitted
else if (grid[i][j].type == 5)
{
if (enemy[grid[i][j].parentIndex].gun.bulletList[grid[i][j].index].isActive)
{
BoundingSphere bulletSphere = new BoundingSphere(enemy[grid[i][j].parentIndex].gun.bulletList[grid[i][j].index].position,
if (shipSphere.Intersects(bulletSphere))
{
ship.health -= enemy[grid[i][j].parentIndex].gun.damage;
enemy[grid[i][j].parentIndex].gun.bulletList[grid[i][j].index].isActive = false;
grid[i].RemoveAt(j);

break; //no need to check other bullets

}
}
else
{
grid[i].RemoveAt(j);
}
}


What am I doing wrong here? I thought a grid implementation would be faster than checking each one.

• – Laurent Couvidou Sep 14 '12 at 12:36
• I'm not entirely sure how to read the results of that. – Fibericon Sep 14 '12 at 14:30

Here you have created a new instance of bulletItem... OK, but see later...

  GridItem bulletItem = new GridItem();


Check if grid doesn't contains bulletItem... NOT OK, Why? The line above, you have made an new instance of bulletItem, it is 100% guaranteed not to be in any grid and so no need to check if it in any grid. The for next loop will never succeed in Remove() either, so...

     if (!grid[bulletPosition].Contains(bulletItem))
{
for (int j = 0; j < grid.Length; j++)
{
grid[j].Remove(bulletItem);
}
}
}


May as well just be...

 grid[bulletPosition].Add(bulletItem);


 else if (grid[i][j].type == 5)
{
if (enemy[grid[i][j].parentIndex].gun.bulletList[grid[i][j].index].isActive)
...e.t.c...


do

 GridItem bulletItem = grid[i][j];
else if (bulletItem.type == 5)
{
if (enemy[bulletItem.parentIndex].gun.bulletList[bulletItem.index].isActive)
...e.t.c...


Not only is it more readable, depending on how smart the compiler is, it may end up recalculating the pointer to grid[i][j] each time you reference it.

Instead of creating a new instance of BoundingSphere within the loop which requires allocating memory each time

 BoundingSphere bulletSphere = new BoundingSphere(.....)


Can you not create 1 instance at the very top and let all bullets share the same instance? You should be able to call a method to set bound for each bullet you wish to check. Doing it as you are currently doing means each time you create an instance will call the memory manager to allocate memory which takes a bit of processing time, there is no need to create what could be like 100+ instances and fragmenting the memory quickly. Also, not sure how memory management works, it is automatically garbage collected? If not, make sure you are deleting them when you finish with them.

Is

  for (int j = 0; j < grid[i].Count; j++)
{


Counting the actual number each time or it is a constant? For example, the following may be quicker.

  int c = grid[i].Count;
for (int j = 0; j < c; j++)
{


for (int i = 0.....
if (grid[i].Contains(shipItem))
{


Do something like

int i = shipItem.gridIndex;


which is basically a cross reference to which grid the shipItem is currently in, it saves having to loop what could essentially be up to 1,000 times just to find it.

• On the first point, I believe it actually will be in the grid, because the only values in the bullet item are the index, the enemy index, and the type. However, your second point seems to have helped significantly. – Fibericon Sep 14 '12 at 14:30
• I believe it won't. Because GridItem bulletItem = new GridItem(); is essentially a pointer to a data structure / class. This is unique each time you declare the variable which is what you are doing here. Add some debug code by putting in else { print "Already Inserted"; } and see if it ever appears. I'm betting it won't but then again I don't have access to full code to see what Contains() is actually doing. – John Sep 14 '12 at 14:44
• Well what is has custom Equals method – Kikaimaru Sep 14 '12 at 15:49

My guess is that the slowness comes from this "adding objects to a grid" thing. This is not the "grid implementation" as everyone knows it because such grid implementations usually include only one native (or smaller, like a few bits) value per grid cell. How you use it is totally up to you. However, there must be no nested arrays or anything as horrible as that.

So in this case, I don't see a good reason why a grid should be used.