My grid based collision detection is slow
- by Fibericon
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);
}
grid[bulletPosition].Add(bulletItem);
}
}
}
}
And here's how I check if it collides with the ship:
if (ship.isActive && !ship.invincible)
{
BoundingSphere shipSphere = new BoundingSphere(
ship.Position, ship.Model.Meshes[0].BoundingSphere.Radius * 9.0f);
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,
enemy[grid[i][j].parentIndex].gun.bulletModel.Meshes[0].BoundingSphere.Radius);
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.
