• 12
• 14
• 13
• 10
• 11

# how we do a collision?

This topic is 746 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

all objects have rectangles dimensions. but doing a loop for all objects for test the collision it can be to much for CPU.

for(int i=0; i<objects.count(); i++)
{
if(isCollision(player, objects[i])==true)
blncollision=true;

}


so what it's the best for collision control?

##### Share on other sites

Not sure what you're asking.  Can you be more specific?

##### Share on other sites

Not sure what you're asking.  Can you be more specific?

i will try.

when we move the player we must test the collision to another object. imagine that we have more than 100 objects. everytime that i move and test the collision, more cpu is used.

so what is the best for test the collision?

##### Share on other sites

What is the code inside isCollision()?

If youre doing a simple axis aligned bounding box (AABB) the cpu usage of even 100,000 collisions should be negligable on modern hardware.

Have you run a profiler to determine that this is your bottleneck or is this premature optimisation?

##### Share on other sites

What is the code inside isCollision()?

If youre doing a simple axis aligned bounding box (AABB) the cpu usage of even 100,000 collisions should be negligable on modern hardware.

Have you run a profiler to determine that this is your bottleneck or is this premature optimisation?

is more an optimisation.

the isCollision() just use the position and dimentions of the object for test the collision

##### Share on other sites

Not sure what you're asking.  Can you be more specific?

i will try.

when we move the player we must test the collision to another object. imagine that we have more than 100 objects. everytime that i move and test the collision, more cpu is used.

so what is the best for test the collision?

Hmm, yes I understood all that.  I meant that I wasnt sure if you're asking about what code should be in isCollision(), are you're asking about the best way to optimize it (except you didnt give your code so I cant tell you how to optimize it), or asking if there's a different way to do it, etc.

In any case, I'll give some thoughts and you can say if it helps or not.

Since you only appear to be testing player vs object collisions and not all objects vs all other objects, the performance shouldnt be too bad, since it grows as N instead of N^2.

A good and simple approach to optimize this would be to initially calculate an AABB (axis-aligned bounding box) for each object that bounds the object in any rotation (just calculate the bounding sphere and then the AABB around that).  For the player you can dynamically calculate a more accurate AABB each frame before you go into your loop.  Then in your isCollision() function you start by testing the player AABB versus the object AABB (a very fast test) and if that succeeds you can go on to a more accurate collision test.

Next, you can store your objects (or better, just your object AABBs) in a contiguous array.  This will make the loop even faster (read more about the caches and prefetcher if you're not sure why).

Lastly, doing your collision in a loop like you're doing will probably give you adequate results (if your time steps are small enough), but you might have cases were collisions are not accurate.  This is because you have an implicit order dependence in how the player and objects collide.  If you want to be more accurate, you'll need to double-buffer your object physics data so you can calculate all the objects that collide with your player and then determine the resultant collision response from that summed collision.  But this might just not be an issue for you, in which case just ignore it.

But if you're just testing a collision between a player and 100 objects, that should be pretty fast no matter how it works.  You really need to start thinking about more optimizations if you get into colliding with thousands or tens of thousands of objects (or more).  If that was the case, you can also look into multi-threading your collision code.

##### Share on other sites

all objects have rectangles dimensions. but doing a loop for all objects for test the collision it can be to much for CPU.

for(int i=0; i<objects.count(); i++)
{
if(isCollision(player, objects[i])==true)
blncollision=true;

}


so what it's the best for collision control?

Wat? Er... If I understand this correctly, you're asking how do you limit the number of computations?

Well, it's all in the data structure really. So... lets put it into perspective.

Logically speaking under any given circumstance two objects that are thirty meter away from each other will not collide with each other within the frame. Those two shouldn't even try to test against each other, less than even notice each other.

Two objects that are within a meter of each other is when they need to start paying attention to each other. Kinda like driving really. You don't care about about the idiot five miles down the street, but you do care about the tail gating douchebag in the hummer behind you, and his engine is practically breathing on your bumper.

So, most implementations will actually use some form of scene graph, or octree. Where only the objects in the same cell will actually pay attention to each other.

There is also a graphical dependency to adhere too. If you start at some arbitrary node (an object to check for collisions) logically you should not have to check that one again. So the collisions between those two objects are now done, you look at the next object. It should be noted that time can also be saved by ignoring objects that are currently not moving. But they still need to be checked against. The benefit of this? If a portion of the graph has absolutely no energy (moving objects) it can just be straight up ignored completely.

Lastly, there is also a "broadphase", It's typically a very simple collision detection between two bounding boxes or spheres. If they intersect, than you can run the more complicated algorithms.

Edited by Tangletail

##### Share on other sites

see these untested function(i don't have sure if these function works fine, but is only for show you what i mean):

bool isCollion(RECT rect1, RECT rect2)
{
RECT rectDest;
if(IntersectRect(rectDest,rect1,rect2)==TRUE)
return true;
else
return false;
}



doing these for all objects. ok, in these case, i'm just testing the player movement. but i can have a a moving objects too, like a plataform games, so i must do another loop for it... maybe more small.

the multithread can save the CPU, true. but using that, i can lose the speed game on collision detection?

##### Share on other sites

Yes, you can still loose some precious time in a 16ms limit. Like I said. Use a scene graph (an overlapping octree will do just fine) to limit the objects you are checking. Objects in  Math is actually very fast on the processor. The problem comes when you make a bunch of needlessly redundant checks. This is where the overhead comes from.

An overlapping Octree or a "loose leaf" I think it's called is a tightly fitted octree when you are organizing bodies. But when it comes time to do collision detection, each octree becomes just a little bigger for testing. This is to compensate for objects that are near the boundries of a leaf's volume.

In a scene of 1004 objects, you can skip a child that holds 10 objects if none of them are moving. If there's movement in a child that holds N moving objects, then you will only need to do (roughly thinking...) Sum( n=1 to N: n) - 1 + N * Number of Non moving objects checks.

So... that leaf has 4 moving objects and no stationary objects? 9 checks. 2 moving objects and 2 stationary? That's 6 checks.

that's significantly different then a scene holding 1004 objects, which will equate to a total of... 504510 checks.

That is a normal scene in a game by the way.

What constitutes to an object being in motion? Any time it has a vector, or an impulse large enough to get it moving has been applied. The moment an object has a velocity, the octree will mark it's self in needing a physics check, it will also keep a list of moving objects.

Edited by Tangletail