1行代碼生成隨機(jī)迷宮，這個(gè)概率編程語(yǔ)言登GitHub熱榜，作者曾開(kāi)發(fā)著名WFC算法

蕭簫 發(fā)自 凹非寺
量子位 | 公眾號(hào) QbitAI

探索游戲中的迷宮很有趣，然而玩多了就沒(méi)啥“新鮮感”了？

沒(méi)錯(cuò)，如果游戲迷宮差別不大，時(shí)間一久就容易熟悉地圖，降低了探索的樂(lè)趣。

現(xiàn)在，一個(gè)“橫空出現(xiàn)”的概率編程語(yǔ)言MarkovJunior解決了這一問(wèn)題：

利用馬爾科夫算法，隨機(jī)生成批量迷宮，沒(méi)有一個(gè)是重復(fù)的，你永遠(yuǎn)也不知道玩到的下一個(gè)迷宮長(zhǎng)什么樣子：

不僅是2D迷宮，就連需要搭建好幾層地圖的3D迷宮，也能隨機(jī)生成：

這個(gè)項(xiàng)目一出，立刻上了GitHub熱榜，不到一周就已經(jīng)收獲2.6k Star。

有網(wǎng)友感嘆，用這個(gè)編程語(yǔ)言就能直接給RPG游戲或動(dòng)作游戲生成建筑了。

Keras的作者也對(duì)這個(gè)概率編程語(yǔ)言挺感興趣：

來(lái)看看它的原理究竟是什么、又是如何隨機(jī)生成各種迷宮的。

基于馬爾科夫算法構(gòu)造

據(jù)作者介紹，這套概率編程語(yǔ)言借鑒了馬爾科夫算法（Markov algorithms）。

（MarkovJunior這個(gè)名字，也是以提出馬爾科夫算法的數(shù)學(xué)家Andrey Markov命名）

具體來(lái)說(shuō)，這套概率編程語(yǔ)言由一系列特定規(guī)則（Rewrite Rules，重寫(xiě)規(guī)則）組成，是一個(gè)有序列表。

它在生成一個(gè)（迷宮）模型的過(guò)程中，會(huì)利用馬爾科夫算法實(shí)現(xiàn)“隨機(jī)生成”，再通過(guò)制定一系列特定規(guī)則，決定生成模型的類別，例如是迷宮、地形圖，還是電路圖等。

馬爾科夫鏈具有“無(wú)記憶”性質(zhì)，即下一狀態(tài)的概率分布只能由當(dāng)前狀態(tài)決定，在時(shí)間序列中它前面的事件均與之無(wú)關(guān)。

所以，這些特定規(guī)則究竟長(zhǎng)啥樣？

例如，一個(gè)最簡(jiǎn)單的規(guī)則，就是將“黑色”色塊重寫(xiě)為“白色”色塊，直到最終填滿整個(gè)模型：

又例如，執(zhí)行將“白-黑”色塊重寫(xiě)為“白-白”色塊的規(guī)則，結(jié)合馬爾科夫算法，就能得到一個(gè)概率生成模型：

再例如，基于“推箱子游戲”的規(guī)則，

就能用這批小紅點(diǎn)隨機(jī)將白色方塊“搬運(yùn)”到指定地點(diǎn)：

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

那么，我們究竟要怎么利用這些規(guī)則，來(lái)生成一個(gè)隨機(jī)（迷宮、電路圖等）模型呢？

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

先以隨機(jī)生成一個(gè)2D迷宮為例：

從圖片中來(lái)看，這個(gè)迷宮算法會(huì)自動(dòng)生成一個(gè)“起始點(diǎn)”紅點(diǎn)，在一塊黑色地圖中隨機(jī)探索并重寫(xiě)路徑，最終填滿整個(gè)地圖，完成一個(gè)有始有終、也有分岔口的“迷宮”。

這樣的隨機(jī)迷宮，MarkovJunior隨手就能做出一大把，只需要基于兩個(gè)規(guī)則：

第一個(gè)規(guī)則，將“紅-黑-黑”色塊隨機(jī)重寫(xiě)為“綠-綠-紅”色塊。

第二個(gè)規(guī)則，在第一個(gè)規(guī)則被“卡住”，也就是沒(méi)有符合條件的可選項(xiàng)時(shí)，自動(dòng)執(zhí)行將“紅-綠-綠”色塊隨機(jī)重寫(xiě)為“白-白-紅”色塊。

這樣一來(lái)，算法就能通過(guò)第一個(gè)規(guī)則生成隨機(jī)路徑，并通過(guò)第二個(gè)規(guī)則回溯還沒(méi)有經(jīng)過(guò)的路徑、生成岔路口，最終遍歷整個(gè)黑色地圖，生成一套“2D迷宮”。

還有更簡(jiǎn)單的思路，將所有“白-黑-黑”替換成“白-A-白”，其中A是一個(gè)中間態(tài)，不作為起點(diǎn)，在迷宮生成完成后被替換為白色。

據(jù)作者表示，利用這個(gè)規(guī)則，1行代碼就能隨機(jī)生成2D或3D迷宮。

基于這樣的思路，換套規(guī)則組合方法，還能生成隨機(jī)地形圖。

例如，試圖生成一塊河流地形圖，就只需要利用上面的生成模型方法，再添加一些其他的重寫(xiě)規(guī)則，就能搞出一個(gè)隨機(jī)河流圖來(lái)：

除了地形圖、簡(jiǎn)單的2D/3D迷宮，更復(fù)雜的3D建筑也能搞定，只需要在兩層2D“迷宮”之間的隨機(jī)位置生成一批“樓梯”：

嗯，連電路圖都能畫(huà)……

據(jù)作者介紹，只要靈活運(yùn)用這些規(guī)則，就能用MarkovJunior隨機(jī)生成各種各樣的建筑和圖畫(huà)。

可以說(shuō)是非常好用了。

還是著名WFC算法的作者

這個(gè)概率編程語(yǔ)言的作者M(jìn)axim Gumin，是一名獨(dú)立游戲開(kāi)發(fā)者。

他搞過(guò)最有名的項(xiàng)目，應(yīng)該是一套叫做“波函數(shù)坍縮算法”（WaveFunctionCollapse，WFC）的東西，目前在GitHub上已經(jīng)有18.7k?Stars。

這套WFC算法是他受量子力學(xué)中“波函數(shù)坍縮”概念的啟發(fā)自創(chuàng)出來(lái)的，目前已經(jīng)被應(yīng)用到一些游戲中，如《城鎮(zhèn)疊疊樂(lè)》（Townscaper）等。

Maxim Gumin并未透露更多自己的信息，但我們能在他的主頁(yè)上看到，這位老哥自稱“概率模型之王，程序化生成の彌賽亞，馴服馬爾科夫鏈的人……”（手動(dòng)狗頭）

從GitHub來(lái)看，這些年他一直專注于將各種數(shù)學(xué)算法應(yīng)用于程序化生成中，做出各種有意思的模型。

說(shuō)不定你玩過(guò)的游戲中，有一些已經(jīng)用過(guò)他開(kāi)發(fā)的算法了。

項(xiàng)目地址：
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