algorithm - 类似于 Unblock Me 的游戏的关卡生成算法

Question

对于类似于 Unblock Me 的游戏，什么是合适的关卡生成算法？

我的第一次尝试是从已解决的关卡开始，然后倒退。我从棋盘右侧导出旁边的红色水平矩形开始。最初，棋盘上有零个其他棋子。所以我试着伪随机地添加件数到所需的件数(比如七件)。仅限于水平或垂直部分的水平不是很有趣，所以我在添加时在水平和垂直部分之间交替。最后，我试图通过随机移动来打乱它们。在研究了几个示例后，很明显这种方法通常会生成无趣的关卡。最小移动次数也是未知的。

下一次尝试以不同的方式解决问题。级别是随机生成的。然后搜索算法找到解决难题的最少步数(如果可能的话)。虽然我还没有实现它，但我认为它会创建一些有趣的关卡。由于电路板相对较小(10x10 上限)，我认为运行时间对于生成与应用程序捆绑的关卡来说是可以接受的。最小移动计数也是已知的，这对得分很重要。

我怀疑第一种方法是否有效。但是，我没有考虑过的变体可能会起作用。我对第二种方法的唯一保留是潜在的代码复杂性。我认为它将是一个带有备忘录表和 BoardState 对象的 BFS。在深入探讨第二种方法之前，我想听听一些替代方案。

Answer 1

我会这样做:

• 生成游戏的随机状态，其中红色矩形位于导出旁边
• 从该状态开始计算棋盘的完整状态空间
• 选择状态空间中距离已解决状态最远的状态之一作为实际问题。我会使用不同棋子的移动次数作为距离度量，即将同一棋子连续移动的多次移动计为 1
• 如果生成的状态空间太小，则去掉碎片重做
• 如果生成的状态空间很大，但任何状态到解决方案的距离都很小，则添加碎片并重做