游戲里探索迷宮很好玩，玩多了就沒什么新了。

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

現(xiàn)在，概率編程語言MarkovJunior解決了這個(gè)問題:

使用馬爾可夫算法，批量迷宮隨機(jī)生成，無一重復(fù)。你永遠(yuǎn)不知道你玩的下一個(gè)迷宮會是什么樣子:

它不僅是一個(gè)2D迷宮，還是一個(gè)3D迷宮，有幾層地圖，可以隨機(jī)生成:

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

有網(wǎng)友感嘆，這種編程語言可以直接為RPG游戲或者動作游戲生成建筑。

我們來看看它的原理是什么，如何隨機(jī)生成各種迷宮。

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

具體來說，這種概率編程語言由一系列特定的規(guī)則組成，是一個(gè)有序列表。

在生成模型的過程中，它會利用馬爾可夫算法實(shí)現(xiàn)隨機(jī)生成，然后制定一系列特定的規(guī)則來確定生成模型的類型，比如迷宮，地形圖或者電路圖。

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

那么，這些具體的規(guī)則到底是什么樣子的呢。

例如，最簡單的規(guī)則之一是將黑色色塊重寫為白色色塊，直到它最終填充整個(gè)模型:

例如，通過實(shí)現(xiàn)將白—黑色塊重寫為白—白色塊的規(guī)則，并結(jié)合馬爾可夫算法，可以得到一個(gè)概率生成模型:

再比如，基于推箱游戲的規(guī)則，

推箱子游戲

可以用這批小紅點(diǎn)隨機(jī)運(yùn)送白方到指定地點(diǎn):

像這樣的具體規(guī)則還有很多，都包含在MarkovJunior里面。

那么，我們?nèi)绾问褂眠@些規(guī)則來生成隨機(jī)模型呢。

2D/3D迷宮，可以繪制地形圖和電路圖。

以隨機(jī)生成2D迷宮為例:

這樣一個(gè)隨機(jī)的迷宮，MarkovJunior手邊能做出一把，只基于兩條規(guī)則:

第一個(gè)規(guī)則是將紅—黑—黑色塊隨機(jī)改寫成綠—綠—紅色塊。

第二條規(guī)則，當(dāng)?shù)谝粭l規(guī)則被卡住，即沒有符合條件的選項(xiàng)時(shí)，自動執(zhí)行，將紅綠綠色塊隨機(jī)改寫為白—白—紅色塊。

這樣，算法可以通過第一條規(guī)則生成隨機(jī)路徑，回溯沒有經(jīng)過的路徑，通過第二條規(guī)則生成分叉，最后遍歷整個(gè)黑圖生成一組2D迷宮。

有一個(gè)更簡單的想法將所有白—黑—黑替換為白—A—白，其中A為中間狀態(tài)，不作為起點(diǎn)，迷宮生成后替換為白色

3D迷宮看起來像這樣

基于這一思想，通過改變規(guī)則組合方法，可以生成隨機(jī)地形圖。

比如嘗試生成一個(gè)河流地形圖，只需要使用上面的生成模型方法，再加上一些其他的重寫規(guī)則，就可以得出一個(gè)隨機(jī)的河流圖:

除了地形圖和簡單的2D/三維迷宮，更復(fù)雜的三維建筑也可以做。只需要在兩個(gè)2D迷宮之間的任意位置生成一批樓梯:

嗯，連電路圖都能畫出來…

可以說非常好用。

他做過最著名的項(xiàng)目應(yīng)該是一套叫波函數(shù)坍縮算法的東西目前，GitHub上有18.7kStars

這個(gè)WFC算法是他受量子力學(xué)中波函數(shù)坍縮概念的啟發(fā)而創(chuàng)造的，目前已經(jīng)應(yīng)用到一些游戲中，比如小鎮(zhèn)折疊樂等等。

馬克西姆·顧敏沒有透露更多關(guān)于自己的信息，但我們可以在他的主頁上看到，這位大哥自稱概率模型之王，程序化的一代彌賽亞，馬爾可夫鏈的馴服者。

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

可能你玩過的一些游戲已經(jīng)用上了他開發(fā)的算法。

項(xiàng)目地址: