生長樹演算法迷宮生成器

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

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

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

關於生長樹演算法

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

樹形生長演算法的工作原理

步驟 1：初始化

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

步驟 2：迷宮生成循環

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

步驟三：終止

• 當清單中沒有更多單元格時，演算法結束，這意味著整個迷宮已被雕刻完畢。

細胞選擇策略（演算法的彈性）

生長樹演算法的關鍵特徵在於如何選擇接下來要處理的單元格。這個選擇會大大影響迷宮的外觀：

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

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

隨機單元格（隨機化Prim演算法）：

• 每次從清單中隨機選擇一個儲存格。
• 形成一個分佈較均勻、路徑複雜交錯的迷宮。
• 減少長走廊，增加分支道路。

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

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

混合方法：

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

• 90% 最新，10% 隨機：看起來主要像遞歸回溯迷宮，但偶爾會有分支打破長長的走廊。
• 50% 最新，50% 最舊：平衡長廊與茂密植被。

進一步閱讀

如果您喜歡這篇文章，您可能也會喜歡這些建議：

• 埃勒演算法迷宮生成器
• 遞歸回溯迷宮生成器
• 威爾遜演算法迷宮生成器