《暗黑破坏神1》是1996年经典的骇人风格。 这是将群众引入流氓行为的首次成功尝试之一，直到那时，流氓字符都以ASCII艺术形式出现。 游戏产生了几个续集和许多模拟。 她以幽暗，阴郁的气氛而闻名，随着玩家下沉进入特里斯特拉姆（Tristram）市地下的地牢，她的身形变得越来越浓厚。 对于我来说，这是最早生成程序地图的游戏之一，生成如此可信的关卡的可能性震惊了我。

我最近发现，由于发现了带有调试符号的各种文件，因此游戏的许多支持者承担了对源代码进行反向工程以清除源代码并弄清开发人员编写的代码的任务。 因此，我开始了为期一周的游览，研究了首席开发人员David Brevik如何创建这些级别。 也许正因为如此，游戏的魔力对我来说部分消失了，但是我学到了许多对类似游戏的开发者有用的技术，因此在本文中，我将与大家分享。

感谢David Brevik和Blizard North团队创造了如此出色的游戏，以及galaxyhaxz和Devilution团队在恢复项目的可读源代码方面所做的出色工作。

引言

暗黑破坏神是一款由等轴测图块组成的游戏。 游戏包含4个阶段，每个阶段有4个关卡。 游戏阶段：大教堂，地下墓穴，洞穴和地狱。 还有几个固定级别，例如Tristram市，我将不在本文中讨论。 暗黑破坏神在这四个阶段中的每个阶段都有单独的级别生成过程，因此，我将首先讨论它们的功能，然后分别考虑每个阶段的操作。

我只对如何生成级别感兴趣。 要了解任务，怪物等。 我建议阅读Jarulf的Diablo和Hellfire指南 ，其中详细介绍了这些方面。

一般特征

尽管每个阶段都有自己的电平生成器，但是它们都有共同的特征。

地牢和瓷砖

生成游戏的每个级别以填充40 x 40格的网格。 X轴对应于东南，Y轴对应于西南。

这些磁贴仅用于关卡生成任务。 创建关卡后，每个图块都分为4个“地牢片段”，这些片段在屏幕上呈现。


此更详细的网格用于确定遍历的图块，还可以更有效地重用图形内存。 之前，我写过关于磁贴分割方案的文章 。

这意味着标准的暗黑破坏神卡包含一百多个磁贴，其中许多是其他磁贴的微小变化，要考虑到所有可能的连接方式。 我们稍后再讨论。

令我惊讶的是，与本系列的其他游戏不同，地牢地图不是由预先创建的块组成的。 几乎所有内容都是通过使用算法创建的。

多阶段过程

每个地牢生成过程分为两个阶段。 前代根本不涉及瓷砖的选择。 它只是生成一个数组，其中标记了可通过的磁贴，其中有门的磁贴以及其他一些高级细节。 在第二阶段，将这种地牢毛坯转换为图块阵列，然后执行生成并考虑这些图块进行更改。

这对于设计者来说应该非常方便。 您可以尝试完全独立于瓷砖和样式选择的平面图。 但是在许多情况下，它们是相互关联的，从而提供了更全面的层次感。

创建地牢坯料的所有阶段都始于填充有坚固“硬度”的层，然后该层的各个部分递归转换为地砖。 我将在下面对此进行更详细的讨论。

成品碎片

完成的片段是预先创建的级别块，可将其简单地插入随机生成的级别中。 它们用于大多数游戏任务。 在每个级别上，只能有一个完成的片段，每个阶段的位置都是单独选择的。


Butcher's Den是游戏中最早的预制片段之一。

迷你套

迷你工具包是将内容插入到预先创建的内容级别中的另一种方法。 这些都是小块，通常大小约为3×3，随机插入地牢中。 有一个简单的模式匹配方案，这使它们仅出现在“正确的”位置。 通常，它们会按其他要求进行编码，例如，迷你集不能彼此靠近放置，它们不能与现成的片段重叠，依此类推。 一些迷你工具包总是搜索和替换，而另一些则以固定的概率进行搜索和替换。

暗黑破坏神迷你套装用于许多不同目的。 它们用于放置瓷砖等大型物体（例如楼梯），以固定彼此之间无法很好连接的瓷砖组合，并为瓷砖添加随机变化。

主题室

主题房间是一堵墙和门所围成的小空间。 通常以随机的方式在其中定位某些预定对象。 例如，图书馆总是有一个书架，书架的两边各有两个蜡烛，还有几个随机的书挡和怪兽。 怪物巢穴包含许多怪物和随机物品，依此类推。

在athedral阶段，生成器创建合适的房间，这些房间可以通过填充识别并重新使用。 在其他阶段，该算法会找到开放空间，在其中绘制墙壁和门以创建房间。

每种类型的主题室都对其生成的大小和阶段有一定的要求。

瓷砖更换

有些卡对图块有特殊的修改，但它们都有一个共同的特征：有些图块可以用类似的变体替换。 最标准的瓷砖（例如，地板和平坦的墙壁）具有各种变化，从而降低了水平的单调性。 磁贴替换永远不会并行使用。

模式和“更正”的比较

如上所述，微型集用作纠正生成器缺陷的搜索和替换机制。 但是在大多数阶段，都有一些程序可以检测并修复更具体的问题。 我不会详细介绍，因为只有一堆。 只需说出《暗黑破坏神》是个虫子，就可以了。在接近发行版时，很明显增加对特定问题的认识比消除其根本原因要容易得多。

最常见的“修复”之一是“锁定”：它检查是否可以遍历整个地牢，如果不能，则重新开始生成。

任务

大多数任务是使用现成的片段创建的，但有些任务使用了自己的逻辑。 例如，疯狂的扎尔（Zhar the Mad）生成了主题图书馆房间，中毒水的入口是通过微型拨号生成的，而愤怒的铁砧（Anvil of Fury）具有特定级别的生成代码。 我不会详细介绍，但是代码中充满了对任务的类似检查。

大教堂

大教堂可能是暗黑破坏神阶段中最具标志性的。 它的特点是排成一排的哥特式拱门，狭窄的房间和许多门廊形式的瓶颈。 让我们看看它是如何创建的。

地牢空白

该算法要做的第一件事是绘制卡的核心。 他沿中心轴X或Y在预定位置随机选择了最多三个10×10的房间。连接这些房间的宽走廊也沿该轴绘制。 如果水平仪上有完成的碎片，则它始终位于这些房间之一的中心。 这些中央地牢房间被标记为不适合新墙壁使用，因此它们始终保持较大的开放空间。

所有其他房间都是通过递归芽接技术在称为L5roomGen的函数中生成的，该函数在每个这些房间中启动，并选择了轴。

L5roomGen功能

• 她经过了原始房间的矩形，从该矩形开始您需要开始萌芽，以及首选的轴。
• 首选轴以1/4的概率发生变化。
• 选择新房间的随机大小，每侧有2、4或6个图块。
• 对于原始房间沿选定轴的每一侧（即，SE / NS表示X，SW / NE表示Y）：
  
  • 新房间的矩形与原始房间边缘的中心对齐
  • 检查是在此之前没有绘制任何内容，并且我们还没有到达地图的尽头。 墙壁需要一个瓷砖的边框。
  • 如果检查成功，将绘制一个房间。
• 对于要L5roomGen每个房间，将递归调用L5roomGen ，它传递新房间和与先前使用的房间相反的轴。

最终，此过程从在“实心”瓷砖内切出几个房间开始，然后反复粘贴新的矩形以切出新的可通过区域。 在此阶段，所有“房间”都在一侧打开，因为每个新房间都直接位于前一个房间的旁边，而没有用于放置墙壁的通行证。

然后，生成器计算生成的遍历图块的数量。 如果它低于最小阈值（随着每个级别的增加而增加），则将破坏地牢并重新进行生成尝试。

地牢

到目前为止，该算法仅具有“实体”和性别分块。 我们需要用真正的墙砖代替它们。 为此，暗黑破坏神使用行进平方算法，我在上一篇文章中对此进行了描述 。

但是，游戏使用其不寻常的变化。 大教堂的图块包含墙，但它们始终位于图块的远端。 因此，在东北边缘没有墙的瓷砖，但在东南边缘没有墙的瓷砖。 要在另一侧创建墙，您需要找到一个“实心”砖，该砖具有从墙的边界向外延伸的附加墙。 听起来很奇怪，但实际上按深度对墙壁进行分类非常方便。


为了解决这个问题，暗黑破坏神在行进立方体阶段跳过了一些墙壁：


稍后，在“修复”阶段添加其他墙。 我认为这个简单的程序最能影响大教堂的“风格”。 由于相对的墙是贴在实心砖上的，因此在两个房间被一个墙砖隔开的情况下，根本不会创建相对的墙。 这意味着房间之间的分隔线比通常在执行行进正方形时所获得的分辨率“更细”。

放置主墙后，生成器将四个独立柱添加到每个中央房间，并为中央走廊添加一个拱门柱廊。 这使您可以比其他级别更周到地给大教堂带来设计感，还可以帮助玩家进行导航。

然后，生成器随机添加分隔墙。 分隔墙始终沿轴线从一堵墙到另一条墙直行。 它们从角落开始，因此区域被漂亮地分成了房间。 在25％的情况下，墙是一系列的拱门，在25％的情况下，它是一系列用格栅挡住入口的拱门，在所有其他情况下，它是坚固的墙。 如果是格栅和坚固的墙壁，则沿着分隔墙的某个位置，会随机添加一扇门或拱门，以使空间可以通过。

填充过程将检测潜在的主题房间。

放置楼梯以连接其他楼层。 如果无法放置它们，则重新尝试生成地牢。

至于小型装置，“固定装置”和替换装置的布置，我将不作详细介绍。 最重要的是，我喜欢PANCREAS1迷你套件，它有1％的机会在地板砖上放一堆鲜血的肉。 最后，在其上放置5-10个灯饰以装饰地牢。

地下墓穴

与看起来像是设计建筑的大教堂不同，地下墓穴感觉更加自发。 它们的特点是方形房间之间通过许多蜿蜒的走廊相互连接。 在许多地方，除了门以外，还设有宽大的开口。 增加玩家被许多敌人包围的可能性。

游戏中最复杂的生成算法用于生成地下墓穴。 我怀疑时间的紧迫迫使开发人员在后续阶段中应用了更简单的解决方案。

地牢空白

为地下墓穴创建地牢空白的过程非常独特。 在所有其他阶段，只有一个布尔值指示存在或不存在性别（另外还有一组位用于其他详细信息）。 地下墓穴以ASCII卡的形式存储地牢空白，几乎就像经典的流氓一样。 考虑到戴维·布雷维克（David Brevik）承认他从安格班德（Angband）汲取了暗黑破坏神的灵感，这并不令人感到意外。

主要房间生成器再次是递归算法，但是这次是递归分区。 对于40×40减去1个边框图块的整个地牢区域， CreateRoom调用CreateRoom函数。

CreateRoom功能

• CreateRoom函数CreateRoom传递一个矩形，该矩形表示您要在其中生成房间的区域。 详细信息也传递给有关原始房间的功能（最初为null）
• 如果该区域太窄，则退出该功能。
• 考虑到要放置房间的区域的最大大小，为房间的每侧从4到9个图块中选择一个随机大小。
• 在该区域中，选择一个随机位置放置房间。
• 房间在ASCII映射上呈现。 在图中，符号'.' 标有地砖， '#'符号是围墙，字母'A' ， 'B' ， 'C'和'E'是四个角。
• 如果一个房间有一个源房间：
  
  • 在原始房间和新房间的最近边缘选择一个随机图块。
  • 此信息记录在走廊列表中，稍后将使用。
• 除当前房间外，该区域的其余部分都被切掉，创建了四个矩形。
• 将每个矩形的大小减小两个小块以在房间之间创建一个空间，然后递归调用CreateRoom函数，使用该矩形的区域将创建的房间作为源。

如果地图上有完成的片段，它将始终位于CreateRoom创建的第一个房间中，并对其尺寸进行标注，以便将该片段放置在其中。

调用CreateRoom得到一个类似于下面所示的ASCII数组（感谢nomdenom从代码中提取出来）：

 A##B #..# A####B #..# #....# #..# #....# C##E #....# C####EA#####B #.....# #.....# A########B #.....# #........# #.....# #........# C#####E #........# A#B #........# #.# #........# #.# #........# #.# #........# #.# #........# #.# C########E #.# #.# A#BC#E #.# A####B #.# #....# #.# #....# #.# #....# #.# C####E #.# #.# A#####BC#E #.....# A###B #.....# #...# #.....# C###E #.....# C#####E 

在这种情况下，最初创建的“根”房间是最低的。

然后应用先前收集的走廊信息。 在每个记录的点对之间绘制一条线。 当它穿过墙壁时， 'D'写上'D' ，而当它穿过实心砖时， 'D'写上',' 。 走廊的宽度随机：1、2或3。边角砖用于辅助导航。

如果门与另一扇门相邻，则将跳过它们，并且走廊可以相互重叠，这使您可以隐藏发电机的简单性。

记录所有通道后，将清除ASCII卡。 边角瓷砖变成了墙砖，而' '旁边','瓷砖也变成了墙。 最后，将字符','替换为字符'.' 。 因此，我们得到了如下所示的地牢计划。

 #### #..# ###### #..# #....# #..# #....# #D## #....# #.# #D#### ##D#### #..# #.....# #..# ###.....# ##D######## #.D.....# #........# #.#.....# #........# ### #.##D#### #........# #.### #.##...# #........###.D.# #.##...# #........##..#.# #.##...# #........##..#.# #.##...# #........##..#.# #.##...# #........##..#.# #.##...# ###D#######..#.# #.##...# #.......#..#.# #.###D## ###.....#..### #.# #.# #######D##.# #.# #.# #....#.# #.# #.# #....D.# #.# #.# #....###### #.# #.# ##D####....## #.# #.# #...........# #.# #.# ####....###D####.# ### ######.....##.# #####.D.....##.# #...D.#.....D..# #####.#.....#### ######### 

如您所见，此过程可以在地图上留下很多空白。 因此，发生器的下一步是“填充空隙”。 他搜索可以将其他地板矩形粘贴到的任何相邻墙段。 矩形的大小至少应为5×5，并且不得超过12×14。

空隙填充将继续，直到获得最少700个磁贴，或达到重试限制。 如果生成器无法达到700瓦，则地牢生成将从零开始。

这为我们提供了如下所示的地牢空白。

  ########## #........# ########### #........# #.........# #........# #.........# #........# #.........# #### #........# #.........# #..# #######..###.........# #..# #..............# #..# #..............# #D## #..............# #.# #D####.........# ##D#### #..# ########### #.....# #..# ###.....# ##D######## #.D.....# #........# #.#.....# ########........# ### #.##D#### #...............# #.### #.##...# #...............###.D.# #.##...# #...............##..#.# #.##...# #...............##..#.# #.##...# #...............##..#.# #.##...# #...............##..#.# #.##...# #......###D#######..#.# #.##...# #......# #.......#..#.# #.###D## #......# ###.....#..### #.# #.# #......#########D##.# #.# #.# #.........# #....#.# #.# #.# #.........# #....D.# #.# #.# #.........# #....###### #.# #.# #.........# ##D####....## #.# #.# #.........# #...........# #.# #.# #.........# ####....###D####.# ### #.........# ######.....##.# #.........# #####.D.....##.# #.........# #...D.#.....D..# ########### #####.#.....#### ######### 

地牢

同样，地下墓穴不同于标准水平的配方。 代替行进正方形算法（后者根据地牢空白的2×2平方分配图块），它使用自己的模式匹配过程，该过程检查地牢空白的3×3矩形中的每个矩形并为地牢选择相应的图块。 模式决定每个地牢砖应该是什么：墙壁，地板，门，实心砖或它们的组合。 我不太明白为什么。

大教堂的其余功能对您来说似乎很熟悉。 在地图上放置上下楼梯，检查地牢是否完全通过，并进行各种更正。 如“一般功能”部分所述，将插入房间，然后插入许多迷你集和瓷砖。

我认为微型套件会以某种方式影响门口，但是如果没有工具，它们会很无聊，因此我没有深入研究这个主题。

洞穴

洞穴的水平充满了广阔的开放空间和熔岩河。 该区域的墙壁粗糙且呈波浪形。 这里唯一的矩形组件是木制脚手架，显然比洞穴本身晚出现。

多亏了动画熔岩，这个阶段是游戏中最漂亮的阶段之一。 有人认为它与以前由房间组成的层有很大不同。 因此，令我感到非常惊讶的是，这一代的主要部分是根据大教堂舞台的原理建模的，并且使用棘手的技巧赋予了卡片更加“凹”的外观。

地牢空白

创建洞穴等级始于一个随机的2×2房间，该房间位于靠近地图中心的位置。 然后，生成器为此块的每个边缘调用DRLG_L3CreateBlock过程。

在此级别绘制矩形时，不使用普通填充。 内部始终是坚固的，但是边界上的每个瓷砖都有50％的机会成为地板，否则它将保持坚固。

DRLG_L3CreateBlock过程

• 此函数获取矩形的边缘，即 起点，方向和长度。
• 每边在3-4范围内选择新创建的块的大小。
• 新块相对于输入边缘随机放置。
• 如果没有足够的空间来绘制块，则执行退出。
• 块被绘制。
• 以1/4的概率执行输出。
• 除了我们所来自的那一个以外，还DRLG_L3CreateBlock了三个边缘的DRLG_L3CreateBlock 。

尽管此过程与L5roomGen相似， L5roomGen使用较小的块大小并绘制粗边框会使其看起来更加自然。 此外，它不包括墙的1个图块的边框，因此，与以前的生成器不同，它可以创建循环。

在创建了地牢形状的粗略草图之后，生成器将执行腐蚀过程：

• 首先，他找到2×2块瓷砖的区域，这些区域具有对角相对的实心瓷砖。 在进行行进正方形时，通常很难使用这种构造，因此，其中一个实体图块会随机替换为性别。
• 被8个地砖包围的所有实体单砖都将替换为地砖。
• 通过将50％的墙壁换成地砖，可任意粗化所有长而直的墙壁部分。
• 连续瓷砖的对角线会被反复消除。

所有这些过程都添加了更多的地砖，因此地图变得更加开放。

如果其地板块少于600个，则将重新生成地图。

地牢

使用行进方块将地牢空白转换为图块。 与大教堂和地下墓穴不同，图块集在这里更加方便，并且包含行军所需的几乎所有组合。 其中没有用于对角墙的瓷砖，但是在工件阶段已将其消除，因此它们从未出现。

然后，像往常一样，有许多迷你套装。 该代码有几个微型集，这些微型集定义了墙壁的单独部分，并用石笋和地板代替，从而增加了空间的开放性。

熔岩湖被添加。 该算法使用fill搜索相邻的墙段。 如果他设法找到少于40块完全被地砖包围的墙/实心砖部分，则将它们替换为熔岩。 如果找不到熔岩湖，那么地牢的产生将重新开始。


3×3的墙变成了熔岩湖

然后添加了几条熔岩河。 发电机多次尝试绘制一条从熔岩湖开始到墙的河流。 对河流有以下要求：河流不应穿过河流，河流的长度为7-100瓦，并且在河上应该有合适的位置。 桥接图块可确保整个地图保持可传递状态。 如果地图上有空间，最多可以添加四个河流。

然后放置主题房间。 在此阶段，主题房间的墙壁是木栅栏，您不能穿过它，但可以观看。 在以下两个步骤中也使用了木栅栏。 第一个在墙的所有其余部分上都设置了围栏，并具有相当长的笔直部分。 第二个在地图上从一堵墙到另一面绘制一道栅栏，然后插入门。 与生成大教堂的过程不同，它不寻找拐角来创建这些墙。

地狱

地狱是暗黑破坏神的最后阶段。 在其中，主要重点已经放在了怪物上，关卡的设计被抛在一边。 这个舞台的砖块最小，大部分用于巨大的楼梯和五角星。 地狱级别通常由几个方形房间组成，并且布局对称。

地牢空白

地狱的产生开始于每侧随机有5-6个磁贴的房间（如果有用于任务的现成碎片，则更多），然后应用与大教堂中相同的递归芽接。 但是，生成限制为20×20。

添加了垂直和水平走廊，一直延伸到20×20区域的边缘。

然后将地牢坯进行水平和垂直镜像以获得完整尺寸。

地牢

地牢空白再次使用行进方块转换为图块。 然后，类似于大教堂的创建，在地下墓穴和洞穴中添加墙壁。

结论

我真的很喜欢阅读这段代码。 尽管其中显然存在错误，但是名称是随机分配的，并且某些部分无法在高质量的源代码中重新创建，但可以清楚地看到，此代码经过了艰苦的测试，充满了聪明的主意。

这是对我来说最重要的课程：

• 细节在于魔鬼：各个组成部分并没有疯狂复杂，但是当结合在一起时，它们会带来奇妙的效果。 我可以想象开发人员如何在提高质量之前全神贯注，直到水平从“好”变为“好”为止。 瓦片的数量和瓦片集的组合复杂性也很高-如果不注意元素的连接方式，就不可能实现这一点。
• 搜索和替换模式匹配是一个非常强大的工具，您可以使用它实现许多不同的效果。 它修复了生成错误，增加了可变性，插入了预先创建的内容，管理了侵蚀等等。
• 在设计和调试方面，将地牢生成划分为通畅图（地牢准备）和图块生成也是一种非常方便的技术。
• , . , .
• , .