作者：Ichiro Lambe

理想的过程内容生成（Procedural Content Generation，简称PCG）算法是，只需按下一个键就生成整个世界。

但那太困难了，所以我们还没达到那个境界。在本文中，我们提出的思路也许可以让读者离那个理想界境更近一步。

PCG是生成一切，包括背景、声音、剧情的算法。是个诱人的想法，对吧？

手动制作游戏世界既费时间又占用空间。自《Starflight》和《Elite》的诞生之日起，开发者们就致力于使用电脑完成无限的创意。

粗略地说，开发者们依赖PCG的原因有三：

1、使开发者能够更快地制作内容。

2、使游戏对玩家产生即时的反应。

3、减少游戏内容的占用空间。

我们还发现了一个隐藏的好处：

4、使开发者可以通过实验产生更多创意。

在本文中，我们将变谈论PCG的历史、问题、解决方法和我们发现的使用思路。我们的使用方法是在2009年开发简称为《Aaaaa!》的游戏和即将完成的简称为《Ugly Baby》的游戏时发现的。

成功使用于游戏开发的PCG

首先，有证据表明PCG确实可行实用，除了有时候看起来有些像飞行汽车——理论上成立，实际上不实用。

《Rogue》仍然是PCG运用于游戏制作的绝佳范例。这款大约完成于1980年的游戏，使电脑在玩家游戏时生成幻想的背景、隐藏的房间和弯曲的通道，并且将之先制作好的药水、敌人和武器填充于上述场景中。这种地下城风格的制作方法很成功（《Hack》、《Moria》、《Larn》、《Nethack》、《Angband》、《Dungeon Siege》、《Dungeon Siege II》、《暗黑破坏神》、《暗黑2》和《暗黑3》等等）也相以容易研究，所以许多开发者都用它制作《Rogue》式的游戏和许多用于《Rogue》式开发的物品。

在《Starflight》中，我们可以探索到的许多星系和上百个世界。各个星系都包含大量行星，所有行星都有自己的特征（游戏邦注：例如表面温度、重力、天气、大气、水）。

那时，尤其令人惊喜的是，玩家可以在星球模块中置入任何以上特征，使星球的自然环境发生变化，如增加曲折的海岸和起伏的高山、填充矿藏（铝、钼等）和根据 海拔和星球类型决定生物（固定的和活动的）的密度和种类。原版可以装入双面的5.25英寸的软驱中。Braben/Bell的经典之作《Elite》 （1984）的著名之处也许在于，创造了相当于8个星系的星球，让玩家在其中自由飞行和交易。更近的时候，《孢子》展示了程序性模型生成和动画。在游戏中，玩家可以调整生物骨头的长度和周长，增加四肢、眼睛、耳朵、翅膀等等，使创意成为玩法的一部分。

另外，数年以前，《kkrieger》让世界震惊了，因为这个射击游戏占用的磁盘空间甚至比本文还少（仅97280字节）。

PCG的使用贯穿了整个游戏的历史，并且今天仍然在使用。

内容制作工具中的PCG

在我们于2009年开发的游戏《Aaaaa!》中，我们想探索自动完成任务和辅助创意的工具。

你是否曾经一像素一像素地画图？或者，放置存储单元？这个过程很沉闷，所以开发者们为数字艺术家创造了更好的工具——现在，你只需要移动鼠标就可以填充那些像素点、画一个填充好的矩形、或渲染一段渐变的文本。

自动工具很重要，因为能节省时间——这些工具通常能够按我们的想法工作。点击画布上的一个点，然后点击另一个点，你就填充好一个理想的矩形了。

《Aaaaa!》是一款极限跳伞游戏，跳伞的地方是悬浮在半空中、高楼林立的未来波士顿。我们手动制作了许多内容，在游戏编辑器里，我们放置摩天大楼、大梁、走道、标牌、飞车和巨型土豆等。

从技术上说，自动工具不错，但我们最终厌倦了——做出来的东西开始让人感觉千篇一律，部分是因为这个工具让某些任务变得太简单，而其他的太困难。

例如，在关卡编辑器中放几座建筑再用得分板加以装饰，这很容易：

然而，创造一些更复杂的东西则需要手动放置对象，这种工作太乏味了。虽然我们可以容忍，手动放置对象（也许需要雇佣更多关卡设计师以及花更多时间），但仍希望有一个更好的解决方法，那就是自动化——例如，有一个脚本可以生成一纵队得分板，然后我们再把这些得分板拉成我们需要的形式。

下一步是旋转得分板并按照随机的曲线路径放置：

# Create 40 plates in a sinusoidal pattern:

for i in 0..40:

plate.x = sin(i*freq1)*amplitude

plate.y = sin(i*freq2)* amplitude

真正有趣的时候是，我们开始将很高的频率填入其中，于是产生了很荒唐的结果：

完全不能玩的东西冒出来了， 但有趣的东西也出现了，这出乎我们的意料。因为我们埋头于关卡设计，像这样的东西让我们的视野焕然一新。

这是关于“过程生成”的关卡的一个小例子，但不止一次，我们使用像这么简单的脚本做出了令我们开心的东西。这些改变了我们创造关卡的方式，对玩家提出了新挑战。

不久，我们有了一系列用于创造我们所谓的“关卡骨骼”的通用脚本。我们大量使用这些脚本制作让我们满意的东西（“啊！我们从来没想过这种事会发生。真是太棒了！”），然后手动完成关卡的剩余部分。

《Aaaaa!》的表现不错，除了其他奖项，还让我们获得了独立游戏节提名。所以，我们有了信心，决定在我们的下一款游戏中大胆尝试，我们将PCG用于所有的关卡设计。但毕竟，我们还算是体面的程序师，这么做未免太过简单了？

PCG是万灵药

我们的下一款游戏《Ugly Baby》玩起来很像《Aaaaa!》，但我们想让它在运行时，根据玩家提供的媒体，通过算法生成所有的关卡结构。这个媒体可以是音乐、视频甚至是一段《独立宣言》。我们将游戏形容为：

“与你最喜欢的鼓和贝司作战，或自由飞行于舞曲唱片的旋律之中。《Ugly Baby》用你的MP3音乐创造一个漂浮的世界，邀请你来战斗。”

我们的希望曾是（现在仍是），PCG可以让我们：

1、生成（本质上）无数的有趣的关卡，且比手动生成的《Aaaaa!》关卡更特别。

2、在运行时，根据玩家自己的媒体生成所有关卡内容。

3、允许玩家通过调整“关卡DNA”参与世界创造的过程，产生他们自己的关卡。

我们想制作一种可以读取音乐的脚本，然后产生类似《Aaaaa!》且带敌人的关卡。本以为我们对漂浮建筑和生成艺术的理解可以让这个过程变得很简单，然而，在我们才开始基础工作以前，一个9个月的项目已经变成了24个月。

结果，我们发现了四个主要问题：

1、手动制作的优势是PCG的弱点。

算法和手动制作的内容往往优势互补。如果你要制作大量的山体，且想看看经过侵蚀后的样子，那么算法比手动调整好。虽然你可以也花上一整天的时间自己动手雕刻，再花一点时间在侵蚀工具中执行，但手动操作会让你尝试到一些不同的东西。

另一方面，如果你想在山洞的入口处增加一些树木，手动完成通常比算法简单。如果你想在沙滩上写“HELP”，手动选择工具然后写字更容易些。我们认识到这点是经过了艰难的过程：

第1步：写一个生成关卡框架的算法。（1小时）

第2步：测试后发现建筑物之间的距离太远；增加密度，还使了一点小技巧防止它们重叠。（15分钟）

第3步：测试后发现完全行不通；修改路径使建筑物迂回一些。（15分钟）

第4-9步：执行、重复。（各15分钟）

第10步：若上述方法行不通，手动调整反而更简单。（5分钟）

所以，我们陷入了一种工作模式，先写了一个不错的脚本，无尽地调整，然后达到局部最大值：初始脚本可以生成一种类型的脚本布局，我们花了数个小时寻找其中最好的排列，而不是检查其他地方。我们随后发现“无聊”和“有趣”之间的差距很小，但要实现二者之间的跨越，即对算法做实验或在算法中扩充有趣的细节可能很费时间。

解决方法：有时候，实验最好是手动操作；我们可以从制作的东西中吸取经验教训，然后用算法模拟手动做出来看上去不错的东西。

2、制作重复的内容很容易。

从Alex Norton的帖子AltDevBlogADay中借用一段话：

为什么世界有边界？程序生成代码在过去25年并未改变多少。人们仍然局限于使用碎片、方块和斑点做所有东西，这也太雷同了，简直就像程序生成的内容。对于许多程序师而言，看起来其实就是程序生成的。

如果我们不认真看，我们不会发现我们一次又一次看到的东西都是相同的。例如，在《Ugly Baby》中，玩以下关卡前15秒还觉得有趣，之后就无聊了：

因为每道关卡大约是5分钟长，这意味在整个关卡过程中，我们得切换好几次。一个常用的解决方法是，定期地置换出不同的算法，但那样做可能比较不谐调——想象一下在边界上突然中断的PCG森林。另一个解决方法是扩充算法，在沿途放上新花样，使不同对象之间渐进地改变，但我们又遇到问题了，这也是下文要说到的。

3、PCG算法变得更加有表现力，但复杂的算法看似越来越与设计脱节。

生成简单关卡的算法很容易写——但因为我们做的东西更复杂了，执行也变得更加困难，并且这种困难是不成比例的。例如，在《Ugly Baby》中，起初我们成功地写出在地图上分散建筑物的脚本。然而，扩充脚本时发生了以下对话：

“看起来很棒；如果我们将这些聚为群集会怎么样呢？”

“好吧，但太规律了，还要混杂一点。”

“添加一些得分板、隧道、移动的平台和扇叶。”

“哎呀，得分板和建筑物交叉了。移开一点。将扇叶主在隧道的中间，除非当时还有移动的平台，或如果之前隧道中间就有扇叶，因为那样太无聊了。”

“好吧，现在，什么都不管用了。”

相同地，看到3D角色在草地上来回走动，游戏开发新手会说：“嘿，我会做MMORPG了，真简单！”我们认为，如果简单的脚本能产生有趣的结果，我们只需要不断地用适当的东西拓展算法就行了。但是，有趣的建筑物开始需要维持机制和认真设计的其他内容。

4、有趣的PCG通常产生的结果是1）愚蠢的和2）无聊的内容。

我们见过的最简单的随机名称生成器如下：

# Generate random letters, yo:

for i in 1..random_number():

name += random_ character()

它有可能生成任何你能想象得到的幻想的、科幻的或者宝宝的名字——假如让它重复足够的次数，它有可能输出“Captain Rock McSpectacular”这样的了不起的名称。但更多时候，它产生的是像“ergihwe`=-ufaw38o72wenufse”这样对你完全无用的垃圾。

在《Ugly Baby》中，我们做了类似的东西——一个相对不受约束的算法，产生随机方块，然后围绕中心轴产生一个简单、可玩的隧道。这个算法过程如下：

1、从库中选择一个随机3D模型（方块、三角形、曲线）。

2、选择一个数字N和一个数字M。

3、创造N个平均间隔的环状模型，各个环状中有M个模型实体。

4、返回第1步。

在第一次计算中，结果是：

看上去很有趣，确实有用——它是个隧道！再次运行相同的脚本，生成了一个有趣的序列，有毛发、手指样的东西，伴随着另一个隧道：

也很有趣，出人意料，仍然有用。玩家可以在其中飞行。第三次计算：

这次产生了一个完全不能通过的路径，组成的多边形太多，帧速率跟不上。虽然很漂亮，也许有些时候能用上，但没有形成隧道。

解决方法之一是，限制参数。在刚才那个命名生成器的例子中，也许我们可以构思一句语法（辅音+元音+辅音+元音+辅音），或保存一份常用的姓氏和名称，然后把它们串起来（例如“Billy Margaret Smith”）。类似地，在我们的隧道例子中，我们大概只需要创建一些用不多于某个数量的方块组成的隧道，或限制多边基本方块的数量。

另一个问题是：

结果，我们挑选了一些有趣的分支，有可能让我们自己都感到惊喜（再见啦，Captain Rock McSpectacular）。

我们很快用特例补充好算法，但算法无法执行。

构成关卡的模块化方法

在我们开发《Ugly Baby》的三年时间里，我们并没有解决所有问题，但我们用简单的、模块化的概念组合成复杂的东西时，我们收获了一些成功的经验。

以编程的方式为《Aaaaa!》制作关卡骨骼时，我们成功了，这让我们感到愉快，所以我们返回查看根源。制作看上去有趣的东西其实相当容易，就是重复简单结构。举例说明，一个由方块组成的球体：

这一次，不是把算法变得复杂，而是重复修改输出的结果：

1、生成方块组成的球体。

2、给块赋予颜色（如，调整饱和度，然后根据对象围绕中心轴的位置来选择色相）。

3、改变方块的穿插。

4、只具现化在球体的某个部分的对象。

最终的结果完全不像个球体：

这个简单的概念让我们感兴趣的有三点：首先，我们可以填入稍微不同的参数，就得到非常不同的几何体；其次，在《Ugly Baby》中，我们可以把这些参数与音频关联，这样关卡的外观就会随着音乐改变；最后，修改路径独立于基础结构，所以我们只需对一些方块使用上述方法就可以得到完全新奇而（也许）有用的东西。

有希望，所以我们把这个办法规范了一下。《Ugly Baby》的关卡生成器由三个模块组成：

1、定序器是产生球体、柱体、网格、圆柱等东西的模块。

2、选择器返回满足一系列条件的所有对象，如位于飞机的某一侧，或大于面包箱的所有对象。

3、更改器根据对象的特点使之发生变化。例如，根据位置改变颜色或根据方向缩放比例。

以上三个模块生效的结果如图：

第1步：玩家会沿着线性路径飞行，所以我们先简单地制作一个柱体，其组成的方块沿着落下的中心轴。

代码：

# Instantiate the column:

sequencer_column = sequencer.Column()

queue = sequencer_column.iterate()

第2步：这个关卡隧道有点像铁路射击游戏，所以我们再做一个更像隧道的隧道。我们将简单柱体置换出六个。这需要设置一些基本的参数，如方块与方块之间的垂直距离和围绕着中心轴的方块柱体的数量。

代码：

# Instantiate the cylinder:

sequencer_cylinder = sequencer.Cylinder(layer_delta=4, blocks=6)

queue = sequencer_cylinder.iterate()

第3步：改变定序器生成的各个方块的大小。

代码:

# Change every piece’s scale:

mutator.scale(queue, [1, 4, 1])

第4步：我们写了一个更改器，它可以使方块的一个面朝向Z轴，然后把这个属性赋予所有方块。

代码：

# Turn pieces to face the player’s falling (z) axis:

mutator.face_axis(queue)

第5步：一个“Every-N”的选择器节点可以把填入其中的每N块抓出来。这里，我们希望每四个块选择一次，然后用更改器将其变为红色。

代码：

# Get a list of every 4th pieces that comes into the queue:

every_4th_piece = selector.every_n(queue, 4)

# Turn those pieces reddish:

mutator.set_color(every_4th_piece, [255, 32, 0])

第6步：最后，在垂直距离上调整为曲线方向。

代码：

# Pan from -45..45 depending on a piece’s position along the player’s falling axis:

mutator.cyclic_rotate(queue, freq=0.1, low=[-45, 0, 0], high=[45, 0, 0])

从这里开始，我们可以做到以下事情：

1、因为这些效果是各自分离的，我们可以将对象置换进或置换出。这种模块化操作可以帮助我们尝试新的东西和新的图案。

2、《Ugly Baby》的画面与音乐相关。我们知道在音乐播放到某个点时玩家的所在，我们可以根据这一点，看音频信号构建对象。

例如，在音乐的高音部分压缩隧道或根据声音信号的高频部分改变块的颜色。

3、我们可以允许玩家调整某些值来创造他们自己的关卡。比如，他们不想要6根柱体，而要2根呢？或者，如果他们想让方块更肥大一点呢？

更改器参数上的小调整引起的关卡变化并不大。这里，我们只演示了柱体的数量和大小，以及组成柱体的基础模型：

我们又做了一些变体（如，下图左边的网格状的图案），然后组合起来（下图右边的网格再加上环状物）。

对于抽象物体，这个方法很管用，但我们还想看看对于更有组织的结构，这个方法是否行得通。

用于有机模型制作的模块化方法

在《Ugly Baby》中，我们用更有机的模型补充抽象的几何关卡设计。也就是说，我们在Maya中创造了一个图像的、基于节点的东西，叫作DING。以下是制作一只昆虫的过程。

我们首先生成一个圆柱。上图是两张截图——第一张是显示了图解（左边的节点创造了一个圆柱；右边的节点显示圆柱）。

第二张图显示了结果模型。DING创造几何体，Maya显示几何体（之后将它输入有文件格局（FBX））。

之后我们把圆柱调整成近似锥形体，有些地方做得肥大一点，有些地方做得瘦小一点。上图所示的是锥形体的侧视图——我们手动调整，先挤出胖的部分，再缩小面，再挤出细长的脚。

我们翻转节点（红色），将其调整成垂直方向，然后添加“环”节点，这样就做成了带6足的环状物。

我们再添加球体结点，然后合并（布尔合并结点）到环状物上。这个东西有些像蜘蛛了。

在我们做尖尖的脚以前，要添加整个物体的轮廓线结点。这条轮廓线夹在整个模型的中间。我们还要对模型再细分，使它更平滑一些。

最后，沿着垂直轴压低前部。这东西现在看起来有点像一只遍虱。

因为模型不是在运行时生成的，所以它不会对音乐产生反应，而这是关卡构成的方式。但它确实达到了我们的两个目标，一方面它使我们能够快速制作有趣的内容（这个方法对我们团队当中不熟悉Maya的成员很管用），另一方面，它使我们可以做大量实验。因为所有这些操作都是无损的，所以我们可以增加或减少环状物的足数目，改变周线外形（如下图所示），或甚至置换出柱体或球形基本体。下一步，我们要做的是随机化。

值得注意的是，基于图解的工具用途很多。我们对《Ugly Baby》的关卡做抽象处理，然后实体化敌人，但在2011年的《Aaaaa!》，我们想要更写实的材质，因此我们使用了Spiral Graphics出品的基于节点的Genetica（游戏邦注：这是一个制作无缝材质的编辑器）。

结论

虽然“模块化”的方法并不算新鲜，且联系节点也没有解决所有关卡生成的问题，如交叉对象或无意义的输出，但它帮助我们提高了效率，使我们在挑出无用的部分后仍然能得到有用的输出结果。

同样地，我们能够利用PCG的优势（更快的内容生成、动态内容、更小的占用空间和增加创意）同时回避它的缺点（避免大量代码，使代码便于管理等）。虽然PCG不是万灵药，但我们认为我们可以利用它成功地制作有趣的内容。

我们不是PCG的专家，但我们希望本文能给读者提供有益的参考。（本文为游戏邦/gamerboom.com编译，拒绝任何不保留版权的转载，如需转载请联系：游戏邦）

Procedural Content Generation: Thinking With Modules

by Ichiro Lambe

The platonic Procedural Content Generation algorithm allows you to create entire universes by pressing a button:

We’re not quite there yet, because it turns out to be a tough problem, but in this article, we wanted to offer a few thoughts that might bring us one step closer.

Procedural Content Generation (PCG) — the algorithmic creation of anything from background scenery to symphonies to storylines — is a compelling idea, right?

Manually creating gaming worlds takes time, and storing it all takes massive gobs of space. Since the days of Starflight and Elite, developers have worked towards getting computers to the point where they can be boundlessly creative.

Broadly, developers often lean on PCG for three reasons:

It allows us to empower creators to produce content more quickly.

It allows a game to react to players in real-time in ways otherwise impossible.

It allows us to reduce the on-disk footprint of content.

We also find that there’s another, hidden benefit:

It allows us to become more creative through experimentation.

In this article, we’ll talk about PCG’s history, problems, solutions, and methods we’ve discovered while using it in our 2009 title, AaaaaAAaaaAAAaaAAAAaAAAAA!!! — A Reckless Disregard for Gravity (Aaaaa! for short) and our upcoming 1… 2… 3… KICK IT! — Drop That Beat Like an Ugly Baby (aka Ugly Baby).

Spoiler: We favor a modular, graph-based system to benefit from the upsides of PCG while mitigating some downsides. That’s it in a nutshell. You are now free to either read the rest of the article or become the leader of a pack of Alaskan Malamutes.

Successes in Games

First off, there’s some evidence that PCG is actually viable/useful, despite sometimes seeming like the flying car — forever in sight, but never (yet) practical.

Rogue! It’s still a great example of procedurally generated content in games. Created around 1980, the game empowered the computer, itself, to generate a fantasy world as you played, building subterranean rooms and twisty passages and populating them with (pre-created) potions, enemies, and weapons. This style of dungeon creation is successful (Hack, Moria, Larn, Nethack, Angband, Dungeon Siege, Dungeon Siege II, Diablo, Diablo II, and Diablo III, to name just a few), and relatively well-investigated, with many developers creating roguelikes and many resources for roguelike development.

We couldn’t do an article on PCG without talking about Rogue, but we’re using a screenshot from Temple of Apshai Trilogy for the ST instead, just to be different.

On a galactic sale, Starflight (1986) and its sequel gave us dozens of star systems and hundreds of worlds to explore. Each system contained a number of planets, and each planet was assigned a number of characteristics (surface temperature, gravity, weather, atmosphere, hydrosphere).

What was particularly amazing for the time was that you could land your planetary module on any number of these and explore winding coastlines and mountains, populated by mineral deposits (aluminum, molybdenum, and a dozen others) and living organisms (sessile and mobile), with density and type depending on elevation and planet type. The original could all fit on a double-sided 5.25″ floppy. Braben/Bell’s classic Elite (1984) is, perhaps, even better known for creating eight galaxies worth of planets you could fly and trade within.

Starflight 2 even included villages you could trade with.

More recently, Spore demonstrated procedural model generation and animation. Here, players could tweak the length and girth of a creature’s bones, add limbs, eyes, ears, wings, and so forth, making creativity a part of gameplay.

Creature generation in Spore.

And .kkrieger wowed the world some years back by stuffing an entire first-person shooter into less disk space than this article.

.kkrieger, which uses only 97,280 bytes on disk.

PCG’s been used throughout the history of games, and is still being used today. Surely, it should be used for everything…

…right?

PCG In Content Creation Tools

In our 2009 title, Aaaaa!, we wanted to explore both tools that automated tasks and those that aided creativity.

Aaaaa!, with PCG textures and level both PCG-created, then hand-modified.

Have you ever painted an image pixel by pixel? Or perhaps by POKEing memory locations? It’s tedious, so developers created better tools for digital artists — nowadays, you can move your mouse to light those pixels up, draw a filled rectangle, or render gradient-filled text.

Automation is important, as it saves time — these tools generally do exactly what we expect them to. Click at one point on the canvas, then click at another. You now have exactly the filled rectangle you expected.

Aaaaa! is a BASE jumping game that took place amongst the buildings in a floating futuristic Boston, Massachusetts. We created much of this content by hand, placing skyscrapers, girders, walkways, signage, flying cars, and giant potatoes within our in-game editor.

The tools were technically fine, but we eventually, collectively, hit a rut — things started to feel samey, in part because the tools made particular tasks easy, while others were difficult.

For example, it was easy to drop a few buildings into the level editor, and decorate them with scoring plates:

However, creating something more intricate required tedious hand-placement of objects, and while we could have sucked it up and placed everything manually (perhaps hiring more level designers for more hours), a better solution involved automation — for example, a script that simply generated a column of scoring plates, which we’d then drag into patterns.

A natural next step was to tweak and place the plates along randomized sinusoidal paths:

# Create 40 plates in a sinusoidal pattern:

for i in 0..40:

plate.x = sin(i*freq1)*amplitude

plate.y = sin(i*freq2)* amplitude

The real fun came when we started plugging high frequencies into them to create something ridiculous:

Things that were completely unplayable popped up, but so did some things that ended up being fun in ways we didn’t expect. It’s this bit that really interested us, because we were neck-deep in level design, and things like this provided a fresh look at things.

This is a trivially simple example of a “procedurally generated” level, but more than once, using simple scripts like it, we encountered things that made us grin. These changed the ways we built levels, and suggested new challenges for players.

Soon, we had a small collection of utility scripts that would create what we called “level skeletons”. We’d abuse them to come up with things that delighted us (“Ah! We never intended for that to happen. That’s neat!”), then hand-create the rest of the level.

Aaaaa! did really well for us, bringing us an IGF nomination, among other awards. So, buoyed by the confidence we gained here, we decided to throw caution to the wind: in our next game, we’d use PCG for all level design. After all, we’re decent programmers… Wouldn’t it be easy to just program everything?

(Spoiler: It was not.)

PCG is a Panacea That Will Cure Leprosy

Our next title, Ugly Baby, would play much like Aaaaa!, but we wanted it to generate all of its level structure algorithmically, at runtime, based on player-supplied media. This media could be anything from music, a la Audiosurf or Beat Hazard, to a video to a block of the Declaration of Independence. We describe the game like this:

“Battle your favorite drum ‘n’ bass track, or relax as you fly through that trance album. ‘Ugly Baby’ takes your MP3 music and creates floating worlds for you to fight through.”

Our hopes were (and still are) that PCG would allow us to:

Generate (essentially) an infinite number of interesting levels that were more distinct than the hand-generated ones in Aaaaa!

Generate all level content at runtime based on the player’s own media.

Allow players to participate in the world creation process by tweaking “level DNA” and “growing” their own levels.

We wanted to create scripts that read in the music and spat out Aaaaa!-like levels with enemies, figuring that our understanding of floating architecture and generative art would make it simple. As it happened, a nine-month project turned into 24 months before we even began to get our footing.

We ended up hitting four major problems:

1. Manual creation’s strengths are PCG’s weaknesses.

Algorithms and hand-created content often have complementary strengths. Algorithms can beat hand-tweaking if you have an enormous mountain and want to see what happens if it undergoes erosion. While you could easily spend an entire day sculpting it by hand, running it through an erosion tool will take moments, and allow you to try different things.

On the other hand, if you want to add a few trees around the entrance to a cave, it’s usually easier to just plop a few down by hand and nudge them around than to script that. If you want to carve the world “HELP” in a beach, it’s easier to just select a tool and draw the word. We learned this the hard way, through this process:

STEP 1: Create an algorithm that generates a level skeleton. (1 hour)

STEP 2: Test to determine that the buildings are too far apart; increase the density but finagle it so that they don’t overlap. (15 minutes)

STEP 3: Test to determine that that didn’t work at all; skew the path so that the buildings weaver a bit. (15 minutes)

STEPS 4-9: Rinse, repeat. (15 minutes apiece.)

STEP 10: Curse that the approach isn’t working, when it would be so easy to tweak by hand. (5 minutes.)

So, we’d get into a mode where we created a promising script, tweaked endlessly, and hit a local maximum: the initial script would establish a certain type of level layout, and we’d spend hours exploring the best permutations of that rather than looking elsewhere. We’d later find that the distance between “not fun” and “fun” was small. But it can be time-consuming to experiment with an algorithm or to augment it to include interesting details.

Solution: experimentation is sometimes best done by hand; we can then learn from what we create, then have the algorithm mimic something that turns out looking good.

2. It’s easy to create repetitive content.

We’ll borrow a quote from Alex Norton’s AltDevBlogADay post:

Why have world borders at all? Procedural generation code hasn’t changed much in the last 25 years. People are still stuck using fractals and diamonds and blobs to do everything, which becomes repetitive and quite simply looks like procedurally generated content. To any programmer looking at it, it virtually smells of procedural generation.

If we’re not careful, we see the same stuff over and over again. For example, in Ugly Baby, either of the below levels is interesting for about 15 seconds, after which point they become tedious:

Since levels were each about 5 minutes long, that meant we’d want to switch things up a few dozen times over the course of a level. One common solution is to swap out different algorithms periodically, but that can be jarring — imagine a PCG forest that ended sharply on a boundary. Another is to augment the algorithm with tidbits of new stuff along the way, and gradually morph between things, but we ran into problems with complexity, as we touch on in the next point.

3. As PCG algorithms become more expressive, they seem to become disproportionately more complex to design.

It’s really easy to create an algorithm that generates a simple level — but as we made things more complex, implementation became disproportionately more difficult. For example, in Ugly Baby, we had early success creating a script that scattered buildings around a map. However, augmenting that resulted in this internal conversation:

“That looks great; what happens if we group those in clusters?”

“Okay, but they’re now too regular. Mix them up a bit.”

“Let’s add some scoring plates, tunnels, moving platforms, and fan blades.”

“Oops, the scoring plates are intersecting the buildings. Move them apart. And center the fan blades in the tunnels except when preceded by a moving platform, but not if there were fan blades centered in tunnels before, because that gets boring.”

“Well, now, nothing works.”

In the same way that a neophyte game developer can see a 3D character walking around a grassy terrain will say, “Hey, I can make that MMORPG, easy!”, we figured that if simple scripts created interesting results, we could simply extend them ad infinitum to create proportionally more awesome ones. Interesting structures start to require support mechanisms and carefully engineered exclusions.

4. Interesting PCG often creates either 1) stupid or 2) boring content.

The simplest random name generator we’ve seen looks like this:

# Generate random letters, yo:

for i in 1..random_number():

name += random_ character()

It’s possible to generate every awesome fantasy, sci-fi or baby name you can possibly imagine — given enough iterations, it’ll come up with “Captain Rock McSpectacular,” which is a great name. But it’ll mostly generate junk like “ergihwe`=-ufaw38o72wenufse,” which is completely useless to you. Probably.

In Ugly Baby, we did similar — a relatively unconstrained algorithm that spat random pieces around a central axis created a simple, playable tunnel. The algorithm went something like this:

Pick a random 3D model in our library (cubes, triangles, curves).

Pick a number N and a number M.

Create N evenly-space rings of the model, with M instances of the model in each ring.

Go back to step 1.

On one run, that produced this:

Visually interesting, and actually useful to us — it was a tunnel! Running the same script a second time generated an interesting sequence of hairy, finger-looking things, followed by another tunnel:

Also interesting and unexpected, and still useful. It was something the player could fly through. A third run:

This produced a completely impenetrable path comprising enough polygons to tank the framerate. It was pretty, and potentially useable elsewhere, but didn’t compose a tunnel.

One solution to this problem is to start constraining parameters. In the earlier example of the name generator, perhaps we construct a grammar (consonant + vowel + consonant + vowel + consonant), or to keep a list of common first names and surnames, and simply string those together (“Billy Margaret Smith”). Similarly, in our tunnel example, perhaps we only construct tunnels out of pieces that are less than a certain volume, or limit the total number of high-poly base pieces.

The (sub-)problem with this is:

We end up clipping out some interesting branches that might surprise/delight us (goodbye, Captain Rock McSpectacular).
We quickly fill our algorithm with special cases, and it becomes impossible to manage.

A Modular Approach to Level Structure

In the three years we’ve been working on Ugly Baby, we haven’t solved all of these problems, but we’ve had some success when combining simple, modular concepts to produce complex results.

Early successes in programmatically creating level skeletons in Aaaaa! were a boon, so we went back to those roots. It’s actually pretty easy to create visually interesting things by taking simple structures and iterating on them. Take, for example, a sphere made out of cubes:

This time, instead of adding complexity to that algorithm, we took the output and iteratively modified it:

Generate the sphere of cubes.

Apply color to the pieces (for example, by saturating them, and selecting a hue based on the object’s position around a central axis).

Change the cubes to crosses.

Only instantiate the objects around a certain portion of the sphere.

The end result doesn’t look like a sphere at all:

What’s so interesting to us about this simple concept is threefold: first, we can feed slightly different parameters in and get significantly different geometry out; second, in Ugly Baby, we can tie those parameters to the audio stream, so that the music drives the level’s appearance; and finally, the modification pass is independent of the base structure, so we could just as easily apply the above to a grid of cubes and get something completely novel and (possibly) useful.

This was promising, so we formalized this. An Ugly Baby level generator consists of three types of modules:

Sequencers are modules that create things — a sphere, a column, a grid, a cylinder, and so forth.
Selectors return a set of all objects that satisfy a set of conditions, such as everything on one side of a plane, or all objects bigger than a breadbox.
Mutators apply changes to objects, typically based on its properties. Examples include changing colors based on position or scaling based on orientation.
Here’s all that in action:

Step 1: The player flies along a linear path, so let’s start by simply creating a simple column of blocks along the falling axis.

Code:

# Instantiate the column:

sequencer_column = sequencer.Column()

queue = sequencer_column.iterate()

Step 2: This level’s like a rails shooter, so let’s create something that looks more like a tunnel. Let’s swap out the single column for six of them (essentially the edges of a cylinder). This takes some basic parameters, such as the vertical distance between blocks and the number of columns of blocks around the axis.

Code:

# Instantiate the cylinder:

sequencer_cylinder = sequencer.Cylinder(layer_delta=4, blocks=6)

queue = sequencer_cylinder.iterate()

Step 3: Apply a scale to every piece that the sequencer generates.

Code:

# Change every piece’s scale:

mutator.scale(queue, [1, 4, 1])

Step 4: We wrote a mutator node that simply reorients a piece such that one side faces the Z- axis, and apply that to all pieces.

Code:

# Turn pieces to face the player’s falling (z) axis:

mutator.face_axis(queue)

Step 5: An “Every-N” selector node simply grabs one out of every N pieces fed into it. Here, we want to select every fourth piece and use a mutator to turn them red.

Code:

# Get a list of every 4th pieces that comes into the queue:

every_4th_piece = selector.every_n(queue, 4)

# Turn those pieces reddish:

mutator.set_color(every_4th_piece, [255, 32, 0])

Step 6: Finally, let’s orient them sinusoidally over vertical distance.

Code:

# Pan from -45..45 depending on a piece’s position along the player’s falling axis:

mutator.cyclic_rotate(queue, freq=0.1, low=[-45, 0, 0], high=[45, 0, 0])

From here, we can do a number of things:

1. As each of these effects is separated out, we’re able to swap things in and out. This modularity helps us try new things and new patterns out of old ones.

2. Ugly Baby is about a connection between visuals and music. We can take advantage of the fact that we know where the player’s going to be at any given point in the music, so we can take a look at the audio signal and construct things based on that.

For example, we’ve done this by constricting the tunnel during louder parts of a song or changing piece colors based on the high frequency components of the audio signal.

3. We can allow the player to tweak some of these values to create their own levels. What if, instead of six columns, they want two? Or, what if the pieces should all be extremely fat?

Small changes in mutator parameters led to understandable but tangible changes in the level. Here, we just played with number and scale of the columns, along with the base model that comprises the columns:

We then created a vocabulary of these (e.g. a grid of objects, below, to the left), and combined them (a grid plus a ring of objects, lower right).

That’s worked well for more abstract things, but we also wanted to see if this worked with more organic structures.

Modules in Organic Model Creation

In Ugly Baby, we complement the abstract, geometric level design with models that were more organic. To wit, we created a graphical, node-based utility within Maya, called DING. Here’s the process of creating an insect within that environment.

We begin by generating a cylinder. Above are two screenshots — the top one displays the graph (the left node creates a cylinder; the right node displays it).

The lower image displays the resulting model. DING creates the geometry, and Maya displays it (and later exports it to FBX).

We then apply a (non-destructive) taper to the cylinder, making it fatter in some places, and thinner in others. The graph you see is the taper’s profile — we set this manually, starting out fat, pulling in at the joint, and eventually tapering at the foot.

We toss in nodes (in red) to reorient the piece vertically, then add a “ring” node, which creates a ring of six of the shape.

We add in a sphere node, then merge that (boolean union node) with the ring. It’s beginning to look something like a spider.

As we tapered the leg before, we now add a contour node to the entire thing. This pinches the whole model’s middle. We also subdivide the mesh to make it smoother.

Finally, let’s squash the heck out of the front, contouring along the perpendicular axis. The resulting shape looks something like a tick.

As the model’s not generated at runtime, it’s not reactive to the music, the way the level structure is. But it does satisfy two of our goals, in that it has allowed us to create interesting content quickly (this approach is accessible to our team members not familiar with Maya), and it allows us to experiment a great deal. Since all of these operations are nondestructive, we can increase decrease the number of legs in the ring; change the contour profile (below); or even swap out the cylinder or sphere primitives and see what happens. Next on our Christmas wishlist is a “randomize” button.

It’s worth noting that graph-based tools exist for all sorts of uses. We went abstract for Ugly Baby’s level design and organic for the enemies, but in our 2011 follow-up to Aaaaa! (called AaaaaAAaaaAAAaaAAAAaAAAAA!!! for the Awesome), we wanted realistic textures, for which we went with the excellent node-based Genetica by Spiral Graphics.

Conclusion

While “going modular” isn’t new, and connecting nodes together hasn’t magically solved all our level generation problems of intersecting objects or nonsensical output, it has helped us become more productive and “clip off the degenerate branches” of content generation while keeping the useful output.

As such, we’ve been able to retain PCG’s strengths (quicker content generation, dynamic content, smaller on-disk footprint, and enhanced creativity through happy accidents) while mitigating their downsides (avoiding a spaghetti mass of code makes things more manageable, etc.). And while PCG isn’t a panacea, we think we’re using it to successfully create compelling content otherwise inaccessible to us.

So, that’s that! We’re not PCG experts, but we hope that this article has added a few more data points in your quest for the flying car.(source:gamasutra)