   About collision detection
  Hi all,I have a question about collision detection. If you have about 1000 collision objects on a map, but only 200 show on the screen, do you really have to loop through all 1000 collision objects to check collision?I am using SDL at this moment, and I am asking this question from a 2D game aspect. I don't know if checking every single collision objects I have in this game is efficient at all. If not, what other options do I have?Thanks in advance.Eagle.   
  You only need to check collisions between objects whose direction and velocity are important to the gameplay. If nothing's happening offscreen, you certainly don't need to check those collisions.As that's sort of obvious, I suspect I'm not understanding your question. Is that what you're asking about?   ;  You must be able to determine somehow whether there are any collisions between any objects.The only thing you can do is to try and make it as cheap as possible to check the "false" positives. Usually this means that the " DoesItCollide()" or such method should fail as soon as possible, if there is no way for collision to occur.In short, if your objects move, they must be regularily iterated through to see if they collide. Moving objects vs static objects makes the problem hugely lighter to handle in computational terms. That is, if we use spatial partitioning or similar scheme.Ummm. and yeah. If the objects are "inactive" and away from screen, surely their collision can be overlooked. But as we are talking about "map", I doubt thats the case.   ;  This is how I detect collision.For every collision object I have the position(x, y) and the dimension(w, h). Let's say I have a moving object and 1000 static objects. Every collision check I need to loop through all 1000 static objects to see if anyone of them collides with the moving object.Even though if I know the direction and velocity of the moving object, I still need to loop through all the objects(even if they are not in the screen) until one of them collide with the moving object, and this raises my question in this post.I think it's logical only to check objects that might collide with the moving object, but I can't think of any way to avoid looping through all objects.Please let me know if there is a better way, I appreciate all your help.Thanks,Eagle.;  This is generally handled by using two (or more) "phases" of collision detection. The first, called the broad phase, does a rough test to determine which pairs of objects might be colliding. Look into sweep and prune or spatial partitioning methods. The second phase, called the narrow phase, performs the more expensive tests to determine if the pairs tagged by the broad phase actually are colliding. The narrow phase is generally implemented with some form of the separating axis theorem test.   ;  You could organize the static objects into a spatial partitioning datastructure of some sort. Perhaps quadtree?That way you can only check against those static objects with which a potential of collision exists.Quadtree would simply divide your world space into 4 different "quadrants", each of them dividing themselves into 4 quadrants, each of which again dividing themselves into 4 quadrants and so on.At simplest, if your ship at "upper left" part of your world, the two "right" quadrants and the "lower" left one cannot contain any relevant entities concerning this particular collision test, so you can ignore them.Even A single division into 4 sectors would potentially reduce the amount of comparisons by 75% if entities are homogenously placed.[Edit] Heh. Late again. ^^   ;  Thanks guys, I don't know any of those theories before, but I will definitely look into those. I believe it's something I will need to learn.Thanks again.Eagle.   ;Quote:Original post by BuckeyeYou only need to check collisions between objects whose direction and velocity are important to the gameplay. If nothing's happening offscreen, you certainly don't need to check those collisions.As that's sort of obvious, I suspect I'm not understanding your question. Is that what you're asking about?I don't think thats entirely correct, it is for rendering (render only what you see), but for collisions I think is more correct to say check only what is not resting in place, this may well be what you meant, but I felt it needed further explanation.   ;  It SOUNDS like you'll have many moving objects that have set paths that aren't going to change, kind of like an asteroids type environment.Assuming an asteroids type environment, you have ships and asteroids. The asteroids don't have any change in velocity except when a collision occurs.At the creation of each asteroid object, you could, theoretically, calculate all the collisions that would happen beforehand and just update these predicted collisions relative to any changes that occur to a single object.You can use extrapolation to determine exactly when two objects will collide, then store that in a list somewhere- when that time is reached you can change the direction of the two objects (then find the next collision for each). Any object that is interacted with prematurely you simply update all of the expected collisions with that specific object -- You only use extrapolation up to a single collision (you don't predict collisions beyond the most recent), so you will reduce the number of checks during each iteration of your logic loop, but every time a collision happens the next hit that would happen is calculated immediately. This is disadvantageous if there are many objects in the environment that are free moving, but good if there are many static objects or objects that don't change direction from anything other than physics.