AI：选择立即加速/旋转以到达终点
我正在开发一款游戏，每次游戏循环更新时，人工智能都会运行。在此更新期间，我有机会转动 AI 控制的实体和/或使其加速朝其面向的方向。我希望它到达最终位置（在合理范围内），并且在该位置具有特定的速度和方向（同样不需要精确）也就是说，给定电流：
- P0< /sub>(x, y) = 当前位置向量
- V0(x, y) = 当前速度向量（单位/秒）
- θ 0 = 当前方向（弧度）
- τmax = 最大转弯速度（弧度/秒）
- α max = 最大加速度（单位/秒^2）
- |V|max = 绝对最大速度（单位/秒）
- P f(x, y) = 目标位置矢量
- Vf(x, y) = 目标速度矢量（单位/秒） )
- θf = 目标旋转（弧度）
选择立即：
- τ = [-τ 内的旋转速度max, τmax]
- α = [0, αmax] 内的加速度标量（必须沿方向加速）它当前面临的）
这样可以最小化：
- t = 移动到目的地的总时间
- |Pt-Pf| = 末端距目标位置的距离
- 末端距目标速度的偏差
- |Vt-Vf| = | θt-θf| = 结束时与目标旋转的偏差（包装为 (-π,π)）
参数可以在每个过程中重新计算游戏循环的迭代。一张图片包含 1000 个单词，因此例如给定蓝色家伙的当前状态，在尽可能短的时间内大约达到红色家伙的状态（箭头是速度):
假设 Δt 为常数 α 和 τ（对于理想解决方案，Δt → 0）并将位置/速度分成多个分量，这给出了（我认为，我的数学可能是关闭）：
（编辑：最后一个应该是 θ = θ0 + τΔt）
那么，我该如何选择立即α 和 τ （请记住，这些将在游戏循环的每次迭代中重新计算，通常 > 100 帧/秒）？我能想到的最简单、最幼稚的方法是：
- 选择一个等于游戏循环更新之间最后几个Δt的平均值的Δt（即非常小）
- 计算下一步的上述5个方程的所有组合（α , τ) = {0, αmax} x {-τmax, 0, τmax} （只有 6 个组合和 5 个方程每个，所以不应该花太长时间，而且由于它们运行得如此频繁，相当有限的范围最终将被摊销）
- 为位置、速度和旋转分配权重。也许这些权重可以是动态的（即实体距离位置越远，位置权重越大）。
- 从现在起，贪婪地选择一个能够最小化位置 Δt 的这些值的选项。
它的速度可能很快，而且速度很快。简单，但是，存在一些明显的问题：
- 任意选择权重
- 这是一种贪婪算法（本质上）无法回溯
- 它并没有真正考虑问题空间
- 如果它频繁改变加速度或转弯，动画可能看起来“生涩”。
请注意，虽然算法可以（并且可能应该）在迭代之间保存状态，但 Pf、Vf 和 θf 可以更改每次迭代（即，如果实体试图跟随/将自己定位在另一个实体附近），因此算法需要能够适应不断变化的条件。
有什么想法吗？我缺少一个简单的解决方案吗？
谢谢， 罗伯特
I'm working on a game where on each update of the game loop, the AI is run. During this update, I have the chance to turn the AI-controlled entity and/or make it accelerate in the direction it is facing. I want it to reach a final location (within reasonable range) and at that location have a specific velocity and direction (again it doesn't need to be exact) That is, given a current:
- P0(x, y) = Current position vector
- V0(x, y) = Current velocity vector (units/second)
- θ0 = Current direction (radians)
- τmax = Max turn speed (radians/second)
- αmax = Max acceleration (units/second^2)
- |V|max = Absolute max speed (units/second)
- Pf(x, y) = Target position vector
- Vf(x, y) = Target velocity vector (units/second)
- θf = Target rotation (radians)
Select an immediate:
- τ = A turn speed within [-τmax, τmax]
- α = An acceleration scalar within [0, αmax] (must accelerate in direction it's currently facing)
Such that these are minimized:
- t = Total time to move to the destination
- |Pt-Pf| = Distance from target position at end
- |Vt-Vf| = Deviation from target velocity at end
- |θt-θf| = Deviation from target rotation at end (wrapped to (-π,π))
The parameters can be re-computed during each iteration of the game loop. A picture says 1000 words so for example given the current state as the blue dude, reach approximately the state of the red dude within as short a time as possible (arrows are velocity):
Assuming a constant α and τ for Δt (Δt → 0 for an ideal solution) and splitting position/velocity into components, this gives (I think, my math is probably off):
(EDIT: that last one should be θ = θ0 + τΔt)
So, how do I select an immediate α and τ (remember these will be recomputed every iteration of the game loop, usually > 100 fps)? The simplest, most naieve way I can think of is:
- Select a Δt equal to the average of the last few Δts between updates of the game loop (i.e. very small)
- Compute the above 5 equations of the next step for all combinations of (α, τ) = {0, αmax} x {-τmax, 0, τmax} (only 6 combonations and 5 equations for each, so shouldn't take too long, and since they are run so often, the rather restrictive ranges will be amortized in the end)
- Assign weights to position, velocity and rotation. Perhaps these weights could be dynamic (i.e. the further from position the entity is, the more position is weighted).
- Greedily choose the one that minimizes these for the location Δt from now.
Its potentially fast & simple, however, there are a few glaring problems with this:
- Arbitrary selection of weights
- It's a greedy algorithm that (by its very nature) can't backtrack
- It doesn't really take into account the problem space
- If it frequently changes acceleration or turns, the animation could look "jerky".
Note that while the algorithm can (and probably should) save state between iterations, but Pf, Vf and θf can change every iteration (i.e. if the entity is trying to follow/position itself near another), so the algorithm needs to be able to adapt to changing conditions.
Any ideas? Is there a simple solution for this I'm missing?
Thanks,
Robert
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
听起来你想要一个 PD 控制器。基本上从当前位置到目标绘制一条线。然后以弧度为单位获取直线方向，这就是您的目标弧度。当前的弧度误差是当前航向 - 行航向。就称呼它为呃吧。 （航向错误）那么你说当前的转弯速率将为 KpEh+d/dt EhKd。每一步都用新行执行此操作。
航向加速度的意思
是“加速直到达到最大速度，否则我将无法及时停止”。你提出了一堆积分，所以我相信你会很好地进行计算。
如果您想知道，是的，我以前已经解决过这个问题，PD 控制器可以工作。不要理会 PID，在这种情况下不需要它。 matlab 中的原型。我遗漏了一件事，你需要有一个触发器，比如“我现在已经非常接近了”，所以我应该开始转向进入目标。我刚刚读到您关于“仅朝着我们前进的方向加速”的澄清。这会改变一些事情，但不会太大。这意味着需要“从后面”接近目标，这意味着线目标必须位于真实目标的后面，当您接近后面的目标时，请遵循一条新线，它将引导您到达真正的目标。您还需要遵循规则，而不是仅仅选择一个标题并尝试坚持下去。因此，不要每帧更新该线，只需说误差等于距当前目标线的签名距离即可。 PD 会给你一个转弯速率，加速度是微不足道的，所以你已经设置好了。你需要手动调整 Kd 和 Kp，这就是为什么我首先说 matlab。 （八度也很好）
祝你好运，希望这能为你指明正确的方向；）
双关语。
编辑：我刚刚读到……很多东西，写得很快。这是针对您的问题的行跟踪解决方案，如果您想将此解决方案作为解决问题的基础，只需谷歌行跟踪来配合此答案。
sounds like you want a PD controller. Basically draw a line from the current position to the target. Then take the line direction in radians, that's your target radians. The current error in radians is current heading - line heading. Call it Eh. (heading error) then you say the current turn rate is going to be KpEh+d/dt EhKd. do this every step with a new line.
thats for heading
acceleration is "Accelerate until I've reached max speed or I wont be able to stop in time". you threw up a bunch of integrals so I'm sure you'll be fine with that calculation.
I case you're wondering, yes I've solved this problem before, PD controller works. don't bother with PID, don't need it in this case. Prototype in matlab. There is one thing I've left out, you need to have a trigger, like "i'm getting really close now" so I should start turning to get into the target. I just read your clarification about "only accelerating in the direction we're heading". that changes things a bit but not too much. that means to need to approach the target "from behind" meaning that the line target will have to be behind the real target, when you get near the behind target, follow a new line that will guide you to the real target. You'll also want to follow the lines, rather than just pick a heading and try to stick with it. So don't update the line each frame, just say the error is equal to the SIGNED DISTANCE FROM THE CURRENT TARGET LINE. The PD will give you a turn rate, acceleration is trivial, so you're set. you'll need to tweak Kd and Kp by head, that's why i said matlab first. (Octave is good too)
good luck, hope this points you in the right direction ;)
pun intended.
EDIT: I just read that...lots of stuff, wrote real quick. this is a line following solution to your problem, just google line following to accompany this answer if you want to take this solution as a basis to solving the problem.
我想建议您考虑 http://en.wikipedia.org/ wiki/Bang%E2%80%93bang_control（Bang-bang 控制）以及 PID 或 PD。您试图最小化的事情似乎不会对将油门推到底产生任何惩罚，直到需要将制动器推到底为止，除了您关于如何急躁的观点这会看起来。至少，这为您最初的猜测提供了某种理由。
I would like to suggest that yout consider http://en.wikipedia.org/wiki/Bang%E2%80%93bang_control (Bang-bang control) as well as a PID or PD. The things you are trying to minimise don't seem to produce any penalty for pushing the accelerator down as far as it will go, until it comes time to push the brake down as far as it will go, except for your point about how jerky this will look. At the very least, this provides some sort of justification for your initial guess.