如何生成一個「有趣」的rougelike地牢
前言
本文主要是基於下文的翻譯，有自己的一些小改動。該文的主要內容是關於程序自動生成地牢的演算法介紹，但你也可以從中學習到一些設計概念。
Creating Measurably "Fun" Maps基礎觀點
問：是什麼造成了地牢關卡不夠有趣？
答：玩家在大量區域都未探索的情況下就能通關地牢。這意味著玩家無需挑戰與抉擇就可以規避大部分的怪物、陷阱等地牢中設計的障礙；也可以說玩家抵達了地牢的終點，卻沒有付出太多的代價。（譯者註：這個觀點的前提是遊戲設計的機制本身是有趣的，只是程序自動生成的關卡不夠完善，從而導致玩家沒有辦法充分體驗機制。）
為了預防這個問題，我們認為玩家必須對地牢進行了一定的程度的探索後才能通關。這也是我們生成的地牢所要達到的目標。
理論準備
下面是作者為他的遊戲ADND設計的一套任務型地牢的生成演算法。要實現這個演算法，需要基礎的圖論知識（離散數學瞭解一下），還需要了解Dijkstra最短路徑（DSP）演算法。
我們會把地牢視為一個無向連通圖，每一個房間是一個節點，兩個房間的連接我們稱之為邊。那麼給一組起點房間與終點房間的(x, y)坐標，DSP演算法即可返回從(x_start, y_start)到(x_end, y_end)最短路徑的(x, y)坐標數組（如果最短路徑存在的話）。這是我們實現地牢生成演算法的有效工具。
掌握了這些，我們就可以開始生成地牢啦~
地牢生成演算法
（譯者註：作者這裡的演算法其實是對一個已生成好的地牢進行一些處理，使其變的「有趣」。如果想對地牢生成從0開始研究的，可以看文末的延伸閱讀部分。）
通常來說，地牢的起點房間是一個洞穴入口、樓梯或者無論什麼適合讓玩家開始的地方，而終點房間由你自己定義。我們首要先做的操作就是連接地牢的起點與終點，通過DSP連接這兩個房間，你會得到一條路徑（起點到終點經過最少房間的路徑，也就是最短路徑）。那麼此時就有了兩類節點（作者在這裡就開始統一用了節點這個詞，為了便於理解，這裡再次強調，地牢裏的每一個房間就是一個節點）：一類是在該路徑上的節點，我們稱之為路徑節點（所謂必經之路）；另一類是不在該路徑上的節點，我們稱之為無意義節點。這裡的關鍵就是如何處理無意義節點，使得玩家想要或者不得不去探索它們，從而把這些無意義節點轉化成路徑節點。
其實有很多方法來解決無意義節點的問題，但在這之前，你要把無意義節點進行分組，使它們變成一片片無意義區域。一片無意義區域是指在沒有穿過任何路徑節點前提下，所有可以互相到達的無意義節點的集合。例如你的地牢是一個正方形，起點在左下角，目標點在右上角，那麼路徑就是從左至右的一條對角線，無意義區域有兩個，分別是對角線上方的三角形和對角線下方的三角形。
不管怎樣，只要循環執行以下操作，直到所有無意義區域裏的無意義節點小於自己設置的閾值即可達到我們的目的。
1. 選擇一個最大的無意義區域（無意義節點最多的區域）
2. 通過以下流程來處理這些無意義區域。
a. 選擇離任何路徑節點距離最遠的一個節點（以下稱為P點）。
b. 執行下列任意一個操作。 i. 根據無意義區域的大小，放置一個小型、中型或大型的獎勵在P點上。ii. 選擇路徑上的一個毗連該無意義區域的節點，用門擋住該路徑。把鑰匙放在P點上。（門與鑰匙可以替換為其他包裝）
iii. 如果該無意義區域非常小，可以直接標記為「已處理」而不做任何處理。 iv. 在房間裏放置一個令人討厭的陷阱或者其他可以轉移注意力的元素，以保持玩家對地牢的未知感。c. 從地牢的起點到終點重新計算路徑，這樣會第一次訪問到「已處理」的節點，也得到了新的路徑節點列表，同時自然要將這些節點從無意義節點列表裡移除。
3. 重新計算無意義區域，並按大小排序。
4. 如前所述，如果最大的無意義區域裏包含的無意義節點的數量小於閾值，演算法結束。
延伸閱讀
以下幾篇是幾種普通地牢的生成演算法。
一種 Roguelike 地牢生成演算法
隨機生成 Tile Based 地圖之--洞穴房間和迷宮：一個地牢生成演算法 | indienova 獨立遊戲下面兩篇文章是一樣的，前者是翻譯版。該文章就更著重於從設計的角度去介紹「鎖」的意義。
遊戲設計中的鎖機制 - 牽著老婆滿街逛 - C++博客推薦閱讀：
