推箱子解决方案,提示

Question

我必须做一个推箱子解算器(http://en.wikipedia.org/wiki/Sokoban).你做过一次吗？我正在寻找提示,而不是代码.就像"你可以使用IDA*alg"或"我使用启发式并且它非常好"或"我使用该技术不会避免死锁".

基本上我想在编写任何代码之前在纸上写下策略.

Answer 1

我已经写了关于推箱子算法的硕士论文.我的目的是提供关于推箱子解算器中使用的技术的一个很好的概述.它没有提供明确的答案,但可能为有兴趣编写推箱子解算器的人提供一个良好的起点.

http://weetu.net/Timo-Virkkala-Solving-Sokoban-Masters-Thesis.pdf

Answer 2

条款

field - 当前游戏的等级,整个游戏区域.

位置 - 一个阶段,在现场设置.

最终位置 - 无法转弯的位置 - 目标或死锁.

盒子 - 与箱子一样.

理论

只是一点逻辑 - 它似乎很明显,但我们将在实现部分中使用它.

所以 - 关于推箱子的每一场比赛,我们可以说这是其中之一:

• 可解决的,未解决的 - 在解决过程中
• 可解决的,解决的 - 目标
• 无法解决,未解决 - 如果我们的实现没有产生任何结果,并且没有更多可能的移动/移动组合

现在 - 一个推箱子游戏包括:

• 移动 - 角色可以在由墙和/或方框定义的区域中移动,该区域在整个游戏区域中更小或相等(如果不计算墙壁,并且没有框) - 但是,在场地周围移动角色使没有什么区别,除了得分,这是无关的实际解决方案- 让我们暂时忽略它
• 推 - 推箱子更重要,可能会导致我们的目标 - 解决这个领域 - 推动他们各自的目标

一个盒子可以是:

• 进球 - 很可能这个方框不需要移动,有些规则可以禁止方框在目标位置移动(非常不寻常)
• 可推动 - 在1到4个方向
• 不可用,不在目标
  • 被两面墙挡住了 - 无论如何,目前的位置是无法解决的
  • 其他 - 我们稍后会到这个盒子 - 现在一个箱子挡在我们的路上

处理

这是我们将用于解决(下面的定义)的逐步过程:

1. 在当前位置使用每个可直接访问的推送(可推动或内向)填充possibleTurns _n,其中玩家位于当前位置
2. 采取的第一项possibleTurns _ñ,删除它,执行它
3. 看看当前的位置:
   1. 是最后的 - 目标 - 解决,不做任何事情
   2. 是最后的 - 死锁 - 这个转向导致了僵局,不再填充它,回到2.步骤,n保持不变
   3. 不是最终的 - 增加n并填充possibleTurns _n,可能在此位置转弯

定义:

possibleTurns _x - 二维数组或数组数组 - x定义了转弯的"深度"

n - 在开头为零,将在执行上述算法时递增

提示

最后 - 上面的过程将为您留下一系列转弯,这些转弯将留给一个解决的位置.最后要做的是使用像A*这样的算法来确定这些转弯/推动之间的最短路线,以最大化速度和得分,最小化游戏内转弯次数.

Answer 3

您可以创建一个强力解算器，尝试将您的球员朝各个可能的方向移动。通过使用递归（或堆栈），如果找不到解决方案，您可以追溯您的步骤。

A* 可能不会给你带来任何好处，因为你不需要找到穿过迷宫的路，还需要移动盒子。这意味着您可能需要在移动盒子后朝原来的方向后退一步。因此，对于每一步，您都需要评估所有方向，包括您来自的方向。也就是说，除非您在上一步中没有移动盒子。

[编辑] 你可以使用 A* 让它变得更聪明一些；找到从当前位置到任何可以移动盒子的位置的方法。这可能会让您的解决方案更加高效，因为您不必跟踪中间的所有位置，而只需跟踪从您推送的最后一个框到您要推送的下一个框的位置。