GMLscripts.com

paul23

Member

Registered: 2007-10-17

Posts: 110

instant_closest_approach - optimizing for both movable objects:

well I had a bit of spare time so I finaly wrote the proof for my optimizing code (along with a slightly different way to write it, the proof:

smallest distance if:
[m]{d(dis)}/{dt} = 0  doubleright {d(sqrt{ Delta x^2 + Delta y^2})}/{dt} =0[/m]
bcause root is zero if and only if the actual formula is 0 you can write the formula as:
[m]doubleright {d((f_x(t)-g_x(t))^2+(f_y(t)-g_y(t))^2)}/{dt}=0[/m]
[m](1)doubleright 2(f_x(t)-g_x(t))(f_x{prime}(t)-g_x{prime}(t))+2(f_y(t)-g_y(t))(f_y{prime}(t)-g_y{prime}(t))=0[/m]
filling in the formulas in for both objects (constant speed):
[m]f_x(t) = x_a+h_at doubleright f_x{prime}(t)=h_a[/m]
[m]g_x(t) = x_b+h_bt doubleright g_x{prime}(t)=h_b[/m]
[m]f_y(t) = y_a+v_at doubleright f_x{prime}(t)=v_a[/m]
[m]g_y(t) = y_b+v_bt doubleright g_x{prime}(t)=v_b[/m]
where [m]x_a[/m] = "start" position object A, [m]h_a[/b] = starting speed of object A.. Similar for object B..

filling in the values in formula 1)
[m]2((x_a+h_at) -(x_b+h_bt))(h_a-h_b)+2((y_a+v_at)-(y_b+v_bt))(v_a-v_b)=0[/m]
[m](x_a-x_b)(h_a-h_b)+t(h_a-h_b)^2=-(y_a-y_b)(v_a-v_b)-t(v_a-v_b)^2[/m]
[m]t={(y_b-y_a)(v_a-v_b)+(x_b-x_a)(v_a-v_b)}/{(h_a-h_b)^2+(v_a-v_b)^2)} doubleright[/m] strange repitition here..

As you can see there isn't an answer if (h_a-h_b)^2+(v_a-v_b)^2) = 0 (alright at this point the system crashed....) this means that both the horizontal and vertical "speed differences" are simply the same, so the objects are moving parallel.
also the function can return a negative t, which is the case if the closest point happened in the past.

anyway putting everything in code gives us:

Expand/*
**  Usage:
**      instance_closest_approach(inst)
**
**  Given:
**      inst    an instance id
**
**  Returns:
**      t       Number of step after which the
**              given instance (inst) will approach
**              the current instance (with a speed), based on the
**              position (x,y) and speed (hspeed,vspeed)
**              of the given instance (inst).
**
**  Notes:
**      if the given instance (inst) is heading away from the
**      current instance, the time returned is negative.
**
**  GMLscripts.com
*/
{
    var inst,x1,y1,x2,y2,h1,h2,v1,v2,t;
    inst = argument0;
    x1 = x;
    y1 = y;    
    x2 = inst.x;
    y2 = inst.y;
    h2 = inst.hspeed;
    v2 = inst.vspeed;
    h1 = hspeed;
    v1 = vspeed;
    if (((h2-h1) == 0) && ((v2-v1) == 0)) {
        return 0;
    }else{
        t = ((x2-x1)*(h1-h2)+(y2-y1)*(v1-v2))/(sqr(h1-h2)+sqr(v1-2));
        //distance = point_distance(0,0,t*h1,t*v1);
        return t;
    }
}

The method described above (taking the derative from the x and y functions to t and then making it 0) works for any motion where a formula for x/y -> you need to fill them in at formula (1) and then 'simply' solve to t.

Last edited by paul23 (2007-11-04 12:24:14)

Yourself

Member

Registered: 2007-10-09

Posts: 48

Re: instant_closest_approach - optimizing for both movable objects:

That seems overly complicated.  There's no reason you have to consider the motion of both objects.  You can always consider one object stationary and just look at the relative motion between the objects.  In the case of constant velocity, the whole problem ends up reducing to the closest approach to a line.  The formula you ended up with is exactly what you'd get only without all the trouble and tedium.

paul23

Member

Registered: 2007-10-17

Posts: 110

Re: instant_closest_approach - optimizing for both movable objects:

Looking back that's indeed true, however i like doing things the difficult way . (Why do all my methods turn out to be the long way round..)

Yet I think the ending code:

Expandt = ((x2-x1)*(h1-h2)+(y2-y1)*(v1-v2))/(sqr(h1-h2)+sqr(v1-2));

is a bit better than the ending code currently (which is basicly point-line distance), because the end-user doesn't have to take into account relative motions that way .

And the proof isn't that difficult: all pretty straight forward.

Yourself

Member

Registered: 2007-10-09

Posts: 48

Re: instant_closest_approach - optimizing for both movable objects:

The user would never have to account for the relative motion, the script can do that itself.  You just subtract positions and velocities and then everything's relative.