Question about the collision of two objects (points) in space

[mre521]

Hello. I am new to these forums. I don't really know if this is the right place to post this, but here it goes.

I was thinking, what If there were two bodies (represented by points) in space (two dimensional space to keep it simple) with known position at time zero, where the first is moving at a known velocity and the second moving at an unknown velocity.

There is, however, a restriction on the velocity of the second body: it can have any direction, however, it must have a specific speed, i.e. magnitude.

Let Vf = velocity of the first body,
Df = position of first body at time zero

Let Vs = direction of the second body's velocity (unit vector),
Ss = speed of the second body (magnitude of velocity),
Ds = position of second body at time zero

If Vf, Df, Ss, and Ds are known, how then can I determine Vs such that the two bodies collide in the shortest time possible?

As well, how can I determine whether or not it is possible for the two bodies to collide? For example, if |Vf| ≥ Ss and Vf points away from Ds than the two bodies would have no chance of colliding no matter what Vs is, providing |Vs| = one.

It seems to me that this may require calculus to solve, especially due to the parameter of the shortest time possible. This is the main reason why I am not sure whether this post should be in this forum or the calculus forum.

Thank you for any help.

 

[jedishrfu]

I think what you're asking about are pursuit curves:

http://en.wikipedia.org/wiki/Pursuit_curve

Solving these require differential equations experience.

 

[mre521]

Yes, I think that this will allow me to solve my problem. So I was correct, calculus is required to do it.

The actual scope of the problem is a computer game where there is a moving target and you shoot it with a projectile. So with what direction do I fire at a given time to hit the moving target if the target maintains its velocity and the bullet has a constant speed and the bullet is to hit the target in the lowest amount of time possible? I think I can use pursuit curves to figure this out.

Thank you

 

[mfb]

With uniform motion, I don't see why you would need calculus, and the shortest interception always uses a straight line. If you calculate the difference between the two objects, you get a formula for a straight line in 3D space. You just have to adjust two parameters (for the direction) to let it hit the origin. There are at most two solutions.

 

[jedishrfu]

With uniform motion, I don't see why you would need calculus, and the shortest interception always uses a straight line. If you calculate the difference between the two objects, you get a formula for a straight line in 3D space. You just have to adjust two parameters (for the direction) to let it hit the origin. There are at most two solutions.

But if this is for a game then you might like to see the curved track as a realtime calculation and it would allow for the tracked object to change direction and speed.

 

[mre521]

Yes, the main issue is that the projectile moves at a specific speed at any direction but the target could be moving at any constant speed and direction.

- If you aimed directly at the target and shot, the target would be gone from its position when the projectile reaches there.

- Even if you predict the target's future position based on the time the projectile would take to reach the target's original position, then aim towards this prediction, the time for the projectile to reach the predicted position would be different than the time used to predict that position: the target would not actually be there when the shot gets there.

If you figure out where the target would actually be when the shot gets to the target's previously predicted position and then aim at this newly predicted position, the case would be the same.
There would be one difference, however, I think: the distance between the shot and the actual target's position would get smaller each time you do this.

This is the reason I believed calculus was required: the distance between the bullet and the target's position would approach zero as you did more predictions. It's like a limit I guess.

Here is a diagram of what I'm trying to explain:

 

[jedishrfu]

you could simulate it in your game by integrating the values:

x1,y1 is the position of object 1
x2,y2 is the position of object 2

vx1,vy1 is the velocity vector for object 1
vx2,vy2 is the velocity vector for object 2
v2 is the speed for object 2

while(not hit) {
    x1=x1+vx1
    y1=y1+vy1

    sx = x1 - x2
    sy = y1 - y2
    ss = sqrt(sx*sx + sy*sy)

    vx2 = sx / ss * v2
    vy2 = sy / ss * v2

    x2 = x2 + vx2
    y2 = y2 + vy2

    plot x1,y1 and x2, y2 
}

 

[mfb]

Yes, the main issue is that the projectile moves at a specific speed at any direction but the target could be moving at any constant speed and direction.

I know.

- If you aimed directly at the target and shot, the target would be gone from its position when the projectile reaches there.

- Even if you predict the target's future position based on the time the projectile would take to reach the target's original position, then aim towards this prediction, the time for the projectile to reach the predicted position would be different than the time used to predict that position: the target would not actually be there when the shot gets there.

Sure. That's the reason you have to solve equations. You don't need differential equations.

This is the reason I believed calculus was required: the distance between the bullet and the target's position would approach zero as you did more predictions. It's like a limit I guess.

There is no need to do it iteratively.Let $x_t$ be the current position of the target (vector in 2D) and $v$ its velocity (again, a vector).
Let $x_b$ be our current position and w be the magnitude of our velocity, define (sin θ, cos θ) as the direction we should go to. Note that this vector is normalized, so our velocity is w*(sin θ, cos θ).

Our distance to the target is now $$\vec{d(t)}=\vec{x_t}+\vec{v}t - \vec{x_b}-w t \left(
\begin{array}{c}
\sin \theta\\
\cos \theta\\
\end{array}
\right)$$
Set d(t)=0 and solve the two equations for t and θ, and you are done.

 

[A.T.]

See equation 1 here:

http://en.wikipedia.org/wiki/Torpedo_Data_Computer#Angle_solver

 

[jedishrfu]

Here's a java processing (processing.org) sketch illustrating a pursuit curve computed in realtime:

float x1,y1=0;          // object 1 position
float x2,y2=0;          // object 2 position

float vx1=1.2,vy1=1.2;  // velocity of object 1
float v2=2.0;           // speed of object 2

int boom=10;

int WIDTH=640;
int HEIGHT=400;

float CLOSENESS=1.0;

void setup() {
  
  x2=WIDTH;
  y2=HEIGHT/2;
  
  // setup CANVAS size
  size(WIDTH, HEIGHT);
  
}

void draw() {
  
  if(Math.abs(x1-x2)<CLOSENESS && Math.abs(y1-y2)<CLOSENESS) {
    
    // BOOM they collided...
    if(boom<100) { 
      boom=boom+1;
      ellipse(x1,y1,boom,boom);
    } 
    
  } else {
    
    // UPDATE object 1 position
    x1=x1+vx1;
    y1=y1+vy1;
    
    // COMPUTE distance between objects
    float sx = x1 - x2;
    float sy = y1 - y2;
    float ss = (float)Math.sqrt(sx*sx + sy*sy);

    // COMPUTE velocity vector for object 2
    float vx2 = sx / ss * v2;
    float vy2 = sy / ss * v2;

    // UPDATE object 2
    x2 = x2 + vx2;
    y2 = y2 + vy2;

    // PLOT object 1 and 2
    ellipse(x1,y1,10,10);
    ellipse(x2,y2,10,10);
  }    

}

 

[mfb]

Well, a pursuit curve is not optimal (and can be far away from this, or even fail if our velocity is below the target velocity).

 

[jedishrfu]

Well, a pursuit curve is not optimal (and can be far away from this, or even fail if our velocity is below the target velocity).

Quite true, in general the pursuer must move faster and even then may not catch the target in a resonable amount of time. I just thought it was useful in real life when you don't know the actual speed of the target but you think you can catch it.

 

[mre521]

Here's a java processing (processing.org) sketch illustrating a pursuit curve computed in realtime:

float x1,y1=0;          // object 1 position
float x2,y2=0;          // object 2 position

float vx1=1.2,vy1=1.2;  // velocity of object 1
float v2=2.0;           // speed of object 2

int boom=10;

int WIDTH=640;
int HEIGHT=400;

float CLOSENESS=1.0;

void setup() {
  
  x2=WIDTH;
  y2=HEIGHT/2;
  
  // setup CANVAS size
  size(WIDTH, HEIGHT);
  
}

void draw() {
  
  if(Math.abs(x1-x2)<CLOSENESS && Math.abs(y1-y2)<CLOSENESS) {
    
    // BOOM they collided...
    if(boom<100) { 
      boom=boom+1;
      ellipse(x1,y1,boom,boom);
    } 
    
  } else {
    
    // UPDATE object 1 position
    x1=x1+vx1;
    y1=y1+vy1;
    
    // COMPUTE distance between objects
    float sx = x1 - x2;
    float sy = y1 - y2;
    float ss = (float)Math.sqrt(sx*sx + sy*sy);

    // COMPUTE velocity vector for object 2
    float vx2 = sx / ss * v2;
    float vy2 = sy / ss * v2;

    // UPDATE object 2
    x2 = x2 + vx2;
    y2 = y2 + vy2;

    // PLOT object 1 and 2
    ellipse(x1,y1,10,10);
    ellipse(x2,y2,10,10);
  }    

}

I can modify your sketch to test that my theory of using the iterations does work:

float x1,y1=0;          // object 1 position
float x2,y2=0;          // object 2 position

float vx1=-1.2,vy1=-1.4;  // velocity of object 1
float ax1 = 0.0, ay1 = 0.01; // accel of object 1
float v2=2.5;           // speed of object 2
float vx2, vy2;

int boom=10;

int WIDTH=640;
int HEIGHT=400;

float CLOSENESS=5.0;
int ITERATIONS=10;

float DELTA_T = 1.0;

float pos1x(float t) {
  float dx = x1;
  float vx = vx1;
  
  for(float t2 = 0.0; t2 <= t; t2 += DELTA_T) {
      dx += vx*DELTA_T;
      vx += ax1*DELTA_T;
  }
  
  return dx;
}

float pos1y(float t) {
  float dy = y1;
  float vy = vy1;
  
  for(float t2 = 0.0; t2 <= t; t2 += DELTA_T) {
      dy += vy*DELTA_T;
      vy += ay1*DELTA_T;
  }
  
  return dy;
}

void setup() {
  
  x1=WIDTH/2;
  y1=HEIGHT/2;
  
  x2=WIDTH;
  y2=HEIGHT/2;
  
  // setup CANVAS size
  size(WIDTH, HEIGHT);
  
  // direction for 
  float dy = 0, dx = 0;
  float distance = 1;
  float time = 0.0;
  float predx1, predy1;
  float predx2, predy2;
  
  for(int i = 0; i < ITERATIONS; ++i) {
    predx1 = pos1x(time);//x1+time*vx1;
    predy1 = pos1y(time);//y1+time*vy1;
    
    dx = predx1-x2;
    dy = predy1-y2;
    
    distance = (float)Math.sqrt(dx*dx + dy*dy);
    time = distance/v2;
  }
  
  vx2 = v2*dx/distance;
  vy2 = v2*dy/distance;
}

void draw() {
  
  if(Math.abs(x1-x2)<CLOSENESS && Math.abs(y1-y2)<CLOSENESS) {
    
    // BOOM they collided...
    if(boom<100) { 
      boom=boom+1;
      ellipse(x1,y1,boom,boom);
    } 
    
  } else {
    
    // UPDATE object 1 position
    x1=x1+vx1;
    y1=y1+vy1;

    vx1 += ax1;
    vy1 += ay1;
    
    // UPDATE object 2
    x2 = x2 + vx2;
    y2 = y2 + vy2;

    //clear();
    // PLOT object 1 and 2
    ellipse(x1,y1,10,10);
    ellipse(x2,y2,10,10);

  }    

}

This shows it works even if the target is not moving in a straight line

And @mfb, I am not quite sure how I can solve the equation for both variables. I know you can break it into the component equations but I don't see how you could eliminate a variable because the terms wtsinθ and wtcosθ contain both.

 

[mfb]

And @mfb, I am not quite sure how I can solve the equation for both variables. I know you can break it into the component equations but I don't see how you could eliminate a variable because the terms wtsinθ and wtcosθ contain both.

The equations are of the type 0=a+bt+sin θ and 0=c+dt+cosθ
Multiply the first equation with d and the second with b:
0=ad + bdt + d sinθ and 0=bc + bdt + b cosθ
Now subtract both:
0=ad - bd + d sinθ - b cosθ
This is an equation with one unknown variable only. It can be solved with various methods to combine sin and cos.