生長樹演算法迷宮生成器

生長樹演算法很有趣，因為它可以模擬其他幾種演算法的行為，這取決於在生成過程中如何選擇下一個單元格。本頁的實作採用廣度優先、類似隊列的方法。

完美迷宮是指從迷宮中的任意一點到另一點都只有一條路徑的迷宮。這意味著你不會最終陷入繞圈的境地，但你會經常遇到死胡同，迫使你轉身返回。

這裡產生的迷宮地圖包含一個預設版本，沒有任何起點和終點位置，因此您可以自己決定：從迷宮中的任何點到任何其他點都會有一個解決方案。如果您想要靈感，您可以啟用建議的開始和結束位置 - 甚至可以看到兩者之間的解決方案。

關於生長樹演算法

生長樹演算法是一種靈活且強大的生成完美迷宮的方法。這個演算法很有趣，因為它可以模擬其他幾種迷宮生成演算法的行為，例如 Prim 演算法、遞歸回溯和遞歸除法，這取決於您如何選擇下一個要處理的單元格。

生長樹演算法的工作原理

步驟 1：初始化

• 從未訪問過的單元格網格開始。
• 選擇一個隨機的起始儲存格並將其新增至清單中。

第 2 步：迷宮生成循環

• 當儲存格清單不為空時：
  • 根據特定策略從清單中選擇一個儲存格（如下所述）。
  • 從選定的單元格開闢一條通道到其未訪問的鄰居之一（隨機選擇）。
  • 將鄰居添加到列表中，因為它現在是迷宮的一部分。
  • 如果選定的儲存格沒有未存取的鄰居，則將其從清單中刪除。

步驟 3：終止

• 當清單中不再有單元格時，演算法結束，這表示整個迷宮已被雕刻。

小區選擇策略（演算法的彈性）

生長樹演算法的定義特徵是如何選擇下一步要處理的單元格。這個選擇極大地影響了迷宮的外觀：

最新單元（類似堆疊的行為）－遞歸回溯器：

• 始終選擇最近新增的儲存格。
• 產生長而曲折的走廊，其中有許多死胡同（就像深度優先搜索迷宮一樣）。
• 迷宮通常通道較長，容易解決。

隨機細胞（隨機原始演算法）：

• 每次從清單中隨機挑選一個儲存格。
• 創建一個分佈更均勻、路徑複雜且蜿蜒的迷宮。
• 長廊減少，分支增加。

最老的單元（類似隊列的行為）：

• 始終選擇清單中最舊的儲存格。
• 產生分佈較均勻的迷宮，類似廣度優先搜尋模式。
• 短而茂密的通道，連接緊密。
• （這是此處實現的版本）

混合方法：

結合針對不同迷宮特徵的策略。例如：

• 90％ 最新，10％ 隨機：看起來大部分像遞歸回溯迷宮，但偶爾會有分支打破長廊。
• 50％ 最新，50％ 最舊：平衡長廊與灌木叢生長。