随机生成推箱子游戏的关卡？

Question

我正在制作一款推箱子风格的游戏(即它与推箱子不完全相同，所以我不能使用现有的关卡)，并且想在其上创建随机关卡，以便玩家可以继续玩它并且始终有关卡尝试。有什么方法可以让计算机自动或半自动地为我生成关卡(半自动，我的意思是我可以给它初始 map ，但没有 crate 位置)？

我的一个想法是随机生成一张 map ，将 crate 放置在完成状态(即十字架上)，然后随机移动 crate ，就好像它们被游戏角色拉动一样。这保证了我这个关卡应该是可以解决的。然而，主要的问题是如何知道关卡是简单/困难、有趣/无聊？例如，Sokoban 是 NP 难的，所以我实际上无法要求机器检查是否有一个简单的解决方案。

我知道创建与人类专家竞争的随机关卡会很困难，但我只是在寻找像样的东西。

编辑:顺便说一句，我对生成小而有趣的推箱子级别更感兴趣，例如5x5 级别而不是 50x50 级别。这可能会使事情在计算上更加可行。

Answer 1

该网站有许多推箱子关卡生成器:http://www.erimsever.com/sokoban7.htm

您可能会发现了解它们的工作原理很有用。