[程式] Wave Function Collapse 隨機地圖產生

[dklassic (DK)]

因為自己在做遊戲的緣故，開始研究各種省錢（？）的開發手段，趁等待的空檔打一篇教
學文簡易積積陰德。其中最重要的一個就是關卡編輯與自動化關卡產生。
總之因為沒有時間與人力製作從頭製作關卡，所以不如想個辦法自動化產生關卡。

這部分目前最實用的手段就叫做 Wave Function Collapse。
可能很多人的印象最深刻的例子是來自這個 Github：
https://github.com/mxgmn/WaveFunctionCollapse
我個人則是從 Oskar Stalberg 2018 年的演講入坑的：
https://www.youtube.com/watch?v=0bcZb-SsnrA
從這邊聽個大概，似懂非懂很難理解，剩下很多片段都是在實作過程中才理解。
最後得到的結論就是 Wave Function Collapse 聽起來很厲害，但具體意義就是「有設定
好條件的暴力解」，只要掌握這個精隨什麼都很好實作。



以下是具體的實作方法。
總之 Wave Function Collapse 比較簡單的做法是對規則形狀的物件做。
為了方便舉例就以方形舉例。

1. 定義單位方塊的屬性
例如在我的實作測試中作了一個簡單的牆壁、地板組合，單元如下：
https://imgur.com/KnZSeeI
接著要詳細實作規則定義，基本上就是定義要有怎樣的 Tag 的物件才能接上。
https://imgur.com/bGUxUDk
以這邊的例子來說就是要把牆壁的區域對接、地板的區域對接。
就寫個 Script 來定義這些屬性。

2. 生成環境
首先當然是產生一些 Empty Game Object 來存放各個單元。
就把預先做好的單元在每個格子都塞好一份：
https://imgur.com/rhw1pOb
https://imgur.com/uXcaEj1
上圖塞四份是因為我懶得紀錄各個單元的旋轉版本，所以就直接複製四份。
雖然應該算是沒效率四倍，但是因為好寫又沒有即時的需求就這樣做了。
也因為複製四倍這種因素，產生過程中都直接把 Renderer 關好關滿。

3. 開始崩塌（Collapse）
這邊是個循環，基本過程就是
3a. 尋找熵（Entropy）最低的格子
簡單來說就是可選選項最少的格子。
如果機率都一樣的話就用隨機。
3b. 崩塌該格
基本上是隨機崩塌，也就是從可選選項中隨機選一個出來用。
3c. 更新鄰居的熵
因為將一格的未來確定之後，附近鄰居可以與該格接起來的選項就變少了。
所以要更新選項、熵值。

所以每做一個循環就會像這樣：
https://imgur.com/bcqgiEc （執行前）
https://imgur.com/srRPTd5 （執行後）
會崩塌一格，並且讓週邊鄰居的可能性變少。

接著就無限執行循環直到每一格的未來都決定好：
https://imgur.com/bQCUMnL.mp4 （崩塌全程錄影）


實作上就是如此的樸實無華。
此外的延伸議題有：
1. 錯誤應對
簡單來說根據你單塊選項、銜接規則的設計，可能會出現某個位置完全沒有選項能與週邊
銜接。這時候有兩種做法。
1a. 正解－回溯變更
簡單來說就是既然有問題，就試著讓前一步變成別的方塊看看。
這部分最好多一些輔助，像是「隨著錯誤次數越多，回溯的步數也增加」。
根據隨機機率，早晚會生出一個可以完全解開的版本。
1b. 懶人－錯誤偵測與重來
簡單來說就是只偵測錯誤，而撞到錯誤就重來。
這個方法實作上比較簡單，但是比較沒效率。而且根據規則寫得完備程度越差，撞到錯誤
而必須重來的次數可能也會增加，是個危險的做法。
而隨著方塊的總量越多，單次產生所需要的時間也越來越長，為了避免大量的時間都被浪
費在重新產生，寫個踏實的歷史步驟紀錄系統也比較重要。

2. 可用程度偵測
根據關卡需求，可能要寫一些自動化的條件來偵測關卡的可用程度。
例如說各方塊通行區域的連通程度等等，加深自動化的有效性。
也同樣可以在可用程度過低的時候直接重新產生，不用浪費時間，更不用人力檢查。

3. 預先設計條件加強可用程度
以我遊戲需求，我只寫了確保邊緣一定是牆壁的機制。
但延伸可以考慮的面向就包含：
a. 整張地圖的連通程度（有沒有房間被隔開無法通行）
b. 可通行區域的面積
這些當然都是寫偵測比較簡單，要寫出可靠的解法比較難。
就看專案需求來決定要走好寫但是產生過程比較困難，或者是確保可以產生出來但比較難
寫的版本。

4. 三維化
目前我寫的版本只用了兩維，不過其實三維的概念也是一模一樣的，只是邊界銜接條件精
細度可能要寫比較多。事前準備稍微複雜點但概念還是一致。

5. 多核心化
老實說我還不太確定怎樣平行化比較好 XD


總之大概是這樣，老實說整個過程做起來還是很簡單，我弄出第一個可以產生的程式只花
了十個小時左右。不過過程中還是各種想要尋求細節實作的部分都沒在網路上看到。
因此順便在板上獻一點微薄之力。
另一個我雖然沒有開來看但是有開源的專案或許值得參考一下：
https://github.com/marian42/wavefunctioncollapse

因為有人問，所以我簡單寫了一個 Pseudo Code 提供參考：
https://pastebin.pl/view/2b6f80ed

之一的內容也就是基礎產生，之二應該會講如何把場景精細化的實用經驗。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.166.25.73 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/GameDesign/M.1608787057.A.FA7.html
※ 編輯: dklassic (118.166.25.73 臺灣), 12/24/2020 13:18:41
※ 編輯: dklassic (118.166.25.73 臺灣), 12/24/2020 13:20:54
推 wyvernlee: 強!
推 ZooseWu: 好像挺好玩的
等手上的專案結束後想要用這個機制配上 cj 貓的 Mudbun 做做看類似 Oskar Stalberg
小鎮建造遊戲概念的東西 XD
應該有很多雖然未必可以稱為遊戲，但是依然能充滿樂趣的小機制開發。
※ 編輯: dklassic (118.166.25.73 臺灣), 12/24/2020 16:12:10
推 oopFoo: 蠻有趣的，但一直用不上。
推 johnny94: 推推
推 cmcer: Diablo-like或不思議迷宮類型很容易會用到
關卡 Base 或直接是房間 Base 的遊戲都還滿適用的。
但其實最重要的意義可能是 WFC 有點像是在做 Upsampling（用低解析度的規則產生符合
規則的高解析度版本），是一個用少量素材就可以產生大量內容的手段。
或許只要有大量內容產生需求就滿適用的。
※ 編輯: dklassic (118.166.25.73 臺灣), 12/25/2020 01:32:45
推 yukari8: 推個
※ 編輯: dklassic (118.166.25.73 臺灣), 12/25/2020 15:34:23
※ 編輯: dklassic (118.166.25.73 臺灣), 12/25/2020 17:10:04
※ 編輯: dklassic (118.166.25.73 臺灣), 12/26/2020 15:01:23
推 a82611141: 推
推 megah321: 推
推 wangm4a1: 推
推 MaxWei: 感謝分享，雖然現在還沒用到但一直滿有興趣這題目的
推 rickkcir: 感謝分享，看起來很酷
推 yellowd54321: 推 隨機地圖真的有趣