Lag created when detecting collision

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

A simple answer could be a simplified axis sweep broadphase.

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);
    }
}