Miklix

生長樹演算法迷宮生成器

已發佈: 2025年2月16日 晚上9:37:27 [UTC]
最後更新: 2025年3月6日 上午9:57:28 [UTC]

迷宮生成器使用生長樹演算法來創建完美的迷宮。該演算法傾向於產生與 Hunt and Kill 演算法類似的迷宮,但典型解決方案略有不同。

該頁面是由英語機器翻譯而來的,以便盡可能多的人可以訪問。不幸的是,機器翻譯還不是一項完善的技術,因此可能會出現錯誤。如果您願意,可以在這裡查看原始英文版本:

Growing Tree Algorithm Maze Generator

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

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

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


生成新迷宮








關於生長樹演算法

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

生長樹演算法的工作原理

步驟 1:初始化

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

第 2 步:迷宮生成循環

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

步驟 3:終止

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

小區選擇策略(演算法的彈性)

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

最新單元(類似堆疊的行為)-遞歸回溯器:

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

隨機細胞(隨機原始演算法):

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

最老的單元(類似隊列的行為):

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

混合方法:

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

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

分享至 Bluesky在 Facebook 分享在 LinkedIn 分享在 Tumblr 上分享分享至 X在 LinkedIn 分享固定在 Pinterest 上

米克爾·邦·克里斯滕森

關於作者

米克爾·邦·克里斯滕森
麥可 是 miklix.com 的創建者和所有者。他有超過 20 年的專業電腦程式設計師/軟體開發人員經驗,目前全職受僱於一家歐洲大型 IT 公司。不寫部落格時,他會將業餘時間花在各種各樣的興趣、愛好和活動上,這在一定程度上反映在本網站所涵蓋的主題的多樣性上。