1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ how many items are you iterating through ? \$\endgroup\$ – concept3d Dec 1 '13 at 12:55
  • \$\begingroup\$ 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?" \$\endgroup\$ – MickLH Dec 1 '13 at 13:01
  • \$\begingroup\$ 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. \$\endgroup\$ – Hamza Dec 1 '13 at 13:12
  • \$\begingroup\$ 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. \$\endgroup\$ – Kelly Thomas Dec 1 '13 at 13:38
1
\$\begingroup\$

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.

enter image description here

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.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Maybe he can get rid of the temporaries also. Probably don't need to throw 3000 new Vector2() at the GC for no reason. \$\endgroup\$ – MickLH Dec 1 '13 at 13:28
  • \$\begingroup\$ 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? \$\endgroup\$ – Hamza Dec 1 '13 at 13:52
  • \$\begingroup\$ @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 \$\endgroup\$ – concept3d Dec 1 '13 at 13:54
  • \$\begingroup\$ 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. \$\endgroup\$ – Hamza Dec 1 '13 at 13:59
  • \$\begingroup\$ @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 \$\endgroup\$ – Anastasios G Dec 2 '13 at 9:31
0
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Hamza Dec 1 '13 at 13:15
  • \$\begingroup\$ This is a feasible option, but an axis sweep seems a better choice for simple point distance. \$\endgroup\$ – MickLH Dec 1 '13 at 13:19
0
\$\begingroup\$

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);
    }
}
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.