在遊戲中,若想創造無限延伸又變化多端的世界,我們該怎麼做?這令人想到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多行,然而包含了上述演算要素的基本實現,對於實現自己的波函數塌縮來說,是個不錯的起點。

作者簡介


Advertisement

更多 iThome相關內容