Check an Array of Objects for Collision

[DaChief]

hey guys...

if you have an array of objects for example some balls in a Pool-Game. Then you may have a Problem to make collision detection between all these objects without loosing a lot of performance...
i will not describe here, how to do the collision-detection itself.. it is just a "system" to check an array of objects in a very "performance-friendly" way.

Maybe this is a guide for newbies... but i discovered this way myself and i was very proud of, so i wanted to share my experience with you

First. How do you think, you could do a collision detection between all those Objects in the array... sure.. for every Object do collision detection for all the others... this will look like this:

Code: Select all

const int OBJ_COUNT=30;
MyObject obj[OBJ_COUNT];

For(int i1=0;i1<OBJ_COUNT;i1++)
{
     For(int i2=0;i2<OBJ_COUNT;i2++)
     {
          collisionCheck(obj[i1],obj[i2]);
      };

};

But in this way, it could be that i1=i2 so the object tests collision with itself... doesn't make much sense.
so we add a litte modification to the code:

Code: Select all

const int OBJ_COUNT=30;
MyObject obj[OBJ_COUNT];

For(int i1=0;i1<OBJ_COUNT;i1++)
{
     For(int i2=0;i2<OBJ_COUNT;i2++)
     {
           if(i1!=i2)
           {
                collisionCheck(obj[i1],obj[i2]);
           };
      };

};

Well.. better this time...
The next step is to reduce useless checks...
for example in a pool-game, you don't have to check the balls, which aren't in the game anymore... so add a bool-var to the object-class and add this to the code:

Code: Select all

const int OBJ_COUNT=30;
MyObject obj[OBJ_COUNT];

For(int i1=0;i1<OBJ_COUNT;i1++)
{
     if(obj[i1].active)
     {
          For(int i2=0;i2<OBJ_COUNT;i2++)
          {
               if(obj[i2].active && i1!=i2)
               {
                     collisionCheck(obj[i1],obj[i2]);
                };
           };
      };
};

looks very nice... the last thing is something i discovered recently...
if you analyse the code now.. you see, that some of the checks are made twice... for example:
i1=0; i2=1 -> collisionCheck(obj[0],obj[1]);
i1=1; i2=0 -> collisionCheck(obj[1],obj[0]);
looks very similar, right ?
and yes, it is absolutely useless to check the collision twice. it could reduce performance by about 50%.

But how can i prevent these double-checks ?
very easy... just chance this in the code:

Code: Select all

const int OBJ_COUNT=30;
MyObject obj[OBJ_COUNT];

For(int i1=0;i1<OBJ_COUNT;i1++)
{
     if(obj[i1].active)
     {
          For(int i2=0;i2<OBJ_COUNT;i2++)
          {
               if(obj[i2].active && i1>i2)
               {
                     collisionCheck(obj[i1],obj[i2]);
                };
           };
      };
};

now to the example before:
i1=0; i2=1 -> collisionCheck(obj[0],obj[1]);
i1=1; i2=0 -> collisionCheck(obj[1],obj[0]); //<- SKIPPED because i1<i2 !

and if i1 and i2 are the same value, it will also be skipped.
now, i'm quite sure, you can't optimize it more.

before i quit this "lesson" a litte hint:
if you use 2-dimensional arrays for your objects (for example [type][instance]) you have to use 4 for-loops, if you do it like my example. but in the second, you should use "i1<=i2" instead of "i1<i2". because if you set it to "i1<i2" the objects of the same type can't collide with each other..

i hope that someone can use it... and i hope i didn't overlook a similar tutorial like mine...

cheers

[Warchief]

Well, i wouldn't do such thing (i would let every object to control its own collision), but anyway, the code above would work fine. Im just going to comment that you could skip the i1<=i2 check.

Code: Select all

const int OBJ_COUNT=30;
MyObject obj[OBJ_COUNT];

For(int i1=0;i1<OBJ_COUNT;i1++)
{
     if(obj[i1].active)
     {
          For(int i2=0;i2<OBJ_COUNT;i2++)
          {
               if(obj[i2].active && i1>i2) // Did you meant i1<=i2
               {
                     collisionCheck(obj[i1],obj[i2]);
                };
           };
      };
}; 

Code: Select all

For(int i1=0;i1<OBJ_COUNT;++i1)
{
     if(obj[i1].active)
     {
          For(int i2=i1+1;i2<OBJ_COUNT;++i2) // i2 = i1+1, so i2 will never be < i1
          {
               if(obj[i2].active) // no need to check i1<i2
               {
                     collisionCheck(obj[i1],obj[i2]);
                };
           };
      };
}; 

Just changed:

• for(int i2 = i1+1;...) // So i2 is never < i1 and can skip unseful checks
• i1++ and i2++ by ++i1 and ++i2 // Preincrement is faster (compiler dependant)
• Uhm, think you should have posted i1 <= i2 instead of i1>i2

Isntt it?

[DaChief]

Well, i wouldn't do such thing (i would let every object to control its own collision), but anyway, the code above would work fine.

hmm.. interesting... really interesting.. i never thought of that ^^
but how could you prevent the double-checks in that case ?
for example:
your object checks for collision with two other objects.. how could you prevent the two objects in doing the check in the other direction...
Object 1:
1->2
1->3
Object 2:
2->1
2->3
Object 3:
3->1
3->2
(so object 3 doesn't have to do any collision checks...)

maybe i didn't get your way to solve all these collision-problems.. whatever ^^ ("don't change a running system")


the "For(int i2=i1+1" thing is not bad... sounds much better...

but i'm not sure of that one -> ++i2
what is the difference between i2++ and ++i2 ?

thanks for your comment anyway ^^

[Warchief]

@about objects and its collision

Its up to you to decide, i just said that i would do something like:

Code: Select all

class MyColObject {
    Control(float elapsed);
}

Code: Select all

MyColObject::Control(float elapsed) 
{

   // Ask someone where would the object collide
   CollisionManager::GetClosestCollision( m_moveDirection, collision );
   if ( collision ) {
     // Do stuff, change direction, speed or whatever
   }
}

Where CollisionManager has to do a fast GetClosestCollision (triangle selector or any other way), returning the collision if there is one (with distance to collision point, object that would collide, etc).

So:

Code: Select all

MyGame::Control() {
    float elapsed = GetElapsed(); // Elapsed is the time passed in this frame

    for( everyObjectInMyFantasticGame ) {
     myObject[iterator].Control(elapsed);
   }
}

The control(float) to do every object stuff is commonly used for games.

@about preincrement vs postincrement

Well, you may better read something like:
http://discuss.fogcreek.com/joelonsoftw ... ost=171881

It is just a good habit to use ++i instead of i++.

Hope it helps.

[DaChief]

the CollisionObject thing sounds very cool... now i got it...
it makes much sense in some way... i'll do it in my next project in a similar way i think..
but my current project doesn't "need" it, because it is much simpler, if i make the collision detection myself(x,y coords - width,height etc.) and in a loop because there are only some balls and it is very simple to calculate the radius and distance. Also the Creation of the Loops isn't very hard...
in other words -> efficient collision-handling is not that important in my project. It's only a 2D-Game.. and not that complex...

i only thought of that loop-improving because i wanted to write a tutorial in here... i got so much information in this forum so i wanted to give some back

[Warchief]

Yep, i just wanted to complete the tutorial.

[Guest]

i only thought of that loop-improving because i wanted to write a tutorial in here... i got so much information in this forum so i wanted to give some back

In that case I want to add that inside tight loops it is often NOT an optimization to pepper it with lots ifs. Every time the branch prediction fails the instruction cache is screwed and that can easily be more expensive than doing a few semi complex operations. Ie. the "if" can cost more than a sphere-sphere distance check. Tests that will only filter out very few objects will mean lots of potentially wasted cycles in all other cases.

"Inactive" objects shouldn't be in that array in the first place. When order doesn't matter, swap with the last element and reduce array size by one, whenever a ball leaves the game (just where you end iterating over it, don't delete anything). If it wouldn't be completely pointless for a pool game with less than a dozen balls one could sort them along the longer axis and drastically reduce the amount of tests by only testing until the distance of the first test object is too big along this axis. But in this case you could probably check all the balls twice in the time it would take to sort the array (or keep it sorted).

So:
a) always start the inner loop with the object after the current object to avoid redundant checks
b) put inactive objects at the end of the array and stop the loop before you reach them

The only if in that whole code should be the part that says "if (squared_distance <= 4*r*r)" and there still won't be any redundant or useless collision checks.

[kaeles-notlogged]

the difference between ++i and i++ is that if i said
array[i++] it would check for i then increment
if i said
array[++i] it would increment, then look at i