Sign in to follow this  
Waaayoff

Yet another Collision Detection Question?

Recommended Posts

Apologies for asking so many questions, but this have been bugging me for some time. I've been reading about simple CD techniques like SAT, AABBs, Circles, per pixels etc.. But what i don't understand is how do you know which objects are collidable? Let me explain: Let's say your game contains thousands of collidable objects. Do you store ALL of their coordinates and dimensions? in a file maybe? And if you do, checking for a collision whenever something moves with every single object is insane.. How do you specify which objects to check for collision with? And lastly, what about shapes like Trees and mountains? they are very irregular.. you can use a box (many actually) around them and check for collision with the boxes, then take more complex measures.. What exactly are these complex measures? Thank you :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Waaayoff
Apologies for asking so many questions
Not at all, we're happy to help.

Quote:
if you do, checking for a collision whenever something moves with every single object is insane.. How do you specify which objects to check for collision with?
You would usually use some sort of data structure or organizational system to reduce the amount of checks to a more manageable number. You might also group objects together if appropriate.

Read up on Space partitioning, and check out some of the example partitioning systems listed in that article.

For very simple games you might also just use a grid-based scheme, where objects that aren't in the same cell of the grid obviously can't be colliding. Check out Grid base collision detection and raycasting for an example of this.

Quote:
And lastly, what about shapes like Trees and mountains? they are very irregular.. you can use a box (many actually) around them and check for collision with the boxes, then take more complex measures.. What exactly are these complex measures?
What more complex measures are would depend on your requirements, but would usually involve using a more accurate (but also more computationally expensive) method of collision detection. If you'd previously used a large bounding box to determine an object is near another you might then use a per-pixel test to see if it really is colliding, or you might test against a series of smaller bounding boxes that more closely match the actual shape.

Once you're done with that you'll also have to respond to the collision, but how you may wish to do so is really a whole additional topic.

Does that help? [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by Waaayoff
Let's say your game contains thousands of collidable objects. Do you store ALL of their coordinates and dimensions? in a file maybe?


Usually you only need the visible Objects. And i usually do not have thousands of those ... may some 'cluster' of really small objects, but then i simply put a box around the cluster.

Quote:

And if you do, checking for a collision whenever something moves with every single object is insane.. How do you specify which objects to check for collision with?


Start with a quick check if two objects even near each other. 'Not moving objects' do not collide with other 'not moving objects'.

Quote:

And lastly, what about shapes like Trees and mountains? they are very irregular.. you can use a box (many actually) around them and check for collision with the boxes, then take more complex measures.. What exactly are these complex measures?

Thank you :)


That should better be explained by someone else. Just remember that you only neet to check parts of objects that are able to collide. For trees it is usually the trunk and not the crown ... or even single leaves.

Share this post


Link to post
Share on other sites
First, no apologies for asking questions in a forum that is supposed to provide answers.

Second, you don't have to store your objects in a seperate list. You already have a list of your obkects in memory somewhere because you need that to render your objects anyway.

Third, doing each against each other collision detection if a single object move is not insane. It is just slow. So slow that you won't obviously do that. Instead use a scene management structure such as an octree or something like that. You divide your whole world into smaller volumes or areas. You can even do this recursively and subdivide those volumes or areas until a certain criteria is reached (size of the volume, number of objects inside the volume, ...).

Finally, store a simple bounding volume (a sphere or a box or ...) for each of your objects. Then sort those boxes into the scene structures eg. the octree. If an object moves update its position in the octree. Then just do the CD with only those objects that are inside the octree boxes intersected by the moving object. At first you only do a bounding volume against bounding volume CD which is very fast. If the volumes do not intersect there is no collision between those two objects. Only if the bounding volumes of two objects intersect you decide about the granularity of CD you need. You can have a recursive bounding volume hierarchy for each object and proceed to a more detailed CD of those bounding volume hierarchies. At the lowest (and slowest) level you can do real triangle versus triangle collision but this gets too slow pretty fast.

Last not least, special objects such as terrain require special treatment. The terrain cannot move. So you only have to make sure that your moving objects do a CD against the terrain as well. Basically, the terrain would own the octree (or quadtree) you use as scene management structure mentioned above. So each node of the octree should also know which part of the terrain lies inside the node. Simply do a CD of your moving objects with the triangles belonging to the same octree node as the moving object.

Note that I only have used the octree as sample here. You can plugin any scene management structure you like such as cells and portals, quadtrees, loose octrees, ...

Share this post


Link to post
Share on other sites
An unrelated advice to everyone:
Please don't add "Yet another" to the title.
We all know that there are many threads like that.
And why do you feel you have to apologize in advance? If you feel you are guilty, then don't post. If not, then post.

Everyone will gladly help you, even if you don't apologize in advance.
It's more annoying for me, than a simple straight question.

Sorry for the OFF.

Share this post


Link to post
Share on other sites
Quote:
Original post by Waaayoff
Apologies for asking so many questions, but this have been bugging me for some time. I've been reading about simple CD techniques like SAT, AABBs, Circles, per pixels etc.. But what i don't understand is how do you know which objects are collidable? Let me explain:

what you describe is all narrow phase collision detection. What you are asking about is broad phase.

A simple way to do broad phase using narrow phase like with SAT is make the axis pointing from center point to center point of the objects an axis and check that before any other axes.

other ways include grids, a multitude of different types of trees (quad, sphere/circle, BSP), ray casting, etc.

Google broad phase collision detection. Now that you k now what you're looking for you should be able to find a lot on it.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this