Jump to content

  • Log In with Google      Sign In   
  • Create Account

Fast-moving 2D collisions?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
8 replies to this topic

#1 megabaki   Members   -  Reputation: 126

Like
0Likes
Like

Posted 20 April 2014 - 08:51 PM

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.
 



Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13934

Like
8Likes
Like

Posted 20 April 2014 - 09:39 PM

In order to test a sphere colliding against walls, you can reduce the sphere to a point and augment the walls by the radius of the sphere. Now instead of just checking whether a single point is inside the augmented walls, check if the segment that joins the two consecutive positions of the center of the sphere intersects the augmented walls.

#3 Buckeye   Crossbones+   -  Reputation: 6402

Like
7Likes
Like

Posted 20 April 2014 - 10:07 PM

As an alternative to Alvaro's suggestion, if you have fast moving objects, you should probably be predicting, rather than checking for, collisions each frame. That is, rather than moving the object and then checking for collisions, use the current position (prior to moving) and check for collisions along the objects path for a minimum distance of v*dt, where v is the vector velocity, and dt is the frame update delta-time. Checking the intersection of a line with a plane is a pretty inexpensive calc.


Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.


#4 ferrous   Members   -  Reputation: 2146

Like
2Likes
Like

Posted 21 April 2014 - 10:40 AM

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, 21 April 2014 - 10:54 AM.


#5 Waterlimon   Crossbones+   -  Reputation: 2644

Like
3Likes
Like

Posted 21 April 2014 - 10:54 AM

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, 21 April 2014 - 11:06 AM.

o3o


#6 ferrous   Members   -  Reputation: 2146

Like
0Likes
Like

Posted 21 April 2014 - 11:05 AM

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.



#7 0BZEN   Crossbones+   -  Reputation: 2025

Like
3Likes
Like

Posted 21 April 2014 - 12:22 PM

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, 21 April 2014 - 12:23 PM.

Everything is better with Metal.


#8 ferrous   Members   -  Reputation: 2146

Like
2Likes
Like

Posted 21 April 2014 - 01:25 PM

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, 21 April 2014 - 01:25 PM.


#9 megabaki   Members   -  Reputation: 126

Like
1Likes
Like

Posted 21 April 2014 - 03:02 PM

Thanks all!  Good suggestions.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS