Miklix

威爾遜演算法迷宮生成器

已發佈: 2025年2月16日 晚上7:34:56 [UTC]

迷宮生成器使用威爾遜演算法來創建完美的迷宮。該演算法以相同的機率產生給定大小的所有可能的迷宮,因此理論上可以產生許多混合佈局的迷宮,但由於較短走廊的迷宮的可能性比較長走廊的迷宮更大,因此您會更經常看到這些迷宮。

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

Wilson's Algorithm Maze Generator

Wilson 演算法是一種循環擦除隨機遊走方法,可產生均勻生成樹來創建迷宮。這意味著所有給定大小的可能迷宮都有同等的可能性被生成,使其成為一種無偏的迷宮生成技術。 Wilson 演算法可以被認為是 Aldous-Broder 演算法的改進版本,因為它產生具有相同特徵的迷宮,但運行速度更快,所以我沒有在這裡費心實現 Aldous-Broder 演算法。

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

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


生成新迷宮








關於威爾遜演算法

使用循環擦除隨機牆產生均勻生成樹的 Wilson 演算法由 David Bruce Wilson 創建。

Wilson 最初在 1996 年研究機率論中的隨機生成樹和馬可夫鏈時提出了該演算法。儘管他的工作主要在數學和統計物理學領域,但該演算法由於其能夠生成完美均勻的迷宮而被廣泛應用於迷宮生成。

威爾遜演算法如何產生迷宮

威爾遜演算法透過使用隨機遊走迭代地從未訪問的單元中開闢路徑,確保最終的迷宮完全連通而沒有任何循環。

步驟 1:初始化

  • 從佈滿牆壁的格子開始。
  • 定義所有可能的傳代細胞的清單。

第 2 步:選擇隨機起始儲存格

  • 選擇任意隨機儲存格並將其標記為已存取。這是迷宮生成過程中的起點。

步驟 3:循環擦除隨機遊走

  • 選擇一個未訪問的單元格並開始隨機遊走(朝隨機方向移動)。
  • 如果步行到達已經造訪過的儲存格,則刪除路徑中的所有循環。
  • 一旦步行連接到已訪問區域,就將路徑上的所有單元標記為已訪問。

步驟4:重複,直到存取所有儲存格

  • 繼續選擇未訪問的單元格並進行隨機遊動,直到每個單元格都成為迷宮的一部分。
分享至 Bluesky在 Facebook 分享在 LinkedIn 分享在 Tumblr 上分享分享至 X在 LinkedIn 分享固定在 Pinterest 上

米克爾·邦·克里斯滕森

關於作者

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