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 :)

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]

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, ...

Thanks to you all :) You've been very helpful!!

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.