Allegro.cc Forums » Programming Questions » pre-calculation of circle collision

 This thread is locked; no one can reply to it.
 pre-calculation of circle collision
 Martin Kalbfuß Member #9,131 October 2007 Hi,I try to calculate the time of collision of two circles. After thinking a while about it I got the following equation:r1 + r2 = |(s1 + v1 * dt) - (s2 + v2 * dt)|;wherer1, r2 => radiuss1, s2 => starting positionv2, v2 => velocitydt => time of collisionI have to solve for dt. But I'm not sure how to handle the absolute value. I neverhad to do this for an equation like this.Thanks for any help. http://remote-lisp.spdns.de -- my server side lisp interpreterhttp://www.nongnu.org/gm2/ -- Modula-2 alias Pascal++
 Matthew Leverton Supreme Loser January 1999 Just split it up into two separate equations:or Then solve each independently for dt.
 Myrdos Member #1,772 December 2001 [EDIT] Whoops, didn't read your question carefully enough. __________________________________________________
 Oscar Giner Member #2,207 April 2002 You just handle 2 equations, one where it's positive:r1 + r2 = (s1 + v1 * dt) - (s2 + v2 * dt)and another when it's negative:r1 + r2 = -((s1 + v1 * dt) - (s2 + v2 * dt))That is, you get 2 solutions. You need to check which of the 2 is the one you want (you probably want the smaller dt which is >= 0). --[Website | e-mail][Tetris Unlimited] [AllegAVI | AlText]
 Arthur Kalliokoski Second in Command February 2005 Un-removed due to double stupidity (the first one seemed to only work if circle center was tangental to circle 2)The way I'd do it:Find the closest the center of circle 2 will get to circle 1http://math.ucsd.edu/~wgarner/math4c/derivations/distance/distptline.htmThen the hypotenuse is the sum of the radii.Use trigonometric identities to find how far circle 2 has progressed.{"name":"604390","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/8\/08f4c24026f741f06187590d6e4d7c22.png","w":584,"h":360,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/8\/08f4c24026f741f06187590d6e4d7c22"} “Throughout history, poverty is the normal condition of man. Advances which permit this norm to be exceeded — here and there, now and then — are the work of an extremely small minority, frequently despised, often condemned, and almost always opposed by all right-thinking people. Whenever this tiny minority is kept from creating, or (as sometimes happens) is driven out of a society, the people then slip back into abject poverty. This is known as "bad luck.”― Robert A. Heinlein
 Martin Kalbfuß Member #9,131 October 2007 Sorry guys. I've made a mistake.It's the absolute value of a vector not a scalar. I'm not sure if I used the correct words and symbols to represent this.I forgot what I've learned in school.I assume that's the correct solution. I will write a small simulation in the end.Thanks for your answers. What do you think about it? Both balls are moving.I need to know when to change the moving directions of the two circles(balls). http://remote-lisp.spdns.de -- my server side lisp interpreterhttp://www.nongnu.org/gm2/ -- Modula-2 alias Pascal++
 Arthur Kalliokoski Second in Command February 2005 I think my idea would still work if you simply took circle 1 to be stationary and subtracted the circle 1 vector to circle 2 trajectory. I'll make an allegro 4 program to demonstrate if you can compile an allegro 4 program. “Throughout history, poverty is the normal condition of man. Advances which permit this norm to be exceeded — here and there, now and then — are the work of an extremely small minority, frequently despised, often condemned, and almost always opposed by all right-thinking people. Whenever this tiny minority is kept from creating, or (as sometimes happens) is driven out of a society, the people then slip back into abject poverty. This is known as "bad luck.”― Robert A. Heinlein
 Edgar Reynaldo Member #8,592 May 2007 I did this some time ago, and solved it using intercept times. The code is kind of old, and a little messy, but you should get the picture anyway.PhysicsTest4.7z (src, exe, A44 dll)Use the arrow keys to accelerate, space to stop, - and = to decelerate and accelerate and escape to quit.{"name":"604394","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/7\/e7d3d1cfce2f9a891e2af6f4a85bd2d4.png","w":812,"h":632,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/7\/e7d3d1cfce2f9a891e2af6f4a85bd2d4"}Arthur's approach might be simpler, but his diagram is misleading. The point where the trajectory of the first circle is closest to the center of the second circle is not always on the edge of the first circle, so you can't mark the distance from there to the center of the first circle after it moves as being equal to the radius of the first circle.To use Arthur's method, I would :1) Find the relative velocity of circle 1 to circle 2. We'll consider circle one as moving and circle 2 as stationary.2) Create a line equation using the ray created by the relative velocities (cx1,cy1)->(cxvel1,cyvel1). The magnitude of the relative velocity must be non zero or they can't collide.3) Find the point on the line closest to the center of circle 2.4) Find the distance from the point in 3 to the center of circle 2. This distance must be less than or equal to the sum of the radii or they will never collide.5) The distance from 3 to the center of circle 1 is the square root of ((sum of radii) squared minus the distance in 4 squared).6) Find the distance from the point in 3 to the center of circle 1.7) The distance traveled by circle 1 is the distance in 6 plus and minus the distance in 5.8) Divide the distance traveled by the relative speed of circle 1 to find the time of intercept.
 Arthur Kalliokoski Second in Command February 2005 Edgar Reynaldo said: The point where the trajectory of the first circle is closest to the center of the second circle is not always on the edge of the first circle.That was a second attempt, and still too hurried. The fact is that it doesn't depend on the tangent of either the first circle (first attempt) or second circle (second attempt). It just needs to check that the sum of the radii is greater than the closest distance.Here's a third attempt{"name":"604398","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/4\/94d9f8b157f3f26893eeb8f9707cd3e1.png","w":466,"h":279,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/4\/94d9f8b157f3f26893eeb8f9707cd3e1"} “Throughout history, poverty is the normal condition of man. Advances which permit this norm to be exceeded — here and there, now and then — are the work of an extremely small minority, frequently despised, often condemned, and almost always opposed by all right-thinking people. Whenever this tiny minority is kept from creating, or (as sometimes happens) is driven out of a society, the people then slip back into abject poverty. This is known as "bad luck.”― Robert A. Heinlein
 Martin Kalbfuß Member #9,131 October 2007 I have problems,because of its complexity.Currently I translate the coordinate-system before to eleminat .{"name":"604403","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/4\/347d4bf6af32bd7d7201f8b5b1a0b306.png","w":794,"h":1123,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/4\/347d4bf6af32bd7d7201f8b5b1a0b306"}This way is eleminated. translation equal sized ballsI'm not able to solve for Any Idea? Thanks.Edit: I can eleminate , translating the coordinate system. But there's still which is the main problem.Edit: Some words about the equation. is the time when the absolute value of the distance is equal to the added radi. This is the time, when both circles collide. I'm still not sure, if this is correct.Edit: Oh! I have two unkown variables. and . They're only equal for a collision. But they don't have to be even if their paths are crossing. http://remote-lisp.spdns.de -- my server side lisp interpreterhttp://www.nongnu.org/gm2/ -- Modula-2 alias Pascal++
Edgar Reynaldo
Member #8,592
May 2007

Martin Kalbfub said:

I'm not able to solve for

Sure you can, you just have to multiply everything out and then sort the coefficients on the powers of time.

Dejaime has the right idea, but he didn't go fully into the equations involved, so I will.

First, you have circle one and circle two. Consider circle two as the leader circle. All positions and velocities will be relative to circle two one. That means circle one is effectively stationary and centered on the origin.

Find the relative position of the leader circle :

Find the relative velocity of the leader circle :

Write the equations for the x and y position of the leader circle at time t :

Write the equation for the distance from the origin squared at time t (this should be set equal to the squared sum of the radii) :

Substitute in the equations for xpos(t) and ypos(t) :

Sort the factors according to powers of t :

So now you have a quadratic equation :

Use the quadratic formula :

With these as A, B, and C :

That gives you the times of intercept.

If the discriminant[1] of the quadratic formula is negative or if A is zero then there are no real solutions. If the discriminant is zero, there is one solution and the circles glance off of each other. If the discriminant is positive, then there are two real solutions. To indicate a collision, one of the solutions must be positive. If both are positive, use the smallest one, as that is the earliest collision.

Once you get that method to work, you should try out Arthur's solution. You have to know how to use a general first degree equation of a line, but that's not too hard. His solution really is simpler.

## References

1. The difference of B squared and 4 A C
 Martin Kalbfuß Member #9,131 October 2007 Edgar Reynaldo said: So now you have a quadratic equation :Use the quadratic formula : Thank you very much. I completely forgot about the quadratic formula to solve a quadratic equation. http://remote-lisp.spdns.de -- my server side lisp interpreterhttp://www.nongnu.org/gm2/ -- Modula-2 alias Pascal++
 dejaime Member #12,984 June 2011 Edgar Reynaldo said:Dejaime has the right idea, but he didn't go fully into the equations involved, so I will. Thank you for the math, I find that part boring... [:If you happen to test and one root is Zero that means the objects are "touching but not colliding", if you get me. So, the second root (probably not equal to zero unless both objects are points or other situations regarding parallel movement directions) will tell you if they are going to collide shortly (positive root) or they are not going to collide (negative root).If you have a negative and a positive root that means the objects are already colliding.If anyone can confirm this, I'm feeling kinda dumb 2day, anything can happen!@edit: I needed this coz there were some different interactions on collisions in my design, some kind of ethereal state, where some objects could go through other while applying an abnormal effect... Something like Physical + Physical or Ether + Ether = normal Collision, Physical + Ether = no collision, but I still needed to know if they were "sharing space" so I could apply the secondary effects. If you have no need for this, it'll be even simpler!
 Go to: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads