为推箱子游戏随机生成级别？

Question

我正在做一个推箱子风格的游戏（即它不是完全一样，推箱子，所以我不能用现有的水平），并希望在其上创建随机水平，使玩家可以继续玩它，总是有水平试试。有没有什么方法可以使计算机自动或半自动地为我生成关卡（通过半，我的意思是我可以给它初始地图，但可能没有包装箱的位置）？

我有一个想法是随机生成的地图，将箱子在他们整理的状态（即：在十字），然后随机移动的箱子，好像他们是由游戏角色拉动。这保证了这个关卡应该是可以解决的。然而，主要问题是如何知道这个级别是否简单/困难和有趣/无聊？例如，推箱子是NP-hard，所以我不能实际问机器然后检查是否有简单的解决方案。

我知道这将是很难创建随机的水平，将与人类专家竞争，但我只是在寻找的东西，是体面的。

编辑：顺便说一下，我会更感兴趣，如产生小而有趣的推箱子样的水平5x5级而不是50x50级。这可能使事情在计算上更可行。

Answer 1

这个网站有一些推箱子级发电机：http://www.erimsever.com/sokoban7.htm

你可能会发现，看他们是如何工作的。