0
$\begingroup$

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.

Sketch of problem

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.

$\endgroup$
4
  • 1
    $\begingroup$ I think the issue relates to how fast the ship should return (rotation speed of vector), and if you can rotate + move translationally at same time or if you can rotate at a time and move at a time individually only. If you can only do either rotate or translate, then first rotate to right direction then translate. $\endgroup$ Jan 8, 2022 at 3:50
  • $\begingroup$ The ship is able to apply a constant acceleration in any direction at a given timestep. To get an optimal solution, it really seems like some sort of equation needs to be evaluated at each timestep since the applied acceleration direction is able to change at each timestep. I can't quite wrap my head around where to begin to figure out what the equation would be, though! $\endgroup$ Jan 8, 2022 at 3:55
  • $\begingroup$ There's the equation r=aT², r is the common ratio of a arithmetic sequence (a: constant acceleration, T: timestep). $\endgroup$
    – The Tiler
    Jan 8, 2022 at 9:04
  • $\begingroup$ Is the acceleration magnitude fixed, or limited? Also, constant acceleration at every time step means variable acceleration over time. Also is the direction of acceleration relative to the ship orientation, or fixed in space? $\endgroup$ Jan 10, 2022 at 15:55

1 Answer 1

0
$\begingroup$

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:

fig1

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.

fig2

$\endgroup$
3
  • $\begingroup$ Hey John, thanks for the detailed response! To answer you questions from the comment, the acceleration is limited, not fixed. I am not tracking ship orientation at all, so the direction of the acceleration is fixed in space. You can think of the ship more just like a particle that's moving through 2d space with some position, velocity, and acceleration. Edit: With that in mind, I'm trying to think of how to rewrite your equations without a ship orientation in mind. I suppose the turn angle would just be the angle between the starting velocity vector and the exit velocity vector? $\endgroup$ Jan 10, 2022 at 19:24
  • $\begingroup$ The ship orientation is always defined as the direction of the velocity vector. In my diagram that is the blue arrow. Crucial to the above is that acceleration parallel to the motion vector exists for phases AB and DE and acceleration perpendicular to the motion for phase BD. $\endgroup$ Jan 11, 2022 at 1:54
  • $\begingroup$ Thanks! I'll give this method a go. I'll mark this as the answer as it's definitely the most comprehensive response I've gotten and looks to mostly be what I'm looking for. $\endgroup$ Jan 11, 2022 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.