🏗️ Scaffold 关卡编辑器

在上周的 Nightshift Galaxy 每周开发直播中，我展示了我在 Unreal Level Editor 内部构建的专用关卡编辑工具，我称之为 Scaffold。

我即兴介绍了我的动机和灵感，但经过反思，这个话题值得深入探讨。

在设计工具时，我遵循三个高级目标：

Scaffold 通过以下方式解决这些目标：(i) 一个交互式的室内设计工具，优先考虑高级用户的热键和可破解性；(ii) 游戏玩法系统，用带有主观判断的并行系统来补充 Unreal 的内置碰撞和导航；以及 (iii) 受 90 年代游戏引擎启发的、通过构造实现高效的数据结构。

背景：凸分解 (Convex Decomposition)

为了解释系统的细节，我们需要首先建立一些与设计相关的凸几何 (Convex Geometry) 的背景知识。简而言之，凸包属性描述了任何形状，其中_连接形状内任意两点的直线也包含在该形状内_。

2D 中的凸形状示例

这与具有凹口或孔的凹形状形成对比。

2D 中的凹形状示例

游戏中的大多数空间算法，特别是光线追踪和寻路，都通过一种称为凸分解 (Convex Decomposition) 的过程，将复杂的场景划分为连接的凸体网络，从而隐式地依赖于凸包属性。

在这种数据结构中，体积的面分为两类：墙 (Walls)，封闭了组成形状的外部；以及_窗 (Windows)_，位于共享的内部边缘之间，在逻辑上是开放的。

凸分解

要追踪穿过场景的光线，我们首先识别哪个体积包含光线的起点（通常从上下文中得知）。由于凸包属性，我们知道可以将直线一直延伸到边缘上的一个点，我们通过射线平面相交来识别该点。然后我们检查边缘是否是“墙”，如果是，则我们已成功识别命中；否则，如果是“窗”，则我们返回并对新进入的体积重复该过程。

在凸分解中进行光线投射

相对于场景的大小，此算法是_局部的_，并且对于具有固定容量的边数，具有 O(1) 的复杂度，而不是检查每个墙的蛮力算法，因此具有 O(n) 的复杂度。

我们通过将每个体积与一个图元列表相关联来将该算法扩展到松散道具和移动角色，我将其称为“对象桶 (object-bucket)”，在前进到远边之前会搜索该列表以查找命中。

使用松散对象“桶”进行光线投射

通过为桶分配固定容量，这使成本保持在 O(1)。当我们考虑到每个角色都在每帧进行自己的追踪以移动时，这给了我们类似于 O(n) 的总性能复杂度，而不是蛮力，在蛮力中，每个角色都在检查每个其他角色，从而导致 O(n²) 的总性能复杂度，这对于交互式应用程序来说是不可接受的。

如果桶具有可变容量，我们可以通过在空间上递归细分桶并制作树状结构来避免“每个人都挤在一个体积中”的极端情况。对于角色的均匀分布，这具有 O(log n) 的追踪复杂度和 O(n × log n) 的总复杂度，这是游戏编程中“可以通过性能分析修复”的典型阈值。

导航 (Navigation)

凸分解的另一个用例是_寻路_。通过在每个“窗口”的中间绘制航点，我们知道我们可以通过直线将它们连接到它们的共享体积（同样，由于凸包属性）。此外，凸体内部的任何角色都可以到达该体积的任何航点，并且只要存在连接的路径，我们就可以在任意两点之间绘制一条没有碰撞的路径。

在凸“导航网格”上寻路

确定路径是否存在的算法超出了本文的范围，但它被称为 A* 搜索算法，并且在网上有很多容易搜索的文献。

通用游戏引擎中的碰撞和导航 (Collision and Navigation in General-Purpose Game Engines)

在理解这些概念如何应用于现代通用游戏引擎（如 Unity 和 Unreal）时，出现了一个曲折，即它们的关卡编辑器的架构。两者都避开了空间分解的显式构造，而是向设计者公开了一个简单的松散对象列表，这些对象是一个接一个地手动放置的（在 Unreal 中称为“Actor”，在 Unity 中称为“GameObject”）。因此，为了应用这些算法，在游戏设备上，基于启发式、经过微调的方法，在运行时构建动态数据结构。

对于碰撞和光线投射，空间分区是通过隐式链接的凸网格单元的不可见格子构建的（可以想象成 Minecraft 中的格子，只不过每个单元都有一个对象桶，而不是一个固体体素）。

这是一个 2D“四叉树”的说明。凸分解仅限于盒子和对象桶，但没有真正的“墙”

光线的起点通过量化来确定，并以与上面概述的相同方式进行，只是网格单元只有“窗口”边缘，因此我们只进行桶的碰撞检查。通过局部桶快速过滤的步骤在文献中被描述为“Broad-Phase Collision（广阶段碰撞检测）”。

通过广阶段空间分区追踪光线（大大简化）。

由于矩形网格单元可以干净地划分为 8 个子单元，因此这种格子数据结构称为“八叉树 (Octree)。由于其简单性，Octree 是最常见的空间分区，但也存在其他有趣的方案，并且生产中的解决方案通常有几个有趣的优化，这些优化超出了本摘要的范围 - 但原理是相同的。Unreal 和 Unity 过去都依赖于 PhysX 库来完成这项任务，尽管 Unreal 已过渡到名为 Chaos 的内部解决方案。另一个值得注意的解决方案是 Jolt，它最初是为游戏 Horizon Zero Dawn 开发的，还有 Havok，它已经存在很长时间了，最近最著名/最近为 Nintendo 的 Breath of the Wild 提供支持。

“我就像一家价值数百万美元的公司开发游戏一样开发我的独立游戏”并不是一个成功的策略。

对于导航，通用引擎依赖于手动放置的体积，以便在后台线程上执行许多连续的光线投射，从而异步填充可以执行寻路的连接的“地面形状”。这个过程更多的是艺术而不是科学，并且依赖于大量的微调参数，这些参数需要设计师不断调整才能获得良好的结果。特别是 Unreal，依赖于 Recast 库来完成这项任务。

来自 Recast Navigation 系统的屏幕截图，来自他们的官方 GitHub 页面。

这些通用动态解决方案的缺点是 CPU 和 RAM 要求高于预计算的显式分解，并且它们更有可能表现出可变的 O(n × log n) 复杂度，这需要费力的性能调整。此外，它们将构建分区的全部工作转移到最终用户的游戏设备上，而不是允许静态场景数据在开发人员工作站上提前“烹饪 (cooked)”。

温故而知新 (Looking Forward by Looking Backward)

它们在大团队的生产环境中是可行的，但在我的情况下，它们抵制了我的所有三个高级目标。因此，我开始寻找替代方案 - 不是要完全替换这些功能，而是要用并行系统来补充它们，以用于它们不太适用的特定情况。

事实上，原则上它们都共享一个公共数据结构，这让我觉得我应该能够制作一个可以“一物二用”的工具。

在寻找灵感时，我开始想到 90 年代中期的射击游戏，这些游戏在_非常_适度的低功耗商用 PC 上完成了我想要的很多事情，特别是 DOOM (1993) 和 DESCENT (1995)。这些游戏是如何工作的？我是否可以利用这些遗留技术来超越通用解决方案的性能和生产力限制？

DOOM：二叉空间分割 (Binary Space Partitioning)

id Software 于 1993 年开发的 DOOM 的游戏过程

在原始 DOOM 中，像恶魔和子弹这样的松散对象非常稀疏，其中墙壁碰撞占据了运行时复杂度的大部分。DOOM 关卡编辑器允许主要任意放置墙壁，但随后运行一种特殊的分解算法，将其分解为称为_二叉空间分割 (Binary Space Partitioning, BSP)_ 的显式凸区域。

原始 DOOM 关卡编辑器的屏幕截图。

其思想是随机选择一面墙，然后考虑将其余的墙细分为位于该墙平面前方或后方的墙（将跨越平面的墙细分为两部分）。对于这两个子集，您反复进行，直到耗尽所有墙，并且细分的叶子上剩下的就是场景的凸分区，可以在关卡数据中提前计算和存储。

来自 Valve 的 Source Engine 文档的图表，演示了通过二叉空间分割进行凸分解。

原始 DOOM 通过强制所有墙壁完全垂直来简化这些 BSP，因此分区主要是 2D 的，尽管后来的 Quake 和 Unreal Tournament 版本也使用了相同的技术，并带有倾斜的几何体。

虽然研究它以了解广阶段碰撞检测如何在历史上发展很有趣，但我并不觉得有很多东西可以利用。

DESCENT：通过构造实现凸性 (Convex By-Construction)

我研究的另一个有趣的案例是 Descent，它自诩为第一个“全 3D”射击游戏，具有复杂的体积填充几何体，而不是像 DOOM 那样主要扁平到水平面上。

Interplay 于 1995 年开发的 Descent 的游戏过程

通过摆弄模组社区的关卡编辑器 DLE，我更好地理解了他们是如何实现这一点的，在 DLE 中，关卡是由凸“段 (segments)”构建的，每个凸“段 (segments)”都是六面长方体六面体。乍一看，这似乎是一个限制性的限制，会导致矩形腔室，但跨边缘和角落的创造性链接实际上可以通过足够的创造力产生您想要的几乎任何形状。此外，将面限制为全部为四边形简化了纹理和材质的应用方式，而不必考虑奇怪的三角形拓扑结构。

Descent 关卡编辑器的屏幕截图。乍一看它看起来像一个网格编辑器，但实际上您正在编辑链接的长方体“段 (segments)”。

2018 年，最初的开发人员重新召集起来开发精神继任者 Overload，其中一个社区 关卡编辑器 和教程系列以周到的方式扩展了相同的想法。真正吸引我眼球的是他们如何将“应用材质”的想法扩展到四边形面，以组装具有现代外观（而不是低多边形）的套件。例如，岩石面具有粗糙的几何形状，可以填充缝隙，使这些区域具有有机外观。

Overload 关卡编辑器教程系列中的第一个视频

玩这些工具对我来说是一个重要的_顿悟_时刻 - 通过从凸形状构建，无需像 BSP 那样进行任何类型的“分解”，因为空间是通过构造进行分区的。

我决定以此为起点，然后朝着自己的方向前进。

Nightshift Galaxy Scaffold

我没有像 Overload 团队那样构建一个完全独立的应用程序，而是决定在 Unreal Level Editor 内部构建。这是一种权衡 - 一方面，它限制了向社区提供模组工具的便利性，这是我一直考虑的事情。但另一方面，它大大减少了我需要编写的代码量（因为应用程序框架/资产处理/撤消系统已经到位），并让我专注于我的增值部分，而不是重新实现 Unreal 已经完美处理的所有其他松散对象。

游戏开发直播将于_明天_太平洋标准时间中午恢复。正在考虑演示我一直在为关卡设计制作的“Scaffold”工具，也许还有一点关于 3D 场景几何体的讲解。#indiegamedev pic.twitter.com/eaWQEAOSvv — Max! (@xewlupus) 2025 年 4 月 3 日

在 Unreal Level Editor 内部运行的 Scaffold 的早期先睹为快。

我不会详细介绍所有无聊的细节，只需说对于 Unreal 爱好者来说，我从 SplineComponentVisualizer 作为参考开始，并从那里构建了自己的工具。花了大约一周的时间从大约 2500 行代码中获得一个 MVP 版本。我拥有所有基本操作 - 用于顶点、边、面和“立方体 (cubs)”（我对凸段的称呼 - “小隔间 (cubby hole)”的缩写）的选择模式、基本拉伸和桥接选项，以及用于立方体、环和圆柱体等常见形状的“图章 (stamps)”。

对于灰色的“粗略 (blockout)”墙壁，我正在使用来自 GeometryScripting 扩展的 DynamicMesh 对象（但我打算用实例化的装饰套件网格替换它们），并且为了为每个立方体创建“真实碰撞”触发体积，我通过引用 ShapeComponent 和 BoxComponent 的实现添加了 PrimitiveComponent 的 CubComponent 子类型。

我编写了一个“scaffold 光线追踪”测试，即使在其简单的快速而肮脏的实现中，也比使用 Unreal 的内置碰撞进行普通光线追踪快 100 倍。我不会将其用于玩家子弹或通用追踪，但对于专门的批处理，例如敌人子弹地狱模式，它开启了很多机会。

直播后：更新了 BulletManager，不仅使用与帧速率无关的时间，而且还进行子帧位置采样以获得更高精度的模式。#ScreenshotSaturday #shmup 🎶 金星战记 OST (久石让) 🎶 https://t.co/otWOFaQrOE pic.twitter.com/K1Alnu0J8v — Max! (@xewlupus) 2025 年 3 月 1 日

来自早期子弹地狱实验直播的镜头。

但对我来说，真正的_绝招_是，正如我所预期的那样，Scaffold 数据也可以作为导航系统！我为每个共享立方体面生成一个航点，并快速检查立方体的“地板”是否是墙还是窗，并快速生成一个导航图，该导航图适用于地面单位和空中单位，而无需额外的工作。

昨天直播的更新 - Scaffold 关卡编辑器现在除了粗略墙壁碰撞之外，还为 AI 寻路生成导航数据。#screenshotsaturday pic.twitter.com/qaUStE3V1j — Max! (@xewlupus) 2025 年 4 月 5 日

在 Scaffold 内部工作的空中导航的首次测试。

此时，我对解决方案的方向充满信心，因此现在我正在充实缺失的功能，并添加更多“智能”操作，以便我可以更快地布局空间。Nightshift 和 Descent 的最大区别在于，我想退出飞船/小行星基地/下水道隧道/洞穴/工业内饰，也在外面飞行，因此我还需要开始考虑“外部船体”工具集。但我想先制作六张经过验证的游戏玩法的地图。