动态障碍物寻路
我正在实现一个模拟，需要我进行一些寻路。
当我的环境没有改变时，A* 对我来说效果很好。
当我遇到原始地图中不存在的静态障碍物时，LPA* 和 D* Lite 对我来说效果很好。
但是，当这些障碍物以一定速度移动时，我该如何处理？
LPA* 或 D* Lite 算法是否有变体可以处理此问题？
或者我是否必须将某种形式的转向行为与这些算法结合起来？
最终，在我的模拟中，我想让我的“代理”在有移动障碍的环境中从起点移动到终点。
I am implementing a simulation that requires me to have some pathfinding.
A* works fine for me when my environment does not change.
LPA* and D* Lite work fine for me when I encounter a static obstacle that is not in my original map.
However, how do I handle the situation when these obstacles are moving at a certain velocity?
Is there a variant of the LPA* or D* Lite algorithm that handles this?
OR Do i have to combine some form of steering behaviour with these algorithms?
Utimately in my simulation I want to have my 'agent' move from a start point to an end point in an environment in which there will be obstacles that move.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可能最好考虑将问题分成两部分，而不是尝试使用单一算法来解决它。
角色移动有两个组成部分：高级目标选择和寻路，以及局部转向。寻路解决了“我在这里，我需要知道如何到达那里”的问题。本地转向解决了“我正在去那里的路上，有人挡住了我的路”的问题。
保持现在的寻路方式。您需要添加的是角色沿着该路径移动时检测障碍物的能力，然后调整路径的局部部分以避免障碍物。
《游戏人工智能》一书（作者网站：http://ai4g.com/ 和亚马逊：http://amzn.to/k9K62F）详细介绍了将寻路与避免碰撞相结合的几种方法。这个论文还相当高水平地涵盖了转向算法。我实施的一项非常有效的技术是引导管道，也称为合作仲裁。
任何完整的答案都将取决于您的世界代表性以及实施过程中特定的其他因素，但我希望这会有所帮助。
You might be better to consider breaking the problem into two parts than trying to solve it using a single algorithm.
Character movement has two components: high-level goal selection and pathfinding, and local steering. Pathfinding solves the problem of "I'm here, and I need to know how to get there". Local steering solves the problem of "I'm on my way there and someone just got in my way".
Keep your pathfinding as it is now. What you need to add is the ability for characters to detect obstacles as they are moving along that path and then adjust that local portion of the path to avoid the obstacle.
The book Artificial Intelligence for Games (author site: http://ai4g.com/ and Amazon: http://amzn.to/k9K62F) details several ways to combine pathfinding with collision avoidance. This paper also covers steering algorithms fairly well at a high level. A highly effective technique I've implemented is a steering pipeline, also known as cooperative arbitration.
Any complete answer will depend on your world representation and other factors specific to your implementation, but I hope this helps.
这篇文章有关于动态 A* 的好主意，这可能对
随时动态 A*：随时重新规划算法
马克西姆·利哈切夫、戴夫·弗格森† 杰夫·戈登†、安东尼·斯坦茨† 和塞巴斯蒂安·特龙
还有这篇文章，带有移动障碍物的随机动力学运动规划 通过
David Hsu Robert、Kindel Jean-Claude Latombe、Stephen Rock
他们应该是一个好的开始。
This article has great ideas about dynamic A*, which could be usuful to you
Anytime Dynamic A*: An Anytime, Replanning Algorithm
Maxim Likhachev, Dave Ferguson† Geoff Gordon†, Anthony Stentz†, and Sebastian Thrun
Also this article, Randomized Kinodynamic Motion Planning with Moving Obstacles by
David Hsu Robert, Kindel Jean-Claude Latombe, Stephen Rock
They should be a good start.
您可以看到动态场景，例如定期更新的静态场景，并且您必须在场景的每个步骤/修改中重新计算寻路
。定期使用移动物体的新位置更新地图，并在每一步重新计算寻路
对于移动障碍物/物体，请在更新的地图上的移动障碍物/物体周围添加例如一到两个“像素”的边距，以便轻松处理事实上，它们可以在迈步期间移动到“随机但非常接近”的位置。
更好的是，在开始时标记最大移动障碍物的轨迹，并且仅更新实时特殊轨迹，例如门、楼梯或移动物体例如
You can see a dynamic scene such a static scene that is regularly updated and where you have to recompute the pathfinding at each step/modification of the scene
Cf. regularly update the map with new positions of yours moving objets and recompute the pathfinding at each step
For moving obstacles/objects, add for exemple a marging of one or two "pixels" around moving obstacles/objects on your updated map for to easily handle the fact that they can move to a "random but very near" position during the time of the step
Better, mark the trajectories of the maximum of moving obstacles at the begining and only update on real time specials trajectories such as doors, stairs or moving objects for exemples