理解波函數塌縮演算

在遊戲中，若想創造無限延伸又變化多端的世界，我們該怎麼做？這令人想到Minecraft，會依據玩家的移動，即時地生成新區塊，因而世界沒有盡頭。

事實上，Minecraft的世界生成是基於Perlin噪聲，從玩家實際的位置計算噪聲值，生成具備隨機而又連續的自然地形。關於Perlin噪聲的介紹，可參考先前專欄〈隨機演算之美〉。

不過，在這個世界中，我們若想加入較多的限制呢？例如，生成過程中若要有屋頂、牆面、階梯等，而且彼此銜接必須合理，不致於產生破碎的房屋、斷掉的階梯等建築呢？Minecraft顯然就有這類問題。在Minecraft中，想要看到房屋被嵌在山壁上或者切了一半，並不是稀奇的事情。

若想體會一下這類無限延伸的世界，是怎麼一回事，我們可以玩玩Marian Kleineberg寫的無限城，裏頭各式各樣的建築元素彼此合理地銜接，而且，這座城沒有盡頭，不斷地往外走的同時，新的建築又會接續生成。

在Marian Kleineberg的無限城頁面上，標題寫著：Wave Function Collapse（波函數塌縮），這是2016年遊戲設計師Maxim Gumin提出的演算法，Maxim Gumine也為它在Github上，設了個repository，說明並示範了該演算法於2D/3D上的應用，而Marian Kleineberg的無限城，正是波函數塌縮（Wave Function Collapse）演算的實現之一。

其實，這套波函數塌縮演算法的名稱概念，取自量子力學，常用來創造無限延伸的2D/3D世界，相關實現的程式原始碼看似複雜，然而，基本概念並不困難！

波函數？塌縮？

波函數塌縮是量子力學中的概念，波函數描述了量子系統的量子狀態，在量子力學的科普文章中，多半會談到量子的狀態疊加，也就是某系統中波函數描述的對象，可以「同時」具有多種狀態，只有在「測量觀察」它的時候，系統與環境作用之下，波函數塌縮成被測量觀察到的其中一個狀態。

「薛丁格的貓」是常被拿來描述這個概念的思想實驗：有隻貓關在箱子裏，箱子中有個毒氣瓶與放射性物質，若偵測到放射性物質衰變，毒氣瓶就會被打破，機率是50%，在還沒有打開箱子前，以機率觀點來說，貓可能活著，也可能在死亡狀態，然而從波函數的觀點來看，貓是同時處於活狀態與死狀態（既是活的也是死的），直到你打開箱子，波函數塌縮為活或死的其中一個狀態，成為你觀察到的結果。

而Maxim Gumin的演算法名稱，就是取自波函數塌縮的概念。在〈The Wavefunction Collapse Algorithm explained very clearly〉中，以婚禮座位安排為例，適切地闡述了演算法與波函數塌縮的關係，因為，關於婚禮座位安排這件事，總有誰跟誰可以坐一起，誰跟誰不能坐一起的問題，而你已經建立了規則表，現在該怎麼安排座位？

假如時間不夠了，你不能慢慢排，需要有個有效率的方式，於是，在每個座位上都放了一疊完整的賓客卡片，然後從一個座位開始，隨機地從該座位卡片堆疊中抽出一張卡片，其他賓客卡片就丟了，於是，一整疊卡片塌縮成一張卡片。

而且，Maxim Gumin的演算法中的塌縮，還會傳播。既然坐這個位置的人確定了，就從鄰接座位的整疊卡片中，剔除不能跟這位置的人坐一起的賓客卡片，就像砂漏似地，中間的砂子掉落，周圍的砂子也跟著下滑。

也就是說，一開始，你的演算法就類似波函數，對於該位置的賓客（狀態）描述，並非可能是哪個（這是機率上的描述），而是同時有多個賓客坐在那個位置（狀態疊加），在你摸出一張卡片時（打開箱子時）所觀察到的，只是該位置有該位賓客的狀態。

到這邊為此，我們就完成了演算法中的一次迭代，接著，挑選其他座位中卡片最少的，隨機地抽出了一位賓客，使一整疊卡片塌縮成一張卡片，然後傳播塌縮；如此不斷地迭代，直到賓客座位全數安排妥當，或者產生矛盾（不能坐一起的終究被排在一起）而安排失敗，這時，最好的處理方式是重新開始。

區域相似與熵

在婚禮的比喻中，賓客的就座規則是你自行建立的，但實際上，Maxim Gumin的演算法不需要自行建立規則。

以2D地圖生成為例，你可以用一張圖作為輸入，演算法會自動剖析圖片，然後輸出風格相近的圖片，或者更確地根據Maxim Gumin的定義，輸出了區域相似（Local similarity）的圖片。

在〈Overlapping Wave Function Collapse〉中，有個JavaScript實現的波函數塌縮範例，你可以自行繪製輸入圖片，範例將自動生成更大的圖片，而且，鄰接規則來自於你繪製的圖片輸入。

根據Maxim Gumin的定義，所謂的區域相似，是指若使用了N*N個圖案模式來拼接出一張輸出圖片，那麼，你的輸入圖片必須包含這N*N個圖案模式；而且輸入的圖片，分布上必須有足夠的資訊，以計算出相關係數，或者說是權重，使得輸出的圖片，也能依權重而產生類似的分佈。

在這兩個定義中，輸出的圖案模式來自輸入，這點較易理解，後者呢？簡單來說，如果輸入圖片中包含一大片草地，輸出的圖片中若有草地，也希望有一定的連續範圍，而不是一小塊、一小塊破碎而不相鄰的草地吧！

就像方才的婚禮比喻中，每次迭代都簡單地選擇卡片最少的座位，在Maxim Gumin的演算法中，選擇的標準則是熵（entropy），這個名詞來自化學及熱力學，是能量退化的指標，也常用於計算系統的失序現象，而Maxim Gumin的演算中，會使用輸入得到的各模式權重來計算熵，並選出熵最少的位置進行塌縮，以得到更好的區域相似，減少矛盾的可能性。

乍看之下，這有點類似騎士巡邏問題時所採用的Warnsdorff規則，騎士要走的下一步是「再選擇時，能走的步數最少的一步」，而如果依照這一規則而行，往往可以找到一條路徑，但是並不一定能夠成功；如此做的好處是不用回溯（backtracking），就像方才所提到的，失敗了就重新開始是最好的處理方式。

有原始碼嗎？

相對而言，波函數塌縮演算是比較新的作法，文件不多，Maxim Gumin一開始寫的C#範例也不容易理解，加上又有量子力學、化學及熱力學的名詞概念，雖然後來有其他開發者做了不同實現，然後各自包含了效率、矛盾解決等考量，但是，想從原始碼中理解有一定的難度，令不少人望之生畏，覺得難以理解。

若要克服這樣的難題，我認為可以從方才提到的〈The Wavefunction Collapse Algorithm explained very clearly〉下手，這當中包含了一個Python範例，是個文字模式的波函數塌縮實現，程式碼包含註解只有300多行，然而包含了上述演算要素的基本實現，對於實現自己的波函數塌縮來說，是個不錯的起點。