Procedural Level Generation for a 2D Platformer

程序控制生成2D平台游戏（2D平台游戏举例：《超级马里奥》《索尼克》）

By Fabien Benoit-Koch

Jack Benoit is my latest mobile game, a not-so-original 2D platformer for Android. My goal was to make a fast, responsive game for mobiles, with the best possible controls, and to have complete procedural generation for the levels. By complete, I mean not based on manually crafted level pieces, assembled randomly, but truly randomised to the tile granularity, something that is often advised against. But hey, it was fun to try and the results are not that bad. I’ll describe the whole process in this article.

Jack Benoit是我的一款，不算完全自主创意的安卓2D平台游戏。我的目标就是在短时间内做出一款手机游戏，操作简单，所有地图利用程序生成。不用人工设计，完全随机生成瓦块数量，尽管大家都劝我不要这么做。但是我喜欢，勇于尝试，而且结果也不赖。

Description of the game  游戏介绍

You control a character able to jump and climb ladders, and your goal is to simply reach the exit of a level, which are made of various sets of platforms, ladders, and hazard zones (spikes). Jack Benoit uses 4 layered tile maps:

The parrallax background,

The platforms,

The ladders,

The sprites (collectable items, decorations, etc).

All of the layers are constructed procedurally. The background is simply made out of Perlin noise, filtered and smoothed using transition tiles, I won’t talk about it, the subject has been covered to death by better authors than me. This article will focus the architecture (platforms, blocks, and ladders).

在游戏中，玩家控制一个小人，通过梯子，跳跃，危险区域，来回来去寻找每关的出口。 游戏用了四层tile地图：

1、视差背景（Parallax，视差，是指从不同的点看一个物体时形成的视觉差异）

2、platforms

3、ladders

4、sprites 

每一层面都由程序生成。背景用Perlin噪声（Perlin噪声可以用来模拟自然界中的噪声现象。由于它的连续性，如果将二维噪声中的一个轴作为时间轴，得到的就是一个连续变化的一维函数。同样的也可以得到连续变化的二维图像。该噪声可以用来模拟人体的随机运动，蚂蚁行进的线路等。另外，还可以通过计算分形和模拟云朵，火焰等非常复杂的纹理。）算法生成，用过渡tile进行过滤并整平。我在这里不多说了，有更好的文章。本文主要阐述游戏中建筑（platform，blocks和ladders）

Step 1. Generating a level layout

第一步：生成一个关卡布局

Levels are composed by a random set of discretely connected “rooms” (rectangles of 20×16 tiles). Each room can have up to 3 “walls”, at its own edges. Two rooms are connected if their shared edge doesn’t contain a wall. The structure becomes quite clear when you see a whole level. This one is made of 15 rooms:

关卡是由随机一组不相关联的room组成（room是一个20x16 瓦块的长方形）。每个room最多有3面墙，每面墙占据长方形四个边的其中之一。两个能连起来的room，连接的那一面，各自本来都是没有墙的。下面我们来看一张完整的关卡结构图，它由15个room组成。

The first step is to create this random path of rooms. The goal is to get a data structure describing something like this:

第一步是要随机创造出一个rooms组合，得到一个如下所示的数据结构：

We simply represent this using a 2D array of Room objects. The algorithm is a simple recursive graph exploration, with backtracking.

我们用一个2D array of Room objects来描述。算法是一个简单的递归地图探索（recursive graph exploration），不用倒退。

function findPath(x, y, minDistance):

if (x,y is goal and minDistance == 0) return true

if (x,y not open) return false

mark x,y as part of layout path

switch(random number 1 out of 4):

case 1: if (findPath(North of x,y, minDistance - 1) == true) return true

case 2: if (findPath(East of x,y, minDistance - 1) == true) return true

case 3: if (findPath(South of x,y, minDistance - 1) == true) return true

case 4: if (findPath(West of x,y, minDistance - 1) == true) return true

unmark x,y as part of solution path

return false

Once this is done, we make sure the structure is easily iterable, and each Room knows about the location of next and the previous ones.

这样做完，可以保证整个结构是可以遍历的，每个房间都能获悉前一个和下一个房间的位置。

Step 2. Generating a solution path

第二步：生成一条最优通关路径

The second step is the most critical to ensure the correctness. It’s very easy, if you’re not careful, to produce impossible levels! In our example, the player must always be able to navigate through all these rooms, to reach the last one. Given that the player movement is constrained by physics (he can jump 4-5 tiles high), we had to make sure that the vertical parts (two or more rooms vertically connected) were always in reach.

第二步对于保证路径的准确性很重要。不小心的话很容易做出一条无解路径！我们要让玩家通过所有的房间再到最后一间。玩家单次最高可以跳过4-5个tile，我们要确保垂直的部分，玩家是都可以抵达的。

That part proved to be tricky. I finally chose to create a solution path, i.e. a set of platforms and ladders that leads the player directly to the level exit, without interruption.

最终，我选择创建一条最优通关路径，通过platform和ladder引领玩家顺利通关

At first, it may seem too straightforward, but once the generation is complete, this path is “hidden” in the middle of the other platforms, and is not evident at all to the player. In fact, it is so camouflaged that I had to put sign posts indicating the direction to follow. The player often gets off the path, finding alternative ones, but at least a solution is guaranteed to exist (no impossible levels).

起初，这么做看起来太直接了，但所有内容完成后，这条路就隐蔽在其它platform中了，玩家不容易发现，我有时还要放一些引导。玩家有些时候，明明走对了却又跳了下来去找别的。不过最后都应该是可以出来的。

The process is quite simple. Generate a random position in each room, then connect all of them using one ladder, and one platform.

生成过程很简单。在每个room里生成一个随机位置，然后每个点之间都用一个ladder和一个platform连起来。

for each room in the layout:

select a random point P1(X1,Y1) in the room

select a random point P2(X2,Y2) in the next room of the layout

set cursor C(Xc, Yc) to P1

while P2 is not reached by cursor:

if (selectionFunction):

create a platform between (Xc, Yc) and (X2, Yc)

move cursor to (X2, Yc)

else:

create a ladder between (Xc, Yc) and (Xc, Y2)

move cursor to (Xc, Y2)

The selectionFunction is used to determine if we start by a ladder or a platform. It’s randomised, however in order to generate well-designed levels, it will also take some heuristics into account, like the minimum length of a ladder or a platform.

这个selectionFunction用来决定，是从ladder还是platform开始。这个是随机的，但要想把关卡设计的更好，还是应该有些大胆的探索，比如给ladder和platform一个长度限制。

Step 3. Fill the rooms with platforms

第三步：在rooms中填充platforms

Now that the path is secured, we must actually fill the rooms. I tried some top-down approaches (generating perlin noise to spread platforms homogeneously) but the simplest ones (pure randomness guided with some ad-hoc heuristics) often produced the best results.

现在路径做好了，我们要把rooms充实起来。我尝试了很多top-down 方法（用Perlin噪声生成platform然后均匀散开），往往最简单的方法给出最佳结果。

I simply on each empty tile of the room, starting in the top-left corner, and for each empty tile (in the platforms layer), there is a chance to generate a platform of some random length. We also make sure that this platform, if generated, does not completely block the level (horizontally or vertically).

我先简单地，从每个room的左上角开始，把所有值为0的tile遍历一遍，这些0值tile（platform层的）都有可能生成随机长度的platform。不过我们要保证这些platform，在水平或者垂直方向，不会将路径堵住。

Step 4. Generate ladders

第四步：生成ladders

On each the generated platforms, we place a ladder top at a random X position on the platform. We then “grow” them (like a plant, which is fortunate, because some of the ladders are actually plants) downward until it reaches a platform below, or the ground.

在每个生成的platform上，我任选一点作为一个ladder的起点，然后让ladder向下生长（游戏中的ladder就是植物的样子），直到触及到下面的platform或者地面

As you can see, while the solution path is quite clear before this step, it is eventually neatly disguised.

如图所示，生成这些ladders后，就可以将之前生成的最优解决路径混淆掉。

Conclusion

结论

This simple method produces a lot of variability, which is nice, yet the gameplay remains relatively consistent. After some runs, the player learns to “guess” what the solution path is. It has some drawbacks though: some (rare) platforms remain sometimes unreachable, because putting a ladder on 100% of all the platform produces too many of them.

简单的方法可以制造出很多的可能性，大致玩法是不变的。玩了几次之后，玩家能猜到这里面藏有一条最优路径。缺点是：少数platform，在有些情况下到不了，给所有platform放一个ladder，就有了太多的可走的路。

A more complex graph exploration, based on the physical characteristics of the player would be necessary to detect and correct these cases, but it is costly, and felt unnecessary given the frequency and the gravity of the problem.

更复杂的地图探索，要有乐于发现并纠正问题的玩家帮助，这就需要你花费更多的精力去应对他们提出的问题。

Thanks a lot for reading this. If you have any questions, feel free to ask!

谢谢阅读。

Note: This post was originally published on Fabien's blog and is republished here with kind permission.

About the Author(s)

After a decade in "corporate" software engineering, I decided to jump back to my first love, game development, hoping to

recreate the arcade feel of classics on modern platforms. With the help of my partner in crime, Marcin JP, we founded Arcade Pulp,

and we're currently busy with "Turbo Smash Blade", an old school brawler for mobiles phones.