algorithm - 推箱子游戏 : move boxes automatically

Question

我已经实现了一个功能，当 keeper 使用广度优先搜索算法自动移动时。现在我希望它也能自动移动盒子(如果管理员可以在不移动另一个盒子的情况下将盒子从源移动到目的地)。我该怎么做？我试过修改BFS，还没有成功。

更新:我不需要解开这个谜题。相反，我想开发方便的用户界面，当用户可以用鼠标移动框时。为此，我需要一些算法，它可以计算移动序列。但这只是关于移动单个盒子，如果没有其他盒子应该移动的话。

Answer 1

像以前一样使用广度优先搜索(如果您愿意，也可以使用 A*)，但搜索适当的状态集。

当您为守门员搜索路径时，状态对应于网格中的方 block 。但是，当您为守门员寻找移动方 block 的方法时，状态对应于网格中的对正方形(一个用于守门员，一个用于方 block )。

这是最小的重要示例。假设我们有一个带有如下标记的方 block 的推箱子关卡:

网格包含守门员和一个方 block 。状态空间由守门员和区 block 占据的成对正方形组成。有 56 个这样的状态，在下图中绘制为小圆圈。

线条显示了该状态空间内可能的转换。细线对应于守门员的移动(并且是双向的)。粗线对应于插入方 block (因此只能朝一个方向移动)。您需要搜索的是这个状态空间。

例如，如果 block 从 7 开始，守门员从 8 开始，那么守门员可以按照状态空间中的红色路径将 block 推到 8:

请注意，沿着这条路径，方 block 经过位置 7–6–5–6–7–8。仅考虑 block 的位置是无法找到这条路径的，因为 block 经过位置 6 和 7 两次。