Fix collision detection penetration

3
votes

I am implementing collision detection in my game, and am having a bit of trouble understanding how to calculate the vector to fix my shape overlap upon collision.

Say for example, I have two squares. squareA and squareB. For both of them, I know their xCo, yCo, width and height. squareA is moving however, so he has a velocity magnitude, and a velocity angle. Let's pretend I update the game once a second. I have illustrated the situation below.

shapes before movement

shapes after movement

Now, I need a formula to get the vector to fix the overlap. If I apply this vector onto the red square (squareA), they should not be overlapping anymore. This is what I am looking to achieve.

enter image description here

Can anyone help me figure out the formula to calculate the vector?

Bonus points if constructed in Java.

Bonus bonus points if you type out the answer instead of linking to a collision detection tutorial.

Thanks guys!

Also, how do I calculate the new velocity magnitude and angle? I would like sqaureA to continue moving along the x axis (sliding along the top of the blue square)

2
javagame-enginephysicscollisiongame-physics
Do you really need do it so precise and complicated? Common approach is to "try" one step further, if collision happens. If it does, you just stop object that is moving. It is used even in a lot of famous and indie games. - libik
I do need it precise. If for example the frame rate is low, your method might leave a huge gap between the two squares. e.g. it would just stay where it is on the first picture. - Dominic Mortlock
true, but how I said, I did it in way I said, it was not perfect, but it was good enough. And then when I was playing games, I was surprised how much famous games used exactly same approach :). - libik
@libik Fair enough. In my old games, I slowly kept reducing one pixel from x and y until they weren't colliding anymore. But this new game I am making is heavily reliant on physics. - Dominic Mortlock
It can be done precisely with analytic geometry. You know movement vector, you can create line which leads from source to target square and you can count intersections, therefore you can find where to put these two squares precisely. However I dont know what to do, if more than 2 objects are moving and can interact multiple times with each other... - libik

2 Answers

0
votes

I had an function that looked something like this:

Position calculateValidPosition(Position start, Position end)
    Position middlePoint = (start + end) /2

    if (middlePoint == start || middlePoint == end)
        return start 

    if( isColliding(middlePont) )
        return calculateValidPosition(start, middlePoint)
    else
        return calculate(middlePoint, end)

I just made this code on the fly, so there would be a lot of room for improvements... starting by not making it recursive.

This function would be called when a collision is detected, passing as a parameter the last valid position of the object, and the current invalid position. On each iteration, the first parameter is always valid (no collition), and the second one is invalid (there is collition).

But I think this can give you an idea of a possible solution, so you can adapt it to your needs.

0
votes

Your question as stated requires an answer that is your entire application. But a simple answer is easy enough to provide.

  1. You need to partition your space with quad-trees
  2. You seem to indicate that only one object will be displaced when a collision is detected. (For the case of multiple interpenetrating objects, simply correct each pair of objects in the set until none are overlapping.)
  3. Neither an elastic nor an inelastic collision is the desired behavior. You want a simple projection of the horizontal velocity (of square A), so Vx(t-1) = Vx(t+1), Vy(t-1) is irrelevant and Vy(t+1)=0. Here t is the time of collision.
  4. The repositioning of Square A is simple.
    • Define Cn as the vector from the centroid of A to the vertex n (where the labeling of the vertices is arbitrary).
    • Define A(t-1) as the former direction of A.
    • Define Dn as the dot product of A(t-1) and the vector Cn
    • Define Rn as the width of A measured along Cn (and extending past the centroid in the opposite direction).
    • Define Sn as the dilation of B by a radius of Rn.
    • Let j be the vertex of B with highest y-value.
    • Let k be the vertex that is most nearly the front corner of A [in the intuitive sense, where the value of Dn indicates that Ck is most nearly parallel to A(t-1)].
    • Let K be the antipodal edge or vertex of A, relative to k.

Finally, translate A so that k and j are coincident and K is coincident with Sk.