面向游戲場景生成的細分插槽WFC算法研究

靳仕恒，鄭春輝，呂德生

1.互動媒體設計與裝備服務創(chuàng)新文化和旅游部重點實驗室，哈爾濱 150001

2.哈爾濱工業(yè)大學 建筑學院，哈爾濱 150001

伴隨著數(shù)字娛樂領域相關產業(yè)的高速發(fā)展，虛擬世界在人們生產生活與娛樂活動中扮演著越來越重要的角色，但虛擬世界的構建也面臨著巨大的挑戰(zhàn)。以游戲為例，傳統(tǒng)游戲虛擬世界的構建隨著游戲世界體量的增長，生產成本隨之也急速增長。程序化內容生成（PCG）技術可以通過自動化或輔助性游戲內容生成來解決上述挑戰(zhàn)[1]。

PCG技術通過應用算法來創(chuàng)建道路、建筑物等三維模型，甚至整個游戲地圖場景，以實現(xiàn)一個不需要調整或很少調整的獨特外觀虛擬環(huán)境[2-3]。PCG通過將部分藝術工作流從藝術家轉移到程序員和技術藝術家中，在減少游戲開發(fā)工作量的同時，提供了更加易于實現(xiàn)的優(yōu)勢[4]。

PCG技術在降低游戲開發(fā)與迭代成本，提高游戲開發(fā)速度等方面有著重大的應用價值[5-6]。PCG作為生產輔助工具，在“No Mans Sky”“Bad North”等游戲及Dungeon類游戲中發(fā)揮出巨大作用（如圖1）[7]?！癟ownscaper”游戲直接以程序化生成作為自身的核心玩法，并憑借其基于PCG的新奇交互體驗，獲得了廣泛關注。

圖1 游戲Bad North截圖Fig.1 Screenshot of game Bad North

然而，PCG的實踐應用仍存在許多困難。多數(shù)PCG的輸出是對抽象的目標函數(shù)優(yōu)化的結果，設計者對它的輸出難以精確控制[8]。設計者需要一種方法能夠直觀地描述PCG開發(fā)中場景元素之間的約束規(guī)則。波函數(shù)坍縮算法（wave function collapse，WFC）是一種新型的程序化內容生成算法，它把模型之間的約束規(guī)則設計引入生成過程，具有模塊化生成功能和高度的可拓展性[9]。WFC算法的思想是某一區(qū)域在未生成模型時，可以存在多種不同的可能性。一旦該區(qū)域的模型被確定下來，這些可能性就會消失，波函數(shù)進行崩潰，只留下最終的生成結果[10]。WFC算法以模型基礎元件（基元）為基本生成單位。

傳統(tǒng)的WFC算法只進行單層次的場景基元生成，在高精細度場景生成的應用上有很大局限性。本文在現(xiàn)有的WFC算法基礎上[11]，提出了一種插槽多維細分的算法改進方法。該系統(tǒng)為每個基元創(chuàng)造內部細分空間，并在這些空間中生成模型，以期對PCG場景進行豐富和細化，并減少模型基元建模的工作量，為當前游戲場景的程序化內容生成提供新思路。

1 相關工作

WFC算法使用網格化的生成思路，它的基本生成單元是插槽。如圖2所示，3D網格將空間分成若干立方體插槽，基元在插槽內部填充形成場景。用戶需要導入制作好的模型原型，為模型原型的每個面朝向制訂連接規(guī)則。算法把模型原型繞Y軸旋轉0°、90°、180°、270°，得到4個基元，這樣做可以使模型資源得到重復利用。在生成的過程中，不斷向插槽內部填充滿足連接規(guī)則的基元，實現(xiàn)空間的程序化生成。

圖2 3D網格空間劃分與基元填充Fig.2 3D grid division and slots filling

不同基元以連接規(guī)則為準進行連接，這些連接規(guī)則以模型各個方向的截面形狀及功能作用為依據(jù)。如圖3所示，左側是模型原型，右側為各界面形狀，模型之間相連接的面需有相同截面[11]。算法會根據(jù)連接規(guī)則，為基元的每個面朝向計算出可成為鄰居的基元組合。

圖3 模型原型與各截面形狀Fig.3 Prototype model and cross-sectional shapes

場景中，每個需要生成基元的位置都會創(chuàng)建插槽，每個插槽對應一組可選基元的集合。插槽包含一個熵值，該值與可選基元數(shù)量呈正相關，求熵值的公式如下：

式中，n為可選基元數(shù)量，P(i)是第i個可選基元的自定義概率參數(shù)，H(x)即為該插槽的熵值。

WFC算法的主循環(huán)立足于坍縮-約束傳播-回溯三個步驟（如圖4），具體算法如下所示。

圖4 WFC主循環(huán)流程圖Fig.4 WFC main loop flowchart

坍縮：計算所有待坍縮插槽的熵值，對熵值最低的插槽進行坍縮。該插槽按下式確定最終的基元選擇概率：

式中，R(i)代表該基元被選中的概率，P(i)代表該基元的概率參數(shù)，H(x)代表所在插槽的熵值。

坍縮用于確定插槽中生成的基元，沒有被選中的基元將會從可選基元集合中刪去，并以這些基元為基礎，進行約束傳播步驟。

約束傳播：插槽中，每個可選基元在各個面朝向都對應著一批潛在的鄰居基元。當可選基元被刪去后，潛在的鄰居基元在鄰居插槽中出現(xiàn)的可能性會下降甚至消失。算法需要借助約束傳播步驟，將各個插槽中不被允許出現(xiàn)的可選基元一一刪去，保證由坍縮帶來的規(guī)則約束傳播到各個插槽。

回溯：在算法進行約束傳播的過程中，有時會導致多個鄰居插槽可選基元的規(guī)則約束在某一塊插槽相互矛盾，該插槽可選基元數(shù)目降為0，無法生成任何基元。這時，就需要引入回溯機制。在每一個插槽的坍縮-約束傳播步驟中，各個插槽被刪除的可選基元會保存為歷史信息。這些歷史信息會被讀取并還原，坍縮進度會退回到最近幾個步驟進行之前的狀態(tài)，之后重新進行這部分插槽的坍縮。

WFC算法最初應用于2D紋理或者瓦片地圖的繪制上。Sandhu等人[10]通過使用非局部約束，權重計算和修改WFC的傳播路徑，改變了傳統(tǒng)WFC方法局部約束的局限性，優(yōu)化了生成效果。將WFC算法引入到3D空間之后，Kim等人[8]將基于網格的WFC算法拓展到了基于圖的系統(tǒng)；M?ller等人[12]則借助增長網格網絡，形成密鋪的不規(guī)則網格作為插槽，實現(xiàn)了基于不規(guī)則插槽的建筑生成。此外，Karth等人[13]使WFC算法能夠通過機器學習生成程序化內容；Lu等人[14]則將WFC算法引入建筑領域，探索了離散化單元布局的建筑程序化生成。

目前，大多數(shù)WFC算法局限于純粹的建筑景觀，沒有形成深入精細的空間以及與之配套的潛在物品，也缺少關于細化網格插槽的嘗試。據(jù)此，本文提出WFC算法的一種插槽多維細分方法，使同一種輪廓的模型將能借助細分對應多種不同的外觀形式，這將會減少約束與建模方面的工作量，同時，在模型的內部也能夠形成富有隨機性的空間，在一定程度上降低程序化空間生成的重復性。

2 插槽多維細分的設計與實現(xiàn)

本文中場景生成的改進方法如圖5算法結構概要所示，改進重點體現(xiàn)在模型原型與連接規(guī)則部分，并添加區(qū)塊劃分與區(qū)塊坍縮步驟，實現(xiàn)了插槽的多維細分。

圖5 算法結構概要Fig.5 Summary of algorithm structure

2.1 模型原型及約束屬性

模型原型定義為用戶導入的一組用于場景生成的基本模型，模型原型的每個面朝向上都包含著一組約束規(guī)則。用戶通過調節(jié)約束規(guī)則的各個參數(shù)，能夠為模型原型制訂連接規(guī)則，限制其各個面朝向潛在的鄰居模型。面朝向主要的約束屬性如表1所示。

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

基元由模型原型旋轉而來，基元分為容器基元與子基元兩種。容器基元用于填充插槽。子基元則是對容器基元的細化，是在容器基元內部的頂面、底面、前面、左面、后面、右面上依托容器基元所生成的模型，子基元類型如表2所示。如圖6，左側是容器基元，右側是帶有子基元的容器基元。吊燈（頂面子基元），立柱（前面、左面、后面、右面子基元），汽車（底面子模型）的加入，豐富了容器基元細節(jié)。

表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，兩個插槽的空余空間被模型隔開，“墻壁”為子插槽的生成留下了充足的位置，可以出現(xiàn)壁燈、壁掛等子基元。

圖7 容器基元面朝向約束屬性Fig.7 Face orientation constraint property of container module

子插槽的生成并不總是依附于墻壁，如圖8，需要在道路側面的左右子插槽中生成路燈。為此，公式（1）額外規(guī)定當passage為true時，withInner為true。passage意味著該面朝向為通道，但需要細節(jié)補充，如：從道路通向樓房，從一個房間通向另一個房間，這種地方往往需要出現(xiàn)門、窗、路燈、路牌等子基元。

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

2.2 約束規(guī)則

2.2.1 容器基元-子基元的約束規(guī)則

容器基元-子基元基本約束條件需滿足的公式如下：

式中，I代表子基元向容器基元的約束規(guī)則，innerSetting是C中的結構體，存儲向子基元的約束規(guī)則。符號∧左側的公式保證子基元與容器基元對應面連接器適配；右側參數(shù)withInner保證容器基元的該面朝向位置可以生成子插槽。

僅滿足基本約束規(guī)則的場景生成常會帶來如圖9的錯誤結果。因此，約束規(guī)則還需考慮子基元與容器基元相鄰面的關系。

圖9 僅考慮子基元-容器基元基本約束條件帶來的錯誤情況Fig.9 Error case of only basic constraints of sub-modules-container modules considered

子基元-容器基元相鄰面約束條件滿足如下兩個公式：

式中，CL代表容器基元的相鄰面朝向，IL代表子基元正對著該相鄰面的面朝向。如圖10，具有相同下角標的CL與IL能夠滿足上述面朝向對應關系。子基元的balance屬性表示該方向上模型已經完整，不必繼續(xù)往該方向生成，以圖中的半個汽車為例，汽車左、右、后3個方向為balance，前方反之，它還要補充汽車的另一半來構成完整模型。allowTurn表示子基元在IL面朝向的鄰居可以是容器基元CL面朝向上的子基元。公式（3）則要求當CL為passage時，子基元的IL面朝向為passable，能夠留出空間，不會把通道堵住。

圖10 容器基元-子基元的約束規(guī)則示意圖Fig.10 Schematic diagram of constraint rules for container modules-sub-modules

如圖10，方框代表容器基元，圓圈代表子插槽，虛線代表容器withInner為false的面，實線代表withInner為true的面，箭頭代表容器基元為passage的面。大寫字母代表公式（1）、（2）、（3）中出現(xiàn)的基元面朝向，小寫字母代表子基元面朝向需要滿足的約束屬性。圖中子插槽左側CL的withInner為false，對應的IL不需要滿足任何約束屬性；右側CL為邊界，有通道，對應的IL需要滿足約束規(guī)則passable∧(balance∨allowTurn)。

只有符合容器基元-子基元基本約束條件，且滿足容器基元四個相鄰面的子基元-容器基元相鄰面約束條件，一個子基元才會被允許在容器基元對應面上出現(xiàn)。滿足上述兩個約束條件的生成效果如圖11所示。

圖11 通過容器基元-子基元約束規(guī)則實現(xiàn)的效果Fig.11 Effect achieved by container modules-sub-modules constraint rules

2.2.2 子基元-子基元的約束規(guī)則

當考慮子基元周圍是否可以產生另一個子基元時，有直走、內轉、外轉3種鄰接情況，如圖12所示。圖中，方框代表容器基元，圓圈代表子插槽，子基元在子插槽中生成；虛線代表容器withInner為false的面，實線代表withInner為true的面。

圖12 子基元-子基元約束規(guī)則的3種形式Fig.12 Three forms of sub-module-sub-module constraint rules

直走：子基元與子基元屬于同一種基元類型，兩者在不同的插槽中存在直接相鄰的關系；

內轉：子基元與子基元存在直接相鄰的關系，但兩者子基元類型（如表2）不同，且共同處于同一個容器基元中；

外轉：子基元與子基元存在直接相鄰的關系，但是兩者子基元類型（如表2）不同，且處于不同的容器基元中。如圖13所示，多個容器基元中的側面子基元連接成陰角線，陰角線拐角處兩端的一對子基元呈現(xiàn)外轉關系，它們相連接部分的面朝向allowTurn屬性為true。

圖13 外轉情況示意圖Fig.13 Schematic diagram of external transfer

因此，子基元每個面朝向潛在的鄰居都需要考慮直走、內轉、外轉3種情況。allowTurn是子基元面朝向的約束規(guī)則，表示子基元在該面朝向上可以與呈現(xiàn)轉彎關系的子基元建立鄰接關系。

當判斷一個子基元的轉彎的面朝向上是否可以生成某個特定子基元時，需要滿足以下兩個公式：

式中，I1、I2是兩個相鄰子基元相對接的面朝向。對于直走的情況，僅需保證公式（4）成立即可。

3 交互式場景生成系統(tǒng)

本文引入交互式的場景生成系統(tǒng)，將用戶感知納入其中，為用戶提供一個仿真交互場所[15]，讓用戶直觀地觀測生成效果，改進生成效果，使場景生成更加符合設計者的需求。

場景生成方式主要分為4種：場景自動生成、增加模型、修改模型以及強制替換模型。本文改進后的WFC算法場景生成系統(tǒng)的基本結構如圖14所示，左側為傳統(tǒng)WFC算法的場景生成系統(tǒng)，右側為本文改進后的場景生成系統(tǒng)。其中，生成容器基元之后的步驟統(tǒng)稱為空間細化。

圖14 場景生成系統(tǒng)結構圖Fig.14 Structure diagram of scene generation system

3.1 區(qū)塊劃分

區(qū)塊是插槽的集合，包括團塊和房間兩種。在插槽完成坍縮，容器基元在場景中生成之后，進行區(qū)塊劃分。團塊是由n3個插槽共同構成的立方體區(qū)域，n代表團塊邊長，團塊每條邊上分布的插槽數(shù)量為n，n值可由用戶設定。房間是由多個容器基元圍成的相對封閉的區(qū)域。

在區(qū)塊劃分的過程中，需要把插槽放入與其位置相對應的團塊中。對于能夠圍成封閉體積的容器基元，還要將它加入對應的房間。

區(qū)塊完整性檢測包括團塊完整性和房間完整性檢測兩部分。團塊的完整性檢測判斷已生成基元的數(shù)量是否等于n3。房間完整性檢測判定依據(jù)是房間內所有模型向室內的面朝向已經生成鄰居，保證房間閉合。每次房間加入新的室內容器基元，都會計算它們每個通往室內的面朝向上是否已經生成了容器基元。其中，基元的面朝向是否朝向室內由以下表達式推斷：

在圖15中，方框為容器基元，虛線代表朝向室內的面朝向，箭頭代表容器基元為passage的面。房間A、B為閉合的房間，房間C則右側未閉合。

圖15 房間劃分示意圖Fig.15 Schematic diagram of room division

3.2 區(qū)塊坍縮

插槽坍縮用于確定插槽生成的容器基元，區(qū)塊坍縮則用于確定區(qū)塊內所有子插槽生成的子基元。區(qū)塊坍縮過程以一個區(qū)塊為輸入，將容器基元中屬性withInner為true的面朝向生成可用的子插槽。

其次，獲取這些子插槽各方向的鄰居子插槽。依次尋找子插槽旁邊是否存在相互關系為直走、右轉、左轉的鄰居子插槽，找到鄰居之后，就會建立它們之間的鄰居關系（直走、右轉或左轉）。

之后，所有子插槽進行容器基元-子基元的約束規(guī)則限制，篩選符合容器基元要求的子基元。以那些被刪除的子基元為依據(jù)，進行約束傳播步驟。

最后，對待坍縮子插槽進行WFC主循環(huán)坍縮，并進行子基元生成。

經過區(qū)塊坍縮后，可以形成圖16中的效果。

圖16 空間細化效果示意圖Fig.16 Schematic diagram of spatial refinement effect

3.3 交互實現(xiàn)

本文結合場景生成系統(tǒng)，利用Unity3d引擎，實現(xiàn)了交互式場景生成系統(tǒng)，支持用戶自定義導入模型的面朝向約束屬性設置，如圖17所示。

圖17 面朝向約束屬性Fig.17 Constraint properties of face orientation

在人機交互與參數(shù)化生成方面，設置團塊邊長與增加模型范圍為可調節(jié)參數(shù)，場景自動生成設為可選功能，并可選擇要強制修改的模型基元；交互實現(xiàn)中4種場景生成的方式如下所示。

（1）場景自動生成：用戶在場景中可以自由行走，場景會依次將靠近用戶位置的團塊輸入場景生成系統(tǒng)，坍縮團塊內所有插槽并進行空間細化。

（2）增加模型：以輸入插槽在輸入面朝向上的鄰居插槽為中心，n3個插槽圍成的立方體區(qū)域進行坍縮，之后進行空間細化。

（3）修改模型：如果輸入插槽已經坍縮，在不影響周圍插槽坍縮結果的前提下，該插槽的坍縮結果隨機替換為另一個可用的基元，并重新進行空間細化。

修改模型、強制修改或刪除模型這些操作涉及對坍縮結果的撤銷，所以，執(zhí)行之前需要進行回溯步驟：查找到相關插槽及其子插槽坍縮的歷史記錄，并還原這些歷史記錄。

（4）強制修改或刪除模型：強制將輸入插槽坍縮為選定的基元，其周圍的插槽以及子插槽也會重新坍縮為適應該基元作為鄰居的情況，之后進行修改范圍內的空間細化。刪除模型則把插槽的坍縮結果強制修改為空基元。

修改模型、強制修改或刪除模型的效果如圖18所示。

圖18 修改模型與強制修改模型效果示意圖Fig.18 Schematic diagram of model modification and forced modification effect

4 實驗結果與分析

4.1 實驗設計

為了驗證細分插槽WFC算法的有效性，本文基于交互式場景生成系統(tǒng)，將算法納入應用場景，考察細分插槽及容器基元-子基元的約束、子基元-子基元的約束在場景生成中的實際效果。

此外，為了驗證算法的改進效果，本文統(tǒng)計了在實現(xiàn)相同效果前提下，使用細分插槽WFC算法與使用傳統(tǒng)的WFC算法的差異。本文將場景按照復雜程度分為3組，對兩種算法各自使用的基元數(shù)量與約束規(guī)則數(shù)量進行了對比。場景一為僅有道路和房屋的場景（如圖19（a））；場景二追加了一種車輛與一種路燈（如圖19（b））；場景三進一步追加了一種車輛與基于約束規(guī)則的車流模擬（如圖19（c））。

圖19 實驗場景概覽Fig.19 Overview of experimental scenarios

4.2 實驗結果

在實驗場景中，細分插槽WFC算法依賴容器基元-子基元的約束規(guī)則，能夠實現(xiàn)汽車靠右行與房屋正面臨街等效果；依賴子基元-子基元的約束規(guī)則，能夠實現(xiàn)路燈的自然排布與房屋連接等效果。在場景三基于約束規(guī)則的車流模擬中，左右方向為通行車流，前后方向為等候車流。十字路口容器基元向汽車子基元傳遞交通信息作為約束規(guī)則，汽車子基元之間相互約束形成不同的車流（如圖19）。在交互式場景生成系統(tǒng)中，使用者可以對場景進行實時調整（如圖20）。

圖20 運行中的交互式場景生成Fig.20 Interactive scene generation on running

為了讓傳統(tǒng)的WFC算法能夠實現(xiàn)相同的效果，實驗把容器基元與子基元可能的組合方式分別制作成傳統(tǒng)WFC算法的基元，并進行場景生成。實驗統(tǒng)計了在實驗場景中使用兩種算法帶來的基元數(shù)量以及面朝向約束規(guī)則數(shù)量的差異（見表3）。

表3 對比實驗Table 3 Contrast experiment

實驗結果表明，本文提出的細分插槽WFC算法能夠產生豐富、細節(jié)可控的環(huán)境。同時，在與傳統(tǒng)WFC算法的對比中，由于容器基元中的子基元能夠憑借算法替換為其他子基元，使同一容器基元能對應多種外觀形式，因此，在面對細節(jié)要求更高的游戲場景生成時，插槽的多維細分方法更加靈活，能減小建模與約束的工作量，并減少基元的數(shù)目，提供更易實現(xiàn)的優(yōu)勢。

5 結束語

本文在傳統(tǒng)的WFC算法基礎上，提出了插槽多維細分的改進方法，將WFC算法中使用的模型擴充為容器基元與子模型兩類，將約束規(guī)則拓展為容器基元-容器基元、容器基元-子基元、子基元-子基元三類，配合區(qū)塊劃分與區(qū)塊坍縮等策略，拓寬了WFC算法生成結果的豐富性和應用范圍，使之能夠勝任更復雜的模型關聯(lián)情況，能夠生成更加精細化的游戲空間。本文改進算法的提出，使同一種輪廓的模型基元借助細分對應多種不同的外觀形式，進而減少約束與手動建模方面的工作量。同時，在模型的內部也能夠形成富有隨機性的空間，降低程序化空間生成的重復性。此外，交互系統(tǒng)的加入，可以將用戶感知納入其中，讓用戶直觀地觀察階段性生成效果并動態(tài)改進效果，用戶實時交互算法所生成的階段性效果能使程序化生成的結果更加符合受眾的設計需求。