三套簡單的迷宮地圖生成方案

概述

文章基於一種基礎的地圖，來討論三套不同的地圖生成方案。

文章不會出現跟代碼相關的內容，會以較為通俗的語句和不少簡單的示意圖來表示迷宮的生成方案。其中不少方法來自於遊戲界前輩，我根據自己的基礎地圖做了不少修正（畢竟迷宮和地圖的形式多種多樣，適合自己遊戲的才是最好的）。

根據方案生成地圖之後，還可以加上一些靜態分布來豐富地圖表現，大家就自行發揮啦！

地圖基礎

地圖的形式很多，這裡我使用的地圖是以tile塊為單位分割的地圖，地圖上的tile塊形式很多，但主要分成三種：

A：陸地，可以在上面分布一些角色啦物件啦

B：過渡，根據物理框可以在上面移動，不過一般不會分布物件

C：水域，不可移動的區域，可以理解成為迷宮的「牆」

在後文的迷宮生成方案里，會以水域作為分割，主要圍繞陸地的分布來設計迷宮，過渡的地塊根據遊戲實際需要再去生成。如果你不希望地圖用水域來分割，那隻需要把水域改成傳統的牆壁即可。

本文用來展示的地圖，面積都比較小，方便表達迷宮的生成規則。在實際遊戲製作時，按需求去鋪量就行。

方案一：主路扭曲型

1、首先，按照下圖的間隔規則來生成基礎的大地圖，1為陸地，0為水域。

2、然後，選擇一個靠近邊緣的1作為起點，在它的周圍隨機找另一個黃色的1（這裡的「周圍」指的是上下左右4個方向，斜邊不算）。找到就把他們聯通，即把兩個1之間的0變成陸地，這裡用紅色來表示。

3、把上一步「終」的格子作為新的一個「起」格子，不停循環第二步的過程，直到找不到周圍有黃色的1。

4、這時候，原路往回走（即不停去找前一個格子），直到找到一個格子，這個格子周圍有黃色的1，那麼從這個格子開始重複前兩個步驟。

5、接下來就是不停重複上面的步驟，找到就聯通，找不到就往回走~

6、填充完整個地圖之後，迷宮就算是製作完成了，根據需求加上終點即可。

總結一下，這種方案生成的迷宮會有一條明顯的主路，即一條特別長、貫穿大部分區域的路線，同時，迷宮的路線一般比較扭曲。

方案二：自然分岔型

這個方案的雛形來自於隨機prim演算法，具體步驟如下：

1、跟方案一一樣，生成一個基礎地圖。格子先用黃色1和灰色0來表示，暫時不區分水陸。

2、隨機取一個地圖邊緣的黃色1，把它標記為紅色1，即變成陸地。然後把它旁邊的灰色0標記成藍色0，表示「待定」。（注意的是，大地圖四周的灰色0固定不變，作為地圖邊緣而存在）

3、敲黑板了！！這裡是重點！！！

隨機選一個藍色的0（這一步很重要，會使這個方案明顯區別於上一個方案），然後看紅色1隔著這個藍色0對面的格子，是否是黃色的1：

如果是，則把對面的黃色1標記成紅色1，即變成陸地，然後把藍色0變成紅色的0，即也變成陸地；

如果不是，就把這個藍色的0變成灰色的0。

最後，把新創建的紅色1周圍的灰色0，標記成藍色0。

4、繼續重複上面的步驟

5、對比上圖和下圖，這裡取一個藍色0生成一個紅色1之後，新生成的紅色1旁邊，有兩個藍色0的兩邊都是紅色1了，那麼就根據第三步的規則，在稍後取到這些藍色0時，就會把他們變成灰色0

6、繼續重複上述步驟，直到整個地圖沒有藍色0了，地圖就生成完畢

總結一下，對比方案一，這套方案不會出現明顯的主路，迷宮相對比較自然，但迷宮的分岔路會比較多，所以迷宮可能會更複雜，即玩家需要做選擇的次數可能比較多。

方案三：塊狀分割型

上述兩個方案有個共同的特點，就是道路永遠都是1個格子寬，如果遊戲需要給地圖創造一些小型地塊或者更寬的道路，需要在迷宮生成之後再用各種分布的規則來豐富迷宮。

而第三個方案則以小型地塊作為出發點來設計迷宮，這套方案的雛形來自於國外大神Bob Nystrom，文章後面附上了他的個人主頁。

1、首先，在大地圖（還是之前那個大地圖）上生成若干小型地形，保證邊長是奇數且不重合就好（示意圖全部使用了正方形，實際上可以做成長方形讓地圖更加自然）。注意頂點要在黃色1格子上即可，這裡我用橙色1來表示這些小型地塊。

2、然後，根據之前方案一的迷宮生成方案，在非小型地塊的區域里，用迷宮來填充。這一步完成之後，迷宮和小型地形是分隔開來的。

3、在橙色1的小型地形周圍，隨機取點以連接黃色1，連接點的數量可以根據需要來確定，建議是不要吝嗇連接點的個數，因為這種地圖之下，分岔路遠比前兩種方案要少。

4、接下來是簡化地圖，目的是去掉一些死胡同，因為這種方案的核心在於小型地塊，沒有必要讓玩家在迷宮的路上繞。方法是把一些3邊都是灰色0的黃色1去掉即可，具體數量也根據遊戲需求來制定，我這裡只去掉了一部分。

5、最後，給地圖加上出口和入口，地圖就做完啦！

總結一下，這種方案比前兩種多了小型地塊，這一點比較適合設計玩家的階段性反饋。同時地圖的分岔路明顯減少，玩家在這種方案下的選擇次數會明顯降低。另外，由於這個方案的步驟相對多且獨立，所以對於設計者來講會比較容易控制地圖的結構。

參考

隨機prim演算法參考了很多網上的資源和代碼，也有很多變種，網上都可以搜得到，比如：

隨機迷宮生成演算法整理分析 | indienova 獨立遊戲

[迷宮中的演算法實踐]迷宮生成演算法--Prim演算法-布布扣-bubuko.com

【Tree】迷宮生成演算法 - visayafan - 博客園

而塊狀分割型地圖的思路就來源於Bob Nystrom，這是他的個人主頁和文章：

journal.stuffwithstuff.comRooms and Mazes: A Procedural Dungeon Generator

------6.15---------------------------------------------------------------

還有一個很有趣的迷宮生成網頁：

Maze Generator

可以直接規定迷宮的大小，甚至是迷宮的形狀規則

推薦閱讀：