生長樹演算法迷宮生成器
已發佈: 2025年2月16日 晚上9:37:27 [UTC]
最後更新: 2025年3月6日 上午9:57:28 [UTC]
該頁面是由英語機器翻譯而來的,以便盡可能多的人可以訪問。不幸的是,機器翻譯還不是一項完善的技術,因此可能會出現錯誤。如果您願意,可以在這裡查看原始英文版本:
Growing Tree Algorithm Maze Generator
Growing Tree Algorithm Maze Generator
生長樹演算法很有趣,因為它可以模擬其他幾種演算法的行為,這取決於在生成過程中如何選擇下一個單元格。本頁的實作採用廣度優先、類似隊列的方法。
完美迷宮是指從迷宮中的任意一點到另一點都只有一條路徑的迷宮。這意味著你不會最終陷入繞圈的境地,但你會經常遇到死胡同,迫使你轉身返回。
這裡產生的迷宮地圖包含一個預設版本,沒有任何起點和終點位置,因此您可以自己決定:從迷宮中的任何點到任何其他點都會有一個解決方案。如果您想要靈感,您可以啟用建議的開始和結束位置 - 甚至可以看到兩者之間的解決方案。
關於生長樹演算法
生長樹演算法是一種靈活且強大的生成完美迷宮的方法。這個演算法很有趣,因為它可以模擬其他幾種迷宮生成演算法的行為,例如 Prim 演算法、遞歸回溯和遞歸除法,這取決於您如何選擇下一個要處理的單元格。
生長樹演算法的工作原理
步驟 1:初始化
- 從未訪問過的單元格網格開始。
- 選擇一個隨機的起始儲存格並將其新增至清單中。
第 2 步:迷宮生成循環
- 當儲存格清單不為空時:
- 根據特定策略從清單中選擇一個儲存格(如下所述)。
- 從選定的單元格開闢一條通道到其未訪問的鄰居之一(隨機選擇)。
- 將鄰居添加到列表中,因為它現在是迷宮的一部分。
- 如果選定的儲存格沒有未存取的鄰居,則將其從清單中刪除。
步驟 3:終止
- 當清單中不再有單元格時,演算法結束,這表示整個迷宮已被雕刻。
小區選擇策略(演算法的彈性)
生長樹演算法的定義特徵是如何選擇下一步要處理的單元格。這個選擇極大地影響了迷宮的外觀:
最新單元(類似堆疊的行為)-遞歸回溯器:
- 始終選擇最近新增的儲存格。
- 產生長而曲折的走廊,其中有許多死胡同(就像深度優先搜索迷宮一樣)。
- 迷宮通常通道較長,容易解決。
隨機細胞(隨機原始演算法):
- 每次從清單中隨機挑選一個儲存格。
- 創建一個分佈更均勻、路徑複雜且蜿蜒的迷宮。
- 長廊減少,分支增加。
最老的單元(類似隊列的行為):
- 始終選擇清單中最舊的儲存格。
- 產生分佈較均勻的迷宮,類似廣度優先搜尋模式。
- 短而茂密的通道,連接緊密。
- (這是此處實現的版本)
混合方法:
結合針對不同迷宮特徵的策略。例如:
- 90% 最新,10% 隨機:看起來大部分像遞歸回溯迷宮,但偶爾會有分支打破長廊。
- 50% 最新,50% 最舊:平衡長廊與灌木叢生長。