Sign in to follow this  

Implimenting Collision Detection

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, What I am really wondering is how I should call the collision detection. I have a Node which contains the translation of the object and a bounding box. However I am not sure when I should call the collision detection 1. After the object moves (eg. In the update if it requires one) to check if there is a collision. If so send out a message 2. Check every object every frame (I think that this might be slower). However I am not sure what is best or faster or even if there is a better way. I know how to check if an object has collided, but I am not sure when to check.

Share this post


Link to post
Share on other sites
I wish people would care to search around a bit. There is a forum on Maths on Physics . It exists for a purpose...

Share this post


Link to post
Share on other sites
Quote:
Original post by horizon981
I wish people would care to search around a bit. There is a forum on Maths on Physics . It exists for a purpose...


This is not the how but the when, which does not involve math and physics.

Thanks MOD I meant to put it in Game Programming, but I was for some reason in OpenGL!

Share this post


Link to post
Share on other sites
Instead of writing such a complex system, you could consider using an existing one:
http://www.ode.org/
http://photoneffect.com/coldet/

Share this post


Link to post
Share on other sites
Well, I want the experience, I could just use an existing one but my whole project is just to learn for now.

Share this post


Link to post
Share on other sites
For every object, I associate a 'Bubble' (a sphere consisting of a centerpoint and radius) which is not necesarially centered on the object, but contains it.

For each object I check it against all other objects in the sector for collisions; simultaneously I resize its Bubble so that it is half the distance to the nearest other object.
Now on a subsequent movement, if the object in question is still within the boundaries of its own Bubble, it cannnot possibly be the initiating participant in a collision, and I can skip it's collision pass.
If it leaves the bounds, then it May be colliding and checking against all the other N-1 objects must occur. Collisions are checked and the object's Bubble has a new center and radius assigned.

This Bubble system basically means that the timing of collision check occurs as a function of both the object's speed, and proximity to other objects.
(an object far away for others has a large Bubble that it takes a long time to exit from, while a slow moving object won't exit very quickly either)

Share this post


Link to post
Share on other sites
Well there are many ways you can do it depending upon how accurate you want the collision to be. If every object is moving then you might as well just check all objects every frame. Depending on how fast and small your objects are you may need to test cylinders (think a bounding sphere over time). The way you can optimize this is by sticking every object into a oct tree or some kind of spatial tree, this way you only test objects that might interesect and you don't have to test them all.

Share this post


Link to post
Share on other sites
Ok well then that could be computationally difficult since i'd have 128 sprites(players, of course these objects would be complex but you dont have to check inside of the main AABB unless they colide) but i'd also have around 1280 projectiles at a time (say an average of 10 per player sometime more and less. These are all visible and may live for seconds at a time). So id have to check for a collision between 128 ships and 1280 shells so that would be (128 * 1280) * (128 *1280) or arround 2 million calculations a frame, right?

However what if I only need to check for a collision between the sprites and the land, and the shells and the ships instead of checking each object with all of the others. However I am not sure exactly how I could tell the difference between a sprite and a projectile, quickly. Would I want to have a list of pointers to all of the projectiles and ships to keep them seperate so it would be more like:
for each projectile, check a collision against each sprite and
for each sprite check collision again land
NOTE: sprites do not collide

However I can see a major problem with this solution. An projectile could be deleted from the node but it would still be in the list of projectiles. Would this be the best way to do what I want, if so i'd have to find a way to work out this bug! Is there even a better way?

Share this post


Link to post
Share on other sites
Ok, I have one more question, were would I put a function to check if a collision has occured. Would I put it inside of the Node class and have a param that requires a pointer to the node to check against? It would then signal an event if a collision was detected. This is the only way that I can think of doing this.

Another class then would commence all of the calling to check for a collision.

Share this post


Link to post
Share on other sites
I think its better to handle response immediatly after a collision detection, else you might get some strange results when multiple objects collide.

I do it something like this...

func checkCollisions
{

loop1
{
loop2
{
response = checkCollision(objFromLoop1, objFromLoop2)
if (response.collision)
{
response.execute()
}
}
}

}

Share this post


Link to post
Share on other sites
Quote:
Original post by starfleetrp
Ok well then that could be computationally difficult since i'd have 128 sprites(players, of course these objects would be complex but you dont have to check inside of the main AABB unless they colide) but i'd also have around 1280 projectiles at a time (say an average of 10 per player sometime more and less. These are all visible and may live for seconds at a time). So id have to check for a collision between 128 ships and 1280 shells so that would be (128 * 1280) * (128 *1280) or arround 2 million calculations a frame, right?

However what if I only need to check for a collision between the sprites and the land, and the shells and the ships instead of checking each object with all of the others. However I am not sure exactly how I could tell the difference between a sprite and a projectile, quickly. Would I want to have a list of pointers to all of the projectiles and ships to keep them seperate so it would be more like:
for each projectile, check a collision against each sprite and
for each sprite check collision again land
NOTE: sprites do not collide

However I can see a major problem with this solution. An projectile could be deleted from the node but it would still be in the list of projectiles. Would this be the best way to do what I want, if so i'd have to find a way to work out this bug! Is there even a better way?

This is how we did it in Rumble Box:

The world is split into a grid (for simplicity sake, we'll say its 2D and it's a 2x2 grid). Each grid square has an index/iterator/pointer to an object. When an object enters a grid square, it tells the square "add me to your list", and it tells its previous grid square "remove me from your list". When an object is deleted, it tells the list "remove me from your list".

So that creates a bunch of sectors, each sector has a list of objects in it, and each object knows what sector it is in. Choosing collision possibilities are now as simple as searching nearby sectors. And you don't have the problem of "I deleted it, but it still thinks it exists" because the object just tells its own sector that it no longer exists.

I prefer to implement a system like this using a set of pre-allocated vectors for the grid, and each object has a bool to say whether it is actually valid or not. Then when we add a new object we just search for the next open slot and fill it, and when we delete it we set that bool to false. But that's just me. :)

Share this post


Link to post
Share on other sites
Now that I think about it, there is another thing we did in Rumble Box that may be of use to you:

An object only has to check for a collision if it is moving. No reason to check if it's not going anywhere. So we have a "stationary" flag that says "you're not moving", and then you don't have to do any calcs on it. When it is touched by any moving object, we set that stationary flag to false, so then it can react to the force.

This turned out to be a very efficient solution.

Share this post


Link to post
Share on other sites
Why use a flag to indicate if its moving, because from what I have read from ronkfist, why not just check for a collision when the object is being moved. Eg translate(vector3). When this is called I can check the collision then and check it with objects in a close sector for a collision then respond appropriatly (spelling?)?

EDIT: After I re-read you post, I guess I should have that flag, even though my game does not react in bouncing off objects. They either collide against world, stop and take damage, or explode against another sprite!

I have one more question about the sectors, lets say eac sector is 2x2xinfinite height(3D). But your object/sprite has a size of 10x10x50 or whatever. What would you do then? Would the object then exist is 5 or more sectors (dont feel like doing the math for the exact amount).

If the sprite only exists in one sector, then how would you decide which one and decide which sectors could be classified as near by, since for all I know the object that its colliding with could be 30 sectors away (depending on size) then what would be the point of a sector. So I am lead to beleive that the above would have to apply.

On another note, how would I check if the object that is moving has passed through another AABB or sector. I must admit that this probably would not happen in my game, but how would you go about checking for this/

Thanks you for all of your replies so far. They have been very helpful!

Share this post


Link to post
Share on other sites
I also use somekind of flag to indicate wether the object can move or not to chose a different collision response.

- 2 movable objects collide: impulse based response
- a movable and non-movable object collide: projection based response

Share this post


Link to post
Share on other sites
Sign in to follow this