在一些新游戏中 ，有关编程，图形和声音的工作已经结束-仅保留关卡。 简单而有趣的工作，但是由于某些原因却很难。 也许是普遍疲劳的效果。
在思考如何简化他的生活时，程序生成的想法浮现在脑海。 当然，它也必须写出来，但是正如在一项著名的作品中所说的那样，“最好是丢掉一天，然后在五分钟内飞起来。”
注意！ 下切了很多文字和“胖子”的GIF。
介绍性
水平仪仍将手动抛光，因此对内存，速度甚至所产生水平仪的质量没有特殊要求。
最初，我计划生成器仅抛出房间和门，并且所有进一步的优化（情节，风景和敌人）都将以手动模式执行。 但就目前而言，我认为发电机可以做的更多。 尽管如此，手动调整仍然会保留-玩家必须感觉到至少在关卡上投入了一点爱。
我查看了有关游戏开发人员的知识，并在单独的文档中写了有关程序生成的文章的链接。 当然，大多数都与生成经典迷宫或生成地形 （顺便说一句，结果非常令人印象深刻）有关，这不适合3D射击游戏。 但是有些接近我的需求（用星号标出那些最适合我的星号）：
我决定从最后两个开始-它们正在实施中，并给出了良好的结果。
发电机结构
实际上，我并不是立即进入这种结构，而是在进行大量的重构和重写的过程中，但是我马上就写了一下，这样很清楚发生了什么事情：
- 生成初始几何体（从“ BSP”或房间布局中选择）。
- 清除垃圾区（游戏中不存在的垃圾区）。
- 建立连接。
- 清除垃圾子图（这些相互连接的部分组，但与其余部分没有任何关系）。
- 清除不必要的连接（建立生成树 ，将链接指向最小生成树，因为那里有图片，但是对于生成器，则不需要最小生成树）。
- 连接的随机化是恢复一些远程连接（对于更“人性化”的级别），以及将其他一些连接转换为部分之间的通道（将多个部分合并为一个更复杂的形式）。
- 秘密房间的一代。
- 生成“方案”（初始和最终部分将位于何处，以及必须经过哪条路径才能从初始到最终）。
- 连接优化。
- 创建门窗。
- 选择本节中要执行的操作（按开关，抬起钥匙或找到秘密墙）。
大约还有12点，但是还没有完成（当我完成时，我将写一篇关于它们的单独文章）。
初始几何生成：“ BSP”
该翻译被作为基础。 我不确定此算法中发生的次数是否接近实际的BSP，因此我将“ BSP”写在引号中。
该算法非常简单。 首先，创建一个矩形，该矩形的大小等于整个运动场的大小：
然后，我们将其随机分为两部分-水平或垂直。 分隔线所在的位置，我们还随机选择：
我们递归地对新矩形执行相同的操作：
在一定程度上一次又一次地：
然后，在每个矩形中选择一个“房间”，即与原始尺寸相同或更小的矩形（但不小于3x3-在下面的矩形上更大）。
然后，房间通过走廊相连。 但是不是每个，但是有些棘手，因为它们存储在类似“ BSP”的结构中（有关更多详细信息，请参见原始算法）。
连接紫色和白色部分的走廊。
在原始算法中，房间和走廊的颜色相同（即相等），因此仅在房间顶部绘制走廊。 在我的情况下，应保留原始房间，以便绘制走廊，就像在房间“后面”一样。
此外，如果房间（图中的绿松石色）穿过走廊，则应将其分成两个不同的部分（因此，可以用不同的颜色绘制同一条走廊）：
结果如下：
然后开始标记垃圾单元的阶段：
正如我已经写过的，任何扇区都不能小于3x3单元。 这是由于以下事实：该扇区必须被墙壁包围（每侧至少1个单元），并且必须至少具有一个自由空间单元：
因此，所有不符合此规则的单元格都将被标记。 但是，只要接受它，您就无法删除它们-如此多的连接消失了，而且级别很薄。
而是，为每个标记的单元格搜索其可以加入的扇区（遵守3x3规则）：
如果该单元格仍不能归因于任何扇区，则将其删除（但在这种情况下不能删除-此处一切正常）。
在最后阶段，将这张精美的图片矢量化，并将绘制的扇区变成多边形盒-这样的多边形，其中每个边缘要么严格垂直要么严格水平（可能有一个更科学的名称）：
初始几何图形生成：房间布局
另一篇文章被作为依据。 该算法比以前的算法要复杂一些，但火箭科学也没有。
首先，在运动场中填充特定的停止值，然后在其上随机清除一个矩形区域：
清理随机矩形的阶段进行了多次（也是随机的）次数，因此，获得了水准仪的外部轮廓：
在自由空间中，房间生长点是随机分散的（最小房间大小为3x3）：
房间生长的第一阶段开始-为每个房间选择最大的一面，该面仍然可以生长，并且以一个单元格增长（如果有多个相同长度的面，则是一个随机面）。 房间依次移动，因此没有路口。
然后将房间转换为多用盒：
第二阶段开始增长-在这一阶段，这一方面可以分为几个部分。 与第一阶段不同，它不会一次生长一个细胞，而是立即生长到最大停止位置-避免了房间接合处的“梯子”。 如果经过所有房间后仍然有空的牢房，则重复该循环。
结果是充满了空间：
然后以栅格的形式绘制多边形框，并且（如“ BSP”生成器一样），标记“垃圾”单元的阶段开始：
并将它们加入现有行业：
在这里，不可能附加所有单元格-多余的单元格被删除了。
结果将转换回多边形框：
清洁垃圾区
有时会出现其中不遵守3x3规则的部分：
您可以尝试“还原”这些部分，但我采用了更简单的方法，只需删除它们即可：
建筑连接
对于每个部分，将搜索其相邻部分，并在此类部分的接触位置中创建连接。 在两侧都创建了连接-如果A部分与B部分接触，则将存在从A到B以及从B到A的连接。结果是一个双向图。
清除垃圾子图
有时，由于清理了垃圾部分，因此我们得到的不是一个图，而是几个独立的图，如本例所示：
在这种情况下，选择子图作为主要图，子图的部分区域最大，其余部分被删除（“区域”用引号引起，因为尽管可以计算多边形框的实际面积，但我简化了任务，并考虑了边界框的面积-这是错误的，但适用于发电机）。
去除多余的化合物
如果每个扇区到与之相连的每个通道都有一条通道，则在水平面上将有太多的门，并且会更强烈地感觉到它是生成的。 因此，在此阶段，将删除多余的连接：
为了获得更多的随机性，我不会以最少的通过次数生成生成树，而是一次删除一个随机边（在当前步骤中从所有可能的情况中随机选择）。
虽然，当我写这篇文章时，想法似乎是随机选择初始扇区，并删除已经更有效的边缘算法。
连接随机化
在下文中，插图将来自另一代人，因为 在上一个中，生成器中存在一个错误，由于该错误导致其他图片不正确。
但是没有单个多余连接的级别看起来也不是很人道，因此引入了一些混乱：
- 恢复一些删除的边缘。
- 有些变成过道。
此外，在其间形成通道的那些部分合并为一个：
如果在您看来，在此插图中，重新出现了在上一步删除的连接-在您看来：)。 当我阅读文字时，在我看来也是如此，但是仔细看一下前面的插图，很明显，一切都很好。
秘密房间的产生
在图上选择了只有一个连接的扇区：
如果有几个这样的扇区，则它们全部聚集在一个阵列中，并按“区域”排序。 然后，该数组被随机截断（但是至少要保留一个元素）。 这些部门将成为秘密房间：
脚本生成
首先，选择具有最少空闲连接数的扇区（即，靠近图形“边缘”的扇区）：
在此图示中，选择了一个扇区，但是如果有更多扇区，则无论如何都会（随机）选择一个扇区。
注意 在本文的校对过程中，我能够想到一种情况，一个空闲连接数最少的扇区不仅会处于边缘，而且为其分配脚本将导致无法实现的目标。 实际上，您可以选择任何扇区，但只能选择一个扇区，此后该图将不会分成几个子图。
接下来，选择连接到当前扇区并且只有一个空闲连接的扇区。 它们很有可能会用于继续执行脚本。 例如，如果图形与下图相同，则问题所指示的扇区可以包含在列表中。
秘密室用灰色标记，十字线是应在原始图中删除的那些连接，而源扇区为加号。
注意 在本文的校对过程中，在我看来，仅存在一个连接的条件太严格，与上一步中的条件相同就足够了-因此删除该扇区后，该图将不会破裂。
然后，将脚本编号分配给该扇区列表（只是一个数字，在此阶段并不表示任何特定的含义），并且此脚本列表将边界列表的边界处的连接标记为已关闭。
在这些插图中，不同的场景将具有不同的扇区填充颜色。 它们与扇形边框的颜色无关（在接下来的步骤中将对其进行校正，但在这一步中，对我来说更方便）。
接下来，选择下一个扇区，编译一个列表，并用新的场景标记该列表：
注意红色方块内的小蓝点-这是场景开瓶器的绘制方式-即 在带有红色脚本的区域内的某个地方，将有一个键或开关，以打开带有蓝色脚本的扇区的通道。
一直持续到没有可用的空闲扇区为止：
最近的扇区未分配脚本，而仅分配了方案启动器。 该扇区将是玩家开始游戏的扇区。
对于此级别：
- 玩家从起始区域开始，在那里找到黄色区域的“开瓶器”，然后去那里。
- 在黄色部分中，打开蓝色部分，然后去那里。
- 在蓝色区域中打开绿色，然后去那里。
- 在绿色区域中打开紫色，然后转到那里。
- 以紫色打开红色。
- 红色-蓝色。
- 他在哪里找到末级开关。
示意性地可以如下所示：
“开启者”可以是钥匙或开关，也可以是其他任何东西，例如，消灭任何部门中所有敌人的任务（但我不打算在不久的将来由发电机或发动机支持）。
连接优化
在此步骤中，为每个连接选择了一侧（您还记得，最初在两个方向上都生成了连接）。 这对于使关卡看起来更“手动”并简化下一步是必要的（但对于更有趣的关卡类型，我计划在不久的将来采取“对某些连接进行“优化”的步骤） 。
创建门窗
对于每个扇区，都将查看其所有连接（在上一步之后，该连接仅在一个方向上查看），并且在查看的每个连接上都放置了门窗。
- 首先，在连接处选择一个点，最好靠近中心。
- 然后在这一点上放置一扇门或一扇窗户（如果与秘密室相连，则是秘密墙）。
- 如果放置门，则门的大小可以为1到3个单元（一个是普通门，两个或三个是厚的密闭门，按下开关即可打开）。
- 此外，连接分为两部分-所选点之前的部分和之后的部分。 并且，如果之前或之后还有空间，则将以递归方式调用该函数。
为了使关卡看起来更有趣，在不同的步骤中放置门或窗的可能性不同：
- 在第一步，门总是被放置，因为 如果只有窗户，连接有什么用？
- 在第二步中，以高于门的概率（75％）放置窗。
- 如果有第三步（例如，连接很长），则必须在其上放置一个窗口。
- 在第四步的情况下，门或窗户的放置可能性相同。
- 如果连接很长，则生成器将返回第二步。
动作选择
尽管这与生成无关，但可视化在这一步发生了变化-现在，扇区边框以脚本的颜色绘制：
起始扇区为浅灰色，最终扇区为蓝色。 还要注意，不是绘制了秘密室的门（左侧为深灰色），而是绘制了一面墙-一切正确，这是一面秘密墙。
接下来，选择可以放置键的扇区：
它们的选择非常简单：
- 如果这是一个秘密房间，则其中不能有“开启者”，也不能将钥匙放在那里。
- 您也不能将密钥也放置在最终扇区中，因为它是最终的。
- 另外，钥匙不能打开双开门和三开门-由于发动机的特性，只能使用开关打开（上图中没有这样的扇区） 。
此后，随机选择一个级别（从零到三个）的键数，然后从可用的扇区列表中随机选择其中将有键的那些键。
在其余的扇区中将有开关。