永遠走不到邊際的虛擬城市!源自於量子力學的神秘演算法「波函數塌縮」

【我們為什麼挑選這篇文章】波函數塌縮似乎還有很多非常有趣的應用場景,用在城市裡也確實令人感到非常有趣,希望未來還能看到利用波函數塌縮達成的無限延伸地圖遊戲,畢竟只有一堆房子看久了其實也是蠻膩的。(責任編輯:林子鈞)

本文經 AI 新媒體量子位(公眾號 ID: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 試玩

無限城市開源代碼

波函數塌縮原理

波函數塌縮論文

波函數塌縮科普文

工程師的工具包

【佛心來著】AppWorks 推出工程師培訓課程,20 週免費課程初學者也能輕鬆學起

工程師時尚穿搭型錄:不敗格紋襯衫、長白襪搭拖鞋、 連帽 T 包衛生衣

數據科學家、工程師們有福啦!Google「數據搜尋引擎」正式上線

(本文經原作者 量子位 授權轉載,並同意 TechOrange 編寫導讀與修訂標題,原文標題為 〈無邊無際的虛擬城市來了!能走能飛的 Demo,一火再火的“波函數坍縮”開源算法 〉。)


我們正在找夥伴!

2019 年我們的團隊正在大舉擴張,需要你的加入跟我們一起找出台灣創新原動力! 我們正在徵 《採訪社群編輯》、《助理編輯》,詳細職缺與應徵辦法 請點我

點關鍵字看更多相關文章: