前言：上週末和同組的朋友們一起參加了CiGA Game Jam 2023的活動，以TOUCH為主題製作了一款類似《魔塔》的冒險小遊戲，除了一套簡單的元素交互系統之外，遊戲裡的一大重點是自動化的隨機地圖生成算法，它保證了每一局遊戲的地圖都是獨特的。
本文就是來探討這個比賽項目中的隨機地圖生成算法機制的。
正文
地圖是遊戲中非常重要的一個組成部分，它有許多不同的類型和設計方法，地圖設計的好壞往往直接影響著玩家的遊戲體驗。
而無論是哪種地圖設計方法，其本質都離不開數學概念中的“圖”，即一類用於表示多個節點間連接關係的數據結構描述，以及由此派生出的許多算法。
即便是現在的各種3A大作，第一人稱射擊，動作角色扮演，開放世界等等類型的遊戲，它們的地圖設計從抽象層面上來說，依然是最簡單的圖結構，無非就是圖中的節點包含的內容更豐富，連接更復雜多變罷了。
撇開這些高端的地圖不談，僅就傳統的2D遊戲而言，它們的地圖機制和設計方案相對來說是比較有限的，可以是預先畫好的一整張大地圖，也可以是大小地圖結合，通過類似“進入地圖點”的方式銜接。
而當地圖的構成方式被限定在“瓦片式地圖”這個狹窄的範圍內之後，地圖的設計方法也變得相對確定起來。
第一類別自然是最常見的一種，即手工設計地圖，通過編輯器轉化為數據保存下來，並在遊戲中讀取展示。
這種做法好處很多，地圖設計感強，可玩性和地圖機制的平衡性可以設計的很好，也基本不會出現地圖BUG。
但缺點也很明顯，投入工時多，內容固定，反覆遊玩時無法提供新鮮感。
與之相對的就是第二類別，算法自動生成地圖，這種做法的好處和缺點與第一類正好相反，它的設計感不好做，可玩性和機制平衡性也難以設計，地圖BUG可能出現。
好處則是實時生成，隨機性強，新鮮感消退較慢。
由此可以看出，算法生成地圖這種方案更適合一部分開放世界或者RogueLike遊戲。
基於瓦片式地圖的生成算法有好幾種，比如洞穴生成算法，迷宮生成算法和房間地圖生成算法等，而接下來要介紹和討論的是一種結合了迷宮生成和房間鋪設兩種機制的算法，用它能夠生成一些同時具備多個房間和迷宮走廊的地圖結構，很適用於RogueLike遊戲。
該算法來自於文章《Rooms and Mazes: A Procedural Dungeon Generator》
它的基本思路就是按如下步驟生成迷宮地圖：
- 選取房間
- 在房間外生成迷宮
- 用門連接所有迷宮走廊和房間
- 去除所有死衚衕，留下單一的通路
對於第一步的“選取房間”，原作者採用了一個非常簡單粗暴的方式，即隨機選擇房間的大小和位置若干次，如果隨機出來的房間和其它已經選擇好的房間沒有重疊則將其選擇出來，否則拋棄掉再來一次。
運行了一定次數的循環後便可以得到隨機房間的分佈。
這當然是一種略顯低效的做法，而且結果並不穩定，想要對其進行優化改造的話，可以參考另一篇文章《Procedural Dungeon Generation Algorithm》
這篇文章裡提到了一種有些“特別”的房間生成算法，不同於常見的圓內隨機取點加驗證的方法，這種特別的生成方法藉助了遊戲引擎的物理系統的一些特性，它的操作方法大概描述如下：
- 通過圓內取點的方式隨機生成一些房間，並且暫時不考慮它們相互重疊的問題。
- 給每個房間加上剛體和碰撞器
- 運行物理系統，此時這些房間會因為相互排斥而分離開來
- 在沒有房間繼續受到排斥後記錄所有房間的當前位置即可
不得不說這一方案非常巧妙，但同時它的可實施性也確實不太高，尤其是在多線程快速生成地圖的時候。
一個替代方案自然是手動模擬這個物理運算過程，比如採用AABB包圍框算法不停遍歷所有被選出來的房間並改變其座標位置，直至所有房間都不再重疊為止。
至於在實際使用中如何選擇，那就得看具體需求了。
有了生成好的房間，下一步就是在房間之外生成迷宮，由於這裡並非是要生成真正意義上的迷宮，而是需要生成一些“通道走廊”來填充房間之外的區域，因此並沒有採用一些經典的迷宮生成算法，而是採取了暴力開路的方式。
即遍歷整個地圖“內部”（也就是留出最外圈作為外牆）的每一個地塊，如果發現它既不屬於某個房間，也沒有被打開，則從它開始選取任意方向“開路前進”，直至遇到房間牆壁或者地圖外圈才轉彎。
為了增加生成算法的多樣性，在這個過程中加入一個隨機“拐彎”的概率，即使沒有遇到房間牆壁或者外圈，也會有一定概率發生拐彎。
到這裡為止，地圖裡已經有了房間和房間外的“迷宮”，但這些區域都沒有被連接到一起，因此下一步便是尋找可以用於連接的地塊，將它們修改為“門”即可。
這一步算法的核心要點在於“分區”的概念，即將不同的房間以及“迷宮走廊”都標識成不同的“區域”，然後在區域的鄰接點上選擇可以作為“門”的地塊。
分區過程類似泛洪，即從一個點出發進行遍歷，給房間內的空地塊和迷宮走廊都打上“標籤”，計算結束後會得到一張“分區地圖”，之後只要從這個分區地圖上找到可用的鄰接點作為門即可。
到這裡其實地圖的生成就可以說是結束了，有了分佈在各處的多個房間，有了連接房間的走廊，最後的消除死衚衕其實是個可選項，主要看遊戲本身是否需要保留這些“錯誤道路”。
甚至還可以繼續添加一些細節，比如將某些特定位置的走廊擴展成小房間，用來放置一些過渡性的擺設或者機制等。
總之，這一套地圖生成機制適合於同時對房間和迷宮元素都有需求的情況，而且還能對它進行靈活的定製化改造，在製作RogueLike遊戲時是值得考慮的一種地圖生成方案。
附言：我們組正在做的遊戲就打算採用這種地圖生成的方案，歡迎大家來看看
名稱：《邊界迷航》
鏈接：https://www.gcores.com/games/102523