Sign in to follow this  
d3jake

Collision tests and creeping time

Recommended Posts

Hello all! For the last year or so I've been working on a game in SDL. Recently (within the last month or more) I've started making a lot of progress. I've gotten a basic weapon system going, and am writing a class for animated sprites. The problem that I am having now is with collision. I have written some pseudo-code that I want to test in a small example game, separate from my main game, to see if it works correctly. Due to the low velocities of the current weapons, and high frame rate from my computer I doubt that I should have any problems with object moving too quickly for my collision code to catch it. However I want my game to work well with slower machines as well as higher-end. The problem that arises is if the frame rate is very low, there is a chance that objects will not act as they should (objects passing through each other instead of colliding.) My question is about the "creeping time" approach that can be taken for fast moving objects and\or low frame rates which increases the time between checks of collision. The only reference that goes into it that I know of is from Lazy Foo's web SDL web site: here. Even with the source code I am a bit lost when it comes to the theory. Are the vectors of movement used to calculate how far the objects have moved in .001ms, and go ahead from there? How is it known how far to look ahead for the next collision? Or is it part of the algorithm? If anybody could point out resources (preferably free) to where I could read up on this, that would be great. EDIT: Apparently these forums use HTML instead of BB code...

Share this post


Link to post
Share on other sites
The solution to your problem is making sure that the game physics and logic are updated at a fixed rate (like 30 or 60 fps), independent from the rendering which will happen as fast as possible. When rendering faster than the game is updating, you usually update one frame ahead and then render the interpolated positions between the previous and next frames.

I don't have a favourite article about this, but I think this one might explain things in more detail.

Share this post


Link to post
Share on other sites
Here is a really good article from gamasutra.

Basically, if you take the position vector of an objects movement (endpos - startpos) and compare it another object (you can subtract the second objects position vector from the firsts to get their relative movement), using dot products and pythagorean's theorem, you can find the distance to the closest point that they hit. If you do this with all other objects in the scene, you can calculate where the closest collision is (if there is one). Then, using some simple physics, you can determine the time it takes to get to that point (timeleft = timestep - distanceinxdirection / velocityinxdirection). From there, you can compute some kind of bounce and continue for the duration of the frame, but make sure to do the same with all movement, not just the first check.

Oh, and somewhere in that article they messed up the math a bit, but it was a while ago that I read it and I can't remember what. But they did state the principle correctly.

I always test everything I do in Java, just because I can set up a graphical demonstration in about 20 minutes. One interesting way I found to solve the collision detection between any two objects of any size and shape is to have the object have a list of all of its circles, each of which has the same center but different radiuses, and each circle has its edge along some edge of the object. I'm not sure about complex objects, but on objects requiring less than 20 circles, I haven't found any loss in efficiency (and in fact, it is faster for some objects) and the idea behind this is extremely easy to comprehend.

Share this post


Link to post
Share on other sites
Wow... responses quickly! yay!

Quote:
Original post by Brain meI always test everything I do in Java, just because I can set up a graphical demonstration in about 20 minutes. One interesting way I found to solve the collision detection between any two objects of any size and shape is to have the object have a list of all of its circles, each of which has the same center but different radiuses, and each circle has its edge along some edge of the object. I'm not sure about complex objects, but on objects requiring less than 20 circles, I haven't found any loss in efficiency (and in fact, it is faster for some objects) and the idea behind this is extremely easy to comprehend.


Cool, thanks for the idea. I had decided to use circles for a first-pass of collision instead of always checking against every box of every object. I figure even that basic approach should help save some CPU time.

Quote:
Basically, if you take the position vector of an objects movement ... not just the first check.


Ahh, okay. I'd love to try that out, but my bed is calling me. Thanks for the help!

Share this post


Link to post
Share on other sites
Quote:
Original post by Brain me
Rendering as fast as possible at a fixed update rate is pointless. If you render a scene and nothing has changed since the last scene, what's the point of re-rendering?


As I said, you render interpolated positions and rotations between updates. Everything looks very smooth, but the stable simulation with a fixed time-step makes things much easier.

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