3
\$\begingroup\$

I know what an AABB is, but I don't know how you would check for collision with an object that is going really fast. If an object goes fast enough, it can skip over other bounding boxes without it detecting a collision.

Example:
High speed object

So, for an object with a bounding box to move from (0, 0) to (525, 670) in one update, would I have to somehow iterate over each point from the starting point to the end? Because I need objects to be able to go fast and still be tested for collision on other bounding boxes. I hope that makes sense.

\$\endgroup\$
  • \$\begingroup\$ I think you must do line-segment/bounding box intersection detection to avoid that. Or do several box-box intersection detection iterations, as you suggest. \$\endgroup\$ – Vaillancourt Mar 11 '14 at 18:39
  • \$\begingroup\$ @AlexandreVaillancourt Well, then I might just do it the way I suggested because I already thought about it. I would normalize the move vector and then iterate several times adding the vector to the position and also detecting collision. Thanks \$\endgroup\$ – FizzleWizzle Mar 11 '14 at 18:45
  • \$\begingroup\$ then you'll have to make many "physics" iteration (steps) within a single frame, because your boxes are all moving, and only testing "at the end" of the frame will give bad information. \$\endgroup\$ – Vaillancourt Mar 11 '14 at 19:39
  • \$\begingroup\$ @Yeah I understand. Meaning in one frame you iterate <amount of pixels to move> times and check the collision each iteration. \$\endgroup\$ – FizzleWizzle Mar 11 '14 at 19:50
  • \$\begingroup\$ Is your game grid based? Generally I could recommend a very simply raycasting solution for this issue. \$\endgroup\$ – wolfdawn Mar 12 '14 at 12:28
6
\$\begingroup\$

The term you are looking for is "Continuous Collision Detection" (CCD), something also refered to as "Anti-Tunneling" and less commonly "Broad-phase collision detection".

Some CCD implementations rely on ray-casting approaches that cast a ray in the direction of the fast traveling object to check if there is an object in the way and try to estimate whether the next frame update could already bypass this "hit" object (based on current speed). If so the expected time of impact is calculated and the movement restricted accordingly.

Another approach often used by the physics engines (e.g. "PhysX" or "Bullet") is to not only check for collisions at the position the object currently is in (which might already be beyond the object it should have collided with), but to also do various checks between the position from the previous frame and the current one. Bullet does so by using a "swept sphere" which is used to quickly check for potential collisions along that path (a sphere is used since it is even faster to check than a box).

It is advised to only turn on CCD for fast objects since it rather performance-heavy. Therefore, in some engines you have to defined speed threshold and only once they are hit, CCD comes into play (e.g. see this Bullet setup guide).

PS: I know that the mentioned physics engines are C++ and you are asking for Java, but the principles still apply.

BTW: Also have a look at this answer, as well as this more generic / theoretical SO question on potential algorithms.

\$\endgroup\$
  • \$\begingroup\$ Don't worry I know c++ just as well :) \$\endgroup\$ – FizzleWizzle Mar 12 '14 at 0:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.