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

看板GameDesign (遊戲設計)作者dklassic (DK)時間3年前 (2020/12/24 13:17)推噓12(12推 0噓 0→)

留言12則, 12人參與討論串1/1

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

12/24 13:27, 3年前 , 1^F

12/24 13:27, 1^F

推

ZooseWu

12/24 14:44, 3年前 , 2^F

12/24 14:44, 2^F

等手上的專案結束後想要用這個機制配上 cj 貓的 Mudbun 做做看類似 Oskar Stalberg 小鎮建造遊戲概念的東西 XD 應該有很多雖然未必可以稱為遊戲，但是依然能充滿樂趣的小機制開發。 ※ 編輯: dklassic (118.166.25.73 臺灣), 12/24/2020 16:12:10

推

oopFoo

12/24 17:50, 3年前 , 3^F

12/24 17:50, 3^F

推

johnny94

12/24 21:13, 3年前 , 4^F

12/24 21:13, 4^F

推

cmcer

12/24 23:00, 3年前 , 5^F

12/24 23:00, 5^F

關卡 Base 或直接是房間 Base 的遊戲都還滿適用的。但其實最重要的意義可能是 WFC 有點像是在做 Upsampling（用低解析度的規則產生符合規則的高解析度版本），是一個用少量素材就可以產生大量內容的手段。或許只要有大量內容產生需求就滿適用的。 ※ 編輯: dklassic (118.166.25.73 臺灣), 12/25/2020 01:32:45

推

yukari8

12/25 09:43, 3年前 , 6^F

12/25 09:43, 6^F

※ 編輯: 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

12/26 17:24, 3年前 , 7^F

12/26 17:24, 7^F

推

megah321

12/29 10:28, 3年前 , 8^F

12/29 10:28, 8^F

推

wangm4a1

12/29 17:18, 3年前 , 9^F

12/29 17:18, 9^F