總起

本文主要基于Procedural Content Generation in Games第三章介紹構造性方法，他們的主要用途在于地牢和關卡，這些方法能在極短進行生成，并且不會進行評估或重新生成。

關于PCG in Games之前的筆記可見：

第一章讀書筆記 PCG in Games 程序化內容生成 介紹 - 知乎

第二章讀書筆記 PCG in Games 程序化內容生成2 基于搜索的方法 - 知乎

地牢的概念來源于桌游《龍與地下城》，并成為RPG游戲的一大特征，包括《塞爾達傳說》系列和《最終幻想》系列。

Rougelike游戲來源于《Rogue》，特點是程序化實時生成地牢，《暗黑破壞神》是此類游戲的延續者。

一個典型的地牢生成方法考慮以下三種要素：

1.模型，以簡單、抽象的方式替代整個地牢，并提供最終結構的一個簡單預覽；

2.構造模型的方法；

3.根據模型創建真正地牢內容的方法。

本章創建方法特性：

1.建設性的，每次運行只產生一個輸出結果；

2.運行速度快，有一些甚至可以實時創建關卡；

3.只提供有限的屬性，只能對結果進行有限的控制。

本章將討論的方法：

1.空間分割法；

2.基于代理；

3.元胞自動機；

4.基于語法方法；

5.平臺生成方法。

構造性方法

空間分割法

通過遞歸將空間進行細分，并將獲得的子空間組織到一個樹型結構中。對于計算機圖形來說這類方法特別重要，比如高效的射線投射、視錐剔除和碰撞檢測。

具體的方法：

1.BSP（binary space partitioning，二元空間劃分），最流行；

2.四叉樹、八叉樹。

使用四叉樹生成地牢：

1.一張2^n*2^n像素的圖片，其內容可以是黑白兩種顏色；

2.根節點代表整張圖片，四個子節點代表上個節點圖像的四個象限；

3.按照2的步驟一直分割，直到最終葉子節點只有一種顏色。

使用BSP生成地牢：

1.將空間沿著垂直或水平方向進行分割，分出的單元格可以有不同的大小；

2.隨機選擇一個葉子節點繼續進行分割；

3.設定一個葉子節點不能被分為某個更小的尺寸；

4.最終每個葉子節點都包含一個單一的房間；

5.擁有相同父節點的房間會進行連接。

生成效果如下圖，a使用四叉樹，b使用BSP：

本節生成地牢的方法遵循了一種宏觀方法，即算法扮演著全視地牢的建筑師角色，而不是像下節中基于代理的方法所呈現的一個“盲目的”挖掘者，它們通過遞歸分區生成地牢，并能保證所有生成的兩個房間都不會重疊。

基于代理方法

基于一個AI代理挖掘出地牢，該方法的AI行為參數對地牢的外觀有很大影響，但很難被猜測，需要經過大量的測驗和試錯。

一個高隨機的方法：

1.代理轉變方向的概率和放置房間的概率都設定為5%；

2.將代理設置到地圖的任意位置并朝向任意方向；

3.挖掘一個格子；

4.檢測是否要改變方向或放置房間；

5.如果沒有改變方向或放置房間，則將分別的概率提高5%；

6.在地牢沒有生成的足夠大之前，跳到第3步繼續生成。

?

?

這種高隨機的方法很容易出現重疊房間和死路，因此我們將對AI代理進行一定的前瞻性設置。

第二種方法：

1.在地牢中放置一個代理；

2.設置變量Fr = 0，Fc = 0；

3.嘗試放置一個房間，保證它與任意房間不相交，如果放置了房間設置Fr為1；

4.嘗試在任意方向放置一個3到7個單位長度的走廊，保證它與任意房間不相交，如果放置了走廊設置Fc = 1；

5.如果Fr == 1或者Fc == 1，則跳回到第2步。

這種方法相比而言稍微好了一點，但是在最差情況下也有過早結束的問題：

?

總之與本章中介紹的大多數方法相比，代理方法的參數會對生成結果的可玩性和娛樂價值產生非常大的影響，調整這些參數達到最佳效果并不是一件簡單的任務。

元胞自動機

元胞自動機是一個離散型的計算模型，而它作為計算模型、生長發育模型、物理現象模型等，在計算機科學、物理學甚至生物學的一些分支中得到了廣泛的研究。

原理：

1.由n維網絡、一組狀態和一組轉換規則構成；

2.一般情況下使用的網絡是一維的（向量）或二維的（矩陣）；

3.每一個元胞可以是狀態中一個：最簡單的例子狀態可以是打開或關閉的；

4.實驗開始時各個細胞擁有各自的狀態，然后隨著時間推進，每個元胞由自己和鄰居t-1時的狀態來確定t時的狀態。

領域（其大小可以是1或大于1）：

1.一維，向左向后延伸的單位；

2.二維，Moore摩爾領域和von Neumann馮諾依曼領域。

?

Johnson等人使用元胞自動機來生成類似洞穴的無限地牢，洞穴應該看起來像是自然侵蝕形成的，而非擁有筆直的邊緣和角落。

控制地圖生成過程的四個參數：

1.巖石單元的百分比（無法進入的區域）；

2.元胞自動機運行次數n；

3.定義巖石的鄰域閾值T；

4.鄰近細胞的數目。

生成步驟：

1.設置每個房間50x50的格子，每個細胞擁有兩種狀態：空或石頭；

2.“噴灑”石頭，針對每個元胞有一定概率是石頭（比如0.5）；

3.如果相鄰的細胞中至少有T個（例如5）是巖石，則該細胞在下一個時間變成巖石，否則它將變成自由空間；

4.以上的處理進行n次（例如4）。

這樣簡單的生成能獲得驚人的栩栩如生的洞穴房間，如下圖b，使用了參數：n = 4、T = 5。

不過元胞自動機也有其缺點，它的參數比較難以理解，每個參數還對多項特性有影響，并且比較難以定制化。

基于語法方法

使用自然語言描述地牢結構。

Adams使用圖像語法生成了一個FPS關卡：

1.節點代表房間；

2.相鄰的兩個節點代表兩個房間之間擁有一條走廊。

這種方法不會生成任何幾何細節，比如房間大小。通過高層次的、拓撲的關卡進行表示，接著搜索算法查找最為匹配的結果。

Adams研究的一個限制是語法規則，特別是參數，它們是專門的且硬編碼的。

Dormans通過圖像語法生成有向圖，作為游戲任務流程順序的模型，每個任務都被抽象成節點和邊的網絡，然后由形狀語法生成相應的游戲空間。

受到Dormans研究的啟發，van der Linden等人提出了一種用于生成地牢關卡的玩法語法。游戲設計師使用面向游戲玩法的詞匯來表達先驗設計約束，包括玩家在游戲中執行的指令，它們的順序和組合，相互關系和相關內容。

以下圖片a展示了van der Linden等人編寫的具體語法內容，b展示了最終生成的效果：

?

平臺生成方法——基于節奏

Smith等人基于節奏概念進行關卡生成，將用戶時間和重復聯系在一起。

生成節奏組：

1.創造一系列玩家行動；

2.將這些行動轉換成相應的幾何圖形；

3.通過組合節奏組生成多個關卡；

4.評估選擇最佳關卡。

Smith提供了一個控制生成的過程：

1.一條貫穿關卡的道路；

2.生成不同類型的節奏；

3.幾何組件的類型和分配頻率；

4.收藏品跟關卡是分開的。

每個節奏組也有一些參數，比如跳躍頻率、跳躍道具(彈簧)出現的頻率。另一組參數提供對節奏長度、密度、拍型的控制。

Smith等人所定義的節奏概念并不直接適用于地牢，但使用穿過房間和走廊的節奏可能具有類似的價值。

平臺生成方法——ORE

Mawhorter等人提出的Occupancy Regulated Extension（占用率查詢擴展），這種方法依賴于預先編寫的關卡塊，然后使用關卡塊來組裝關卡。

步驟：

1.選擇一個隨機的潛在位置（占用率）來放置一個塊；

2.選擇一個與環境兼容的塊；

3.新的塊與已存在的關卡圖形進行合并。

Mawhorter等人沒有提到算法中特殊的控制參數，但是策劃仍然擁有一些控制。這種混合主導的方法能夠提供最大程度的控制，但是如果做得過火，這種方式和手動構建就基本沒什么區別了，能在PCG中所獲取的收益就會減少。

平臺生成示例

《洞穴探險》關卡生成的階段：

1.通過可用模板房間生成關卡的主要布局，并放置入口點和出口點；

2.障礙生成，使用代理穿過關卡在預留空間中啟發式的放置障礙物；

3.怪物生成，再使用另一個代理搜索并尋找足夠空間放置一個怪物。

?

《無限馬里奧》，Ben Weber提供了一種生成方法，基于代理進行多次遍歷：

1.創建起始點到終點的初始通道；

2.添加山丘；

3.添加管道或大炮等靜態元素；

4.添加移動的敵人；

5.添加未連接的水平塊；

6.添加可收集的硬幣。

本章可以使用平臺AI競爭的關卡賽道生成器(Level Generation Track of the Platformer AI Competition)進行練習。

總結

構造性方法通常在roguelike游戲、平臺類游戲中使用，因為方法運行可預估且運行時間短。

1.空間分割法，遞歸將區域分割的更小；

2.基于代理，使用某種方式穿越地牢進行挖掘；

3.元胞自動機，可以創建類似自然侵蝕形成的效果；

4.基于語法方法，使用生成規則構建地牢，在第五章有更廣泛的討論；

5.平臺生成方法，使用帶有概率的簡單規則進行生成，也很容易使用到地牢生成中。

參考

《Procedural Content Generation in Games》

總結

以上是生活随笔為你收集整理的读书笔记 PCG in Games 程序化内容生成3 构造性方法，针对地牢式关卡的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。