Calculating 2D acceleration vector direction to most quickly reach a point

Question

I am currently writing a game where you fly a starship in 2D space. In a given timestep, the ship has the ability to accelerate at constant rate in any direction. The player can specify a point at which the ship should move to, and the ship should do its best to move to that point.

The way I'm currently calculating the acceleration vector direction in a given timestep is by subtracting the target position from the ship's current position. This is well and good for travelling from rest to the first point. However, after the ship has already built up a reasonable velocity and I specify a new target (say, at a point perpendicular to the ship's current velocity vector), the ship has trouble navigating there and will often just run in circles around the target point.

So, the question is, given some initial ship velocity vector (Vs) and initial ship point (Ps) in 2D space, how do I calculate the direction of the acceleration vector in order to most quickly reach a target point (Pt)? I have been using Pt - Ps normalized, but that just results in the ship going in circles after it has a good initial velocity.

I can't quite wrap my head around how to do it. It almost seems like you must have to do some calculations over multiple timesteps or something.

Answer 1

This is similar to the path a car will take which can use the tire traction either for accelerating/decelerating or for turning, but not both at the same time. Well, both are possible but with limits.

In this case, the general path looks as follows:

If the magnitude of the acceleration is limited to $a$ then the minimum turn radius when the ship has speed $v$ is $$r = \frac{v^2}{a}$$

Here I have marked the location of the target with $(X,Y)$ based on a coordinate system on the starting location and the x-axis along the direction of travel.

The total transit time is the sum of the three legs

$$ t = \frac {|v_B-v_A|}{a} + \frac{|\varphi| v_B}{a} + \frac{|v_E-v_B|}{a} $$

where $v_A$ is the starting speed, $v_B$ is the turn-in speed and $v_E$ is the exit speed (speed at target).

One of the strategies is to come to a complete stop at a distance $\ell_{\rm AB} = \frac{v_A^2}{2 a}$ and then start accelerating towards the target. In this scenario, the time to turn is zero.

The turn angle for this scenario is

$$ \varphi_{\rm min} = \mathrm{atan}\left( \frac{Y}{X + \frac{v_A^2}{2 a}} \right) $$

The transit time is now

$$ t_{\rm min} = \frac{v_A}{a} + 0 + \sqrt{ \frac{ 2 \sqrt{ Y^2 + \left(X + \frac{v_A^2}{2 a} \right)^2 } }{a}} $$

In general, for a larger turn angle $\varphi > \varphi_{\rm min}$ the key speeds and transit time is

$$\boxed{\begin{aligned} v_{B} & =\sqrt{\frac{a\left(X'\sin\varphi-Y\cos\varphi\right)}{1+\tfrac{1}{2}\sin\varphi-\cos\varphi}}\\ v_{E} & =\sqrt{\frac{a\left(\left(2X'-Y\right)\cos\varphi+\left(X'+2Y\right)\sin\varphi-2X'+Y\right)}{1+\tfrac{1}{2}\sin\varphi-\cos\varphi}}\\ t & =\frac{|v_{A}-v_{B}|}{a}+\frac{|\varphi|v_{B}}{a}+\frac{|v_{E}-v_{B}|}{a} \end{aligned}}$$

where $X' = X + \frac{v_A^2}{2 a}$

There is an upper limit on the turn angle $\varphi$ which makes $\ell_{\rm DE}=0$ and this also results in a short transit time, but it is unknown if it is shorter than the case where the ship stops to turn.

This limit is

$$ \varphi_{\rm max} = 2 \mathrm{atan}\left( \frac{X' +2 Y}{2 X'-Y} \right) - \frac{\pi \left( \mathrm{sign}\left(2 X'-Y \right) \mathrm{sign}\left( X' + 2 Y \right) + \mathrm{sign}\left( 2 X'-Y \right) - 2 \right) }{2}$$ and use the expressions above to get $v_B$, $v_E$ and $t$.

In general, with varying conditions, the optimal strategy is between these two extremes but not on the extremes.

here is what the curves look like for some arbitrary conditions, with arrows indicating the optimal turn angle.