基于图块的 A* 寻路，但带有炸弹
Tile Based A* Pathfinding, but with a bomb
我已经编写了一个简单的 A* 寻路算法来快速找到通过基于地牢的地牢的方法，其中地牢包含墙壁的信息。
地牢示例（为简单起见只有 1 条路径）：
但是现在我想在算法中添加可变数量的 "Bombs"，这将允许寻路忽略 1 堵墙。但是现在它找不到最佳路径了，
例如仅使用一个炸弹生成的路径看起来像这里的第一张图片：
编辑：实际上它看起来像这样：https://i.stack.imgur.com/kPoAA.png
而正确的路径应该是第二张图片
问题是 "Closed Nodes" 现在干扰了可能的路径。任何有关如何解决此问题的想法都将不胜感激！
这不是说你只是假装根本没有墙吗？
使用 A* 求出从头到尾的最短路径，然后检查您需要穿过多少堵墙。如果你有足够的炸弹，你可以使用路径。否则，尝试下一条最长的路径，依此类推。
顺便说一句：您可能想查看 http://gamedev.stackexchange.com 以了解此类问题。
您需要调整成本函数来为炸弹花费一些成本，然后 运行 算法通常会为第二颗炸弹花费无限的成本。要在大约一半的时间内获得炸弹，请使用成本函数，它的成本可能约为启发式 A-B 距离乘以空方块的成本。如果你有两个炸弹，成本减半，当然使用三个炸弹成本无限。
但不要指望会有很好的结果。 A* 不是为这种优化而设计的。
您的 "game state" 将不再仅由您的位置定义，还由一个代表您剩余的炸弹数量的整数来定义。如果您在 wikipedia 上遵循 A* 的伪代码，这意味着您不能简单地将 closedSet 实现为布尔网格。它可能应该被实现为，例如，哈希映射/哈希集，其中每个条目都包含以下数据：
- x坐标
- y坐标
- 剩余炸弹数量
通过访问搜索过程中的某个职位，您将不再仅将该职位标记为已关闭。您会将位置 + 剩余炸弹数量的组合标记为已关闭。这样，如果稍后在同一个搜索过程中你 运行 进入一个你在同一位置的位置，但还有更多炸弹，你不会将其视为已关闭而忽略它，但实际上会继续搜索这种可能性。
请注意，如果最大可能的炸弹数量相对较少，您还可以将 closedSet 实现为布尔网格数组，您首先按炸弹数量进行索引，然后按 x 和 y坐标以查明特定仓位是否平仓。
我已经编写了一个简单的 A* 寻路算法来快速找到通过基于地牢的地牢的方法，其中地牢包含墙壁的信息。
地牢示例（为简单起见只有 1 条路径）：
但是现在我想在算法中添加可变数量的 "Bombs"，这将允许寻路忽略 1 堵墙。但是现在它找不到最佳路径了，
例如仅使用一个炸弹生成的路径看起来像这里的第一张图片：
编辑：实际上它看起来像这样：https://i.stack.imgur.com/kPoAA.png
而正确的路径应该是第二张图片
问题是 "Closed Nodes" 现在干扰了可能的路径。任何有关如何解决此问题的想法都将不胜感激！
这不是说你只是假装根本没有墙吗？
使用 A* 求出从头到尾的最短路径，然后检查您需要穿过多少堵墙。如果你有足够的炸弹，你可以使用路径。否则，尝试下一条最长的路径，依此类推。
顺便说一句：您可能想查看 http://gamedev.stackexchange.com 以了解此类问题。
您需要调整成本函数来为炸弹花费一些成本，然后 运行 算法通常会为第二颗炸弹花费无限的成本。要在大约一半的时间内获得炸弹，请使用成本函数，它的成本可能约为启发式 A-B 距离乘以空方块的成本。如果你有两个炸弹，成本减半，当然使用三个炸弹成本无限。
但不要指望会有很好的结果。 A* 不是为这种优化而设计的。
您的 "game state" 将不再仅由您的位置定义，还由一个代表您剩余的炸弹数量的整数来定义。如果您在 wikipedia 上遵循 A* 的伪代码，这意味着您不能简单地将 closedSet 实现为布尔网格。它可能应该被实现为，例如，哈希映射/哈希集，其中每个条目都包含以下数据：
- x坐标
- y坐标
- 剩余炸弹数量
通过访问搜索过程中的某个职位，您将不再仅将该职位标记为已关闭。您会将位置 + 剩余炸弹数量的组合标记为已关闭。这样，如果稍后在同一个搜索过程中你 运行 进入一个你在同一位置的位置，但还有更多炸弹，你不会将其视为已关闭而忽略它，但实际上会继续搜索这种可能性。
请注意，如果最大可能的炸弹数量相对较少，您还可以将 closedSet 实现为布尔网格数组，您首先按炸弹数量进行索引，然后按 x 和 y坐标以查明特定仓位是否平仓。