logo标签列表

AI在2D地图上避开障碍物的导航

c#algorithmartificial-intelligencepath-finding
9
我知道我的问题似乎相当模糊，但我想不出更好的表达方式，所以我将从解释我正在尝试做什么开始。
我目前正在开发一个项目，我已经得到了一张地图，并编写了一个“Critter”，它应该能够在地图上导航。这个“Critter”有各种其他功能，但这些与当前的问题无关。整个程序和解决方案都是用C#编写的。
我可以控制“Critter”的速度，并通过返回其当前的X和Y位置来获取它在地图上的当前位置，在它与阻挡它的地形碰撞时也可以设置它的方向。
我唯一的问题是，我想不出一个智能地在地图上导航的方法；到目前为止，我一直根据“Critter”面对的方向来移动，这绝不是一个好的移动地图的方法！
我不是游戏程序员，这是一个软件任务，所以我对AI技术一无所知。
这里是一个链接，展示了地图和“Critter”的外观：

地图和生物图像

我并不希望任何人给我一个完整的解决方案，只是在地图导航的一般方向上给我一些指引。

你说过当它与阻挡它的地形碰撞时，可以“设置它的方向”。那么，它只能在碰撞时设置方向吗？还是说在它在地图上导航时可以随意改变方向？ - dmcer
我可以随意改变方向！ - Curt Walker
地图是否完全提前知道？还是必须通过探索地形与你的小动物发现障碍和奖励？ - dmcer
4个回答
6
如果你只知道环境中你的小动物的位置和速度，我认为最好的方法是沿着墙壁走。如果你能检测到环境中的其他事物，那么你就有更多的选择。
一些更流行的算法类型包括...
- A*搜索（经典算法） - 可见性图 - 沃罗诺伊图（类似于上面） - 势场 势场是一种花哨的说法，意思是每个障碍物或墙都有一个“排斥力”，而每个目标都有一个“吸引力”。力的强度基于物体与目标之间的距离和物体的“严重程度”。 （穿越熔岩坑比穿过崎岖不平的路要困难得多）。构建力场后，朴素的算法就是沿着最小阻力路径前进。更好的版本可以检测局部极小值和极大值，并逃脱这些陷阱。
    Critter
    -----\    /-------\
          \  /         \ 
           \/           \
   Local Minima Trap     \
                          \
                           \
                             Goal
3

A*搜索

看一下A*寻路算法。这基本上是处理此类问题的标准方法。

Amit Patel在游戏路径规划方面的写作，对A*以及算法的流行变体有一个相当好的介绍。

您可以在这里找到C#实现：这里和这里

动态A*

假设您要搜索的地形事先不知道，而是随着代理探索其环境而发现的。如果代理遇到以前未知的障碍物，您可以更新代理的地形图，然后重新运行A*，以找到绕过障碍物的目标的新路径。

虽然是可行的解决方案，但每次发现新障碍物时从头开始重新运行计划算法会导致相当多的冗余计算。例如，一旦绕过障碍物，可能最有效的路线到目标是沿着您在发现障碍物之前计划采取的路线。通过重新运行A*，您将需要重新计算先前路径的此部分。

您可以使用动态A*（D*）来避免这种情况。由于它跟踪以前计算过的路径，因此当代理找到新障碍时，系统只需在障碍周围区域内计算新路线。之后，它可以重用现有路径。

这篇论文是关于Focused D算法的，而不是D算法。然而，这两种算法都已被D*-Lite算法所取代。请参阅此处获取更多信息，并了解其他可能适用于OP问题的算法。 - BlueRaja - Danny Pflughoeft
0

我会采用目标导向的方法。你的问题说明了目标是探索地图并避开障碍物，所以这就是我们的目标。但是我们如何探索整个地图呢？我们探索未被探索过的区域。

从一开始，你只有一个未被探索的区域，那就是你所在的方格。地图的其余部分都标记为未被探索。你选择一个未被探索的位置，并将其作为探索的目标。但是你如何到达那里呢？你创建一个子目标来探索它旁边的位置。然后如何做到这一点——探索旁边的方格，以此类推，直到你的原始目标被分解成一系列的探索，从你当前的方格开始导航到目标方格。

当你遇到障碍物并发现地图的特征时，一些子目标可能需要更改。例如，当你撞到墙壁时，探索该方格的子目标必须被取消，你需要创建一个新计划来寻找替代路线。这就是所谓的回溯。

这基本上就是高层次描述。希望能对你有所帮助！

我不会完全这样做 - 你想选择一个附近的目标。我的建议是将目标设定为探索最近的未探索方块。 - Loren Pechtel
0

我好像来晚了。如果你的小动物有GPS和完整的地图，那么正确的做法肯定是A*算法，如果地图足够小，而你又不想编写A*算法（因为A*算法有很多你需要正确处理的特殊情况），那么简单的BFS也可以胜任。

然而，另一个问题是，如果你的小动物只知道目标的方向，并且只能在局部范围内观察周围环境呢？如果你的小动物不知道完整的地图呢？

在这种情况下，你需要实现“虫算法”进行导航。链接：http://www.cs.cmu.edu/~./motionplanning/lecture/Chap2-Bug-Alg_howie.pdf

这是一种适用于所有未知地图的可爱算法，我相信你会喜欢编写它。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接