algorithm - 寻找穿过墙的最短路径的算法

我正在为一个基于文本的游戏编写一个人工智能，但我遇到的问题是，我无法确定墙的最薄部分。例如，下面表示二维地图，其中“^”是要穿过由“*”字符表示的墙到达标记为“X”的位置的字符：

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

我已经连续几天在想这个了，我已经没有什么想法了我试过使用一个*算法，当它试图通过一个墙字符时，G成本非常高。不幸的是，算法决定永远不通过墙寻找路径。
代理一次只能左上右下移动一个空间，而不能沿对角线移动。
在上面的例子中，穿过墙的最短路径是一条，因为它只需要穿过一个“*”字符。
我只需要几个简单的想法：）

最佳答案

所有流行的图搜索算法通常都是用具有一定实数（即float/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是曼哈顿到目标的距离
一个直接的反对意见可能是“有了这种启发，在试图穿过墙之前，必须探索墙外的整个空间！”--但这正是要求的。
根据你给出的信息和要求，这实际上是最佳的启发式方法。
一种更复杂的方法可以提供更好的最佳案例性能，那就是将上述方法与bidirectional search结合起来如果你的目标是在一个很小的围墙区域内，双向搜索可以在搜索的早期找到一些“穿过围墙最便宜的路径”。

关于algorithm - 寻找穿过墙的最短路径的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16856348/