威爾遜演算法迷宮生成器

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

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

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

關於威爾遜演算法

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

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

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

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

步驟 1：初始化

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

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

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

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

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

步驟4：重複，直到存取所有儲存格：

• 繼續選擇未訪問的單元格並進行隨機遊動，直到每個單元格都成為迷宮的一部分。