8
\$\begingroup\$

I have a basic 2D physics engine running. It's pretty much a particle engine, just uses basic shapes like AABBs and circles, so no rotation is possible. I have CCD implemented that can give accurate TOI for two fast moving objects and everything is working smoothly.

My issue now is that i can't figure out how to determine whether two fast moving objects should even be checked against each other in the first place. I'm using a quad tree for spacial partitioning and for each fast moving object, i check it against objects in each cell that it passes. This works fine for determining collision with static geometry, but it means that any other fast moving object that could collide with it, but isn't in any of the cells that are checked, is never considered.

The only solution to this i can think of is to either have the cells large enough and cross fingers that this is enough, or to implement some sort of a brute force algorithm. Is there a proper way of dealing with this, maybe somebody solved this issue in an efficient manner. Or maybe there's a better way of partitioning space that accounts for this?

Here's a diagram:

enter image description here

Object A and B's "areas of effect" cross, they should be checked against each other. But with the way i'm currently checking for collisions does not account for this. Again, i can think of a few solutions to this like actually checking if objects' paths cross once their velocity is higher than x, or something, but that feels like a hack and it's a mess to try and implement.

Improve this question
\$\endgroup\$
5
  • \$\begingroup\$ Could you give an example scenario in which your method fails? \$\endgroup\$
    – Anko
    Dec 20, 2012 at 13:39
  • 1
    \$\begingroup\$ I think it would go like this : object A and B are in this configuration : [A][ ][B]. A is going rightward and B leftward. They go fast. The collision check goes as that: is the next cell empty for A ? Yes, bcs there is nothing in the middle cell. Is the next cell empty for B? Yes. So no collision. But real physics would show that A and B are likely to collide (especially in this one dimension game I decribe ;) \$\endgroup\$
    – Cystack
    Dec 20, 2012 at 15:34
  • \$\begingroup\$ @Cystack I have CCD implemented. The situation you described is not an issue. The two objects are going straight at each other, the implementation i described is going to pick that up and solve it. \$\endgroup\$
    – dreta
    Dec 20, 2012 at 17:24
  • \$\begingroup\$ The physics of situation is clear. Let us say that you can identify an object as 'fast moving' ahead of time. Then when you do a collision check you need to check not just for the cell that the object is currently in, but all of the cells it passed through on the last time step. So each fast-moving object actually has multiple locations, like the entire green swath you drew in the above image. \$\endgroup\$
    – john_science
    Dec 20, 2012 at 17:29
  • \$\begingroup\$ @theJollySin i already described the solution you're giving, it's a hack, a special case, i'm looking for a general solution if there is one. \$\endgroup\$
    – dreta
    Dec 20, 2012 at 17:33

1 Answer 1

Reset to default
5
\$\begingroup\$

The problem you are talking about is often called 'broadphase collision detection' and your solution is a 'swept volume', not really a hack, just how it's done (simply take tha AABB of the object including both start and end of the motion and use that for collision - though things get a little tricky with rotations).

Then the go to broadphase collision detection algorithm that makes this fast is called 'Sweep and Prune.'

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I discarded SAP before this issue arose. I'm doing this in JavaScript which makes the overhead for lists noticeable, also arrays can get unreliable when it comes to performance. Guess i'll have to reconsider things. Thanks, the algorithm does indeed solve the issue. \$\endgroup\$
    – dreta
    Dec 20, 2012 at 20:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .