path-finding - 基于图 block 的 A* 寻路，但带有炸弹

Question

我已经编写了一个简单的 A* 路径查找算法来快速找到一种通过基于瓷砖的地牢的方法，其中瓷砖包含墙壁的信息。

地牢示例(为简单起见，只有 1 条路径):



但是现在我想在算法中添加可变数量的“炸弹”，这将允许寻路忽略 1 堵墙。但是现在它不再找到最佳路径，

例如，仅使用 1 个炸弹，生成的路径看起来像这里的第一个图像:


编辑:实际上它看起来像这样:/image/kPoAA.png



虽然正确的路径是第二张图片

问题是“封闭节点”现在会干扰可能的路径。任何有关如何解决此问题的想法将不胜感激!

Answer 1

您的“游戏状态”将不再仅由您的位置定义，还由一个代表您剩余炸弹数量的整数定义。如果您遵循 wikipedia 上的 A* 伪代码，这意味着您不能简单地实现 closedSet作为 bool 值网格。例如，它可能应该实现为哈希映射/哈希集，其中每个条目都包含以下数据:

x 坐标

y 坐标

剩余炸弹数量

通过访问搜索过程中的某个位置，您将不再只将该位置标记为已关闭。您会将位置 + 剩余炸弹数量的组合标记为已关闭。这样，如果稍后在同一个搜索过程中您遇到一个位置，您在同一位置，但还有更多炸弹，您不会将其忽略为已关闭，但实际上会继续搜索这种可能性。

请注意，如果炸弹的最大可能数量相对较低，您也可以实现 closedSet作为 bool 网格数组，首先按炸弹数量索引，然后按 x 和 y 坐标确定特定位置是否关闭。