無邊無際的虛擬城市來了！能走能飛的Demo，一火再火的「波函數坍縮」開源演算法

安妮 栗子 發自 凹非寺

量子位 報道 | 公眾號 QbitAI

神說，要有光。

於是有了光。

神說，要有一座城。

於是有了一座城。

神說，這座城要無限大。

神啊你別再說了，那是另外的價錢。

不過，有種叫做波函數坍縮(Wave Collapse Function) 的演算法，可以讓一座白茫茫的城，在虛擬世界裡無限延伸。

你跑得再快，飛得再遠，都到不了它的盡頭。

因為，這座城可以實時擴張，你往哪裡走，它就往哪裡生成，不會讓你跑出去的。

而它背後的波函數坍縮(WFC) 演算法自誕生以來，每隔一段時日，便會引起人類蜂擁而至的關注。

不管是因為這賞心悅目的應用：

還是因為有人做了完整而深刻的解讀：

無限之城一日游

一位推特名Marian42_(簡稱瑪麗安) 的妹子，用WFC建造了無限之城。

這座城裡沒有街道，有的是各式各樣的房屋，和房屋之間的走道與樓梯。

沿著它們，你可以登上高台俯視全城，也可以穿行在安靜的小道。

不安分的你，還可以從欄杆上一躍而下，並不會受傷，可以繼續往前跑。

當你以為快要走到城市的盡頭，前面看不到建築物了，只要再跑幾步，眼前便又實時生出一片新城。

這裡沒有死胡同，只要你一直跑，城市就會在你前行的方向不斷擴張。

除了跑跑跳跳，還可以用M鍵切換飛行模式，以上帝視角觀察這座城，是如何流暢地向遠方延伸：

當然，進城之後不要只顧著活動筋骨，偶爾也看看風景吧。

你會愉快地發現，中式的屋頂與羅馬式的欄杆和石柱，在同一幢建築里相敬如賓，絲毫不會忸怩。

有閑情的話，可以細數一下，把這89種元素集齊：

畢竟，除了標配的屋頂啦、迴廊啦，幸運的人類還能在轉角遇到優雅的噴泉 (Demo傳送門見文底) 。

原理揭秘

無限城市一日游結束，是時候認真了解一下它背後的演算法了：波函數坍縮，究竟是什麼？

這個名字，來自量子力學中的一個概念，不過演算法本身倒是比量子力學好理解得多，我們先從一個例子開始科普。

婚禮座次問題

想像一下你正在計劃一場婚禮。問題來了，辦幾桌宴席、嘉賓坐哪裡都需要考慮。不巧的是，為了照顧大家的情緒和滿足各種條條框框的習俗，你需要調節幾個問題：

老爹不能坐在老媽兩張桌子以內的距離

老妹如果不能和其他兄弟姐妹坐一桌，會開啟可怕的狂暴模式

最好不要讓叔叔和環保主義者挨在一起坐

不好，離婚禮只有五個小時了。此情此景下，你可以選擇波函數坍縮來解決這個看似棘手的問題。

先畫一張空白的座位表，記錄下規則。

我們可以構建一張每個座位對應一個人的一一對應圖，每個座位都可以對應任何人，也就是我們的初始波函數。

你的座位計劃波函數就從這種變化萬千的情況下開始了，開始的座次就是就是每個座位有效布局的完全疊加。

「疊加」的概念用薛定諤的貓來理解最好不過，在未查看貓的狀態前，這就是一種疊加態，貓死貓活都可能存在。打開盒子後貓的疊加態小時，坍縮成確定態。

先選擇一個位置，隨機安排名單中一個人進去，此時座位波函數開始坍縮。

隨後，確定下的每個人都影響後面人員的排布。如果Michele不想坐在2號桌，那他的妹妹Barack也肯定不在這一桌。通過不斷更新可以坐在2號桌的人員名單，調整座位計劃的波函數。

不斷重複這個過程，直到每個座位的波函數都坍縮了或者遇到了矛盾無法安排。舉個例子，如果遇到無法將剩餘任何人安排到這個空位的情況，那這就是一種矛盾狀態，最好的解決方法就是：重新開始。

再嘗試幾次，能按規則安排下每個人就算大功告成了。

點陣圖（Bitmap）同理

婚禮排座位如此，波函數生成無限城市，將幾十種不同的建築元素拼接組合也是如此。

這個過程非常相似，只是改變了規則。台階可以直接和平地連接，但無法和屋頂元素相連，波函數不斷坍縮直到矛盾出現或全部坍縮。

兩種情況也有不同，婚禮座次問題的規則是提前寫好的，但無限城市的規則是用示例圖像形式呈現的：

演算法自己剖析示例，分析模式，自己推斷出像素或者圖塊的規則如何。

那無限城市到底是如何將建築元素拼接到一起的？我們先考慮一種簡單的特殊情況，一種稱為更簡單的平鋪模型（Even Simpler Tiled Model）的方法。

在這個模型中，可以將每種元素用像素形式呈現，並賦予一種單獨的顏色。舉個例子，下圖陸地、海岸、海洋和山川四種地形圖塊都用了不同的顏色來表示。

更簡單的平鋪模型的規則指定了哪些圖塊可以彼此相鄰放置，也規定了放置方向。每個規則都對應一個坐標，內含兩個相鄰的圖塊和一個方向，比如（海洋，海岸，左邊）代表一個海洋圖塊可以放置在一個海岸圖塊的左邊。

除了明確規則，還需要明確每種圖塊出現的頻率，在生成時這些頻率將作為權重，決定最終生成的畫風。

前面看到的無限城市，生成過程也和這個「比簡單還簡單的平鋪模型」類似，只是涉及的元素、規則更多。

坍縮

規則權重設置好，波函數坍縮可以開始了。

在無限城市問題中，最先確定的建築元素是隨機的，但演算法會按照熵值最小排列方法不斷擴充，也就是按系統的混亂程度最小排列。

一般來說，一個低熵的圖塊集合中，波函數坍縮時能選擇的圖塊類型相對較少，最終圖塊遇到矛盾的可能性就會小一些了。

遵循單個圖塊的權重的同時，還要考慮整張圖的全局權重。

比如，一個圖塊周圍，台階和平地圖塊出現的概率各佔0.5時，在全局權重的指導下，不會出現一塊台階一塊平地的尷尬情境，而可能直接用10塊平地拼接成「大平地」。

此時，波函數坍縮持續進行中。目之所及，無限城市中的地平線在不斷快速向遠處延伸。

所有輸出的波函數，要麼完全坍縮，支撐不斷建起的亭台樓閣，要麼出現了矛盾情況返回到某個節點重新不斷生成。

最終，我們創造出一個虛擬的無盡頭世界。

玩法還可以很花

想用波函數坍縮 (WFC) 來創造世界的，不止瑪麗安。

2016年，兩位美國少年發表了一個都市場景的滑板遊戲，叫Proc Skater 2016。

他們說，這是世界上第一個用WFC來生成關卡的遊戲。

只不過，這個遊戲里的空間，並非實時生成，也不是沒有盡頭。

在那之前，少年們還用同樣的方法，建起過一座屬於自己的城，有限的城。

當然，除了大興土木之外，WFC還有其他功能。

比如，有人就用它來寫十四行詩：

愛麗絲還不知道自己的路該往哪走，就已經不在這裡了。

(她來到了一個陌生的地方。)

那裡有座廳堂，周圍排滿了門。

每一扇門都在說著一些友好的話。

(彷彿在請她進去。)

後面幾句有點恐怖：

Down down down down.

Let me see that would be of very like a candle.

I wish you were down here with me.

大概，走進一扇門，便是不停地降落，降落。停下之後，周圍已不是人間。

底下是清冷幽暗的世界，如果有人陪就好了。

句子再不通順，也不妨礙人類的想像。反而越不通順，越有夢境的錯覺。

《咒怨》試玩，來自山下智博

說不定有一天，恐怖遊戲就不再需要循環場景來告訴你：逃不出去的。

只要有無限生成的世界，和鬼魅的情節或者台詞搭配食用，就夠了吧？

無限城市Demo試玩：

https://marian42.itch.io/wfc

無限城市開源代碼：

https://github.com/marian42/wavefunctioncollapse

波函數坍縮原理：

https://github.com/mxgmn/WaveFunctionCollapse

波函數坍縮論文：

https://adamsmith.as/papers/wfc_is_constraint_solving_in_the_wild.pdf

波函數坍縮科普文：

https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm/

—完—

年度評選報名

加入社群

量子位AI社群開始招募啦，歡迎對AI感興趣的同學，在量子位公眾號（QbitAI）對話界面回復關鍵字「交流群」，獲取入群方式；

此外，量子位專業細分群(自動駕駛、CV、NLP、機器學習等)正在招募，面向正在從事相關領域的工程師及研究人員。

進專業群請在量子位公眾號（QbitAI）對話界面回復關鍵字「專業群」，獲取入群方式。（專業群審核較嚴，敬請諒解）

誠摯招聘

量子位正在招募編輯/記者，工作地點在北京中關村。期待有才氣、有熱情的同學加入我們！相關細節，請在量子位公眾號(QbitAI)對話界面，回復「招聘」兩個字。

喜歡就點「好看」吧 !

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！