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

  1. 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.
     
  2. jcsd
  3. jedishrfu

    Staff: Mentor

  4. 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
     
  5. mfb

    Staff: Mentor

    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.
     
  6. jedishrfu

    Staff: Mentor

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

    Attached Files:

  8. jedishrfu

    Staff: Mentor

    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

    Code (Text):

    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
    }
     
     
  9. mfb

    Staff: Mentor

    I know.

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

    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.
     
  10. A.T.

    A.T. 5,778
    Gold Member

  11. jedishrfu

    Staff: Mentor

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

    Code (Text):

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

    }

     
     
  12. mfb

    Staff: Mentor

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

    Staff: Mentor

    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.
     
  14. I can modify your sketch to test that my theory of using the iterations does work:
    Code (Text):
    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.
     
  15. mfb

    Staff: Mentor

    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.
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?

0
Draft saved Draft deleted