用程序来构建2D平台跳跃游戏关卡的一个思路

作为一个程序员，我经常会沉迷于如何通过程序来自动构建关卡的想法中。

根据游戏类型和玩法的不同，通常需要使用不同的方法。也就是说，并没有一个万能的方法能够完美的适配所有的游戏关卡。

我一直希望能为游戏《影子来了》增加一点roguelike的元素，于是会经常冒出用程序来自动生成关卡的想法。

经过一段时间的尝试，我们构思了一个基于瓦片地图的思路：

1. 建立关卡的模板，例如一个关卡对应的尺寸是 m x n。
   

2. 建立分区模板，每个分区的尺寸为 w x h。
   

3. 对关卡进行分割，按照分区模板的尺寸，分割成不同的区域。

4. 对分割好的区域，采用程序生成，或者分区模板进行填充的方法来构建。
   在上边的模板中，周围的区域采用程序自动生成，而中间主区域，采用模板填充的方式。

5. 进行路径检测，以确保每个分区之间有路线联通。

6. 对于没有路线联通的分区，尝试补全路线。

7. 对于无法补全路线的图，放弃，重复步骤4。

最后结果：

关键点：

1. 分区模板，模板的数量，决定了随机填充以后，关卡的随机程度。
2. 路径检测，这是保证程序设计的关卡的可用性的决定性因素。

其中，路径检测是关键中的关键，难点有几个：

1. 游戏中角色除了水平移动外，还可以通过跳跃在纵向上进行移动，而且还具有多阶跳。
2. 游戏中的平台，有的是实心平台不可穿透，有的是单向平台，可以从下往上穿透。
3. 有些平台是可以动态移动的。

为了减低算法难度，对以上几点进行的简化处理：

1. 跳跃的路线，游戏中，实际的跳跃轨迹是抛物线，我将其处理成折线，将角色一次跳跃时可能触碰到的格子都标记出来，当这些位置上都是没有障碍时，判定为可以通过。这样就省去了进行碰撞检测的过程。
2. 不考虑多段跳的情况，也就是说，生成的关卡，需要保证玩家只用最普通的一段跳跃也可以完成。
3. 不考虑移动平台。