威爾遜演算法迷宮生成器

威爾遜演算法是一種循環消除隨機遊走方法，它產生均勻生成樹用於迷宮生成。這意味著給定大小的所有可能迷宮的生成機率均等，因此它是一種無偏的迷宮生成技術。威爾遜演算法可以看作是奧爾德斯-布羅德演算法的改進版本，因為它生成的迷宮具有相同的特徵，但運行速度更快，所以我在這裡沒有實現奧爾德斯-布羅德演算法。

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

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

關於威爾遜演算法

威爾遜演算法（Wilson's algorithm）是一種利用循環消除隨機牆生成均勻生成樹的演算法，由大衛·布魯斯·威爾遜（David Bruce Wilson）創建。

威爾遜最初在 1996 年研究機率論中的隨機生成樹和馬可夫鏈時提出了這種演算法。儘管他的研究主要集中在數學和統計物理領域，但由於演算法能夠產生完全均勻的迷宮，因此已被廣泛應用於迷宮生成。

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

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

步驟 1：初始化

• 首先畫一個佈滿牆壁的格子。
• 定義所有可能的通道單元格清單。

步驟 2：選取一個隨機起始儲存格

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

步驟 3：循環消除的隨機遊走

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

步驟 4：重複此步驟直至訪問所有細胞：

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

進一步閱讀

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

• 生長樹演算法迷宮生成器
• 遞歸回溯迷宮生成器
• 狩獵與殺戮迷宮生成器