游戏邦在:
杂志专栏:
gamerboom.com订阅到鲜果订阅到抓虾google reader订阅到有道订阅到QQ邮箱订阅到帮看

解析程序生成平台游戏关卡的设计条件

发布时间:2012-05-13 09:30:57 Tags:,,,

作者:Jordan Fisher

你想要制作一款程序平台游戏。你希望它能够根据需要生成关卡,你希望生成的关卡令人惊叹、富有挑战性而且有趣。你希望运算法则有足够的灵活性,这样你可以 设计新的障碍或修改游戏物理,马上用新内容制作出新关卡。你希望游戏能够针对新玩家生成容易的关卡,针对核心玩家生成困难的关卡,针对顶级玩家生成超难关 卡。

但是,创造出的这些关卡最好都能够被打通,否则玩家就会集合起来声讨你的游戏,通过Reddit、4chan及他们的个人博客摧毁你在行业中的声望。

从根本上来说,你想要的是宫本茂及其率领的团队,这样才能制作出令所有玩家感到满意的内容。

或者,你还可以使用精良的关卡设计AI。作为Pwnee Studios的首席程序员,我的工作是为我们首款平台游戏开发这种AI。

程序生成内容在平台游戏之外的其他游戏题材中已经呈现出耀眼的光芒。比如,《暗黑破坏神》中的平原和地下城,《Minecraft》中漂亮的风景,《孢子》中的生物动画。地下城探索和沙盘类游戏都有着悠久的程序生成历史。而且,还出现过许多带有随机关卡的单向卷轴类游戏,比如令人惊叹的《洞穴探险》和《Terraria》。

在这篇文章中,我主要阐述的是快节奏型平台游戏(游戏邦注:比如《马里奥》、《索尼克》和《超级食肉男孩》等)的随机关卡。在程序运算法则领域,这还是款受探索程度相对较低的部分,而且显得更具挑战性。我们想要的是像素完美的跳跃、反抗死亡的冲突和适宜所有技能等级玩家的可调难度,同时还要保证所有关卡都有恰当的解决方案。

优秀的程序运算法则需要满足以下3个条件:

1、可行性。你能否打通关卡?

2、有趣的设计。你是否想要打通关卡?

3、适当的技能等级。关卡挑战性是否恰到好处?

满足以上任何一个条件都是很容易的事情,但是同时满足3个条件就是个很大的问题。尤其是可行性,它会给你制作优秀程序平台游戏带来巨大的障碍。完美地满足另外两个要求也很困难。

首个条件——可行性是最麻烦的条件,所以我们先来阐述这一点。

设计要求1:它必须具有可行性

使用简单的技术就能够确保《暗黑破坏神》中的地下城有通行路径,其技术要求类似于保证生成的迷宫有一定的解决方案。在迷宫中,玩家对他们的位置有绝对的控制权,墙壁不会产生过多的限制和束缚。但是在平台游戏中,玩家对其所处位置的控制力度较弱,会受到许多游戏物理的影响,比如惯性、万有引力和摩擦等。这使问题变得愈发困难。

如果你生成了一个没有解决方案的迷宫,那么你可以敲掉些许墙壁,直到出现解决方案。如果你生成了没有解决方案的平台关卡,那么问题的解决方法并非如此显而易见。

我们需要确保我们的关卡有可能被打通。为满足这种可行性需求,我们需要一个非常优秀的计算机玩家,我们可以将关卡提交给它。这个AI玩家会直接证明关卡是否有可能被打通。这件事说起来容易,执行起来要困难得多,但幸运的是,优秀的平台游戏玩家AI是个已有深入研究的话题,而且有了些许著名的执行方案。执行优秀AI并不是件繁琐的事情,它显得相当直观。

现在,我们有了令人称奇的忍者AI,我们可以在将关卡呈现给玩家前先进行测试。更棒的是,如果玩家在卡在某个关卡上,我们可以让他们看看AI的做法。玩家可以学习并取得进步,至少能够不让他们怀疑关卡无法打通。

但是,我们仍然有个问题。我们要如何才能真正制作出一个可行关卡呢?就像NP完全问题一样,它似乎很容易用来证实解决方案的有效性,但却很难找到测试的方法。我们需要的是,让AI在设计关卡时,自然会考虑到可行和不可行的做法。

实现该目标最简单的方法是让AI了解玩家物理。让玩家站在一个方块上,我们可以预算计算出玩家朝不同方向跳跃可能到达的所有落地点。

列举可能的落地点(from gamasutra)

列举可能的落地点(from gamasutra)

随后,AI会接受这个信息,将其用作限制条件。它放置的每个方块都必须处在其他方块的特定距离内,这个距离取决于方块间的相对高度。这是个适用于简单玩家物理的优秀模型,但是如果物理包括惯性、摩擦和跳跃高度可变等诸多要素,那么预计算的工作量就会变得很大。我们需要根据每种配置来了解玩家最终的落脚点,比如半速奔跑、全速奔跑、全程跳跃和半程跳跃等。

短跳跃(from Gamasutra)

短跳跃(from Gamasutra)

想象个简单的情境,玩家准备奔跑后从一个方块跳到另一个方块。在这种情况下,如果场景中出现一个火球,使玩家在起跳前不得不停止奔跑。这样,玩家的跳跃起始状态就没有了原本的惯性,跳跃距离也就会有所改变。玩家也可以先往回走,再次通过奔跑来获得惯性,但可能这时又会出现其他影响因素。

长跳跃(from Gamasutra)

长跳跃(from Gamasutra)

现在,想想另外一种更简单的情况,玩家的跳跃没有受到火球的干扰。玩家可以全速奔跑,跳跃距离也会更长。这对玩家来说的确是好事,但是对AI设计师来说就变得困难了。现在,AI不仅要知道方块间的相对位置,而且还必须知道每个方块的玩家背景。AI需要知道玩家处在方块A上时的状态和情境,这样才能够计算要在多远的距离内放置方块B。

不幸的是,事情远没有这么简单。事实证明,仅仅知道玩家的状态和玩家在不同状态下的跳跃距离是不够的。想想另一个简单的情境,玩家从位置较低的方块跳到较高的方块上。在首个例子中,方块是静止的,玩家可以成功地完成跳跃。在第二个例子中,方块正在以某种方式移动,即便玩家意图着落的方块的最终位置处在跳跃范围内,方块本身的移动也会使玩家跳跃失败。

ValidInvalid(from gamasutra)

左:有效路径。右:无效路径(from gamasutra)

于是,我们就需要跟踪玩家背景、可能跳跃范围以及玩家同我们放置甚至角色着落的每个方块的互动。我们放置在关卡末端的障碍可能会影响到玩家在关卡前期的路径。这就是所谓的密集问题。我们在放置对象时应当考虑到其他对象的位置。

幸运的是,我们的设计AI有个伙伴,那就是玩家AI。假设我们有个部分完成的关卡,这个关卡到其当前终点仍具有可行性(游戏邦注:也就是说,玩家可以从关卡开始顺利导航至临时终点)。设计AI考虑放置一个新方块,以进一步扩展关卡。

它会询问玩家AI,新添加的方块是否同现有关卡的可行性发生冲突,玩家是否可以移动到这个新方块上。如果玩家AI认为可行,那么设计AI就会将方块放置在该位置,然后继续进行下去。否则,设计AI就会将这个方块放入回收站中,然后尝试其他的方案。我们不断重复这个过程,直到我们达到意想中的要求。

更明确地说,我们将所有可能关卡空间以树状的形式呈现出来,首个节点是个空白的关卡,随着更多方块的加入,子节点会等同于母节点。随后,设计AI遵从深度优先的树状搜索。

从理论上来说,最终搜索会达到这个树状结构的叶节点,也就是形成完整的关卡。

呈现出的结果就是大量的方块,组成一个可行的关卡。有了这个主体结构,我们就可以通过在关卡中添加障碍来让关卡变得更加丰富,同时确保不在玩家AI的成功通关路径上防止与之产生冲突的障碍。

现在,我们有了能够制作出可行关卡的运算法则,是时候将阐述的重点转向其他设计要点。

设计要求2:它必须有趣

如果无需满足其他要求的话,那么实现可行性这个条件事实上相当简单。只需要花不多于两分钟的时间来编程,我就能制作出全新的程序关卡生成器。下图便是它的输出样式:

最优秀的关卡(from gamasutra)

最优秀的关卡(from gamasutra)

每个关卡都是全新的,都是之前从未见过的,但完全没有趣味性!

所以,我们需要进一步改造我们的运算法则。我希望能够有制作有趣关卡的万能方法:一种可在关卡中呈现流动、空间、韵律和玩家期望的简单数学方法;一种将我们的无数可行关卡搜索限制在那些值得玩家体验的关卡中的简单运算法则。这种强大的方法或许存在,但现在我还没有找到。好消息时,这种问题可以得到解决和控制。

我遵从的普遍原则是,让设计运算法则尽可能地一般化。当面对执行细节中的技术选择时,我用利用参数来实现对执行的控制。同样的原则也运用于参数本身。参数应当是简单的布尔数学体系,针对每个特定关卡进行修改,还是应当在关卡的构建过程中不断变动?我不想在这两者之间做出选择,所以我们通过另一个参数来控制首个参数应当表现出的行为。

这种解决方案听起来有点抽象,所以让我来举些具体的例子。设计AI对我们的关卡树进行深度优先搜索。关卡树很大。每个节点有数百万个子节点。我们如何选择转向的分支呢?我们需要一个启发,而可行启发的数量相当多(游戏邦注:多数是毫无意义的)。

有些启发只是简单的偏好,用强制增加的限制来发挥作用。比如,比起绿色弹性方块而言,更偏好蓝色的移动方块。不同的启发会产生截然不同的关卡。有些偏好显得更为微妙。或许我想要个移动的方块,但是只希望它的移动轨道与关卡中其他移动方块有良好的关系。

我们也可以给我们的玩家AI强加限制条件,就像我们在关卡树上添加测试分支。或许我们会限制玩家AI,角色的奔跑速度永远不会小于半速。这会让关卡产生更好的流动感。我们还可以限制AI的动作范围,强迫它避开某些区域,从更顺畅的区域通过关卡。

方块应当设置为多宽?是否应当存在不必要的方块?方块的数量有多少?我们是否需要天花板?角色在跳起时能否撞到天花板?它是否应当对玩家的跳跃产生影响?如果我们想要在单个关卡中设置多种类型的方块,我们如何选择各种方块放置的地点?对于所有这些问题,都可以用参数(游戏邦注:往往是元参数)来提供主管答案。

运算法则包含数百个参数。在关卡制作过程中,每个参数都会与其他参数发生互动。目前,我还无法精确地知道如何改变能够清晰地展示出最终产品。这个系统过于复杂。有时,令人感到不可思议的是,关卡刚开始看起来毫无趣味性可言,可能看起来还不美观。经过最终调试阶段后,反而能够显露出关卡的价值。

设计要求3:它必须具有挑战性

无论关卡看起来多么有趣或是否有打通的可能性,如果关卡不能呈现出一定的挑战性,那么就会变得毫无用处。一个富有挑战性的关卡必须在太简单与太困难之间取得平衡(介于以下两图所示情况之间):

Easy Difficulty(from gamasutra)

Easy Difficulty(from gamasutra)

Hardcore Difficulty(from gamasutra)

Hardcore Difficulty(from gamasutra)

还记得我们需要通过数百个参数来让关卡更为有趣吗?那么,为了控制难度,我们需要数千个参数。与上文所述相同,许多参数能够回答我们的疑问。

方块间应当相隔多远?你在开始跳跃前应当离方块边缘多近?你必须使用全高度跳跃,还是可以使用半高度跳跃?关卡中是否有火球?有多少个?它们以多快的速度移动?玩家需要靠近火球多少距离才能跳过?它们是否都朝相同的方向移动,还是存在不同的水平方向,甚至是从随意方向向玩家袭来?

所有的火球是否会在同一时间发射火焰?如果我们设置10种不同类型的障碍会怎么样?它们应当如何混合和匹配?如果关卡中包含多次跳跃,而且玩家需要将更多的注意力放在正确地完成跳跃上,那么我们是否应当减少障碍回避的数量?是否应当设置安全点?玩家是否需要时刻停止和评估形势,还是被迫持续以全速奔跑?

制作所有这些参数是较为简单的部分。困难之处在于正确地设置。我曾经制作一个用于演变参数值的一般运算法则,但是当我意识到自己正在将一个很不清晰的优化方法放在一个愚蠢的限制引擎上时,我马上停止了自己手头的工作。反之,我使用大量的测试器来完成我的目标。经过3年和累积达数千个小时的投入,参数空间最终成为一个状况良好的领域,成果从最简单到最复杂均有。现在,有个参数可以管理所有的这些参数,那就是难度评级。

现在,玩家可以坐下来自行选择任意难度,或者让游戏为其选择适当的关卡。游戏可以通过许多方法为玩家选择挑战性适当的关卡。它可以根据玩家的死亡率来调整难度。你甚至还可以在游戏过程中改变关卡难度,但在实践中我们发现这会导致玩家的成就感减弱。

应当制作随机平台游戏的原因

我必须承认,我最初选择制作这个项目并没有特别的原因,只是想制作出比《马里奥》游戏更加疯狂的关卡。但是,在完成最初的原型构建后,我开始看到这个引擎拥有的巨大潜力。

程序生成能带来什么?

首先,单纯从设计师的角度来看,游戏设计过程变得更加灵活。通常情况下,游戏的物理和障碍都是预先设计的,与关卡其他元素保持一致。如果你回头修改物理或障碍物,你就会被迫修改整个关卡来适应这些改变。

从本质上来说,在进一步进行关卡设计前,你必须先确定物理。但是如果使用程序运算法则,所有这些都会发生改变。我可以在开发循环的任何阶段修改物理,而所有的关卡生成都会自动容纳这个新物理。事实上,我们甚至可以在发布游戏的同时公开物理编辑器,这样玩家就能够根据自己的需要修改物理,让设计AI为其制作关卡。

但是,更重要的问题是,随机关卡会带给玩家什么?很显然,它让游戏拥有丰富的再玩性,但是在我看来,这一点并非那么重要。以下是些许我喜欢程序运算法则的原因:

1、挑战。无论玩家的技术多好,运算法则都能够生成对她构成挑战的关卡。同样,如果玩家只是为了休闲,运算法则也会呈现与其技能相符的关卡。

2、新游戏类型。我们可以根据随机关卡来制作游戏类型,而并非只是利用关卡。比如,想象下《俄罗斯方块》那种无尽关卡的游戏。如果没有随机性,游戏挑战的只是玩家的记忆力。正因为有了随机性,才使玩家更注重锻炼自己的技能,而不是单纯提高记忆力。

3、可定制性。玩家可以修改运算法则中的参数,制作属于自己的关卡。这是个有待探索的广袤领域。

4、一致性。这个方面与可定制性相反,但却是个重要的工具。我们可以修改运算法则的参数,但仍然可以获得无限的关卡,关卡产生的感觉与原本无异,却仍然有新鲜感。比尔,我们可以修改关卡的“流动”,这样每个关卡都可以在不暂停或后退的情况下打通。维持这种一致性有助于吸引玩家,但也要把握好平衡,保持玩家的兴趣。

为什么不该制作随机平台游戏?

毫无疑问,随机关卡产生的体验与手工设计的关卡有很大的差别。我并不认为随机关卡有一定的优越性,但是我希望自己已经通过上述文章说服你,不应当歧视对待这种关卡。它们确实与普通关卡制作有所不同,它们或许不适合你希望呈现的游戏体验。对我们来说,我们正专注于制作紧凑、快节奏的街机体验,而我们的运算法则给我们带来了很大的帮助。如果你更加专注于谜题的解决,或在关卡中呈现独特的内容,那么随机关卡也可能不是你最恰当的选择。

当然,不要制作随机平台游戏还有个原因。

它做起来很麻烦。我们已经开发了3年时间,在平台游戏中这个时间算相当长的。单是探索性调查我就花费了4个月时间,而保持庞大调查结果的不断成长又花费了无数的时间。

但是,这些付出都是值得的。现在,我可以随时坐下来设计一个新的角色、确定他的奔跑速度、跳跃高度和摩擦等。然后我将其提交给AI,随后就可以找到针对我的新英雄设计的新冒险关卡。作为设计师,看到靠自己的努力呈现出的全新世界,那是种令人惊叹的感觉。我希望玩家也能够体会到我的这种感觉。(本文为游戏邦/gamerboom.com编译,拒绝任何不保留版权的转载,如需转载请联系:游戏邦

附录:伪代码示例

// Make an empty level, and add a start and end platform.

Level = EmptyLevel();

Level.AddBlock(StartBlock);

Level.AddBlock(FinalBlock);

// Create a feasible path between the start and end platform.

CompleteLevel(Level);

// Recursive method to take an incomplete level and make it feasible by adding more blocks.

bool CompleteLevel(Level)

{

// We will keep track of blocks we tried which turned out invalid.

ListOfBlocksTried = { };

// Keep trying different blocks until we find one that is valid.

// If we try too many blocks, perhaps the current level can not be made feasible, so return to the parent node.

while (ListOfBlocksTried.Length < 10)

{

// Choose a block to try and add it to the level.

NewBlock = Heuristic(Level, ListOfBlocksTried);

Level.AddBlock(NewBlock);

// Check to see if we can reach the new block.

if (PlayerAI.BlockIsReachable(Level, StartPos, NewBlock))

{

// If we can reach the exit platform, we are done

if (PlayerAI.BlockIsReachable(Level, StartPos, FinalBlock))

return true;

else

{

// Otherwise, recursively proceed down the tree. If the recursive call returns true, then our new blocks is a good choice.

if (CompleteLevel(Level)

return true;

}

}

// Either the new block wasn’t reachable, or it led to a level that couldn’t be made feasible with additional blocks.

// Either way, remove the new block and add it to our list of used blocks, so we don’t use it again.

ListOfBlocksTried.Append(NewBlock);

Level.RemoveBlock(NewBlock);

}

return false;

}

How to Make Insane, Procedural Platformer Levels

Jordan Fisher

So you want to make a procedural platformer. You want it to spit out levels on demand, and you want the levels to be awesome, challenging, and fun. You want the algorithm to be flexible, so that you can design a new obstacle or change the game physics and instantly have new levels created with your new content. You want it to spit out easy levels for new players, hard levels for core players, and brain melting insanity for leet StarCraft gods with APMs over 9000.

Oh, and all this insanity had better be possible to actually beat, or the players will organize a coup and destroy your reputation via Reddit, 4chan, and probably their personal blogs that they started just to pummel you.

Basically, you want a silicon imprint of Miyamoto and team that you can capture in a box of software to distribute to the masses.

That, or a well-trained level design AI. As lead programmer at Pwnee Studios, my job has been developing such an AI for our first platformer title.

Procedural content has done wonders in genres other than platformers. The expansive plains and dungeons in Diablo, the beautiful landscapes in Minecraft, the creature animations in Spore. Dungeon crawlers and sandboxes in particular have a long history of awesome procedural generation. There are side-scrollers with random levels too, such as the amazing Spelunky and Terraria.

In this piece, I talk more specifically about random levels for a faster paced style platformer (Mario, Sonic, Super Meat Boy). This is a relatively unexplored area for procedural algorithms, and is in many ways much more challenging. We want pixel-perfect jumps, death-defying brushes with lasers, and tunable difficulty for any skill level, all while guaranteeing the levels generated have solutions.

There are three things a good procedural algorithm needs to nail:

1. Feasibility. Can you beat it?

2. Interesting Design. Do you want to beat it?

3. Appropriate Skill Level. Is it a good challenge?

Satisfying any one of these is actually pretty easy. Satisfying them all simultaneously forms a very tight constraint problem. Feasibility, in particular, is a constraint that has greatly hampered efforts to make good procedural platformers; however, the other two requirements are just as difficult to perfect.

The first constraint, feasibility, is the most brittle requirement, so we will start there.

Design Requirement #1: It Must Be Feasible

There are simple techniques to guarantee a dungeon in Diablo has a path through it, analogous to how one assures that a generated maze has a solution. In a maze, the player has absolute control over their position, not considering the constraints imposed by walls. In a platformer, a player has a much looser control of her position and must factor in the game’s physics: momentum, gravity, friction, and so on. This greatly exacerbates the difficulty of the problem.

If you generate a maze with no solution, then you can knock down a few walls until a solution appears. If you generate a platformer level with no solution, it’s not at all clear how to fix things.

We need to make sure our levels are possible to beat. To satisfy this need for provable feasibility we rely on a very good computer player that we can hand off levels to. The player AI directly proves the levels are possible by beating them. This is easier to say than implement, but luckily good platformer player AI is a well-researched topic, with some notable implementations, such as this one. Implementing a good AI is non-trivial, but fairly straightforward.

Now that we have our awesome ninja AI, we can test our levels before throwing them at our players. Even better, if a player gets stuck on a level, we can let them watch the AI. The player can learn and improve, or at least suspend their incredulity.

We still have a problem, though. How do we actually make a feasible level in the first place? Like NP-complete problems, it seems like it’s easy to verify a solution, but very hard to find the solution to begin with. What we need is for the AI designing the levels to itself have some notion of what is and isn’t possible.

The simplest way to do this is to give the AI knowledge about the player physics. Starting with a player standing on a block, we can pre-compute all possible destinations a player may arrive at by jumping in different directions.

(Enumerating possible destinations.)

The AI then takes this information and uses it as a constraint. Each block it places must be within a certain range of some other block, dependent on the relative heights of the blocks. For simple player physics this is a good model, but if the physics also has momentum, friction, and variable jumping heights, then the pre-computation suddenly becomes a lot bigger. We need to know where the player can end up depending on every start configuration: running at half speed, running at full speed, doing a full jump, a half jump, etc.

(Short jump)

Imagine a simple situation where a player is about to run and jump from one block to another. In the first case, a passing fireball forces the player to stop before proceeding to jump. The player now jumps, starting from a standstill, with no initial momentum, retarding the full extent of the jump. The player could first backtrack to get a running start, but perhaps there is an advancing wall of doom impinging on the player.

(Long jump)

Now imagine a second, simpler case without the fireball. The player can run at full speed and can clear a longer jump. Good for the player, bad for the AI designer. Now it’s not enough for the AI to know the relative positions between pairs of blocks, the AI must also know what the player context of each block is. The AI needs to know what state and situation a player will be in when the player is on Block A, so that it can calculate how far away it can place Block B.

Unfortunately, things are even more complicated than this. It turns out it’s not enough to know just the player’s state and how far the player can jump in different states. Imagine another simple situation, where a player is jumping from a lower block to a higher block. In the first case, the blocks are stationary, and the player can successfully clear the jump. In the second case, the blocks are moving in such a way that even though the final position of the block when the player intends to land is within jumping range, the block itself intersects the player’s path earlier on in the jumping arc.

(Left: valid path. Right: invalid path.)

Suddenly we need to keep track of the player context, the range of possible jumps, as well as how all possible player trajectories interact with every block we place and even intend to place. It may turn out that an obstacle we place at the end of a level affects the player’s path at the beginning of the level. This is known as a dense problem. Dense in the sense that where we should place each object in our universe is intimately dependent on the location of every other object, forming a dense tangle of messy dependencies.

Luckily, our design AI has an ally: the player AI. Suppose we have a partially complete level that is known to be feasible up to its current endpoint (that is, a player can navigate from the beginning to the impromptu end). The design AI considers placing a new block, to extend the level further.

It queries the player AI as to whether the new block interferes with the feasibility of the existing level, as well as whether it’s possible for the player to even get to this new block. If the player AI gives the okay, the design AI places the block and continues. Otherwise, the design AI throws the block in the recycle bin and tries something else. We repeat this process until we have arrived at our desired destination.

More specifically we represent the space of all possible levels as a tree, where the first node is the empty level, and child nodes are equivalent to parent nodes with the addition of one more block. The design AI then follows a depth-first search of the tree.

Eventually (theoretically) the search arrives at a leaf node of the tree, which corresponds to a completed level.

The result is a collection of blocks, which we know comprise a feasible level. With this skeleton in hand we can spruce things up by adding obstacles throughout the level, making sure not to add any obstacles that interfere with the player AI’s successful path through the level.

Now that we have an algorithm to make beatable levels, it’s time to tweak it to hit our other design points.

Design Requirement #2: It Must Be Interesting

It’s actually pretty easy to satisfy feasibility if we don’t care about anything else. With slightly less than two minutes of coding, I whipped up a brand new procedural level generator. Behold its output:

(A most excellent level.)

Each level is completely new, never before seen — and completely uninteresting!

Okay, so we want a little more out of our algorithm than that. I wish I could say there was a magic bullet for making interesting levels: a mathematically elegant way to prescribe flow, spacing, rhythm, and player expectation within a level; a simple algorithm that constrains our search amongst the uncountable possible levels to only those levels worth playing. Such a powerful insight may exist, but I have not found it. The good news is that the problem is amenable to a brute force attack.

The general principle I’ve followed is to make the design algorithm as generic as possible. When faced with a technical choice amongst implementation details, I implement both with a parameter to control which implementation is active. The same principle applies to the parameters themselves. Should the parameter be a simple Boolean, fixed for any given level, or should it fluctuate throughout the construction of a level? I don’t want to make a decision between these two choices, so instead let’s make another parameter that controls how the first parameter should behave.

The solution sounds abstract, so let me give some concrete examples. The design AI performs a depth first search of our level tree. The level tree is massive. Each node has millions of children. How do we select which branch to traverse down? We need a heuristic, and there are an uncountable number of possible heuristics (most of which suck).

Some of the heuristics are simple preferences, pruning our tree by imposing additional constraints. For example, a preference for blue moving blocks over green bouncy blocks, which will produce decidedly different levels compared to the opposite heuristic. Some of the preferences are more nuanced. Maybe I want a moving block, but only if the phase of its orbit has a nice relationship to the other moving blocks in the level.

We can also impose restrictions on our player AI as we give it branches of the tree to test. Maybe we restrict the player AI such that it is never running forward at less than half speed. This leads to levels with a greater sense of flow. We can also restrict the range of motion of the AI, forcing it to avoid certain areas, leading to levels with paths that are more convoluted.

How wide should blocks be? Should there be unnecessary blocks? How many? Do we want a ceiling? Can you hit your head on it? Should it impose on the player’s jumps? If we want multiple types of blocks in a level, how do we choose between them at any given location, etc. etc.? For every question, there is a parameter (and often meta-parameter) to provide an arbitrary answer.

There are hundreds of parameters buried in the depths of the algorithm. Each parameter interacts with every other parameter through the level creation process, creating a seething, chaotic pool of coupled variables. I no longer have any idea exactly how changes to them will manifest in the final product. The system is too complex. Sometimes, mysteriously, levels will start looking very uninteresting, maybe ugly, or worse: not fun. The resulting debug sessions aren’t really about debugging so much as black magic.

Design Requirement #3: It Must Be Challenging

Ultimately, no matter how interesting a level looks or whether or not it’s possible to beat, a level is useless if it doesn’t provide a challenge to the player. A challenging level must hit the sweet spot between easy:

and masochistic:

Remember the hundreds of parameters we created to make our level interesting? Well, it turns out we need thousands of parameters to control for difficulty. As before, many of our parameters are answers to questions.

How far apart are blocks? How close to the edge of a block do you need to be before jumping? Do you have to use the full height of the jump, or can you use a half jump? Are there fireballs? How many? How fast are they? How close should a player ever have to get to one? Are they all moving in the same direction, or are there multiple axis-aligned directions (hard), or even multiple arbitrary directions (harder)?

Do fireball emitters all fire at the same time? What if we have 10 different obstacle types? How should they mix and match? If there is a lot of jumping in a level, and a player is more focused on completing jumps correctly, should we decrease the amount of obstacle evasion required? Should there be safe spots? Should players need to stop and evaluate, or should they be forced to continue running at full speed?

Making all these parameters is the easy part. The hard part is setting them correctly. At one point, I toyed around with a genetic algorithm for evolving the parameter values, but I stopped myself when I realized I was putting a dangerously opaque optimization method on top of a stupidly delicate constraint satisfaction engine. Instead, I captured an army of beta testers to do my bidding (in exchange for pizza and beer). Three years and thousands of man-hours later and the parameter space has finally been carved up into well-defined regions, from easy up to humanly impossible, with a continuous scale in between. Now there is a single parameter to rule them all: difficulty rating.

A player can now sit down and dial up a level to any difficulty, or she can just sit back and let the game pick levels for her. There are lots of ways the game can pick the correct challenge for a player. It can adaptively adjust the difficulty as it observes the player’s death rate, or it can provide a simple ramped difficulty of ever more difficult levels. You can even adaptively change the level difficulty on the fly, as a player plays it, although in practice we’ve found it decreases the player’s sense of accomplishment.

Why Should You Make a Random Platformer?

I must admit, I originally took on this project for no other reason than that I wanted to see insane Mario levels. Hectic, crazy, ridiculous Mario levels, densely filled with Bullet Bills and fire spinners and so on; but, after I got an initial prototype built, I started to see how much more potential the engine really had.

What does procedural generation give you?

First, purely from the perspective of a designer, the game design pipeline is made much more flexible. Normally the physics and obstacles of a game are designed, followed by the levels. If you go back and change the physics or how an obstacle acts, you are forced to tweak all your levels to accommodate the change.

Essentially you must lock in your physics before proceeding. With a procedural algorithm all that changes. I can change the physics at any point in the development cycle and all the levels will automatically take the new physics into account. In fact, we are even shipping a physics editor with our game so that players can tinker with the physics and have the design AI create levels for it.

More importantly though is the question, what do random levels give the player? The obvious answer is replayability, but in my opinion that is not that important. Here’s a list of a few of my favorites:

Challenge. No matter how good a player gets, the algorithm can make a level that will challenge her. Likewise, if a player is more casual, the algorithm can cater to her skill level.

New game types. We can make game types that depend on random levels, rather than just utilizing them. For instance, imagine an infinite string of levels strung together in a Tetris-like progression of difficulty. Without randomness, this game would devolve into a memorization challenge. With randomness, the focus shifts toward the player’s skill, rather than muscle memory.

Customizability. Players can tinker with the algorithm’s parameters, creating levels built to their specifications. There is a vast universe to explore.

Uniformity. This is opposite of customizability, but it’s an important tool. We can fix the algorithm’s parameters but still get an infinite string of levels, all very similar in feel, but different nonetheless. For instance, we can fix the “flow” of a level, so that each level can be beat without pausing or backtracking. Maintaining this consistency can help a player get in the zone, although it has to be balanced against trying to keep the player interested.

Why Shouldn’t You Make a Random Platformer?

There’s no doubt that random levels are going to yield a different experience than hand-crafted levels. I don’t claim that they are superior, but I hope I have convinced you that they need not be inferior. They’re different, and they may not be what you want for your game’s experience. For us, we are focusing on a very tight, fast-paced arcade experience, and we have been well served by our algorithm. If you are focusing more on puzzle solving, or Easter eggs, or unique gimmicks in each level, then random levels may or may not be the right tool for you.

There is one other good reason not to make a random platformer.

IT’S HARD. We’ve been in development for three years (which is a silly amount of time for a platformer). I spent four months on pure exploratory research and an unknown number of months maintaining the ever-growing monolithic beast.

But, it’s been worth it. I can sit down and design a new hero, specify how fast he runs, how high he jumps, friction, etc. Then I can hand it to the AI and I’m off playing a new adventure, engaging in levels designed exactly for my new hero, which I’ve never played before. As a designer, it’s an amazing feeling to see a new world unfold from your creation. I hope it is an amazing feeling for the players as well. (Source: Gamasutra)


上一篇:

下一篇: