Jump to content
  • Advertisement
Sign in to follow this  
_kw

2D collision detection problem

This topic is 3539 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I've been working on a little 2D game, which features circular objects knocking into each other. I have a function that derives the time of collision from the positions and velocities of two game objects. I started out with the basic formula that at time t, the two objects would cross each others boundaries and therefore collide. I have restructured this formula to a way where I can solve it with the quadratic formula (http://en.wikipedia.org/wiki/Quadratic_formula#Quadratic_formula). The way I derived the parameters for this function is as follows:
Quote:
P = Position of object (Vector2) V = Velocity of object (Vector2) R = Radius of object (float) NOTE : all objects are circular Initial formula | (P1 + V1*t) - (P2 + V2*t) | == (R1 + R2) Move everything to the left hand side | (P1 + V1*t) - (P2 + V2*t) | - (R1 + R2) == 0 Remove useless braces | P1 + V1*t - P2 - V2*t | - (R1 + R2) == 0 Rearrange variables | P1 + V1*t - P2 - V2*t | - (R1 + R2) == 0 Reintroduce braces to emphasize separation | (P1 - P2) + (V1 - V2)*t | - (R1 + R2) == 0 Write out the length, in sqrt form sqrt( ((P1.x - P2.x) + (V1.x - V2.x)*t)² + ((P1.y - P2.y) + (V1.y - V2.y)*t)² ) - (R1 + R2) == 0 Remove the sqrt by squaring (R1 + R2) ((P1.x - P2.x) + (V1.x - V2.x)*t)² + ((P1.y - P2.y) + (V1.y - V2.y)*t)² - (R1 + R2)² == 0 Write out the two squares (P1.x - P2.x)² + (P1.x - P2.x)*(V1.x - V2.x)*t + (V1.x - V2.x)²*t² + (P1.y - P2.y)² + (P1.y - P2.y)*(V1.y - V2.y)*t + (V1.y - V2.y)²*t² - (R1 + R2)² = 0 Group the variables by their order of t (t², t¹, 1) ((V1.x - V2.x)² + (V1.x - V2.x)²) * t² + ((P1.x - P2.x)*(V1.x - V2.x) + (P1.y - P2.y)*(V1.y - V2.y)) * t + (P1.x - P2.x)² + (P1.y - P2.y)² - (R1 + R2)² = 0 Simplify the parameters |(V1 - V2)|² * t² + (P1-P2) dot (V1-V2) * t + |(P1-P2)|² - (R1 + R2)² Now that it is in a form that can be solved (using the quadratic formula) let us extract the parameters: A = |(V1 - V2)|² B = (P1-P2) dot (V1-V2) C = |(P1-P2)|² - (R1 + R2)²
After some debugging, the problem seems to be that the part inside the square root of the quadratic equation (i.e. "b² - 4ac") is a negative value. Of course, the square root of a negative value is complex, and in this case NaN. I'm wondering where I went wrong, the reasoning all seems straight forward enough.. Did I make a mistake deriving the function? Is there another problem I'm not aware of? I'm pretty stuck with this, any help would be greatly appreciated. Thanks in advance, _kw

Share this post


Link to post
Share on other sites
Advertisement
Your math is almost correct, but there is one small error. B is incorrect. It should be:

B = 2 * (P1-P2) dot (V1-V2)

You may have just made a typo, but I thought I'd point it out just in case. Anyway, the radicand (in this case, b2-4ac) will be negative if the two circles never intersect based on the positions and velocities. So after you fix B in the equation, there is nothing wrong with getting a negative radicand. It just means that they don't ever intersect. You should check for a negative radicand before taking the square root though.

Share this post


Link to post
Share on other sites
Awesome, thanks!
I just tried it and now it all works perfectly :-)
Was already checking for negative square root by the way, but it was getting negative values even when they were about to collide.. Anyway, it works perfectly now, thanks again :-)

-kw

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!