寻找穿墙最短路径的算法

Question

我正在为基于文本的游戏编写 AI，但我遇到的问题是我无法确定墙的最薄部分。例如，以下表示二维 map ，其中“^”是想要穿过由“*”字符表示的墙到达标记为“X”的位置的角色:

------------------
|  X *           |
|*****           |
|****            |
|***             |
|**      ^       |
|                |
|                |
|                |
------------------

这几天我一直在思考这个问题，但我的想法已经用完了。我试过使用*算法，当它试图穿过墙壁角色时，g-cost 变得非常高。不幸的是，该算法决定永远不穿墙寻路。

智能体只能从左-右-上-下移动，不能沿对角线移动，一次一个空间。

在上面的例子中，穿过墙壁的最短路径是一条，因为它只需要穿过一个“*”字符。

我只需要一些简单的想法:)

Answer 1

所有流行的图搜索算法通常都是用具有一些实数(即浮点/ double )成本的成本来制定的。但这不是必需的。对于成本，您真正需要的只是具有严格排序和加法等操作的东西。

您可以对此应用标准 A*。

• 定义具有 (a,b) 形式的成本
  • a是壁细胞上的移动数
  • b是正常细胞的移动次数。
• 定义这些单元格的顺序如下:
  • [(a1,b1) < (a2,b2)] == [(a1<a2) || (a1==a2 && b1<b2)]
  • 这只是一个字典排序，我们总是比我们更喜欢在正常单元格上移动更少之前在墙上移动更少
• 定义这些成本的加法运算如下:
  • (a1,b1) + (a2,b2) == (a1+a2,b1+b2)
• 将启发式(即对目标剩余距离的下限估计)定义为 (0,b)其中 b是到目标的曼哈顿距离

---

一个直接的反对意见可能是“使用这种启发式方法，在尝试穿过墙之前必须先探索墙外的整个空间!” -- 但这正是我们所要求的。

根据您提供的信息和要求，这实际上是最佳 A* 启发式算法。

---

可以提供更好的最佳性能的更复杂的方法是将上述方法与 bidirectional search 结合起来.如果您的目标在一个有围墙的小区域内，双向搜索可以在搜索的早期阶段找到一些候选的“穿过围墙的最便宜路径”。