我正在制作一个推箱子风格的游戏（即它与推箱子不完全相同，所以我不能使用现有的关卡）并且想在其上创建随机关卡，以便玩家可以继续玩它并且总是有关卡可以尝试。有什么方法可以让计算机自动或半自动地为我生成关卡（半自动，我的意思是我可以给它初始地图，但没有板条箱位置）？
我的一个想法是随机生成一张地图，将板条箱置于完成状态（即在十字架上），然后随机移动板条箱，就好像它们被游戏角色拉动一样。这保证了我的水平应该是可解决的。然而，主要的问题是如何知道关卡是容易/难还是有趣/无聊？例如，推箱子是 NP 难的，所以我不能实际要求机器检查是否有简单的解决方案。
我知道很难创建与人类专家竞争的随机关卡，但我只是在寻找一些不错的东西。
编辑：顺便说一句，我更感兴趣的是生成小而有趣的类似推箱子的关卡，例如 5x5 关卡而不是 50x50 关卡。这可能使事情在计算上更可行。