algorithm - 人工智能 : selecting immediate acceleration/rotation to get to a final point

Question

我正在开发一款游戏，在游戏循环的每次更新中，AI 都会运行。在此更新期间，我有机会转动 AI 控制的实体和/或使其朝它所面对的方向加速。我希望它到达最终位置(在合理范围内)并且在该位置具有特定的速度和方向(同样不需要精确)也就是说，给定电流:

• P₀(x, y) = 当前位置向量
• V₀(x, y) = 当前速度矢量(单位/秒)
• θ₀ = 当前方向(弧度)
• τ_max = 最大转弯速度(弧度/秒)
• α_max = 最大加速度(单位/秒^2)
• |V|_max = 绝对最大速度(单位/秒)
• P_f(x, y) = 目标位置向量
• V_f(x, y) = 目标速度矢量(单位/秒)
• θ_f = 目标旋转(弧度)

选择一个立即:

• τ = [-τ_max, τ_max] 范围内的转弯速度
• α = [0, α_max] 内的加速度标量(必须在它当前面对的方向上加速)

使这些最小化:

• t = 移动到目的地的总时间
• |P_t-P_f| = 结束时与目标位置的距离
• |V_t-V_f| = 结束时与目标速度的偏差
• |θ_t-θ_f| = 结束时与目标旋转的偏差(包裹到 (-π,π))<

可以在游戏循环的每次迭代中重新计算参数。一张图片说 1000 个单词，所以例如给定蓝色家伙的当前状态，在尽可能短的时间内达到大约红色家伙的状态(箭头是速度):

Pic http://public.blu.livefilestore.com/y1p6zWlGWeATDQCM80G6gaDaX43BUik0DbFukbwE9I4rMk8axYpKwVS5-43rbwG9aZQmttJXd68NDAtYpYL6ugQXg/words.gif

假设 Δt 的 α 和 τ 为常数(对于理想解，Δt → 0)并将位置/速度拆分为多个分量，这给出(我认为，我的数学可能不对):

Equations http://public.blu.livefilestore.com/y1p6zWlGWeATDTF9DZsTdHiio4dAKGrvSzg904W9cOeaeLpAE3MJzGZFokcZ-ZY21d0RGQ7VTxHIS88uC8-iDAV7g/equations.gif

_{(编辑:最后一个应该是 θ = θ0 + τΔt)}

那么，我如何选择直接的 α 和 τ(请记住，游戏循环的每次迭代都会重新计算这些值，通常 > 100 fps)？我能想到的最简单、最幼稚的方法是:

1. 选择一个 Δt 等于游戏循环更新之间最后几个 Δts 的平均值(即非常小)
2. 针对 (α, τ) = {0, α_max} x {-τ_max, 0, 的所有组合计算下一步的上述 5 个方程式τ_max}(每个只有 6 个组合和 5 个方程，所以不应该花太长时间，而且由于它们经常运行，所以相当有限的范围将在最后摊销)
3. 为位置、速度和旋转分配权重。也许这些权重可以是动态的(即实体离位置越远，位置权重越大)。
4. 从现在开始贪婪地选择最小化位置 Δt 的那些。

它可能快速且简单，但是，这有一些明显的问题:

• 任意选择权重
• 这是一种贪心算法，(就其本质而言)不能回溯
• 它并没有真正考虑到问题空间
• 如果它频繁改变加速度或转弯，动画可能看起来“不稳定”。

请注意，虽然算法可以(并且可能应该)在迭代之间保存状态，但是 P_f、V_f 和 θ_f 可以改变每次迭代(即如果实体试图跟随/将自己定位在另一个附近)，因此算法需要能够适应不断变化的条件。

有什么想法吗？我缺少一个简单的解决方案吗？

谢谢，罗伯特

Answer 1

听起来你想要一个 PD Controller 。基本上从当前位置到目标画一条线。然后以弧度为单位取线方向，这就是你的目标弧度。当前弧度误差是当前标题 - 行标题。就叫诶(航向错误)然后你说当前转弯率将是 KpEh+d/dt EhKd。每一步都换行。

那是标题

加速度是“加速直到我达到最大速度，否则我将无法及时停止”。你扔了一堆积分，所以我相信你会没问题的。

如果您想知道，是的，我之前已经解决了这个问题，PD Controller 可以工作。不要理会 PID，在这种情况下不需要它。 matlab中的原型(prototype)。我遗漏了一件事，你需要有一个触发器，比如“我现在真的很接近了”所以我应该开始转向进入目标。我刚刚阅读了您关于“仅在我们前进的方向上加速”的说明。这改变了一些但不会太多。这意味着需要“从后面”接近目标，这意味着线目标必须在真实目标的后面，当你接近后面的目标时，沿着一条新线引导你到达真实目标。您还需要遵循这些行，而不是仅仅选择一个标题并尝试坚持下去。所以不要每帧都更新线，只要说误差等于与当前目标线的有符号距离。 PD 会给你一个转弯率，加速度是微不足道的，所以你已经准备好了。您需要手动调整 Kd 和 Kp，这就是我首先说 matlab 的原因。 ( Octave 也不错)

祝你好运，希望这能为你指明正确的方向 ;)

双关语。

编辑:我刚读到...很多东西，写得很快。这是针对您的问题的解决方案，如果您想将此解决方案作为解决问题的基础，只需谷歌跟踪此答案即可。