3
\$\begingroup\$

So I have a 2D game involving balls (circles) colliding. I want to be able to detect if two balls will collide before it happens, and the normal vector of the collision if a collision is going to happen. Take a look at the below picture:

Determining if balls will collide

Essentially a normalized vector represented by the red arrow is what I am interested in knowing. How can I figure that out any frame most efficiently, given I know the following:

  • The blue ball has a current initial velocity
  • The ball ball is pulled down by a constant gravity
  • The green ball does not move
  • The sizes and location of both balls
\$\endgroup\$
3
\$\begingroup\$

Chapter 1: Movement Prediction for Beginners

If you know the point of contact and especially the positions of the balls at contact, you can simply normalize the vector

//pseudocode
normalize ( blue.position - green.position )

Now for the collision prediction itself:

In every update the gravity vector is applied to your current velocity. To get out mathematics this means

velocity(0) = initialVelocity
velocity(t+1) = velocity(t) + gravity

where t is the number of Updates that occured after the start of the calculation. Implementing this in code would look like this:

//pseudocode
function predict()
    //I cheat a bit. You have to think of a smart way to copy in your language
    var bluePredict = copy(blue)
    while true do
        //If blue is completly below green and moving downwards, we can't possible hit green anymore.
        if blue.position.y+blue.radius < green.position.y-green.radius and blue.velocity.y < 0 do
            break;
        end

        //We don't actually add the whole G-Vector, but only the one applied in the update-timeframe
        bluePredict.velocity = bluePredict.velocity + gravity*deltaTime;
        bluePredict.position = bluePredict.position + bluePredict.velocity;
        if detectCollision(bluePredict, green) do
            return normalize (bluePredict.position - green.position);
        end
    end
end

Call predict and get the normalized vector back.

Warning This method does not interpolate the point of contact. Your balls will most likely intersect on collision and blue can even pass through green if blue moves fast enough. This is however a common problem of Collision detection and not easily tackled. Specify a language and/or Developmentarea (like Unity for example) and I can give you more detailed help. If you have questions about the interpolation, please feel free to comment.


Chapter 2: Interpolation for Beginners

Note: The following chapter is partially based on this document and this document.

A common problem with collission detection is, that the blue disc "penetrates" the green disc without colliding with it. Take a look at the following picture:

Blue moving towards green

The blue arrow denotes both the direction and speed of the blue disc, it is also often known as velocity-vector.

  1. The disc moves slow enough to collide with the green disc. Normal vector and Position of the collission are known good enough (Inaccuracies come because of my bad Paint.NET-Skills).

  2. The disc moves slow enough to collide with the disc, but too fast for the correct result. For the Programm, it looks like the blue disc collided on the other side of green and it computes a wrong normal vector.

  3. Worst case. Blue moves so fast that within one updatestep it is behind green, without triggering a collission.

So is fast movement necessarily bad? NO! At least not with caution.

What we used in chapter 1 is known as Periodic Interference Test (PIT). It has some great advantages (like speed), but also some great disadvantages (see picture).

The solution: Predicted Instant of Collision (PIC)

Please take a look at this question at stackoverflow, which describes your problem in 3D-Space (but should be easily convertible, as nobody actually cares for the size of the vector in this case.

\$\endgroup\$
  • \$\begingroup\$ I decided to add a chapter about interpolation, but won't be able to post it here before 7-8 hours from now (see timestamp) on. Stay tuned. \$\endgroup\$ – J_F_B_M Aug 2 '14 at 12:24
  • \$\begingroup\$ I currently can't wrap my head around these euqations for nonlinear-PIC, but found a similar question at StackOverflow, where someone already did the whole math ( they assumed both spheres/discs are accelerating, simply assume an acceleration of 0 for green). The math used is both usable in 2D- and 3D-Space, so it is suitable for this question. \$\endgroup\$ – J_F_B_M Aug 2 '14 at 23:03

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.