2D Pathfinding with Momentum

Question

You are piloting a spaceship, outfitted with an engine that can accelerate you at 1km/s^2 in the direction the ship is facing (you have very good inertial dampers). You also have thrusters which can rotate you 180 degrees in 1s (rotating 45 degrees takes 0.25s, etc.).

You see on your scanner another ship, and decide to rendezvous with it. You'll need to plot a course which brings you within 1km of it while your speed is within 1km/s of its speed.

Specifications

Write a function which takes the following pieces of data as inputs:

other_location - The location of the other ship in kms. You may assume that this is no more than 100 units away from the origin for optimization, but your entry should be able to handle larger distances (even if it takes a long time).

other_acceleration - The other ship is accelerating at a constant rate no more than 0.5km/s^2 (their inertial dampers aren't quite as good). You may take this in whatever form you wish - facing + acceleration, or separated into x and y components). The other ship starts at a speed of 0.

You always start at [0,0], facing the positive direction on the x axis.

Your function's output is significantly more constrained. You must return a list of actions your ship will take. There are three possible actions.

1. Acceleration. You accelerate in the direction your ship is facing for an amount of time you specify.

2. Rotation. You rotate to face a direction you specify.

3. Drift. You do nothing for the amount of time you specify.

Your output must have the listed data, but it can be in any format you wish. Please make it human-readable; this isn't code golf.

At the end of the final action in your list, your ship must be within 1km of the other ship and its speed must be within 1km/s of the other ship's speed. Note that if you accelerate from a stop for 1s, you will have moved 0.5kms.

Scoring Criteria

I will run each entry on my machine, a i7-9750H 2.6 GHz Windows 10 laptop. Ideally, there will be straightforward installation instructions for your language; please specify whatever build command I need to run it.

The score of an entry on a particular input will be the product of the time it takes to run and the time that it takes for your ship to intercept the other ship squared. Entries may be non-deterministic, but I will run any non-deterministic entry 10 times on each input and take the worst score.

The winner will be the entry that has the lowest total score across the inputs.

Example inputs

Here are a bunch of sample inputs (that I'll use as the test set, though I might add some more if some programs are very quick). Feel free to post preliminary outputs/scores for each of these (run on your machine), but note that it's a standard loophole to tailor your program to these inputs.

other_location (x, y), other_acceleration (x, y)
[10,0], [0,0]
[6,-3], [0,0.5]
[-2,8], [0.1,-0.2]
[5,5], [0.3,0.3]
[15,18], [0.1, 0.3]
[20,5], [0.2,-0.2]

Example output

For the first example input ([10,0], [0,0]), these are all valid outputs:

[Accelerate, 1], [Drift, 8.5]
[Accelerate, 2.7], [Rotate, 180], [Accelerate, 2.7]
[Accelerate, 2], [Rotate, [-1,0]], [Drift, 2], [Accelerate, 2]

For the second example input ([6,-3], [0,0.5]), this is a valid output:

[Accelerate, 2.23], [Rotate, 180], [Accelerate, 2.23], [Rotate, -90],
[Accelerate, 11.5], [Drift, 5.5]
// The first 3 actions put me directly behind the moving ship (actually
// at [5.9729, 0]) in 5.96s (the other ship is now at [6,5.8804] and
// moving [0, 2.98]), the remainder catch up to it.
// Total time for this route: 22.96s

Answer 1

MATLAB

Try it online

function tf=Intercept(p,a)
X=@(t,a,v,x).5*a*t.^2+v.*t+x;
t=0;
while 1
    
    a1=(0:0.01:1)';
    a2=1-a1;
    theta2=-360:360;
    
    x1=X(t,a(1),0,p(1));
    y1=X(t,a(2),0,p(2));
    theta1=atan(y1/x1)*180/pi;
    T=(t-abs(theta1)/180-abs(theta2-theta1)./180);
    T(T<0)=0;
    x2=0.5*a1.^2*cosd(theta1).*T.^2+0.5*a2.^2*cosd(theta2).*T.^2+a1.*a2*cosd(theta1).*T.^2+a1.*cosd(theta1)*T.*abs(theta2-theta1)/180;
    y2=0.5*a1.^2*sind(theta1).*T.^2+0.5*a2.^2*sind(theta2).*T.^2+a1.*a2*sind(theta1).*T.^2+a1.*sind(theta1)*T.*abs(theta2-theta1)/180;
    x=x1-x2;
    y=y1-y2;
    vx=a(1)*t-(a1*cosd(theta1)*T+a2*cosd(theta2).*T);
    vy=a(2)*t-(a1*sind(theta1)*T+a2*sind(theta2).*T);
    V=sqrt(vx.^2+vy.^2);
    D=sqrt(x.^2+y.^2);
    
    [ida1,idtheta2]=find(D<1&V<1,1);
    
    if ~isempty(idtheta2)
        a1=a1(ida1);
        theta2=theta2(idtheta2);
        break
    end
    
    t=t+0.01;
    
end
if length(theta2) > 1
    return
end
tf=t;
t1=abs(theta1/180);
t3=abs(theta2-theta1)/180;
t3=t3-0*(t3>1);
t2=a1.*(tf-t1-t3);
t4=tf-t3-t2-t1;
x1=a(1)/2*tf^2+p(1);
y1=a(2)/2*tf^2+p(2);
v1=a*tf;
x2=cosd(theta1)/2.*t2.^2+cosd(theta1).*t2.*(t3+t4)+cosd(theta2)./2.*t4.^2;
y2=sind(theta1)/2.*t2.^2+sind(theta1).*t2.*(t3+t4)+sind(theta2)./2.*t4.^2;
v2=[cosd(theta1)*t2+cosd(theta2)*t4;sind(theta1)*t2+sind(theta2)*t4];
V=vecnorm(v1'-v2);
P=vecnorm([x1;y1]-[x2;y2]);
cmds=[theta1,t1,t2,theta2-theta1,t3,t4,tf];
fprintf('Turn %.2f degrees in %.2f seconds\nAccelerate for %.2f seconds\nTurn %.2f degrees in %.2f seconds\nAccelerate for %.2f seconds\nMission Time: %.2f seconds\n\n',cmds); 
fprintf('x1=%.2f, x2=%.2f\ny1=%.2f, y2=%.2f\nv1=[%.2f %.2f], v2=[%.2f %.2f]\nV=%.2f\nD=%.2f\n',x1,x2,y1,y2,v1,v2,V,P);

Explanation:

My methodology is to start by assuming the total mission length \$t\$ starting from 0 (in the case where we already fit the parameters at \$t\$=0) and apply a standard mission profile. The mission has 4 stages:

1. turn towards where the target will be at time \$t\$
2. accelerate towards the target
3. turn to an angle that will cancel velocities so that we are within parameters by time \$t\$
4. accelerate for the remaining time

Using this profile, there are 4 time values to be concerned about. \$t_1\$ is the first turn, \$t_2\$ is the first burn, \$t_3\$ is the second turn, and \$t_4\$ is the last burn. \$t_1\$ is known since the initial angle can be easily calculated. \$t_2\$ and \$t_4\$ are calculated as percentages \$a_1\$ and \$a_2\$ of \$(t_2+t_4)\$, in order to reduce them to \$a_1(t_2+t_4)\$ and \$(1-a_1)(t_2+t_4)\$, thus making both values a function of \$a_1\$. \$t_3\$ is a function of the second turn angle \$\theta_2\$. The next thing is to calculate the x and y positions and velocities at time \$t\$ as a function of \$a_1\$ and the second angle \$\theta_2\$, the only other unknown. I know that these are limited to a specific range of 0:1 and -360:360 respectively, so I calculate all possible positions as a function of \$a_1\$ and \$\theta_2\$ and find the first one that fits the criteria. If none fit, then \$t\$ is increased by 0.01 and the process is repeated. This method takes advantage of the vectorized computing capabilities of MATLAB. And honestly, it's probably the first code golf challenge where MATLAB is more ideal.

I also have some test code that has all of the test cases already, and times it as well according to your scoring criteria. Since the output of the program is the total mission time, and tic/toc calculates time since tic was called at time toc, this calculates the score as well.

% % Test Intercept*

*edited so that toc comes after the function call, so that time is calculated after the function finishes and not before. Oversight on my part.

tic
(Intercept([10,0], [0,0])*toc)^2;

tic
(Intercept([6,-3], [0,0.5])*toc)^2

tic
(Intercept([-2,8], [0.1,-0.2])*toc)^2

tic
(Intercept([5,5], [0.3,0.3])*toc)^2

tic
(Intercept([15,18], [0.1, 0.3])*toc)^2

tic
(Intercept([20,5], [0.2,-0.2])*toc)^2