1行代碼生成隨機迷宮，概率編程語言登GitHub熱榜，作者曾開發(fā)著名WF

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

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

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

使用馬爾可夫算法，批量迷宮隨機生成，無一重復。你永遠不知道你玩的下一個迷宮會是什么樣子:

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

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

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

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

基于馬爾可夫算法的構造

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

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

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

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

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

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

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

推箱子游戲

可以用這批小紅點隨機運送白方到指定地點:

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

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

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

以隨機生成2D迷宮為例:

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

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

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

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

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

3D迷宮看起來像這樣

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

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

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

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

可以說非常好用。

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

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

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

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

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

項目地址: