• ### Announcements

#### Archived

This topic is now archived and is closed to further replies.

# line to line distance

## Recommended Posts

miles vignol    122
you guys were able to help me before, so I figured I''d run this by you guys... I''m doing some collision detection between a tank and a missile. They are both moving, so I figured the best way to prevent a miss due to quantizing of my time slice (like the missile "skips" over the tank) is to express the missile as an old position and a new position (or the line connecting the two). This works okay, but I''m still having problems when the target tank is moving too fast. My thought is to also treat the tank position as a line. So what I need to do then is find the value ''t'' such that the distance between Tank_Position(t) and Missile_Position(t) is minimal for 0<=t<=1. (Tank/Missile_Position(t) being the tank/missile position at time ''t'') My game world is 2D if that makes any difference. It seems like this would be either trivial or not solvable analytically. I''m not sure which. I could always resort to an iterative process, but I''d like to avoid that if possible. It would seem to me that part of the solution is to create a new (mathematical) function that gives you the distance between the points for each ''t''. That would be pretty easy, but from there, I can only see an iterative process to find the minimum... Any thoughts?

##### Share on other sites
Oluseyi    2103
How abotu computing the time when the paths of the tank and missile would intersect, rather than testing for a collision every frame? You''d have to keep this within bounds (perhaps returning a negative value) when the paths don''t intersect.

I''d like to hear what people have to say. I''ll be starting the physical simulation for a sports game soon, and I''m leaning towards having each object registered with a manager which compares paths/locales/mass/force/etc on object pairs...

[ GDNet Start Here | GDNet FAQ | MS RTFM | STL | Google ]
Thanks to Kylotan for the idea!

##### Share on other sites
ragonastick    134
Ok, it is late right now, but I think solving the problem won''t be too hard once you have the function returning distance for given t.

I have a feeling that the function will be a quadratic equation (ie in the form ax^2 + bx + c) so solving it will just be a tiny bit of simple calculus.

Since you possibly haven''t done calculus or anything, here is a crash course

The derivative of a function tells you the gradient of the curve at that point. So, the derivative of

y = ax^2 + bx + c (with respect to x (since a, b and c will be constants))

is:

Now, when the gradient of the curve is equal to 0, it means the curve is flat. For this curve (a parabola), when the gradient of the curve is equal to 0, the curve is at either a maximum or a minimum value, so it is known as a turning point.

To determine whether it is a minimum or maximum turning point, you test the ''a'' value. If it is > 0, then it is a minimum turning point. If it is < 0, then it is a maximum value. (Sorry about the lack of detail )

Now because the lines are not infinite, it means we have to do a bit more (because all non parallel lines will meet eventually). There are 3 possible points where this minimum value will occur, it can either be when t = 0, when t = 1 (or whatever the max for t is) or when 2at + b = 0.

It is quite possible to work out which of those it will be, but it will probably be easier to just test all three and check which is smallest.

hth

Trying is the first step towards failure.

##### Share on other sites
Dracoliche    122
The time when the two objects will be closest is when the velocity of one relative to the other is perpendicular to the position of the former relative to the latter.

So,
(v2(t) - v1(t)) . (r2(t) - r1(t)) = 0

You can substitute in the missile and tank and find out t. Then substitute that back into the relative position (r2(t) - r1(t)). If the result is zero, they collide.
Someone correct me if I''m wrong, it''s getting late.

##### Share on other sites
miles vignol    122
Hmmm... that last one threw me. I think I understand it, but I''ll have to draw it to make sure...

The thing that I keep running up against is that while the lines may intersect, it''s not very likely that they''ll interect with the same ''t'' value (or ''t'' won''t be 0->1).

I started thinking about the derivative this morning. I think I''ll have to write some of this stuff out and see what I come up with. The parallel case should be easily spotted and I don''t think I''ll ever have a case that would be closer at the ends than in the middle.

Thanks.

BTW, the reason I''m doing it this way (as opposed to an intersection with a bounding volume) is to then find the distance at which they are closest. If they''re at their closest and distance < (tank_radius + missile_arming_radius) then the missile will explode. Because explosions do more damage the closer they are, I want to make sure the missile doesn''t explode the instant it gets close enough if it''s due to get closer.

##### Share on other sites
jermz    122
Oluseyi, having a physics tracker to manage all the moving entities works well. However, I''m using it in a 2D game with mainly axis-aligned bounding boxes and constant velocities over each update. I''m sure it can be generalised to handle 3D space and perhaps constant acceleration over each update. Having something other than a AABBs or sphere might give you trouble though.

Right now I just check when the left sides of entity1 collides with the right of entity2 and vice versa. Same thing for top and bottoms.

e1.left + e1.vel.x * time = e2.right + e2.vel.x * time

becomes

time = (e1.left - e2.right) / (e2.vel.x - e1.vel.x)

In order for there to be a collision that frame, time must be in
[0,1], so you can actually eliminate erroenous divisions by sign and magnitude checking beforehand.

Obviously you have to make sure that the objects actually collide during that time instead of just having their edges at the same value and you have to choose the minimum time for each of the 4 collisions. Then theres the issue of order of collision inside each time frame. I handled that using a list of possible collisions ordered on time, and the equations above can be tweaked for that.

Is there a nice sweep algorithm to determine the time and point of intersection between convex polys?

##### Share on other sites
miles vignol    122
Okay, so I''m working with the derivative approach. Couple questions tho...

given:

0,0 = position of missile at u = 0
x,y = position of missile at u = 1

px,py = position of tank at u = 0 (relative to missile 0,0)
px+vx,py+vy = position of tank at u = 1

My distance formula becomes:
(u*x - (px + u*vx))*(u*x - (px + u*vx)) + (u*y - (py + u*vy))*(u*y - (py * u*vy)) = distance*distance

I "reduce" this to:

u*u * (x*x - 2*x*vx + vx*vx) + u * (2*px*vx - 2*x*px) + px*px + u*u * (y*y - 2*y*vy + vy*vy) + u * (2*py*vy - 2*y*py) + py*py = distance * distance

Would at this point take the derivative? If so, would it be:

2*u * (x*x - 2*x*vx + vx*vx + y*y - 2*y*vy + vy*vy) + (2*px*vx - 2*x*px + 2*py*vy - 2*y*py) = 0

What about the "= distance*distance" from the non-derivative function? What happens to it? I''m just solving this for when it reaches 0, right? I ignore the RHS and sub in "= 0"?

So u = (2*(x*px - px*vx + py*vy - y*py)) / 2 * (x*x - 2*x*vx + vx*vx + y*y - 2y*vy + vy*vy)

If this is all correct, then I''m doing something else wrong cuz missiles are blowing up very early. I''m checking the denominator to see if it''s 0. I''m guessing that''s the parallel line case. If it''s not, then I''m solving for u. If u isn''t between 0 and 1, I''m moving on without exlpoding, but somehow u is solving to be between 0 and 1 when there are no tanks around.

OOPS! I think I see something... I''m not negating when I moved the constant portion to the RHS... nothing like explaining a problem to somebody to help find the solution yourself! Dunno if that''ll solve things, tho.

##### Share on other sites
miles vignol    122
Yeah, that seemed to be it!

Excellent...

Thanks, guys.

##### Share on other sites
Timkin    864
quote:
Original post by Oluseyi
I''d like to hear what people have to say. I''ll be starting the physical simulation for a sports game soon, and I''m leaning towards having each object registered with a manager which compares paths/locales/mass/force/etc on object pairs...

Oluseyi, you should defintely start a new thread to discuss this idea as it sounds like it would make for a great discussion! I''d really like to hear what others have done in this situation too.

Cheers,

Timkin

##### Share on other sites
LilBudyWizer    491
If you have object a and object b at positions pa and pb at time zero with velocity vectors va and vb then their positions at time t can be calculated by the vector functions ra(t)=pa+t*va and rb(t)=pb+t*vb. The vector function rab(t)=rb(t)-ra(t) will return a displacement vector from object a to object b at time t. The scalar function d2(t)=rab(t)*rab(t) where "*" is the dot product returns the square of the distance between the two objects at time t. If you graph that function it is a parabola. The square of the distance is always positive so the parabola opens upward. The bottom of the parabola may or may not touch the t axis. If it does then at some time tn the referance points for the objects collide.

The derivative of d2(t) is a straight line. When that line is above the t axis the objects are moving further apart, when it is below the t axis they are moving closer together. When it cross the t axis they are as close as they are going to get to one another. So the challenge is to calculate the derivative of d2(t). To make that a bit simplier you calculate two vectors. These are dp=pb-pa and dv=vb-va. Now the derivative of d2(t), call it dp2(t), is dp2(t)=dv*dv*2*t+2*dp*dv. This is a scalar function and you want the value of t where the value of this function is zero. If you solve dp2(t)=0 for t you get t=-(dp*dv)/(dv*dv). t is not the time of collision. Rather it is the time the objects are closest together.

##### Share on other sites
Oluseyi    2103
quote:
Original post by Timkin
Oluseyi, you should defintely start a new thread to discuss this idea as it sounds like it would make for a great discussion! I''d really like to hear what others have done in this situation too.

Tomorrow. Need sleep now, plus have to finish my term project which is due in about 12 hours... (my fault; I went all out with 2 days to go).

[ GDNet Start Here | GDNet FAQ | MS RTFM | STL | Google ]
Thanks to Kylotan for the idea!

##### Share on other sites
henryx    128
LilBudyWizer:

You say,

Now the derivative of d2(t), call it dp2(t), is dp2(t)=dv*dv*2*t+2*dp*dv.

This stuff is good and I see where you are comming from (and going to) but I can''t see where you get the above derivative dp2(t) from. Any expansion would be appreciated.

henry

##### Share on other sites
henryx    128
Ok, thanks to another post "Vector Maths" i''ve got it now so please ignore my last post.

##### Share on other sites
miles vignol    122
LilBudy - I think I undersand your solution. I''m assuming that in your final solution for ''t'' you''re using ''*'' to denote a dot product as was the case earlier. I''ll have to see how it breaks down. Seems a lot simpler, but it might just be that there''s additional math being done to get there, considering the solution I derived bears a certain similarity... if (dv*dv==0) then the lines are parellel, yes?

##### Share on other sites
LilBudyWizer    491
No, it calculates the point where they are closest, not intersection. Two particles travelling on parallel paths at differant speeds still have a time at which they are closest. Also two particles travelling on non-parallel paths do not necessarily ever collide. Their paths cross, but that doesn''t mean both are at the point of intersection at the same time. As an example when you drive down the road your path intersects the paths of countless other cars, but hopefully you are not colliding with any of them. Those other cars were there yesterday, earlier today, last year, ten years ago, will be there tomorrow. To collide with them they have to be there at the same time you are. Also your car is not a point so you can collide even if the centers of your cars are not in the same place at the same time.

The assumption was that you were not going to do pixel perfect collisions. Rather if they are within a certain distance at the time they are closest then you say they collided. After you find the time they are closest you have to calculate sqrt(d2(t)) to find the actual distance between them. If it is less than some amount then the collided. If you want pixel perfect collisions then you have to actually solve d2(t)=(r1+r2)^2 where r1 and r2 is the radius of a bounding circle. The roots then give you the earliest/latest time a collision can occur. Assuming the sprite is any random shape you have to then step from the earliest to latest time and check for overlap of the sprites at each step. The step size would be the largest time interval that results in the fastest moving object moving a distance of one pixel. Rounding may still cause you to miss a collision but by no more than one pixel. Since this is all done between frames the user might suspect, but they will never prove it.

As for the actual derivation of the formula for the derivative it came from actually calculating the derivative of d2(t) and then reducing it to a simple formula. I use MathCAD so it is easiest just to carry everything through to the end. rab(t) is actually dp+dv*t. That makes d2(t)=dp*dp+2*dv*dp*t+dv*dv*t^2 in terms of dot products. Dot products work pretty much the same as coefficients a in scalar equation. Well, maybe exactly. So (a+b)*(c+d)=a*c+a*d+b*c+b*d except here it is (a+b*t)^2. As for whether it is a dot product or multiplication it depends. If it is two vectors, i.e. dv or dp, it is a dot product. If it is a vector and a scalar then it is scaling the vector. If it is two scalars then it is just normal multiplication. Specifically 2*dp*dv*t is the dot product of dp and dv scaled by the scalar product of 2 and t.