High Speed Collision Detection

Started by
6 comments, last by stonehat 8 years, 8 months ago

I have objects that gain velocity over time and eventually they move pretty fast. Which makes me worried about my collision detection holding up. I mean eventually I know they are going to be moving so fast they tunnel. So I was wondering if this method would work?

My idea is to cast a ray out in the direction that the object is moving. This ray would start from the object's edge at the center and its length would be the current velocity of the object. During the collision detection phase I would do a line intersection test with the hitbox of my other collidable objects. If the test passes I can assume that a collision will occur and handle it next frame

Has anyone tried something like this? Or what have you guys done?

Advertisement

I have used something like that using battleships with shields shooting at each other. Each time a projectile moved it did a raycast to see if it hit anything. The problem was if the target ship was steaming full speed towards the projectile. Then the shield might move past the projectile before the raycast detect it. As we had a limited top speed on the ships it was solved by moving the start of the raycast back a bit along the way the projectile was coming from.

@spinningcubes | Blog: Spinningcubes.com | Gamedev notes: GameDev Pensieve | Spinningcubes on Youtube


During the collision detection phase I would do a line intersection test with the hitbox of my other collidable objects.

If other objects are also moving, you need to raycast all of them.

What you described there has actually a name smile.png

It's Continuous Collision Detection (see here for example: https://en.wikipedia.org/wiki/Collision_detection#A_posteriori_.28discrete.29_versus_a_priori_.28continuous.29 )

Most Physics engines have switches to enable CCD for certain bodies (e.g. bullets, rockets, stuff like that) but often have it disabled by default since it is more costly than the standard simulation.

Edit: This page has some nice graphics explaining the stuff as well: http://www.stencyl.com/help/view/continuous-collision-detection/

What you described there has actually a name smile.png

It's Continuous Collision Detection (see here for example: https://en.wikipedia.org/wiki/Collision_detection#A_posteriori_.28discrete.29_versus_a_priori_.28continuous.29 )

Most Physics engines have switches to enable CCD for certain bodies (e.g. bullets, rockets, stuff like that) but often have it disabled by default since it is more costly than the standard simulation.

Edit: This page has some nice graphics explaining the stuff as well: http://www.stencyl.com/help/view/continuous-collision-detection/

Awesome! Thanks for the links

Is it really that costly? I means its just a line test right?

Well usually physics engines don't use a simple line test but sweep more or less complex shapes to get accurate hit detection in that case.

Bullet for example seems to switch to a swept sphere for CCD instead of using the original shape to reduce cost.

( https://www.panda3d.org/manual/index.php/Bullet_Continuous_Collision_Detection )

However it probably depends on your use case :) If you can get away with a simple ray cast then it shouldn't be too bad considering that this is something physics engines are optimized for.

The PhysX manual - see the advanced section here: https://developer.nvidia.com/sites/default/files/akamai/physx/Manual/Advanced.html also contains interesting tidbits.

Depends on what kind of objects. Can these objects rotate, or are they just translated? Can they collide with one another, or do they only collide with the non-moving world geometry? These questions are important since they might allow a simple solution that makes some key assumptions.

For the object that move so fast it tunnels, you check whether it intersects with the hit box(assumed only one) in the scene

If it does, store the distance from the object to the intersection point. If your algorithm can't provide the contact point,

simply get the length of the vector from the position of the object, to the position of the hit box. It may not be accurate,

but your object gets faster the longer it travels. I think it won't make any difference.

In the next frame, do the same intersection test. If it doesn't intersect(the hit box moves away), discard the distance stored.

But if it does, check if the current position of the object is greater than the intersection point. The concept is that if the

object is beyond the hit box while the algorithm returns true(meaning the object hits the hit box), it not only intersects the box

but also is already beyond it. This could possibly solve the tunneling problem.

This topic is closed to new replies.

Advertisement