Sign in to follow this  
_kw

2D collision detection problem

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
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this