Sign in to follow this  
megabaki

Fast-moving 2D collisions?

Recommended Posts

I'm looking for information on how to detect a 2D collision for a fast-moving object.

The object may be moving faster than the frame rate of the screen, so it's position may pass right through a wall/barrier,
by the time the next frame arrives.

My application is simple, so I'm not using any physics libraries, nor do I want to.
The object is a sphere moving in a straight line, like a bullet.  The domain is in 2D.
 

Share this post


Link to post
Share on other sites

I think the term is a Sweep test, in 2d, you would take the position of the circle, extrapolate it out to where you think the position would be, and end up with a 2D capsule, so start circle + rectangle + end circle.

 

EDIT: And my answer is basically the same as Alvaro's.  Depending on how complicated your walls are, and how many of them you have, it may or may not be better to inflate your walls.  (Or, if you have unchanging wall geometry, and unchanging moving character radius, you can just inflate everything once and store it that way for the collision tests.)

Edited by ferrous

Share this post


Link to post
Share on other sites

If your game is simple, I would probably just do some extra physics updates for fast moving objects to decrease the distance they jump over between collision checks.

 

Eg instead of

 

Ball.updatePhysics(dT=1/FPS)

 

do

 

for 1 to n do:

Ball.updatePhysics(dT=(1/FPS) / n)

 

where you determine n using the velocity of the object relative to its surroundings. If its moving fast, you increase n to advance its physics in smaller steps.

Edited by Waterlimon

Share this post


Link to post
Share on other sites

Waterlimon isn't incorrect and doing that is a good idea, but usually at some point you'll run into something that just moves too fast, even with small timesteps and need to fallback on a sweep test.

Share this post


Link to post
Share on other sites

to summarise :

 

1) approximate to a point and do a raycast test. 

2) use a swept sphere test (solving second order equations).

3) use substep collision detection. Divide your frame timestep into smaller timestep (based on the speed and size of the object), and do multiple checks along the path.

 

1) can be a good approximation for 'bullet hell' type of games. do a segment intersection between from the start position to the end position of the bullet from frame to frame.

2) is probably the most accurate, more math intensive. You can also do more complex swept tests with polygons, or testing fast moving objects against each other, and do proper physics as well (points of contact, accurate deflection and collision response, ect...). 

3) is the easiest to do (since it's just multiple collision detection tests). but not the cheapest computationally, or the most accurate. But can also helps with fast spinning objects, like blades. 

Edited by 0BZEN

Share this post


Link to post
Share on other sites

Just to mention Alvaro's method isn't really the same as your first point, but a simple ray test is decently accurate for small enough objects.  Or even just a couple of rays might be simpler than a very complicated complex shape.  (Though the OP mentioned it was a circle)

 

As an example of Alvaro's method, take two circles, one of radius 3, and one of radius 7, you can do the collision test by just checking if the center point of the first circle is within radius 10 of the second circle.  It's mathematically equivalent.  I inflated the second circle by the radius of the first object.  If the first circle was moving, it simplifies down to a line segment-circle test.  You can see this a lot with navmeshes that are built with a certain radius in mind.  They are all pushed out by the radius of the object they were made for.

Edited by ferrous

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