其实有，可以参考 Ty Taylor 的 The Art and Science of Procedural Puzzle Generation，/watch?v=RLcMvCS4-gY
游戏地图数据有墙壁、地板和目标点等三种不发生变化的游戏地图数据，以及两种可变对象，如盒子和推箱子小人。
推箱子的游戏规则是：玩家控制小人在地图上上下左右移动，当小人移动的方向出现方块时，可以推动方块往对应方向移动. 但是遇到墙，小人就不能动了；如果推箱子时箱子前面有墙或其他箱子，小人无法将箱子向前推。
推箱子的胜利条件是所有箱子都在目标点上方。失败的条件是没有盒子可以被推，并且没有盒子位于目标点上方。
一个有意义的益智游戏关卡通常满足以下要素：
关卡应该是可解的：至少有一个推箱子的步骤才能达到获胜状态。关卡的解状态空间要大：如果一个关卡只有有限的状态空间，则说明该关卡是一次性关卡，过于简单，没有挑战性。例如这个级别：
▩▩▩▩▩▩▩▩▩▩▩▩
▩@#---------------* ▩
▩▩▩▩▩▩▩▩▩▩▩▩
3. 解决一个关卡的最短路径应该足够长：如果一个关卡的最优解路径太短推箱子游戏素材，说明解谜的水平较弱，玩家一眼就能看出解。例如这个级别：
▩▩▩▩▩▩▩▩▩▩▩▩
▩-------------------▩
▩---*----------------▩
▩@#---------------▩
▩-------------------▩
▩-------------------▩
▩▩▩▩▩▩▩▩▩▩▩▩
为此，自动电平生成器通常由三部分组成：
1. 关卡生成器：以随机或程序方式增量生成关卡。
2. Level Solver：输入level generator生成的level，判断是否有解。
3.关卡过滤器：输入一个已经生成并有解的关卡，判断其解状态空间和最小解步数是否满足要求。
三部分的交互如下图所示：
关卡生成器的三个部分及其关系
下面我们详细阐述关卡生成器、求解器和过滤器的具体实现。
电平发生器
关卡生成器采用增量随机生成关卡的策略：
水平求解器
我们采用广度优先搜索算法来解决推箱子谜题。原因是：
1. 广度优先计算游戏从初始状态到成功解谜状态所需的最小步数。
2. 广度优先可以回溯得到解谜过程的状态序列，这些状态序列是解谜过程最短的步骤。
3. 在广度优先搜索的过程中，会得到一个解树。这棵树的深度和广度可以衡量生成关卡的解状态空间复杂度。
由于游戏中唯一可变的单位是盒子和小人的位置，所以状态节点只需要记录盒子和小人的位置。需要注意的是创作人，在使用广度优先搜索的过程中，状态空间会爆炸，每个状态节点都必须剪枝，否则求解会很慢。可以从以下几点考虑剪枝：
死锁情况一：
##
##
死锁情况2：
--▩
▩#
水平过滤器
使用广度优先搜索，可以计算出解状态空间和生成的每个关卡的最短解谜步骤数。因此推箱子游戏素材，过滤器只需要比较和权衡迭代过程中产生的解状态空间和最短解谜步骤数，选择状态空间更大、解谜步骤数最短的层作为最终输出层。
结果显示
以下是使用我们的自动关卡生成器生成的一些推箱子关卡。迭代次数是求解器通过广度优先搜索实现的迭代次数，以找到关卡的最优解。最小步数为推箱子的最小步数+成功解谜所需的最小步数（初始状态也记为1步）。
源代码
/huanggaole/AutoGenerateSokobanLevel
