A*寻路-最接近无法行走的目的地

Question

我已经有了一个工作的A*实现。问题是，如果选择一个不可走的目的地，则不会返回任何路径。我想能得到我能得到的“最接近的”。

更好的选择是完全动态的（而不仅仅是检查目标周围的8个瓷砖来试图找到一个）。这样，即使他们点击一个被一个巨大的方块包围的不可行走的瓷砖，它仍然会尽可能地靠近。

Answer 1

虽然这里提供的简单答案可能已经足够了，但我认为这取决于你的游戏类型和你试图实现的目标。

例如，以这个游戏领域为例（对不起，我重复使用了我用来向您展示战争迷雾的相同软件：））：

正如你所看到的，一只愤怒的小鸡正堵住左侧和右侧之间的路径。愤怒的鸡可能是任何东西...如果是静态障碍物，那么使用最低的H节点可能就足够了，但是如果是动态对象（如上锁的门、画桥等）下面的示例可能会帮助您了解如何解决问题。

你怎么能这么做？一种简单的方法是在层次图上进行pathfind。这听起来很复杂，但事实并非如此。首先，您希望能够构建一组新的高层节点和边，这些节点和边将包含多个网格节点（或其他表示形式，不会改变任何事情）

如您所见，我们现在有一个右边的蓝色节点和一个左边的红色节点。箭头表示两个节点之间的边。你问的这个图怎么建？这很简单，只需从一个打开的节点开始，展开它的所有邻居，并将它们添加到一个高级节点，完成后，打开可能导致图的另一部分的动态节点，并执行相同的操作。

现在，当您请求从我们的英雄到红色X的路径时，您首先在高层进行路径查找...是否有从蓝色节点到红色节点的方法？是的！通过鸡肉。