15
\$\begingroup\$

I have static objects and movable objects. The collisions are detected using the separating-axis-theorem.

For example, in this situation I have two static objects (in red):

enter image description here

and a movable object between the two:

enter image description here

My algorithm is able to compute the collision between two of these objects, and it also spits out a perfect resolution vector (meaning a minimum-displacement-vector) to the collision.

So for example, when I check the collision between the green rectangle and the right red rectangle, the algorithm spits out a vector that tells me how I need to move the green rectangle in order to resolve the collision:

enter image description here

Notice that I just quickly drew this in MSPaint, so in that picture it could actually be that the minimum-translation-vector pushes the green rectangle out on the top, but I'm going to assume here that pushing it out to the left/right is actually shorter.

The general way of approaching this would be to only resolve the collision of one collision per frame, instead of all at once. But in my case, this would result in flip-flopping:

First, the solver detects two collisions but only resolves the collision between the right rectangle and the green rectangle:

enter image description here

Then, in the next frame, it detects only one collision which is between the left red rectangle and the green rectangle, and resolves it:

enter image description here

As you can see, this doesn't actually resolve the collision (for example by pushing the green rectangle out to the top), and instead just flip flops between the two states infinitely.

How can I solve this?

\$\endgroup\$
3
  • \$\begingroup\$ You're using rectangles in your example. Does your collision algorithm only resolve collision on only one axis? If so, it makes sense that the behavior you describe is occurring. \$\endgroup\$ Aug 11, 2011 at 2:39
  • \$\begingroup\$ Nope, it can resolve them with any kind of shapes on all possible axes (not just rectangles, they're just the easiest to draw with MS paint :P) and it will always find the shortest vector that exists which pushes the two objects apart. \$\endgroup\$
    – TravisG
    Aug 11, 2011 at 5:42
  • \$\begingroup\$ +1 Good question. I removed the (2D) "tag" from the title, it's something you should avoid (see meta). \$\endgroup\$
    – bummzack
    Aug 11, 2011 at 14:30

3 Answers 3

7
\$\begingroup\$

Depending on exactly what you are trying to achieve (high physical accuracy or just a close-enough real-time simulation), you could try using speculative contacts.

Here are the details: http://www.wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collision-engine-approach-part-1/

He describes in that article what you need to know to implement it, and it's very simple compared to other approaches (such as sphere casting and then sorting collision resolutions by time of impact).

If you need/want more, you can purchase his source code for (IIRC) $7.

Here is a video of my implementation in 3D: http://www.youtube.com/watch?v=JvT2H1RmOas

Notice how stable the simulation is with just a single iteration. You could easily use multiple iterations per frame to resolve multiple collisions to a stable state, which would be more accurate.

\$\endgroup\$
1
  • \$\begingroup\$ That link to wildbunny.co.uk is broken. I found this archive which I think might be it: vodacek.zvb.cz/archiv/286.html. It mentions wildbunny, is from the same date and has the same title so I think it's the one. \$\endgroup\$
    – PhilT
    Aug 14 at 20:44
2
\$\begingroup\$

You can first compute all vectors needed to solve each collision then compute a resultant from them.

The only case when this can byte you is if these vectors nullify each other, just like in your example. In that case the collision cannot be solved.

\$\endgroup\$
4
  • \$\begingroup\$ Add a small random vector with a magnitude of about epsilon * 10 to the collisions? Floating point arithmetic should do the rest. \$\endgroup\$ Aug 11, 2011 at 13:44
  • 2
    \$\begingroup\$ Yes, this can work, I guess. But it can also create jittering movements. \$\endgroup\$ Aug 11, 2011 at 13:46
  • 1
    \$\begingroup\$ I hope I can still get a reply on this: computing a resultant fixes the "infinite loop" problem, but re-introduces the "crack" problem, where moving while sliding on a wall made of tiles of the same size makes the body get stuck between the "cracks" of the tiles. Is there any way to solve both these problems? \$\endgroup\$ Jan 30, 2013 at 16:02
  • \$\begingroup\$ Agree... there is no best "right answer" to solving an impossible rigid-body collision like that. Either it jitters, or you allow some "mushiness" in one or more of the objects. \$\endgroup\$ Apr 25, 2015 at 16:41
0
\$\begingroup\$

If you closely look at it, that state of objects is (or should be) unachievable..

Let the leftmost red shape be shape R1, and the rightmost red shape be shape R2. Let the green shape be G.

i.e. Given the size and geometry of all three objects, and given that all objects are not penetrable:

 (1) G could not have been just directly to the left of R2, since R1 has been there 
     already. Consequently, the translation of G from left to right, penetrating R2
     could not have occurred.
 (2) G could not have been just directly to the right of R1 since R2 has been there 
     already. Consquence of which is the same as that from (1).
 (3) Had G come from the top, the movement will be blocked by both R1 and R2, given
     that their geometry and Y coordinate is the same.

Now, boils down to it, if your algorithm queries your objects one by one, it then is a matter of concurrency, i.e. in a sense, the algorithm is supposed to check ALL objects at the same time, but the algorithm limits you to do objects and process them one at a time...

If G is checked against R1 after it is checked against R2, then G would appear to legally be to the right of R1 (if G say approaches R1 with the direction of vector <-1,-1> with arbitrary magnitude (or distance)), because the checking between R1 and G permits it, and forgets about the checking between R2 and G which was done before.

A solution you may do is to collect all minimum displacement vectors into an array or whatever data structure you want, and choose one that would prove legal to ALL Objects.

Note that at a given frame, the object (G for instance) can only have ONE direction. (oh man, sounds like the boyband...)

\$\endgroup\$
1
  • \$\begingroup\$ Game shapes aren't static, so it's possible to get here if an object materializes (teleports) or changes shape. For example, I have this problem when multiple nearby enemies are damaged. I have a little speech bubble that reports their damage which is wider than the enemy sprite. The speech bubbles inflate from a width of 0 to their max width, so at some particular frame, the three adjacent bubbles get big enough to inflate into each other and overlap just like this. \$\endgroup\$ Jul 20, 2021 at 21:53

You must log in to answer this question.

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