8

我知道我的问题似乎很模糊，但我想不出更好的表达方式，所以我将首先解释我想要做什么。

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

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

我唯一的问题是我想不出一种智能地在地图上导航的方法。到目前为止，我一直根据小动物与地形碰撞时所面对的方向来确定它，这绝不是在地图上移动的好方法！

我不是游戏程序员，这是一个软件作业，所以我对人工智能技术一无所知。

这是地图和小动物外观图像的链接：

地图和小动物图像

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

4

4 回答 4

6

如果您对环境的唯一了解是您的小动物的位置及其速度，那么您能做的最好的事情就是我认为的墙跟随算法。如果您可以检测到环境中的其他一些东西，那么您有更多选择。

一些更流行的算法类型是......

势场是一种奇特的说法，即每个障碍物或墙壁都有“排斥力”，而每个目标都有“吸引力”。力的强度取决于与物体的距离和物体的“严重性”。（熔岩坑比崎岖不平的道路要严重得多）在构建了力场之后，朴素的算法归结为遵循阻力最小的路径。更好的版本可以检测局部最小值和最大值并逃离那些井。

    Critter
    -----\    /-------\
          \  /         \ 
           \/           \
   Local Minima Trap     \
                          \
                           \
                             Goal
于 2010-05-01T23:46:46.430 回答
3

A* 搜索

看一下A*寻路算法。它本质上是此类事情的标准方法。

Amit Patel关于游戏寻路的文章很好地介绍了 A* 以及该算法的流行变体。

您将在此处和此处找到 C# 实现

动态 A*

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

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

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

于 2010-05-01T23:33:00.767 回答
0

我会使用面向目标的方法。您的问题表明目标不是探索地图并避开障碍物，这就是我们的目标。但是我们如何探索整个地图呢？我们探索未探索的东西。

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

当您遇到障碍并发现地图的特征时，可能需要更改一些子目标。例如，当您撞墙时，必须清除探索该广场的子目标，然后您创建一个新计划来寻找替代路线。这称为回溯。

这基本上就是高级描述。我希望它有帮助！

于 2010-05-01T23:32:36.910 回答
0

我似乎在聚会上迟到了。如果你的小动物手头有 GPS 和完整的地图，那么正确的做法肯定是 A*，如果地图足够小，如果你不想编码 A*（A * 有很多你想正确处理的极端情况）。

然而，一个不同的问题是，如果你的小动物只知道目标的方向并且只能局部观察它周围的情况怎么办？如果你的小动物不知道完整的地图怎么办？

在这种情况下，您可能希望实现导航的“错误算法”。链接：http ://www.cs.cmu.edu/~./motionplanning/lecture/Chap2-Bug-Alg_howie.pdf

这是一个适用于所有未知地图的可爱算法，我敢肯定，你会对它进行爆炸式编码。

于 2017-06-30T19:15:30.210 回答