AI左右导航一张2d地图-躲避障碍物

Question

我知道我的问题看起来很模糊，但我想不出更好的方式来表达它，所以我将从解释我想要做的事情开始。

我目前正在做一个项目，在这个项目中，我得到了一张地图，我正在编写一个“critter”，它应该能够在地图上导航；这个生物还有各种其他功能，但这些都与当前的问题无关。整个程序和解决方案都是用C#编写的。

我可以控制生物的速度，并通过返回它当前的X和Y位置来检索它在地图上的当前位置，当它与阻挡它的地形碰撞时，我还可以设置它的方向。

我唯一的问题是，我想不出一种在地图上智能导航的方法；到目前为止，我一直在根据生物与地形碰撞时面对的方向进行导航，而这绝不是在地图上移动的好方法！

我不是游戏程序员，这是一个软件任务，所以我对AI技术一无所知。

这是地图和生物图片的链接：

Map and Critter image

我不是在寻找任何人给我一个完整的解决方案，只是在地图导航的大方向上推动。

Answer 1

如果你对环境的唯一了解是你的生物的位置和它的速度，我认为你能做的最好的就是一个跟随墙的算法。

一些比较流行的算法类型是...

• A* Search (The classic)
• Visibility Graphs
• Voronoi Diagrams (similar to the above)
• Potential Fields

势场是一种奇特的方式，意思是说每个障碍或墙壁都有“排斥力”，而每个目标都有“吸引力”。力的强度是基于与物体的距离和物体的“严重性”。(熔岩坑比颠簸的道路更难通过)在构建了力场之后，朴素的算法归结为遵循阻力最小的路径。更好的版本可以检测到局部最小值和最大值，并避开这些井。

    Critter
    -----\    /-------\
          \  /         \ 
           \/           \
   Local Minima Trap     \
                          \
                           \
                             Goal

Answer 2

搜索A*

看一看A*寻路算法。它本质上是标准的方法，用于处理这类事情。

Amit Patel关于的文章对A*以及该算法的流行变体有一个非常好的介绍。

您将找到一个C#实现here和here

动态A*

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

虽然这是一个可行的解决方案，但每当您发现新的障碍时，从头开始重新运行规划算法会导致大量的冗余计算。例如，一旦你在障碍物周围，最有效的通向目标的路线可能是你在发现障碍物之前计划采取的路线。通过重新运行A*，您将需要重新计算前一路径的这一部分。

您可以通过使用Dynamic A* (D*)来避免这种情况。由于它跟踪以前计算的路径，当代理发现新的障碍物时，系统只需要在障碍物周围的区域计算新的路线。在此之后，它只能重用现有的路径。

Answer 3

我会使用一种面向目标的方法。你的问题说明了我们的目标是探索地图和避免障碍，所以这就是我们的目标。但是我们如何探索整个地图呢？我们探索未探索的东西。

从一开始，你只有一个未开发的区域，那就是你所在的广场。地图的其余部分被标记为未探索。你选择了一个未探索过的地方，并把它作为探索的目标。但是你如何做到这一点呢？您可以创建子目标来探索它旁边的位置。你如何做到这一点-探索它旁边的方块，依此类推，直到你的原始目标被分解成一系列的探索，从你当前的方块开始，导航到目标方块。

当您遇到障碍并发现地图的功能时，可能需要更改一些子目标。例如，当你撞到一堵墙时，探索那个正方形的子目标必须被擦洗，你必须创建一个新的计划来寻找替代路线。这就是所谓的回溯。

对于高级描述，基本上就是这样。我希望它能有所帮助！