# Lag created when detecting collision

I'm fairly new to gamedev and have encountered a problem with the collision detection system.

The collision is essentially worked out like this:

for (int x = 0; x < playerprojectiles.Count; x++)
{

for (int i = 0; i < enemyships.Count; i++)
{
Vector2 projectilepos = new Vector2(playerprojectiles[x].position.X, playerprojectiles[x].position.Y);
Vector2 enemypos = new Vector2(enemyships[i].position.X, enemyships[i].position.Y);

Console.WriteLine("I=" + i + "  ,  " + "x=" + x);
if (Vector2.Distance(enemypos, projectilepos) < 20)
{
playerprojectiles.RemoveAt(x);
x--;
break;
}

}

}


I can see the problem; it is having to iterate through too many items. However, I can't think of a way to overcome this.

Any help? To specify, can someone direct me to a method that would allow me to detect collision without impeding performance so severely.

• how many items are you iterating through ? Commented Dec 1, 2013 at 12:55
• Please ask your question specifically, "Any help?" is clearly not what you want. Do you mean: "How do I implement a broadphase optimization for collision detection?" Commented Dec 1, 2013 at 13:01
• There are lots of objects. The enemyships may hold up to 100 objects, while the playerprojectiles is limited to around 30 due to the "alivetime" of the projectiles. Commented Dec 1, 2013 at 13:12
• Removing the Console.WriteLine() is the easiest optimisation to make. It is quite expensive and could be called up to 3000 times with those numbers. Commented Dec 1, 2013 at 13:38

The usual solution in order to avoid checking for every pair, would be to implement some kind of spatial partitioning like quad tree or bsp tree.

but this might be too complex for your simple game. There are other trivial optimzations you can do in your loop:

• Calculate DistanceSqaured instead of Distance, because distance needs to calculate square root so distance squared could be much faster, but you need to check with squared distance so instead of 20 you need to compare with 400.

if (Vector2.DistanceSquared(enemypos, projectilepos) < 400)

• You can divide the game into regions (like a grid) and check the projectile with enemy ships in the same region only. This is simpler than a quad tree.

• As an alternative you can sort your enemy objects position by Axis, for example sort by X then by Y. And do collision detection based on near objects, for example projectile coming from -X is more likely to hit objects with less X coordinates.

• Also you can get rid of temporaries by not copying your variables every time to other variables. As suggested by MickLH.

• Maybe he can get rid of the temporaries also. Probably don't need to throw 3000 new Vector2() at the GC for no reason. Commented Dec 1, 2013 at 13:28
• With regard to what you said about incorrect loop implementation. X is only removed if the collision occurs. So if I set x to .count, how would it iterate through the remaining objects in the list if x is not removed? Commented Dec 1, 2013 at 13:52
• @Hamza I also said in the answer "Your solution to decrement x will make you check for objects that are already checked multiple times." So you are actually adding more redundant iterations Commented Dec 1, 2013 at 13:54
• I think I may have misunderstood what you were saying. Did you mean that I should set X to .count and the go down the list as opposed to starting from 0 and going up to .count? Sorry, as you can see i'm pretty new to this. Commented Dec 1, 2013 at 13:59
• @concept3d I don't think that he is doing something wrong. In the example you provide x=6; count=7. When you decrement x by one, you get x=5; count=6. Then it goes to the end of the loop and it is incremented by one, because of x++ and then is checked x < playerprojectiles.Count which is false because x=6 and playerprojectiles.Count = 6 Commented Dec 2, 2013 at 9:31

If you have too much objects, divide the regions. In 3D this is called Octree. You can divide your region in 4 regions and calculate the region of the items. Then you only have to check the items in the same region as the projectile. And when it's not enough, divide this region again. The problem is that you have to calculate, in what region the item is. So maybe you need longer to calculate the regions -> you have to figure out what division is the best.

Another thing is maybe the usage of Lists. I've read somewhere that an array is much more faster than a list. Try to use arrays. But i don't know if it's faster in this case, because you have to check the whole array every call...

Maybe this also helps: Quad trees/grid based collision - putting logic into action

• Wouldn't assigning the objects to regions require the same amount of computation? After all, the only calculation my collision detection does is check distance. What's more, all of my objects are mobile. So the objects would have to be repeatedly assigned to regions. Commented Dec 1, 2013 at 13:15
• This is a feasible option, but an axis sweep seems a better choice for simple point distance. Commented Dec 1, 2013 at 13:19

This involves sorting your list of "enemyships" (the larger list that changes less) by some coordinate, and then taking an early out when you know it's impossible to collide.

The cost of the sort should be almost free since it only has to do work when new enemy ships are added.

It might look like this (UNTESTED):

int firstErase = -1, lastErase = -2;

// Sort all your ships from left to right (not sure if this is the right order)
enemyships.Sort(delegate(EnemyShip a, EnemyShip b) {
return a.position.X - b.position.X;
});

for (int x = 0; x < playerprojectiles.Count; x++) {
//left as an exercise for the reader:
//start from the middle and only check the logical half

for (int i = 0; i < enemyships.Count; i++) {
// this is a slowdown: Console.WriteLine("I=" + i + "  ,  " + "x=" + x);

// early out for everything too far right to be possible
float DistanceX = enemyships[i].position.X - playerprojectiles[x].position.X;
if (DistanceX > 20) break;

// just do DistanceSquared() manually since we did part already
float DistanceY = enemyships[i].position.Y - playerprojectiles[x].position.Y;

if (DistanceX*DistanceX + DistanceY*DistanceY < 20*20) {
// dont edit the list you are looping through
playerprojectiles[x].eraseMe = true;

//Maybe this should go here too:
//enemyships[i].DoDamage(playerprojectiles[x].damage);
break;
}
}
}

int c = playerprojectiles.Count;
while (c--) {
if (playerprojectiles[c].eraseMe) {
playerprojectiles.RemoveAt(c);
}
}