I''ve got a linked list of items that are all the objects in the game. In each node, there''s the x,y coordinates and the width & height. Let''s say I have about 2000-3000 objects in the list, and about 300 are movable. For each frame, I want to detect if there is a collision between the moving object and any other object in the game. Does that really mean I have to scan through the 3000 objects for each object that is moving? That would be about 300x3000 = 900,000 iterations. CRAZY! It would run way too slow! What''s a better way to check for collision detection? Is there a way to check just objects that are just a certain distance from the moving one? I can''t break the map up into, say, 4 squares. If an object is on the edge of one of the areas, then it still has to check the square that it is bordering with. So I really have have the whole linked list broken up. What''s a better way? ColdfireV

You may want to take a look at these:

An Efficient Collision Detection Algorithm for Polytopes in Virtual Environment
I-Collide: An Interactive and Exact Collision Detection System for Large-Scale Environments
Efficient Collision Detection for Animation and Robotics

Especially the first since it's on the development of Q-Collide a collisionpackage that the author proves to be faster than I-Collide, previously one of the fastest ways to do collision detection with a large number of objects.

More information on collision detection can be found at UNC Research on Geometric and Physically-Based Modeling


Edited by - WitchLord on 4/3/00 7:14:41 PM

One way to help speed things up is to split your world into clusters. Thus when you do a collision check you only check what is in that cluster and not in all the world.

Heres a example for say an adventure game like zelda.

Each screen is one cluster so if you shot a bullet all you would have to do is see what cluster your in and only check monsters / whatever that are in that cluster. Or you can have so many tiles or pixels represent a cluster,ect.

Dividing the play area into quadrants is a good idea. You can also eliminate some detections by
(1)check the trajectory of curr_object for intesection with other objects in the same quadrant.
(2)If (intersection) calculate how many frames it will take before they collide (time_to_collision).
(3)Skip collision detection until the number of frames passed is approximately equal to time_to_collision then start detecting.
(4)If curr_object changes direction , got to one

You can do a lot more other things like making sure you do not repeat a detection .(eg testing if (a collide b) and then in the same frame test if (b collide a) ) , you can dump some unnecessary collisions , (eg if clouds are floating around , who gives a damn if they bumb into each other ) etc

IMHO collision detection is very specific to the enviroment you are trying to create .

Edited by - Tha_HoodRat on 4/3/00 7:58:02 PM

Okay, well the environment I am creating is an Isometric Map, RTS game. The major problem with breaking up the map into quadrants is that, let''s say two objects are right next to each other, but not touching (we''ll say the collision detection implemented already prevents the two from moving because the other is in the way). If one happens to be in one quadrant, the other object is in the other quadrant, and they are both on the border, then there is no way to know that the two objects are right next to each other. Of course, you could check to see if the object is on the border somewhere, and then check the objects in the quadrant bordering it. But that brings you back to the original problem of iterating through the linked list, which could contain many, many objects. And that''s the original problem again.


ColdfireV

WhichLord, thanks for the links! However, they''re somewhat long and complicated (yeah, I''m too lazy to read the whole thing... it''s only collision detection ya know...). Is there any other articles on Q-Collide or I-Collide that you have that are smaller... or more direct and to-the-point? That''d be really awesome. Thanks!


ColdfireV

I just have to say thanks a million for the links also, Witchlord. I hadn''t realized that collision detect was still an academic area of research in CS. I read through the papers at school, they sounded very interesting, and not pie-in-the-sky in terms of implementing it into a game.


- Remnant
- (Steve Schmitt)