基于拓扑的三维随机地牢生成方法

‍

本文讨论内容相关实现尝试可见：syan2018/Graph-Based-Dungeon-Algorithm: A Simple Dungeon Generation Algorithm Based on Graph Theory (github.com)

（代码写的比文章快，估计看起来也比文章快?‍♂️）

不过整体进度仍在算法设计阶段，包括后续 植入引擎 / 实例化预定义模块关卡 / 通过算法修饰锁钥 都八字没一撇呢（快进到也不会有撇了?

有一说，后续研究应该结合 Procedurally Generated Dungeons – VAZGRIZ 这一工作进行，他提出了一种绝佳的既定关卡空间排布的方案，比我写的基于模拟退火摁优化的靠谱多了。

正文

随机地牢，是一种常用的游戏关卡构成形式，其在Rougelike系游戏中被广泛使用，用于为玩家创造出多样化且具有随机性的游戏体验。

在早期，随机地牢更多以二维形式呈现（嘛因为早期也只有二维），并且更多与游戏追求随机性的核心玩法伴生。但随着近年来游戏工业化规模的增大，随机地牢这一方法也逐渐被一些3D游戏所青睐，其被用于以较低的制作成本，批量产出用于玩家体验的游戏内容。借以延长玩家的游戏时间，填充游戏内容量。

现如今不少持续运营游戏使用的Rougelike玩法，都是这类典例。

‍

作为引子，我们可以尝试从两个维度简单划分随机地牢的阵营

• 驱动维度：随机关卡的驱动力源自事件、构筑等，抑或是探索关卡本身
• 关卡维度：生成关卡和玩家体验的连续性

	离散关卡	中间学派	连续关卡
事件驱动	杀戮尖塔/邪恶铭刻	崩坏 乐土/模拟宇宙	❌
探索驱动	绝区零/ 走格子舔图类肉鸽	P5 印象空间/ 以撒等关卡制肉鸽	血源 圣杯地牢/ 细胞等2D随机地图肉鸽

上述概述分类或许并不严谨（我个人并非肉鸽游戏和重复性游戏的受众，所以上述多数游戏我都没体验过），但整体也能够描摹我们想要讨论问题的轮廓。

当我们意图从“拓扑”这一角度讨论随机地牢的设计时，关卡维度决定了地牢的拓扑组织形式，而驱动类型决定了我们要拓扑的体验目标。进一步的，当我们将其认知为一个优化问题时，关卡维度能帮助我们建模问题，进而由驱动维度为我们定义目标。

随机地牢概览：玩法和算法

当今人们论及“随机地牢”这一话题，更多考虑的是一种相对二维的随机地牢关卡。

另一方面，当 “随机生成” 被延拓到三维后，其又有了一个新的名字 “程序生成内容” (Procedural Content Generation, PCG)。但随着随机维度的增加，在PCG中对玩法、对体验的讨论却也不免变少了。

‍

大约是作为生活在三维空间中的生物，我们往往能更有效地认知和操纵一个低纬度的世界，无论是线性或树状拓扑的随机关卡，抑或是位于二维平面上的关卡结构，都是易于被我们探索和认知的。而一旦这一切升维到了与我们认知平齐的世界，它自然带了一丝难以认知与神秘感。

想要从零开始构建一个合理且颇具可玩性的三维随机地牢算法，大概有着诸多阻碍，但也许我们可以从低维中学习拓扑的思路，并通过升维的方式实现到高维的擢升。

因此，在正式开始讨论方法之前，也许我们可以先讨论讨论既有的那些成熟经验。

提前找些参考

• 基于《波函数坍缩算法》的无限城市程序化随机生成 - 知乎 (zhihu.com)
• Minecraft 的地形生成算法是什么？ - 知乎 (zhihu.com)
• 房间和迷宫：一个地牢生成算法 | indienova 独立游戏
• Procedural Dungeon Generation Algorithm (gamedeveloper.com)
• 如何生成一个「有趣」的roguelike地牢 - 知乎 (zhihu.com)
• mxgmn/MarkovJunior: Probabilistic language based on pattern matching and constraint propagation, 153 examples (github.com)
• Procedurally Generated Dungeons – VAZGRIZ

‍

波函数塌缩：概率模型

TBD！！！

建模方法讨论

为了避免笔者为了圆一下思路又浪费大把的时间来展开调研（实际上时间确实花了，鸽也确实鸽了），并把文章拖长到没人想看的地步，我们还是迅速切回正题吧。

其实这并非是一个非常正经的随机地牢生成方案讨论，更多是一个自嗨式的对玩家地牢关卡探索体验的假想建模。因为这是笔者朋友公司项目需求中展开的命题，与笔者毫无利益关联，我想做的只是拍一拍脑袋，提供一点白瞎的点子自娱自乐罢了。而当这一项目因重新明确对下沉的追求，战略放弃这一方向后（笑），我也更能肆无忌惮在明面上与更多人分享这一课题了。

---

在这篇文章正式开始前，我们会先提到一篇老生常谈的论文： 如何设计一张有“魂味”的地图？——论“类魂”游戏关卡的拓扑结构 - 知乎 (zhihu.com)

如果我没记错，这篇文章应该在本频道出现过不少次了（虽说不知道你会在哪个频道看到这篇文章）

‍

简单回顾一下这篇文章的结论：

‍

抛开这篇文章在设计上的指导价值不论，其确实提供了一个很新的视角，用于定量和定性分析魂类关卡地图的基本结构，并将“玩家探索体验”这一抽象的概念，在格式塔层级上用关卡的结构进行拓扑。这使得除开使用心流（当然业内统一把说这个词的人当成骗子，所以先用情绪/体验曲线代称）建模线性/半线性体验之外，我们有了一种新的方法论用于建模开放/半开放空间内玩家的探索体验（之前笔者尝试基于野炊的数据地图展开相关理论在开放连续空间内的拓展，可惜鸽了）。

‍

基于这一理论，我们自然可以想到，区别于当今更多服务于延长游戏时间、产生随机游戏体验的无约束/弱约束的随机地牢 —— 适用于持续运营游戏的日常重复体验，我们能否设计一种 流程长度可控、满足探索拓扑、难度投放合理 的地牢生成模型？

一想到这儿就乐了起来！欸！新课题这不就有了！

‍

那么我们重新整理我们的三个 “需求” （倒也没人给我提需求）

• 流程长度可控
• 满足探索拓扑
• 难度投放合理

并基于此分析，我们要如何建模这一问题

需求分析

围绕下述三个需求，我们逐一展开需求分析：

流程长度可控

在商业化游戏的大背景下，对于不同程度玩家的期望体验，如 轻度玩家的可持续体验时间 / 投入产出的基本比例等，相比都有着相对充分的建模。玩法设计虽说是相对独立的模块，但也显然是会受制于商业化的。最终都会经过数值的微调适配。

‍

同时，仅就设计角度而言，设计师也希望更玩家在地牢中感受到稳步的推进感。而不是被无止尽的地牢探索压力压倒，抑或是因猝然而止的流程感到沮丧。

‍

在既往的游戏样本中，不难看到在相似领域的大量构思：

• 以事件驱动地牢为例：

  • 设计师在生成随机关卡时，拓扑了玩家大致能经历的事件，以及在其上获得的成长

  • 最典型和简化的例子为崩坏星穹铁道中的模拟宇宙

    ​

  • 如图所示，通过纯线性的拓扑和有限的分支选择，直接约束了玩家在探索中的体验；但也正因为如此，其能非常有效地控制其作为周常玩法的流程长度，以及控制玩家的成长路线

• 以探索驱动地牢为例：

  • 探索驱动的生成式地牢，往往使用起点到终点之间的空间关系约束
  • 通过既定的空间约束关系进行生长，可以相对有效地控制玩家游戏流程的绝对体验
  • 以 P5 的印象空间为例，就是在确定了探索主干之后生长分支的关卡（无法满足“探索”需要）

‍

为此，我们会希望在建模中引入一种称为“体验预算”的参数，用于评估玩家探索的流程长度

相似的思路也会在“难度合理投放”一节中出现

‍

满足探索拓扑

这一节的需要会相对更加明晰

良好的地牢设计应当鼓励探索。其应具备较高的连通性，允许玩家在探索过程中产生复杂的分支体验，并总能向着完成地牢的目标前进。

在地牢生长算法中约束产生较高的连通性，可以很大程度上满足这一探索体验需要；另一方面，在连通性的基础之上，我们也能使用诸如单向门等要素进一步修饰地牢的探索体验。

‍

难度合理投放

这一节则是要讨论难度的投放。

作为一个偏探索向的关卡，有这么一个理所当然的准则，即玩家经历的磨难需要匹配其获得的奖励，这才能构建一个相对稳定的正反馈。而一段波澜起伏的冒险经历，也总能让玩家更加满意。

因此，在难度投放中，我们需要量化玩家途径关卡和战斗的困难程度，并将其有效在时间轴上编排。

‍

分析汇总

回到“流程长度可控”一节提到的“难度”预算。我们更倾向于这样建模玩家的地牢探索体验

• 在“图”上对玩家的关卡探索体验进行拓扑，以确保关卡的体验连通性；并基于单向边、循环边等后期添加特征进行修饰设计
• 在图的”路径“上设计玩家的体验长度量化，避免过于复杂 / 简单的路径出现，阻碍玩家体验
• 在图的”节点“上设计玩家的冒险经历与产出投放，使关卡整体难度编排合理，产出令人满意

基于这些原则，我们能汇总讨论设计的核心思路

‍

地牢图建模设计

‍

基于上述需求分析汇总，我们可以断言我们希望实现一个满足如下需求的图：

（ 就是我丢给ChatGPT帮我开始写代码的Prompt ）

1. 图具有一个确定的起点和终点，通过一个生长过程生成壮大。
2. 新增节点的过程整体是随机的，它会在已有的图上生长，创建到既有节点的链接。
3. 图具有高连通度，体现为存在多条从起点到终点的可能路径，且较多节点之间存在连通关系。
4. 在图中，每个新增的节点都有一个随机的阻力系数。这个阻力系数在后期设计中，将作为一种评估地牢关卡节点对应关卡或怪物布置难度的参考值。
5. 在图中，每条从起点到终点的路径上，通过节点的阻力系数之和都在一个特定的范围内。

‍

简单图生成算法的实现

在实际实现中，我们会将生成过程拆解，为多个步骤，并逐一满足这些需求

如下为ChatGPT基于完工后代码逆向拆解的实现步骤

1. 确定的起点和终点:

   • 在 DungeonRGT​ 类的 generate​ 方法中，初始节点（起点）是明确定义的，self.graph.add_node(0, resistance=0)​ 这一行代码创建了起点。
   • 终点是通过 _set_end_node​ 方法确定的，该方法选择一个节点作为终点，并设置其阻力系数为0。

2. 高连通随机生长:

   • ​generate_graph​ 函数从环形图开始随机添加边，直到抵达目标平均度，以确保图的高连通性。
   • 初始化通过 add_bi_edge​ 方法添加了双向边，保留后续裁剪空间。

3. 节点阻力系数:

   • 在 DungeonRGT​ 类的 _generate_nodes_and_edges​ 方法中，每个节点被赋予了一个随机的阻力系数。
   • 这个阻力系数随后被用来计算边的权重，以模拟通过该边的难度。

4. 特定范围内的路径阻力系数之和:

   • ​generate​ 方法中，通过控制生成的路径阻力系数之和在一定范围内，确保了每条从起点到终点的路径都满足特定的阻力系数要求。
   • 这是通过 _make_graph_diverse​ 和 _evaluate_graph​ 方法实现的，这两个方法评估了图中的路径，并在必要时调整图来满足阻力系数之和的要求。

进一步的，通过添加修饰单向边、修饰节点，我们能较好地生成一个图的基础拓扑

再后续，我们也能定量调整不同路径上的实际阻力，使得体验编排更加合理

（当然，现在还完全没优化）

​​

Path: [0, 1, 2, 3, 4, 5, 6] Resistance: 32.228143319783435
Path: [0, 1, 2, 3, 4, 5, 7, 6] Resistance: 39.560780702129804
Path: [0, 1, 2, 7, 6] Resistance: 25.34280294030403
Path: [0, 1, 2, 7, 5, 6] Resistance: 32.79874723247958
Path: [0, 1, 5, 4, 3, 2, 7, 6] Resistance: 39.56078070212981
Path: [0, 1, 5, 6] Resistance: 18.397426073906516
Path: [0, 1, 5, 7, 6] Resistance: 25.73006345625289
Path: [0, 1, 4, 3, 2, 7, 6] Resistance: 32.10483640995426
Path: [0, 1, 4, 3, 2, 7, 5, 6] Resistance: 39.560780702129804
Path: [0, 1, 4, 5, 6] Resistance: 21.13964965684544
Path: [0, 1, 4, 5, 7, 6] Resistance: 28.472287039191812

算法生成模型的食用方式

在实际使用中，我们可以基于 节点的阻力系数和连边类型，选用符合条件的地牢模板；

诸如对于一个具有三向连边的模块化地牢，其可被应用在节点④处（当然实际还需和后续的三维空间拓扑一并讨论），同时基于其阻力系数，我们可以选取相同关卡下不同的布怪预设，并给予不同级别的关卡奖励。从而满足难度/奖励投放的需要。

​​

‍

空间优化方法

在空间优化上，使用一个把我打回三年前数学建模时期的模拟退火方法

我们将模型放置在一个 4×4×4 的点阵空间中，并约束了点和边的占用关系，创建当前空间布局的评估函数，使其能产生合理的空拓扑

​​

如图所示为简单实现后上述关卡的地牢拓扑图（当然目测还会有不少瑕疵，比方说需要在空间交点处构建分叉路径（实际上就是一种特殊的房间）

TBD

‍

后续工作

笑死，正事还没做完就开始聊后续工作了

总而言之，目前还是一个相对草率未经调优的生成算法，在有动力将其再次拾取之前，更新一下后续可能进行的工作

‍

多路径阻力系数的协同优化：

我们可以将不同路径上的阻力系数，通过插值匹配到一个地牢探索Target曲线上，并通过反传确定不同节点上阻力系数对该目标曲线的误差。通过多路径同时优化，我们能将阻力系数的分布调整至更合适的范围

​​

评估函数改进：

与上述Target曲线相近，我们需要构建一个更有效的探索体验评估函数

当前其更多仅就连通性和总阻力系数进行评估，整体建模深度不够（因此需要观察采集更多玩家数据

关卡 / 路径多样化：

当前使用_make_graph_diverse​的路径修饰方法还是太简单粗暴了，相关修饰可以被更广泛的使用，并进一步设计玩家探索体验。

动态生成算法：

迭代当前完全前向的生成算法，进一步根据需要动态生成连接关系。

以保证地牢的多样性和流程长度的合理性。

尝试新的布局算法：

脱离点阵空间的约束，使用三维空间中的随机排布和路径填充

vazgriz/DungeonGenerator: Procdural dungeon generator for Unity3D (github.com)

定量分析阻力系数：

定量分析阻力系数和实际关卡难度的关系，确定分级布怪策略的实践

‍

‍