line to line distance
Author
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?
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!
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!
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:
gradient = 2ax + b
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.
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:
gradient = 2ax + b
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.
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,
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.
So,
(v2(t) - v1(t)) . (r2(t) - r1(t)) = 0You 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.
Author
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.
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.
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?
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?
Author
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.
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.
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
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
