游戲里探索迷宮很好玩，玩多了就沒什么新了。
沒錯，如果游戲迷宮差別不大，時間久了就容易熟悉地圖，降低探索的樂趣。
現在，概率編程語言MarkovJunior解決了這個問題:
使用馬爾可夫算法，批量迷宮隨機生成，無一重復。你永遠不知道你玩的下一個迷宮會是什么樣子:
它不僅是一個2D迷宮，還是一個3D迷宮，有幾層地圖，可以隨機生成:
這個項目一出，立刻上了GitHub的熱榜，不到一周就已經收獲了2.6k星。
有網友感嘆，這種編程語言可以直接為RPG游戲或者動作游戲生成建筑。
我們來看看它的原理是什么，如何隨機生成各種迷宮。
基于馬爾可夫算法的構造
具體來說，這種概率編程語言由一系列特定的規則組成，是一個有序列表。
在生成模型的過程中，它會利用馬爾可夫算法實現隨機生成，然后制定一系列特定的規則來確定生成模型的類型，比如迷宮，地形圖或者電路圖。
馬爾可夫鏈具有無記憶的性質，即下一個狀態的概率分布只能由當前狀態決定，在時間序列中之前的事件與其無關。
那么，這些具體的規則到底是什么樣子的呢。
例如，最簡單的規則之一是將黑色色塊重寫為白色色塊，直到它最終填充整個模型:
例如，通過實現將白—黑色塊重寫為白—白色塊的規則，并結合馬爾可夫算法，可以得到一個概率生成模型:
再比如，基于推箱游戲的規則，
推箱子游戲
可以用這批小紅點隨機運送白方到指定地點:
像這樣的具體規則還有很多，都包含在MarkovJunior里面。
那么，我們如何使用這些規則來生成隨機模型呢。
2D/3D迷宮，可以繪制地形圖和電路圖。
以隨機生成2D迷宮為例:
這樣一個隨機的迷宮，MarkovJunior手邊能做出一把，只基于兩條規則:
第一個規則是將紅—黑—黑色塊隨機改寫成綠—綠—紅色塊。
第二條規則，當第一條規則被卡住，即沒有符合條件的選項時，自動執行，將紅綠綠色塊隨機改寫為白—白—紅色塊。
這樣，算法可以通過第一條規則生成隨機路徑，回溯沒有經過的路徑，通過第二條規則生成分叉，最后遍歷整個黑圖生成一組2D迷宮。
有一個更簡單的想法將所有白—黑—黑替換為白—A—白，其中A為中間狀態，不作為起點，迷宮生成后替換為白色
3D迷宮看起來像這樣
基于這一思想，通過改變規則組合方法，可以生成隨機地形圖。
比如嘗試生成一個河流地形圖，只需要使用上面的生成模型方法，再加上一些其他的重寫規則，就可以得出一個隨機的河流圖:
除了地形圖和簡單的2D/三維迷宮，更復雜的三維建筑也可以做。只需要在兩個2D迷宮之間的任意位置生成一批樓梯:
嗯，連電路圖都能畫出來…
可以說非常好用。
他做過最著名的項目應該是一套叫波函數坍縮算法的東西目前，GitHub上有18.7kStars
這個WFC算法是他受量子力學中波函數坍縮概念的啟發而創造的，目前已經應用到一些游戲中，比如小鎮折疊樂等等。
馬克西姆·顧敏沒有透露更多關于自己的信息，但我們可以在他的主頁上看到，這位大哥自稱概率模型之王，程序化的一代彌賽亞，馬爾可夫鏈的馴服者。
從GitHub的角度來看，這些年來，他一直專注于將各種數學算法應用于程序化生成，做出各種有趣的模型。
可能你玩過的一些游戲已經用上了他開發的算法。
項目地址:
聲明：本網轉發此文章，旨在為讀者提供更多信息資訊，所涉內容不構成投資、消費建議。文章事實如有疑問，請與有關方核實，文章觀點非本網觀點，僅供讀者參考。
精彩推薦
每周熱點
