靳仕恒，鄭春輝，呂德生

1.互動(dòng)媒體設(shè)計(jì)與裝備服務(wù)創(chuàng)新文化和旅游部重點(diǎn)實(shí)驗(yàn)室，哈爾濱 150001

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

坍縮用于確定插槽中生成的基元，沒(méi)有被選中的基元將會(huì)從可選基元集合中刪去，并以這些基元為基礎(chǔ)，進(jìn)行約束傳播步驟。

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

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

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

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

2 插槽多維細(xì)分的設(shè)計(jì)與實(shí)現(xiàn)

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

圖5 算法結(jié)構(gòu)概要Fig.5 Summary of algorithm structure

2.1 模型原型及約束屬性

模型原型定義為用戶導(dǎo)入的一組用于場(chǎng)景生成的基本模型，模型原型的每個(gè)面朝向上都包含著一組約束規(guī)則。用戶通過(guò)調(diào)節(jié)約束規(guī)則的各個(gè)參數(shù)，能夠?yàn)槟Ｐ驮椭朴嗊B接規(guī)則，限制其各個(gè)面朝向潛在的鄰居模型。面朝向主要的約束屬性如表1所示。

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

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

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

圖6 子基元生成前后對(duì)比Fig.6 Comparison before and after sub-modules generation

容器基元中，面朝向約束屬性withInner為true的面朝向都會(huì)生成子插槽，子基元在子插槽中填充，with Inner的邏輯表達(dá)式如下：式中，C代表容器基元的某一面朝向。connector代表連接器，該值是模型之間可以相互連接的基礎(chǔ)，反映了該面朝向的模型截面形狀或者用戶需要的連接功能。當(dāng)該值為1時(shí)，說(shuō)明模型的截面鋪滿了插槽的截面，如圖7中兩個(gè)容器基元相對(duì)接的面朝向，它們的connector=1，兩個(gè)插槽的空余空間被模型隔開(kāi)，“墻壁”為子插槽的生成留下了充足的位置，可以出現(xiàn)壁燈、壁掛等子基元。

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

子插槽的生成并不總是依附于墻壁，如圖8，需要在道路側(cè)面的左右子插槽中生成路燈。為此，公式（1）額外規(guī)定當(dāng)passage為true時(shí)，withInner為true。passage意味著該面朝向?yàn)橥ǖ溃枰?xì)節(jié)補(bǔ)充，如：從道路通向樓房，從一個(gè)房間通向另一個(gè)房間，這種地方往往需要出現(xiàn)門、窗、路燈、路牌等子基元。

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

2.2 約束規(guī)則

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

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

式中，I代表子基元向容器基元的約束規(guī)則，innerSetting是C中的結(jié)構(gòu)體，存儲(chǔ)向子基元的約束規(guī)則。符號(hào)∧左側(cè)的公式保證子基元與容器基元對(duì)應(yīng)面連接器適配；右側(cè)參數(shù)withInner保證容器基元的該面朝向位置可以生成子插槽。

僅滿足基本約束規(guī)則的場(chǎng)景生成常會(huì)帶來(lái)如圖9的錯(cuò)誤結(jié)果。因此，約束規(guī)則還需考慮子基元與容器基元相鄰面的關(guān)系。

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

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

式中，CL代表容器基元的相鄰面朝向，IL代表子基元正對(duì)著該相鄰面的面朝向。如圖10，具有相同下角標(biāo)的CL與IL能夠滿足上述面朝向?qū)?yīng)關(guān)系。子基元的balance屬性表示該方向上模型已經(jīng)完整，不必繼續(xù)往該方向生成，以圖中的半個(gè)汽車為例，汽車左、右、后3個(gè)方向?yàn)閎alance，前方反之，它還要補(bǔ)充汽車的另一半來(lái)構(gòu)成完整模型。allowTurn表示子基元在IL面朝向的鄰居可以是容器基元CL面朝向上的子基元。公式（3）則要求當(dāng)CL為passage時(shí)，子基元的IL面朝向?yàn)閜assable，能夠留出空間，不會(huì)把通道堵住。

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

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

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

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

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

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

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

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

內(nèi)轉(zhuǎn)：子基元與子基元存在直接相鄰的關(guān)系，但兩者子基元類型（如表2）不同，且共同處于同一個(gè)容器基元中；

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

圖13 外轉(zhuǎn)情況示意圖Fig.13 Schematic diagram of external transfer

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

當(dāng)判斷一個(gè)子基元的轉(zhuǎn)彎的面朝向上是否可以生成某個(gè)特定子基元時(shí)，需要滿足以下兩個(gè)公式：

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

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

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

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

圖14 場(chǎng)景生成系統(tǒng)結(jié)構(gòu)圖Fig.14 Structure diagram of scene generation system

3.1 區(qū)塊劃分

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

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

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

在圖15中，方框?yàn)槿萜骰摼€代表朝向室內(nèi)的面朝向，箭頭代表容器基元為passage的面。房間A、B為閉合的房間，房間C則右側(cè)未閉合。

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

3.2 區(qū)塊坍縮

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

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

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

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

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

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

3.3 交互實(shí)現(xiàn)

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

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

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

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

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

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

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

（4）強(qiáng)制修改或刪除模型：強(qiáng)制將輸入插槽坍縮為選定的基元，其周圍的插槽以及子插槽也會(huì)重新坍縮為適應(yīng)該基元作為鄰居的情況，之后進(jìn)行修改范圍內(nèi)的空間細(xì)化。刪除模型則把插槽的坍縮結(jié)果強(qiáng)制修改為空基元。

修改模型、強(qiáng)制修改或刪除模型的效果如圖18所示。

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

圖19 實(shí)驗(yàn)場(chǎng)景概覽Fig.19 Overview of experimental scenarios

4.2 實(shí)驗(yàn)結(jié)果

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

圖20 運(yùn)行中的交互式場(chǎng)景生成Fig.20 Interactive scene generation on running

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

表3 對(duì)比實(shí)驗(yàn)Table 3 Contrast experiment

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

5 結(jié)束語(yǔ)

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