Collision Detection Algorithm

EvilProgrammer · 2004-02-17T18:13:07

I''m making a game right now and I''m trying to implement some kind of collision detection system for the objects in my world. I''m a newbie so I have a lot of questions about things there are probably very simple solutions for. Maybe this is more appropriate for the beginner forum, but I chose to put it here. If you have a problem with that, I apologize. I''ve read dozens of online tutorials about collision detection, all dealing with objects intersecting, planes, AABB''s, etc. However, none of these has given a satisfactory explanation for how to go through all the objects in your world every frame and check for collisions. What I mean is, suppose you have two moving objects and you want to see if they collide. Well, you can see if their paths cross, and if they do you can calculate when this happens, but this introduces all kinds of complications (especially since for irregularly shaped objects, finding out when their paths crossed would be a simple matter compared to finding out when they actually collide). Sure, you can say the movement of all objects each frame is so negligible (unless you have some super fast object) that you don''t really need to check their paths because they won''t move far enough to pass through another object. But suppose the frame rate suddenly bombed. You could have two separate results due to a frame rate discrepancy, something I''d like to avoid. Another problem is if you did manage to work out a system that worked, suppose object A collides with object B, bounces off, and crosses the path of object C, which you''ve already moved past the point of possible collision. My personal solution to this problem would be to construct the algorithm so it finds the time it takes for the first collision to occur and animate the world that much time before moving on to the second soonest collision. It all sounds good except it seems like it would all be really ugly and require a lot of math in the end. I''m beginning to think an algorithm that slowly moved all the objects little by little from their initial to their final positions, checking for collisions along the way would be simpler and work faster. So, if someone could clear some of these things up for me tell me how to do this, or point out a really good tutorial, I would be very grateful. If I said something that was incorrect please correct me. Thank you.

Math and Physics Programming

Started by EvilProgrammer December 15, 2003 10:52 PM

23 comments, last by EvilProgrammer 20 years, 2 months ago

CGameProgrammer

640

February 16, 2004 06:52 AM

I''ve written triangle-triangle collision that does not work on intersections; it finds the exact distance between two triangles along the movement direction and handles the collision correctly (including "sliding" collision). I''m working on writing an article/tutorial on it but for now you can try to make sense of the source code posted here. The algorithm for calculating the bounced vector (the new movement direction after you hit something) isn''t totally perfect, but otherwise it should work without a problem.

~CGameProgrammer( );

-- Post screenshots of your projects. There''s already 134 screenshot posts.

~CGameProgrammer( );Developer Image Exchange -- New Features: Upload screenshots of your games (size is unlimited) and upload the game itself (up to 10MB). Free. No registration needed.

keethrus

122

February 16, 2004 03:40 PM

Im a little curious about some of the ideas presented here. Mainly the one where you (1) find all collisions, storing them in a list sorted by time of collision (2) do physics, apply forces on the first collision in the list (3) move all objects to the point in time where the first collision occurred (4) goto 2 until the list is exhausted.

Would this scheme work when a collision is a constant one? Like when a ball is resting on top a plane, and gravity is constantly pulling the ball directly down on the plane. It seems like in step 2 when you apply forces, nothing would happen with this collision and it would still collide instantly. Wouldn''t that mean it would still be the first in the list, and the loop would just stay there forever?

- Jeremiah

inlovewithGod.com

inlovewithGod.com

Charles B

863

February 16, 2004 04:17 PM

Right sliding is not required, I can rely on impulse only in the particular game I have in mind and the test I already made (many balls on a planar surface (2D)). However, I would consider constrainted physics differently. Within certain conditions, I would add temporary constraints. For instance a planar constraint for sliding. I already explained the scheme in details in another thread at GD. But it''s true that I still have not tested it in real life. It may be full of subtelties to handle. Also something most probably required is cinetical energy must decrease, this avoids decor traversal instead of movement decrease then rest (you infinite loop remark).

"Coding math tricks in asm is more fun than Java"

keethrus

122

February 17, 2004 05:49 PM

Im sorry, but I dont understand what you''re trying to say. Could you elaborate on your method and how it fixes the inifinite "resting object" loop? Thanks.

- Jeremiah

inlovewithGod.com

inlovewithGod.com

EvilProgrammer

122

Author

February 17, 2004 06:13 PM

Well, one thing you could do is only apply the force of gravity once, at the beginning of the frame. Then you only get one collision, handle it, and after that you''re fine.

Another approach is to have a flag for each object that tells if the object is at rest. If an object is at rest, it is sitting on something and the force of gravity is assumed to be instantaneously counteracted by that something. So when the object''s at rest, you don''t apply gravity to it and wait until someother object applies a force and gets it moving again.

Collision Detection Algorithm

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Collision Detection Algorithm

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines