??這是一個簡單的游戲，你可以在一個無限延申的城市里行走，這個城市是用波函數(shù)塌縮算法從一堆blocks中生成的。

? 你可以在marian42.itch.io/wfc上下載該游戲，在?github.com/marian42/wavefunctioncollapse 下載該游戲的源代碼。

The algorithm

? 插槽（slot）表示3D網(wǎng)絡(luò)中可以可以包含方塊（block，也可為空）的位置，模塊（module）表示可以嵌入到slot中的block。

? 波函數(shù)塌縮算法為游戲世界中每個插槽選擇合適的模型。slots數(shù)組被視作是一個不可觀測狀態(tài)下的波函數(shù)。這意味著每個插槽都對應(yīng)著一組可能的、可匹配的模塊。用量子力學術(shù)語描述，可以說“插槽是所有模塊的量子疊加態(tài)（The slot is in superposition of all modules）”。

? 世界起始于未被觀察狀態(tài)中，此時每個模塊都有可能出現(xiàn)在任意的插槽中（概率相等）。一個接一個，每個插槽都會塌縮成確定狀態(tài)。這意味著，模塊是隨機挑選出來的。接下來的步驟是加上一個約束傳播：

• 對每個模塊，只允許將其一個子集放置在附近。一個插槽不論何時塌縮，其模塊子集仍可以在需要更新的插槽中使用。

? 約束傳播步驟是算法中計算量最大的部分。

? 波函數(shù)塌縮算法的核心就是選擇哪一個插槽會發(fā)生塌縮。該算法總是選擇具有最小熵的插槽進行塌縮：

• 即該插槽的可選擇項最少（或混亂度）；

• 如果所有模塊具有相同的概率，則可能模塊數(shù)量最小的插槽的熵最小。

• 一般來說，每個模塊都有不同的被選擇概率。一個擁有兩個相同概率的模塊的插槽比擁有一個大概率和一個小概率的模塊的插槽有更多的選擇（更大的熵）。

About blocks, prototypes and modules

? 這個游戲由100個左右的blocks生成，由blender制作。從幾個block開始，逐漸形成整個城市。

??算法需要知道哪些模塊可以相鄰放置。每個模塊有6個可能的鄰居列表，每個方向一個。但我不想手工創(chuàng)建這個列表。我還想找到一種自動生成塊的旋轉(zhuǎn)變量的方法。????

??兩者都可以通過使用我稱之為模塊原型（module prototypes）的方法來實現(xiàn)。這是一個可以在Unity編輯器中方便地編輯的MonoBehaviour。模塊以及允許的鄰域列表和旋轉(zhuǎn)變量都是從這些模塊中自動創(chuàng)建的。

??一個難點是如何建模鄰接信息來使這套自動方法行之有效。我的方法是：

? 為每個block的每個面設(shè)置一個連接器，連接器有一個數(shù)字id。水平連接器可以翻轉(zhuǎn)、不翻轉(zhuǎn)或?qū)ΨQ旋轉(zhuǎn)。垂直連接器的旋轉(zhuǎn)索引在0和3之間（屏幕截圖中為b、c、d），或者它們被標記為無法旋轉(zhuǎn)的。

??基于此，我可以自動檢查哪些模塊允許相鄰。相鄰模塊必須具有相同的連接器編號。并且它們的對稱性必須匹配（垂直方向相同的旋轉(zhuǎn)索引，水平翻轉(zhuǎn)和不翻轉(zhuǎn)的一對），否則它們必須對稱/不變。

? 此外，還設(shè)置了一些排除規(guī)則，來禁止掉那些拼接起來不太好看的blocks。以下是不使用排除規(guī)則生成的地圖的示例：

Reaching infinity

? 原始的波函數(shù)塌縮算法只能生成有限的地圖，這里我要地圖隨著玩家的走動而實時、無限生成。

? 我的第一種方法是生成有限大小的塊，并使用相鄰塊的連接器作為約束。如果生成了塊，并且已經(jīng)生成了相鄰的塊，則只允許與現(xiàn)有模塊相匹配的模塊存在。這種方法的問題是，當一個插槽塌縮時，約束傳播會限制之后的所有可能性，即使是在幾個距離之外的插槽。在改圖中，您可以看到僅僅因為塌縮了一個插槽就影響到所有的位置：

? 當一次只生成一個塊時，約束不會傳播到相鄰塊。但這會導致當模塊在一個插槽中被選中的時候就無法在其他地方被考慮，最終導致算法的下一次生成失?。ㄕ也坏浇鉀Q方案）。

??我沒有使用塊（chunks）來生成，而是將地圖（數(shù)據(jù)）存儲在一個字典中，它將一個插槽位置映射到一個插槽中。它只在需要時增添數(shù)據(jù)。

??算法的某些部分需要對此進行調(diào)整。當選擇要塌縮的插槽時，并不是所有的插槽都可以考慮在內(nèi)。取而代之的是，當玩家到達地圖時，只會同時生成地圖的一小部分區(qū)域。約束仍然傳播到此區(qū)域之外。

? 在某些情況下，這種方法行不通。假設(shè)有這么一個模塊，在屏幕截圖的上方有一個直線隧道段，但是沒有隧道入口。如果算法選擇這樣一個隧道模塊，這就預先確定了一個無限的隧道。約束傳播在每一步都會在這里產(chǎn)生一個插槽，導致無限重復。我設(shè)計了模塊組來避免這個問題。

Boundary constraints

??有兩個重要的邊界約束：地圖頂部的面必須具有“空氣”連接器。地圖底部的面必須有“地面”連接器。如沒有這兩個約束條件，地面上就會出現(xiàn)空洞，建筑物的屋頂也會缺失。

??在有限地圖中，這很容易做到：對于頂層和底層的所有插槽，移除所有帶有不需要的連接器的模塊。然后使用約束傳播刪除不再有效的其他模塊。

??在無限地圖中，這不起作用，因為在頂層和底層有無限多個插槽。我只會在創(chuàng)建插槽后刪除頂層和底層的這些模塊。然而，在一個頂層插槽中移除一個模塊會影響到其相鄰插槽束。這將導致級聯(lián)效應(yīng)，從而再次無限地分配插槽。

??我通過創(chuàng)建一個1×n×1的地圖來解決這個問題，其中n是高度。此地圖使用world wrapping來傳播約束。這就像Pacman一樣，你在右邊離開關(guān)卡，在左邊進入?，F(xiàn)在在這個地圖上我可以應(yīng)用所有的邊界約束。無論何時在無限的地圖中創(chuàng)建一個新的插槽時，它會被地圖上相對應(yīng)的模塊集中的位置數(shù)據(jù)初始化。

Error states and backtracking

?有時，WFC算法會遇到插槽沒有模塊可用的狀態(tài)。在有限世界的應(yīng)用程序中，您可以放棄結(jié)果并重新開始。在無限的世界里，這是行不通的，因為世界的一部分已經(jīng)展示給玩家了。最初我選擇在出錯的地方生成一個白色塊來解決這個問題。

? 我目前的解決方案是回溯。將插槽塌縮的順序和約束傳播相關(guān)的一些信息作為歷史數(shù)據(jù)存儲起來。如果WFC算法失敗，則某些歷史操作會被取消。這在大多數(shù)情況下都是可行的，但有時錯誤識別得很晚，這會導致許多步驟被回溯。在極少數(shù)情況下，玩家所在的插槽會被重新生成。在我看來，這種局限性使得WFC算法生成無限世界的方法不適合商業(yè)游戲。

Outlook

? 當我看到Oskar St?lberg用WFC算法在Bad North游戲中生成地圖時，我就開始研究這個問題。大多數(shù)基礎(chǔ)功能都是在procjam實現(xiàn)的。

? 該項目已開源并遵循MIT開源協(xié)議，你可以用它來實現(xiàn)你自己的想法！

文章來源：https://marian42.de/article/wfc/

github地址：https://github.com/marian42/wavefunctioncollapse

翻譯不易，若轉(zhuǎn)載請注明出處。