宇宙飞船的二维轨迹规划与物理 [英] 2d trajectory planning of a spaceship with physics

问题描述

我正在用太空中的飞船实现一个 2D 游戏.

I'm implementing a 2D game with ships in space.

为了做到这一点，我使用了 LÖVE，它用 Lua 包装了 Box2D.但我相信我的问题可以由比我更了解物理学的任何人回答 - 因此伪代码被接受作为回应.

In order to do it, I'm using LÖVE, which wraps Box2D with Lua. But I believe that my question can be answered by anyone with a greater understanding of physics than myself - so pseudo code is accepted as a response.

我的问题是我不知道如何在支持 2D 物理的世界中正确移动我的飞船.更具体地说:

My problem is that I don't know how to move my spaceships properly on a 2D physics-enabled world. More concretely:

质量为m的船位于初始位置{x, y}.它的初始速度向量为 {vx, vy}(可以是 {0,0}).

A ship of mass m is located at an initial position {x, y}. It has an initial velocity vector of {vx, vy} (can be {0,0}).

目标是{xo,yo}中的一个点.飞船必须以 {vxo,vyo}(或接近它)的速度沿着最短轨迹到达目标.

The objective is a point in {xo,yo}. The ship has to reach the objective having a velocity of {vxo, vyo} (or near it), following the shortest trajectory.

有一个名为 update(dt) 的函数被频繁调用(即每秒 30 次).在此功能上，船舶可以通过对自身施加脉冲"来修改其位置和轨迹.脉冲的大小是二元的:您可以在给定的方向上应用它，也可以根本不应用它).在代码中，它看起来像这样:

There's a function called update(dt) that is called frequently (i.e. 30 times per second). On this function, the ship can modify its position and trajectory, by applying "impulses" to itself. The magnitude of the impulses is binary: you can either apply it in a given direction, or not to apply it at all). In code, it looks like this:

function Ship:update(dt)
  m = self:getMass()
  x,y = self:getPosition()
  vx,vy = self:getLinearVelocity()
  xo,yo = self:getTargetPosition()
  vxo,vyo = self:getTargetVelocity()
  thrust = self:getThrust()

  if(???)
    angle = ???
    self:applyImpulse(math.sin(angle)*thrust, math.cos(angle)*thrust))
  end
end

第一个 ??? 是为了表明在某些情况下(我猜)最好不要冲动"并让船漂移".第二个 ??? 部分包括如何计算给定 dt 上的脉冲角.

The first ??? is there to indicate that in some occasions (I guess) it would be better to "not to impulse" and leave the ship "drift". The second ??? part consists on how to calculate the impulse angle on a given dt.

我们在太空中，所以我们可以忽略空气摩擦等因素.

We are in space, so we can ignore things like air friction.

虽然这会很好，但我不是在找人为我编写代码；我把代码放在那里，所以我的问题很清楚.

Although it would be very nice, I'm not looking for someone to code this for me; I put the code there so my problem is clearly understood.

我需要的是一种策略 - 一种攻击方式.我知道一些基本的物理，但我不是专家.例如，这个问题有名字吗?那种东西.

What I need is an strategy - a way of attacking this. I know some basic physics, but I'm no expert. For example, does this problem have a name? That sort of thing.

非常感谢.

Beta 为此提供了一个有效的策略，法官在评论中直接在 LÖVE 中实施了它.

Beta provided a valid strategy for this and Judge kindly implemented it directly in LÖVE, in the comments.

经过更多的谷歌搜索，我还找到了 openSteer.它在 C++ 上，但它做我假装的.这可能对提出这个问题的任何人都有帮助.

After more googling I also found openSteer. It's on C++, but it does what I pretended. It will probably be helpful to anyone reaching this question.

推荐答案

这就是所谓的运动规划，它不是微不足道的.

It's called motion planning, and it's not trivial.

这是获得非最佳轨迹的简单方法:

Here's a simple way to get a non-optimal trajectory:

1. 停下.施加与速度方向相反的推力，直到速度为零.
2. 计算最后一条腿，这将与第一条腿相反，从站立开始的稳定推力使船到达 x0 和 v0.起点与 x0 的距离为 |v0|^2/(2*thrust).
3. 到达起点(然后进行最后一站).从一个站立点到另一个站立点很容易:向它猛推直到你走到一半，然后向后猛推直到你停下来.

1. Stop. Apply thrust opposite to the direction of velocity until velocity is zero.
2. Calculate the last leg, which will be the opposite of the first, a steady thrust from a standing start that gets the ship to x0 and v0. The starting point will be at a distance of |v0|^2/(2*thrust) from x0.
3. Get to that starting point (and then make the last leg). Getting from one standing point to another is easy: thrust toward it until you're halfway there, then thrust backward until you stop.

如果您想要快速而肮脏的方法来获得最佳轨迹，您可以使用迭代方法:从上面的非最佳方法开始；这只是推力角的时间序列.现在尝试对该序列做一些小的变化，保持一组接近目标的序列.拒绝最糟糕的，尝试最好的——如果你觉得大胆，你可以把它变成一个遗传算法——幸运的是，它会开始拐弯抹角.

If you want a quick and dirty approach to an optimal trajectory, you could use an iterative approach: Start with the non-optimal approach, above; that's just a time sequence of thrust angles. Now try doing little variations of that sequence, keeping a population of sequences that get close to the goal. reject the worst, experiment with the best -- if you're feeling bold you could make this a genetic algorithm -- and with luck it will start to round the corners.

如果您想要确切的答案，请使用变分法.我会尝试一下，如果我成功了，我会在这里发布答案.

If you want the exact answer, use the calculus of variations. I'll take a crack at that, and if I succeed I'll post the answer here.

这是一个更简单问题的确切解决方案.

Here's the exact solution to a simpler problem.

假设我们有四个固定的推进器，而不是我们可以指向任何方向的推力，而是指向 {+X, +Y, -X, -Y} 方向.在任何给定时间，我们最多会触发 +/-X 之一和最多 +/-Y 之一(同时触发 +x 和 -X 没有意义).所以现在 X 和 Y 问题是独立的(它们不在原始问题中，因为推力必须在 X 和 Y 之间共享).我们现在必须解决一维问题——并应用它两次.

Suppose instead of a thrust that we can point in any direction, we have four fixed thrusters pointing in the {+X, +Y, -X, -Y} directions. At any given time we will firing at most one of the +/-X and at most one of the +/-Y (there's no point in firing +x and -X at the same time). So now the X and Y problems are independent (they aren't in the original problem because thrust must be shared between X and Y). We must now solve the 1-D problem -- and apply it twice.

事实证明，最好的轨迹是先向一个方向推进，然后再向另一个方向推进，并且不再回到第一个方向.(仅当另一个轴的解决方案花费的时间比您的解决方案长，因此您有时间解决问题时，惯性运动才有用.)首先解决速度问题:假设(WLOG)您的目标速度大于您的初始速度.要达到目标速度，您需要一段时间的推力 (+) 持续时间

It turns out the best trajectory involves thrusting in one direction, then the other, and not going back to the first one again. (Coasting is useful only if the other axis's solution will take longer than yours so you have time to kill.) Solve the velocity problem first: suppose (WLOG) that your target velocity is greater than your initial velocity. To reach the target velocity you will need a period of thrust (+) of duration

T = (Vf - Vi)/a

(我使用的是 Vf:最终速度，Vi:初始速度，a:推力大小.)

(I'm using Vf: final velocity, Vi: initial velocity, a: magnitude of thrust.)

我们注意到，如果我们只做这些，位置就不会正确.实际最终位置将是

We notice that if that's all we do, the location won't come out right. The actual final location will be

X = (Vi + Vf)T/2

所以我们必须添加一个更正

So we have to add a correction of

D = Xf - X = Xf -(Vi+Vf)T/2

现在为了使位置正确，我们在一个方向之前添加一个推力周期，在相反方向之后添加一个相等的周期.这将使最终速度不受干扰，但会给我们一些位移.如果第一个(和第三个)周期的持续时间是 t，那么我们从中得到的位移是

Now to make the location come out right, we add a period of thrust in one direction before that, and an equal period in the opposite direction after. This will leave the final velocity undisturbed, but give us some displacement. If the duration of this first period (and the third) is t, then the displacement we get from it is

d = +/-(at^2 + atT)

+/- 取决于我们是先按 + 然后 - 还是 - 然后 +.假设它是+.我们求解二次方程:

The +/- depends on whether we thrust + then -, or - then +. Suppose it's +. We solve the quadratic:

t = (-aT + sqrt(a^2 T^2 + 4 a D))/2a

我们已经完成了.

这篇关于宇宙飞船的二维轨迹规划与物理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！