我知道我的问题似乎很模糊，但我想不出一个更好的方式来说明，所以我会先解释我正在尝试做什么。围绕2D地图的AI导航 - 避开障碍
我目前正在开发一个项目，我已经获得一张地图，并且正在编写一个应该能够在地图上导航的“小动物”;生物有其他各种功能，但这些与当前问题无关。整个程序和解决方案都是用C＃编写的。我可以控制小动物的速度，并通过返回其当前的X和Y位置来检索它在地图上的当前位置，我还可以在它与阻止它的地形碰撞时设置它的方向。
我唯一的问题是，我想不出一种方法来智能地导航我的方式围绕地图;到目前为止，我一直以它在与地形碰撞时生物体面临的方向为基础，而这绝不是绕地图移动的好方法！
我不是一个游戏程序员，这是一个软件任务，所以我不知道人工智能技术。
下面是什么样的地图和小动物看起来像一个图像的链接：
我绝不找任何人都可以给我一个完整的解决方案，只是一个推入一般在地图导航方向。
我会使用一种以目标为导向的方法。你的问题指出的目标是探索地图并避开障碍，所以这就是我们的目标。但我们如何探索整个地图？我们探索什么是未开发的。
从一开始，您只有一个未开发区域，即您所在的广场。地图的其余部分标记为未探索。您选择一个未开发的位置，并将其作为探索它的目标。但你如何到达那里？你创建一个子目标来探索它旁边的位置。你如何做到这一点 - 探索旁边的广场，等等，直到你的原始目标被分解为一系列探索，从你当前的广场开始，并导航到目标广场。
当你遇到障碍物并发现地图的特征时，一些子目标可能需要更改。例如。当你撞墙时，探索这个广场的子目标必须被清理，并且你创建了一个新计划来寻找替代路线。这被称为回溯。
这基本上是高层次的描述。我希望它有帮助！
我不会这样做 - 你想选择一个附近的目标。我会让目标去探索最近未知的广场。 – 2010-05-04 04:51:18
A *搜索
看看在A*寻路算法。它基本上是这种东西的标准方法。
阿米特帕特尔的写在pathfinding for games有一个相当不错的介绍A *以及算法的流行变种。
动态A *
比方说，你可以搜索不提前知道地形，而是被发现的代理探讨其环境。如果您的代理遇到一个以前未知的障碍，你可以只更新代理的地形地图，然后重新运行A *寻找新的路径目标障碍物周围的路由。
虽然可行的解决方案，每次发现新障碍从头重新运行规划算法导致大量的冗余计算。例如，一旦你在障碍物附近，最有效的途径可能就是在你发现障碍物之前遵循你打算采取的最有效途径。通过重新运行A *，您需要重新计算以前路径的这一部分。
您可以通过使用Dynamic A* (D*)避免这种情况。由于它跟踪以前计算的路径，当代理发现新的障碍物时，系统只需计算障碍物周围区域的新路线。之后，它可以重复使用现有的路径。
这是聚焦D *的纸，而不是D *。但是，这些都被D * -Lite所取代。有关更多信息，请参见[here]（http://cstheory.stackexchange.com/a/11866/8532），以及可能适用于OP问题的其他算法。 – 2012-07-13 19:56:21
如果您有环境的唯一知识是你的小动物和它的速度，你能做的最好的位置是墙下面的算法我想。如果你可以检测到你的环境中的其他一些东西，你有更多的选择。
一些比较流行的算法类型的...
势场是奇怪的说每道障碍或墙壁都有“排斥力”的时候艾尔拥有“吸引力”。力的强度取决于与物体的距离和物体的“严重性”。 （熔岩坑是更严重的比路坎坷穿越）构建的力场天真的算法归结为以下阻力最小的路径之后。更好的版本可以检测当地的最小值和最大值，并逃离这些井。
Critter
-----\ /-------\
\/ \
\/ \
Local Minima Trap \
\
\
Goal
我似乎迟到了派对。如果你的小动物有GPS和完整的地图，正确的做法肯定是A *，如果地图足够小，如果你不想编码A *（A *有好几个角落案例需要处理）。
但是，另一个问题是如果你的小动物只知道目标的方向，只能在本地观察它是什么？如果你的小动物不知道完整的地图怎么办？
在这种情况下，你会想实现导航的“bug算法”。链接：http://www.cs.cmu.edu/~./motionplanning/lecture/Chap2-Bug-Alg_howie.pdf
这是一个可爱的算法，适用于所有未知的地图，你会有一个爆炸编码，我敢肯定。
你说你可以“设置它的方向，当它与阻止它的地形碰撞。”你只能在与某物碰撞时设定方向吗？或者，您可以在地图周围导航时随意更改方向吗？ – dmcer 2010-05-02 04:41:14
我可以随意改变方向！ – 2010-05-05 12:55:55
地图是否提前完全知道？或者，您是否需要通过与小动物探索地形来发现障碍和奖励？ – dmcer 2010-05-07 07:29:46