Allegro.cc - Online Community

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

This thread is locked; no one can reply to it. rss feed Print
pre-calculation of circle collision
Martin Kalbfuß
Member #9,131
October 2007
avatar

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

where

r1, r2 => radius
s1, s2 => starting position
v2, v2 => velocity
dt => time of collision

I have to solve for dt. But I'm not sure how to handle the absolute value. I never
had to do this for an equation like this.

Thanks for any help.

http://remote-lisp.spdns.de -- my server side lisp interpreter
http://www.nongnu.org/gm2/ -- Modula-2 alias Pascal++

Matthew Leverton
Supreme Loser
January 1999
avatar

Just split it up into two separate equations:

<math>r1 + r2 = (s1 + v1 * dt) - (s2 + v2 * dt)</math>

or

<math>r1 + r2 = -((s1 + v1 * dt) - (s2 + v2 * dt))</math>

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
avatar

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

Arthur Kalliokoski
Second in Command
February 2005
avatar

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 1

http://math.ucsd.edu/~wgarner/math4c/derivations/distance/distptline.htm

Then 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"}604390

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

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.

<math>r_1 + r_2 = \sqrt{((x_1 + v_{x1} * d_t)-(x_2 + v_{x2} * d_t))^2 +
                        ((y_1 + v_{y1} * d_t)-(y_2 + v_{y2} * d_t))^2}</math>

<math>(r_1 + r_2)^2 = ((x_1 + v_{x1} * d_t)-(x_2 + v_{x2} * d_t))^2 +
                        ((y_1 + v_{y1} * d_t)-(y_2 + v_{y2} * d_t))^2</math>

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 <math>dt</math> to know when to change the moving directions of the two circles(balls).

http://remote-lisp.spdns.de -- my server side lisp interpreter
http://www.nongnu.org/gm2/ -- Modula-2 alias Pascal++

Arthur Kalliokoski
Second in Command
February 2005
avatar

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
avatar

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"}604394

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
avatar

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"}604398

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

I have problems,because of its complexity.
Currently I translate the coordinate-system before to eleminat <math>s_b</math>.

{"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"}604403

This way <math>s_b</math> is eleminated.

<math>\vec s_a = - \vec s_b</math> translation
<math>r_1 = r_2</math> equal sized balls

<math>r_1 + r_2 = |\vec{s_a} + \vec{v_a} \cdot \Delta t - \vec{s_b} - \vec{v_b} \cdot \Delta t|</math>

<math>2 \cdot r_1 = |\vec{s_a} + \vec{v_a} \cdot \Delta t - \vec{s_b} - \vec{v_b} \cdot \Delta t|</math>

<math>d_1 = |\vec{s_a} + \vec{v_a} \cdot \Delta t - \vec{s_b} - \vec{v_b} \cdot \Delta t|</math>

<math>d_1 = |\vec{s_a} + \vec{v_a} \cdot \Delta t + \vec{s_a} - \vec{v_b} \cdot \Delta t|</math>

<math>d_1 = |2 \cdot \vec{s_a} + \vec{v_a} \cdot \Delta t - \vec{v_b} \cdot \Delta t|</math>

<math>d_1 = |2 \cdot \vec{s_a} + \Delta t (\vec{v_a}- \vec{v_b})|</math>

<math>d_1 = \sqrt{(2 \cdot s_{a,x} + \Delta t (v_{a,x} - v_{b,x}))^2 + (2 \cdot s_{a,y} + \Delta t (v_{a,y}- v_{b,y}))^2}</math>

<math>d_1^2 = (2 \cdot s_{a,x} + \Delta t (v_{a,x} - v_{b,x}))^2 + (2 \cdot s_{a,y} + \Delta t (v_{a,y}- v_{b,y}))^2</math>

I'm not able to solve for <math>\Delta t</math>

Any Idea? Thanks.

Edit: I can eleminate <math>s_{a,y}</math>, translating the coordinate system. But there's still <math>s_{a,x}</math> which is the main problem.

Edit: Some words about the equation. <math>\Delta  t</math> 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. <math>\Delta t_1</math> and <math>\Delta t_2</math>. 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 interpreter
http://www.nongnu.org/gm2/ -- Modula-2 alias Pascal++

dejaime
Member #12,984
June 2011
avatar

I made a game (some kind of different space shooter) and used something different there for my circular collision pre-detection.
I used some resources to simplify that, it's not too hard to understand.
You simplify the problem from 2 positions, 2 radius and 2 speeds
to 2 positions, 1 radius and 1 speed or even 1 position, 1 radius and 1 speed if you consider one in the origin (0,0) and use the second as (dX, dY).
All you have to is check if the distance between the 2 positions is < (or<=) than the radius.

1: Consider object 1 as if it was a point and object 2 as a circle with diameter = (Obj1 diameter + Obj2 diameter)
This way, you check if the "point" is inside the circle with the added radius of both objects

2: Use one of the objects in the center (witch of them you choose will affect calculations, but it's really simple).

3: Use both speed vectors as one. You'll need to subtract them (not sum!)
Imagine that one circle is fleeing from the other, so, it's "escaping speed" is it's speed minus the other circle's.
So, you consider Obj 1 as the origin and make the calculations for obj 2, creating a new scheme of origin and a third obj (Obj3). (see the attached images, they'll help)
So, Obj3 has the following characteristics:
radius = Obj 1 radius + Obj 2 radius
Position = dPos = Pos2 - Pos1
Speed = dSpeed = v2 - v1
and then you look at witch time Obj 3 touches the origin (IF, it may not touch at all what means no collision).
PS: If you choose to bring Obj2 to the center, the position and speed calcs are different:
Pos = Pos1 - Pos2
Speed = v1 - v2
The circle in the center is always the negative one.

This way, you'll have only one single circle obj moving "for both", and all you have to test is if the obj is colliding with the origin.
Actually, in my game, I didn't bring any of the circular obj to the center, just used its real position and the other one's real position too, checking the dt with a different radius and speed vector...

{"name":"604406","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/1\/e10e0570bd5039387bba840e7e95eaad.png","w":271,"h":355,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/1\/e10e0570bd5039387bba840e7e95eaad"}604406 {"name":"604407","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/4\/64e672f3300916d94ff7e5288202d20a.png","w":549,"h":389,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/4\/64e672f3300916d94ff7e5288202d20a"}604407

Take a moment to consider if this can be applied to your situation, it fitted like a glove in my project.

If I find that old code I'll bring it to ya, but can't promise...
ps: keep the third object allocated, you wouldn't want to create a new object every time.

Edgar Reynaldo
Member #8,592
May 2007
avatar

Martin Kalbfub said:

I'm not able to solve for <math>\Delta t</math>

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 :
<math>Lx = Cx_2 - Cx_1</math>
<math>Ly = Cy_2 - Cy_1</math>

Find the relative velocity of the leader circle :
<math>Lvx = Cvx_2 - Cvx_1</math>
<math>Lvy = Cvy_2 - Cvy_1</math>

Write the equations for the x and y position of the leader circle at time t :
<math>xpos(t) = Lx + Lvx*t</math>
<math>ypos(t) = Ly + Lvy*t</math>

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) :
<math>dist(t)^2 = xpos(t)^2 + ypos(t)^2 = (Cr_1 + Cr_2)^2</math>

Substitute in the equations for xpos(t) and ypos(t) :
<math>Lx^2 + 2*Lx*Lvx*t + Lvx^2*t^2 + Ly^2 + 2*Ly*Lvy*t + Lvy^2*t^2 - Cr_1^2 - 2*Cr_1*Cr_2 - Cr_2^2 = 0</math>

Sort the factors according to powers of t :
<math>(Lvx^2 + Lvy^2)*t^2 + (2*Lx*Lvx + 2*Ly*Lvy)*t + (Lx^2 + Ly^2 - Cr_1^2 - 2*Cr_1*Cr_2 - Cr_2^2)*t^0 = 0</math>

So now you have a quadratic equation :
<math>A*t^2 + B*t + C = 0</math>

Use the quadratic formula :
<math>t = \frac{-B \pm \sqrt{B^2 - 4*A*C}}{2*A}</math>

With these as A, B, and C :
<math>A = Lvx^2 + Lvy^2</math>
<math>B = 2*Lx*Lvx + 2*Ly*Lvy</math>
<math>C = Lx^2 + Ly^2 - Cr_1^2 - 2*Cr_1*Cr_2 - Cr_2^2</math>

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
avatar

So now you have a quadratic equation :
<math>A*t^2 + B*t + C = 0</math>
Use the quadratic formula :
<math>t = \frac{-B \pm \sqrt{B^2 - 4*A*C}}{2*A}</math>

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 interpreter
http://www.nongnu.org/gm2/ -- Modula-2 alias Pascal++

dejaime
Member #12,984
June 2011
avatar

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: