面向游戏场景生成的细分插槽WFC算法研究

靳仕恒，郑春辉，吕德生

1.互动媒体设计与装备服务创新文化和旅游部重点实验室，哈尔滨 150001

2.哈尔滨工业大学 建筑学院，哈尔滨 150001

伴随着数字娱乐领域相关产业的高速发展，虚拟世界在人们生产生活与娱乐活动中扮演着越来越重要的角色，但虚拟世界的构建也面临着巨大的挑战。以游戏为例，传统游戏虚拟世界的构建随着游戏世界体量的增长，生产成本随之也急速增长。程序化内容生成（PCG）技术可以通过自动化或辅助性游戏内容生成来解决上述挑战[1]。

PCG技术通过应用算法来创建道路、建筑物等三维模型，甚至整个游戏地图场景，以实现一个不需要调整或很少调整的独特外观虚拟环境[2-3]。PCG通过将部分艺术工作流从艺术家转移到程序员和技术艺术家中，在减少游戏开发工作量的同时，提供了更加易于实现的优势[4]。

PCG技术在降低游戏开发与迭代成本，提高游戏开发速度等方面有着重大的应用价值[5-6]。PCG作为生产辅助工具，在“No Mans Sky”“Bad North”等游戏及Dungeon类游戏中发挥出巨大作用（如图1）[7]。“Townscaper”游戏直接以程序化生成作为自身的核心玩法，并凭借其基于PCG的新奇交互体验，获得了广泛关注。

图1 游戏Bad North截图Fig.1 Screenshot of game Bad North

然而，PCG的实践应用仍存在许多困难。多数PCG的输出是对抽象的目标函数优化的结果，设计者对它的输出难以精确控制[8]。设计者需要一种方法能够直观地描述PCG开发中场景元素之间的约束规则。波函数坍缩算法（wave function collapse，WFC）是一种新型的程序化内容生成算法，它把模型之间的约束规则设计引入生成过程，具有模块化生成功能和高度的可拓展性[9]。WFC算法的思想是某一区域在未生成模型时，可以存在多种不同的可能性。一旦该区域的模型被确定下来，这些可能性就会消失，波函数进行崩溃，只留下最终的生成结果[10]。WFC算法以模型基础元件（基元）为基本生成单位。

传统的WFC算法只进行单层次的场景基元生成，在高精细度场景生成的应用上有很大局限性。本文在现有的WFC算法基础上[11]，提出了一种插槽多维细分的算法改进方法。该系统为每个基元创造内部细分空间，并在这些空间中生成模型，以期对PCG场景进行丰富和细化，并减少模型基元建模的工作量，为当前游戏场景的程序化内容生成提供新思路。

1 相关工作

WFC算法使用网格化的生成思路，它的基本生成单元是插槽。如图2所示，3D网格将空间分成若干立方体插槽，基元在插槽内部填充形成场景。用户需要导入制作好的模型原型，为模型原型的每个面朝向制订连接规则。算法把模型原型绕Y轴旋转0°、90°、180°、270°，得到4个基元，这样做可以使模型资源得到重复利用。在生成的过程中，不断向插槽内部填充满足连接规则的基元，实现空间的程序化生成。

图2 3D网格空间划分与基元填充Fig.2 3D grid division and slots filling

不同基元以连接规则为准进行连接，这些连接规则以模型各个方向的截面形状及功能作用为依据。如图3所示，左侧是模型原型，右侧为各界面形状，模型之间相连接的面需有相同截面[11]。算法会根据连接规则，为基元的每个面朝向计算出可成为邻居的基元组合。

图3 模型原型与各截面形状Fig.3 Prototype model and cross-sectional shapes

场景中，每个需要生成基元的位置都会创建插槽，每个插槽对应一组可选基元的集合。插槽包含一个熵值，该值与可选基元数量呈正相关，求熵值的公式如下：

式中，n为可选基元数量，P(i)是第i个可选基元的自定义概率参数，H(x)即为该插槽的熵值。

WFC算法的主循环立足于坍缩-约束传播-回溯三个步骤（如图4），具体算法如下所示。

图4 WFC主循环流程图Fig.4 WFC main loop flowchart

坍缩：计算所有待坍缩插槽的熵值，对熵值最低的插槽进行坍缩。该插槽按下式确定最终的基元选择概率：

式中，R(i)代表该基元被选中的概率，P(i)代表该基元的概率参数，H(x)代表所在插槽的熵值。

坍缩用于确定插槽中生成的基元，没有被选中的基元将会从可选基元集合中删去，并以这些基元为基础，进行约束传播步骤。

约束传播：插槽中，每个可选基元在各个面朝向都对应着一批潜在的邻居基元。当可选基元被删去后，潜在的邻居基元在邻居插槽中出现的可能性会下降甚至消失。算法需要借助约束传播步骤，将各个插槽中不被允许出现的可选基元一一删去，保证由坍缩带来的规则约束传播到各个插槽。

回溯：在算法进行约束传播的过程中，有时会导致多个邻居插槽可选基元的规则约束在某一块插槽相互矛盾，该插槽可选基元数目降为0，无法生成任何基元。这时，就需要引入回溯机制。在每一个插槽的坍缩-约束传播步骤中，各个插槽被删除的可选基元会保存为历史信息。这些历史信息会被读取并还原，坍缩进度会退回到最近几个步骤进行之前的状态，之后重新进行这部分插槽的坍缩。

WFC算法最初应用于2D纹理或者瓦片地图的绘制上。Sandhu等人[10]通过使用非局部约束，权重计算和修改WFC的传播路径，改变了传统WFC方法局部约束的局限性，优化了生成效果。将WFC算法引入到3D空间之后，Kim等人[8]将基于网格的WFC算法拓展到了基于图的系统；Møller等人[12]则借助增长网格网络，形成密铺的不规则网格作为插槽，实现了基于不规则插槽的建筑生成。此外，Karth等人[13]使WFC算法能够通过机器学习生成程序化内容；Lu等人[14]则将WFC算法引入建筑领域，探索了离散化单元布局的建筑程序化生成。

目前，大多数WFC算法局限于纯粹的建筑景观，没有形成深入精细的空间以及与之配套的潜在物品，也缺少关于细化网格插槽的尝试。据此，本文提出WFC算法的一种插槽多维细分方法，使同一种轮廓的模型将能借助细分对应多种不同的外观形式，这将会减少约束与建模方面的工作量，同时，在模型的内部也能够形成富有随机性的空间，在一定程度上降低程序化空间生成的重复性。

2 插槽多维细分的设计与实现

本文中场景生成的改进方法如图5算法结构概要所示，改进重点体现在模型原型与连接规则部分，并添加区块划分与区块坍缩步骤，实现了插槽的多维细分。

图5 算法结构概要Fig.5 Summary of algorithm structure

2.1 模型原型及约束属性

模型原型定义为用户导入的一组用于场景生成的基本模型，模型原型的每个面朝向上都包含着一组约束规则。用户通过调节约束规则的各个参数，能够为模型原型制订连接规则，限制其各个面朝向潜在的邻居模型。面朝向主要的约束属性如表1所示。

表1 面朝向主要的约束属性Table 1 Constraint properties of each side

基元由模型原型旋转而来，基元分为容器基元与子基元两种。容器基元用于填充插槽。子基元则是对容器基元的细化，是在容器基元内部的顶面、底面、前面、左面、后面、右面上依托容器基元所生成的模型，子基元类型如表2所示。如图6，左侧是容器基元，右侧是带有子基元的容器基元。吊灯（顶面子基元），立柱（前面、左面、后面、右面子基元），汽车（底面子模型）的加入，丰富了容器基元细节。

表2 子基元类型Table 2 Sub-modules type

图6 子基元生成前后对比Fig.6 Comparison before and after sub-modules generation

容器基元中，面朝向约束属性withInner为true的面朝向都会生成子插槽，子基元在子插槽中填充，with Inner的逻辑表达式如下：式中，C代表容器基元的某一面朝向。connector代表连接器，该值是模型之间可以相互连接的基础，反映了该面朝向的模型截面形状或者用户需要的连接功能。当该值为1时，说明模型的截面铺满了插槽的截面，如图7中两个容器基元相对接的面朝向，它们的connector=1，两个插槽的空余空间被模型隔开，“墙壁”为子插槽的生成留下了充足的位置，可以出现壁灯、壁挂等子基元。

图7 容器基元面朝向约束属性Fig.7 Face orientation constraint property of container module

子插槽的生成并不总是依附于墙壁，如图8，需要在道路侧面的左右子插槽中生成路灯。为此，公式（1）额外规定当passage为true时，withInner为true。passage意味着该面朝向为通道，但需要细节补充，如：从道路通向楼房，从一个房间通向另一个房间，这种地方往往需要出现门、窗、路灯、路牌等子基元。

图8 子基元生成示意图Fig.8 Schematic diagram of sub-modules generation

2.2 约束规则

2.2.1 容器基元-子基元的约束规则

容器基元-子基元基本约束条件需满足的公式如下：

式中，I代表子基元向容器基元的约束规则，innerSetting是C中的结构体，存储向子基元的约束规则。符号∧左侧的公式保证子基元与容器基元对应面连接器适配；右侧参数withInner保证容器基元的该面朝向位置可以生成子插槽。

仅满足基本约束规则的场景生成常会带来如图9的错误结果。因此，约束规则还需考虑子基元与容器基元相邻面的关系。

图9 仅考虑子基元-容器基元基本约束条件带来的错误情况Fig.9 Error case of only basic constraints of sub-modules-container modules considered

子基元-容器基元相邻面约束条件满足如下两个公式：

式中，CL代表容器基元的相邻面朝向，IL代表子基元正对着该相邻面的面朝向。如图10，具有相同下角标的CL与IL能够满足上述面朝向对应关系。子基元的balance属性表示该方向上模型已经完整，不必继续往该方向生成，以图中的半个汽车为例，汽车左、右、后3个方向为balance，前方反之，它还要补充汽车的另一半来构成完整模型。allowTurn表示子基元在IL面朝向的邻居可以是容器基元CL面朝向上的子基元。公式（3）则要求当CL为passage时，子基元的IL面朝向为passable，能够留出空间，不会把通道堵住。

图10 容器基元-子基元的约束规则示意图Fig.10 Schematic diagram of constraint rules for container modules-sub-modules

如图10，方框代表容器基元，圆圈代表子插槽，虚线代表容器withInner为false的面，实线代表withInner为true的面，箭头代表容器基元为passage的面。大写字母代表公式（1）、（2）、（3）中出现的基元面朝向，小写字母代表子基元面朝向需要满足的约束属性。图中子插槽左侧CL的withInner为false，对应的IL不需要满足任何约束属性；右侧CL为边界，有通道，对应的IL需要满足约束规则passable∧(balance∨allowTurn)。

只有符合容器基元-子基元基本约束条件，且满足容器基元四个相邻面的子基元-容器基元相邻面约束条件，一个子基元才会被允许在容器基元对应面上出现。满足上述两个约束条件的生成效果如图11所示。

图11 通过容器基元-子基元约束规则实现的效果Fig.11 Effect achieved by container modules-sub-modules constraint rules

2.2.2 子基元-子基元的约束规则

当考虑子基元周围是否可以产生另一个子基元时，有直走、内转、外转3种邻接情况，如图12所示。图中，方框代表容器基元，圆圈代表子插槽，子基元在子插槽中生成；虚线代表容器withInner为false的面，实线代表withInner为true的面。

图12 子基元-子基元约束规则的3种形式Fig.12 Three forms of sub-module-sub-module constraint rules

直走：子基元与子基元属于同一种基元类型，两者在不同的插槽中存在直接相邻的关系；

内转：子基元与子基元存在直接相邻的关系，但两者子基元类型（如表2）不同，且共同处于同一个容器基元中；

外转：子基元与子基元存在直接相邻的关系，但是两者子基元类型（如表2）不同，且处于不同的容器基元中。如图13所示，多个容器基元中的侧面子基元连接成阴角线，阴角线拐角处两端的一对子基元呈现外转关系，它们相连接部分的面朝向allowTurn属性为true。

图13 外转情况示意图Fig.13 Schematic diagram of external transfer

因此，子基元每个面朝向潜在的邻居都需要考虑直走、内转、外转3种情况。allowTurn是子基元面朝向的约束规则，表示子基元在该面朝向上可以与呈现转弯关系的子基元建立邻接关系。

当判断一个子基元的转弯的面朝向上是否可以生成某个特定子基元时，需要满足以下两个公式：

式中，I1、I2是两个相邻子基元相对接的面朝向。对于直走的情况，仅需保证公式（4）成立即可。

3 交互式场景生成系统

本文引入交互式的场景生成系统，将用户感知纳入其中，为用户提供一个仿真交互场所[15]，让用户直观地观测生成效果，改进生成效果，使场景生成更加符合设计者的需求。

场景生成方式主要分为4种：场景自动生成、增加模型、修改模型以及强制替换模型。本文改进后的WFC算法场景生成系统的基本结构如图14所示，左侧为传统WFC算法的场景生成系统，右侧为本文改进后的场景生成系统。其中，生成容器基元之后的步骤统称为空间细化。

图14 场景生成系统结构图Fig.14 Structure diagram of scene generation system

3.1 区块划分

区块是插槽的集合，包括团块和房间两种。在插槽完成坍缩，容器基元在场景中生成之后，进行区块划分。团块是由n3个插槽共同构成的立方体区域，n代表团块边长，团块每条边上分布的插槽数量为n，n值可由用户设定。房间是由多个容器基元围成的相对封闭的区域。

在区块划分的过程中，需要把插槽放入与其位置相对应的团块中。对于能够围成封闭体积的容器基元，还要将它加入对应的房间。

区块完整性检测包括团块完整性和房间完整性检测两部分。团块的完整性检测判断已生成基元的数量是否等于n3。房间完整性检测判定依据是房间内所有模型向室内的面朝向已经生成邻居，保证房间闭合。每次房间加入新的室内容器基元，都会计算它们每个通往室内的面朝向上是否已经生成了容器基元。其中，基元的面朝向是否朝向室内由以下表达式推断：

在图15中，方框为容器基元，虚线代表朝向室内的面朝向，箭头代表容器基元为passage的面。房间A、B为闭合的房间，房间C则右侧未闭合。

图15 房间划分示意图Fig.15 Schematic diagram of room division

3.2 区块坍缩

插槽坍缩用于确定插槽生成的容器基元，区块坍缩则用于确定区块内所有子插槽生成的子基元。区块坍缩过程以一个区块为输入，将容器基元中属性withInner为true的面朝向生成可用的子插槽。

其次，获取这些子插槽各方向的邻居子插槽。依次寻找子插槽旁边是否存在相互关系为直走、右转、左转的邻居子插槽，找到邻居之后，就会建立它们之间的邻居关系（直走、右转或左转）。

之后，所有子插槽进行容器基元-子基元的约束规则限制，筛选符合容器基元要求的子基元。以那些被删除的子基元为依据，进行约束传播步骤。

最后，对待坍缩子插槽进行WFC主循环坍缩，并进行子基元生成。

经过区块坍缩后，可以形成图16中的效果。

图16 空间细化效果示意图Fig.16 Schematic diagram of spatial refinement effect

3.3 交互实现

本文结合场景生成系统，利用Unity3d引擎，实现了交互式场景生成系统，支持用户自定义导入模型的面朝向约束属性设置，如图17所示。

图17 面朝向约束属性Fig.17 Constraint properties of face orientation

在人机交互与参数化生成方面，设置团块边长与增加模型范围为可调节参数，场景自动生成设为可选功能，并可选择要强制修改的模型基元；交互实现中4种场景生成的方式如下所示。

（1）场景自动生成：用户在场景中可以自由行走，场景会依次将靠近用户位置的团块输入场景生成系统，坍缩团块内所有插槽并进行空间细化。

（2）增加模型：以输入插槽在输入面朝向上的邻居插槽为中心，n3个插槽围成的立方体区域进行坍缩，之后进行空间细化。

（3）修改模型：如果输入插槽已经坍缩，在不影响周围插槽坍缩结果的前提下，该插槽的坍缩结果随机替换为另一个可用的基元，并重新进行空间细化。

修改模型、强制修改或删除模型这些操作涉及对坍缩结果的撤销，所以，执行之前需要进行回溯步骤：查找到相关插槽及其子插槽坍缩的历史记录，并还原这些历史记录。

（4）强制修改或删除模型：强制将输入插槽坍缩为选定的基元，其周围的插槽以及子插槽也会重新坍缩为适应该基元作为邻居的情况，之后进行修改范围内的空间细化。删除模型则把插槽的坍缩结果强制修改为空基元。

修改模型、强制修改或删除模型的效果如图18所示。

图18 修改模型与强制修改模型效果示意图Fig.18 Schematic diagram of model modification and forced modification effect

4 实验结果与分析

4.1 实验设计

为了验证细分插槽WFC算法的有效性，本文基于交互式场景生成系统，将算法纳入应用场景，考察细分插槽及容器基元-子基元的约束、子基元-子基元的约束在场景生成中的实际效果。

此外，为了验证算法的改进效果，本文统计了在实现相同效果前提下，使用细分插槽WFC算法与使用传统的WFC算法的差异。本文将场景按照复杂程度分为3组，对两种算法各自使用的基元数量与约束规则数量进行了对比。场景一为仅有道路和房屋的场景（如图19（a））；场景二追加了一种车辆与一种路灯（如图19（b））；场景三进一步追加了一种车辆与基于约束规则的车流模拟（如图19（c））。

图19 实验场景概览Fig.19 Overview of experimental scenarios

4.2 实验结果

在实验场景中，细分插槽WFC算法依赖容器基元-子基元的约束规则，能够实现汽车靠右行与房屋正面临街等效果；依赖子基元-子基元的约束规则，能够实现路灯的自然排布与房屋连接等效果。在场景三基于约束规则的车流模拟中，左右方向为通行车流，前后方向为等候车流。十字路口容器基元向汽车子基元传递交通信息作为约束规则，汽车子基元之间相互约束形成不同的车流（如图19）。在交互式场景生成系统中，使用者可以对场景进行实时调整（如图20）。

图20 运行中的交互式场景生成Fig.20 Interactive scene generation on running

为了让传统的WFC算法能够实现相同的效果，实验把容器基元与子基元可能的组合方式分别制作成传统WFC算法的基元，并进行场景生成。实验统计了在实验场景中使用两种算法带来的基元数量以及面朝向约束规则数量的差异（见表3）。

表3 对比实验Table 3 Contrast experiment

实验结果表明，本文提出的细分插槽WFC算法能够产生丰富、细节可控的环境。同时，在与传统WFC算法的对比中，由于容器基元中的子基元能够凭借算法替换为其他子基元，使同一容器基元能对应多种外观形式，因此，在面对细节要求更高的游戏场景生成时，插槽的多维细分方法更加灵活，能减小建模与约束的工作量，并减少基元的数目，提供更易实现的优势。

5 结束语

本文在传统的WFC算法基础上，提出了插槽多维细分的改进方法，将WFC算法中使用的模型扩充为容器基元与子模型两类，将约束规则拓展为容器基元-容器基元、容器基元-子基元、子基元-子基元三类，配合区块划分与区块坍缩等策略，拓宽了WFC算法生成结果的丰富性和应用范围，使之能够胜任更复杂的模型关联情况，能够生成更加精细化的游戏空间。本文改进算法的提出，使同一种轮廓的模型基元借助细分对应多种不同的外观形式，进而减少约束与手动建模方面的工作量。同时，在模型的内部也能够形成富有随机性的空间，降低程序化空间生成的重复性。此外，交互系统的加入，可以将用户感知纳入其中，让用户直观地观察阶段性生成效果并动态改进效果，用户实时交互算法所生成的阶段性效果能使程序化生成的结果更加符合受众的设计需求。