蕭簫 發自 凹非寺

量子位 | 公眾號 QbitAI

探索遊戲中的

迷宮

很有趣，然而玩多了就沒啥“新鮮感”了？

沒錯，如果遊戲迷宮差別不大，時間一久就容易熟悉地圖，降低了探索的樂趣。

現在，一個“橫空出現”的

機率程式語言

MarkovJunior解決了這一問題：

利用馬爾科夫演算法，

隨機

生成批次迷宮，沒有一個是重複的，你永遠也不知道玩到的下一個迷宮長什麼樣子：

不僅是

2D迷宮

，就連需要搭建好幾層地圖的

3D迷宮

，也能隨機生成：

這個專案一出，立刻上了GitHub熱榜，不到一週就已經收穫

2.6k Star

。

有網友感嘆，用這個程式語言就能直接給RPG遊戲或動作遊戲生成建築了。

Keras的作者也對這個機率程式語言挺感興趣：

來看看它的原理究竟是什麼、又是如何隨機生成各種迷宮的。

基於馬爾科夫演算法構造

據作者介紹，這套機率程式語言借鑑了

馬爾科夫演算法

（Markov algorithms）

。

（MarkovJunior這個名字，也是以提出馬爾科夫演算法的數學家Andrey Markov命名）

具體來說，這套機率程式語言由一系列特定規則

（Rewrite Rules，重寫規則）

組成，是一個有序列表。

它在生成一個

（迷宮）

模型的過程中，會利用馬爾科夫演算法實現“

隨機生成

”，再透過制定一系列特定規則，決定生成模型的

類別

，例如是迷宮、地形圖，還是電路圖等。

馬爾科夫鏈具有“無記憶”性質，即下一狀態的機率分佈只能由當前狀態決定，在時間序列中它前面的事件均與之無關。

所以，這些

特定規則

究竟長啥樣？

例如，一個最簡單的規則，就是將“黑色”色塊重寫為“白色”色塊，直到最終填滿整個模型：

又例如，執行將“白-黑”色塊重寫為“白-白”色塊的規則，結合馬爾科夫演算法，就能得到一個機率生成模型：

再例如，基於

“推箱子游戲”

的規則，

△推箱子游戲

就能用這批小紅點隨機將白色方塊“搬運”到指定地點：

像這樣的特定規則還有很多，都包含在MarkovJunior中。

那麼，我們究竟要怎麼利用這些規則，來生成一個隨機

（迷宮、電路圖等）

模型呢？

2D/3D迷宮、地形圖和電路圖都能畫

先以隨機生成一個

2D迷宮

為例：

從圖片中來看，這個迷宮演算法會自動生成一個“起始點”紅點，在一塊黑色地圖中隨機探索並重寫路徑，最終填滿整個地圖，完成一個有始有終、也有分岔口的“迷宮”。

這樣的隨機迷宮，MarkovJunior隨手就能做出一大把，只需要基於兩個規則：

第一個規則

，將“紅-黑-黑”色塊隨機重寫為“綠-綠-紅”色塊。

第二個規則

，在第一個規則被“卡住”，也就是沒有符合條件的可選項時，自動執行將“紅-綠-綠”色塊隨機重寫為“白-白-紅”色塊。

這樣一來，演算法就能透過第一個規則生成隨機路徑，並透過第二個規則回溯還沒有經過的路徑、生成岔路口，最終遍歷整個黑色地圖，生成一套“2D迷宮”。

還有更簡單的思路，將所有“白-黑-黑”替換成“白-A-白”，其中A是一箇中間態，不作為起點，在迷宮生成完成後被替換為白色。

據作者表示，利用這個規則，

1行程式碼

就能隨機生成2D或3D迷宮。

△3D迷宮長這樣

基於這樣的思路，換套規則組合方法，還能生成隨機

地形圖

。

例如，試圖生成一塊河流地形圖，就只需要利用上面的生成模型方法，再新增一些其他的重寫規則，就能搞出一個隨機河流圖來：

除了地形圖、簡單的2D/3D迷宮，更復雜的

3D建築

也能搞定，只需要在兩層2D“迷宮”之間的隨機位置生成一批“樓梯”：

嗯，連

電路圖

都能畫……

據作者介紹，只要靈活運用這些規則，就能用MarkovJunior隨機生成各種各樣的建築和圖畫。

可以說是非常好用了。

還是著名WFC演算法的作者

這個機率程式語言的作者Maxim Gumin，是一名獨立遊戲開發者。

他搞過最有名的專案，應該是一套叫做“波函式坍縮演算法”

（WaveFunctionCollapse，WFC）

的東西，目前在GitHub上已經有

18.7k

Stars。

這套WFC演算法是他受量子力學中“波函式坍縮”概念的啟發

自創

出來的，目前已經被應用到一些遊戲中，如《城鎮疊疊樂》

（Townscaper）

等。

△圖源：Steam

Maxim Gumin並未透露更多自己的資訊，但我們能在他的主頁上看到，這位老哥自稱“機率模型之王，程式化生成の彌賽亞，馴服馬爾科夫鏈的人……”

（手動狗頭）

從GitHub來看，這些年他一直專注於將各種數學演算法應用於程式化生成中，做出各種有意思的模型。

說不定你玩過的遊戲中，有一些已經用過他開發的演算法了。

專案地址：

https：//github。com/mxgmn/MarkovJunior

參考連結：

［1］https：//twitter。com/ExUtumno

［2］https：//github。com/mxgmn/WaveFunctionCollapse

［3］https：//www。youtube。com/watch？v=DOQTr2Xmlz0

［4］https：//twitter。com/fchollet/status/1532019171038355456

— 完 —

量子位 QbitAI · 頭條號簽約