遞歸回溯迷宮生成器

遞歸回溯演算法其實是一種通用的深度優先搜尋。當用於迷宮生成時，它會稍加修改以隨機選擇路徑，而如果用於實際搜尋目的，通常只會按線性順序搜尋每個層級。它往往會產生具有長而蜿蜒的走廊和非常長而曲折的解決方案的迷宮。

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

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

遞歸回溯演算法是一種深度優先搜尋方法，用於產生完美迷宮（沒有循環且任兩點之間只有一條路徑的迷宮）。它簡單、高效，並能創造出具有長而蜿蜒的走廊的視覺吸引力十足的迷宮。

儘管它的名字如此，但它並不一定必須使用遞歸來實現。它通常採用 LIFO 佇列（即堆疊）的迭代方法實作。對於非常大的迷宮，使用遞歸更容易導致呼叫堆疊溢出，這取決於程式語言和可用記憶體。 LIFO 佇列可以更容易地適應處理大量數據，甚至在可用記憶體不足時將佇列保存在磁碟或資料庫中。

工作原理

此演算法採用基於堆疊的深度優先搜尋方法進行操作。以下是詳細步驟：

1. 選擇一個起始儲存格並將其標記為已存取。
2. 當存在未存取的儲存格時：
   • 查看尚未造訪過的鄰近儲存格。
   • 如果至少存在一個未訪問的鄰居：
     • 隨機選擇其中一個未訪問的鄰居。
     • 移除目前儲存格和所選鄰居之間的牆壁。
     • 移動到選定的鄰居並將其標記為已存取。
     • 將目前單元格推入堆疊。
   • 如果不存在未訪問的鄰居：
     • 透過從堆疊中彈出最後一個單元格來進行回溯。
3. 繼續此過程直到堆疊為空。

關於這個演算法的一個有趣的事實是，它既可以作為迷宮生成器，也可以作為迷宮解算器。如果您在已經生成的迷宮上運行它並在到達決定的終點時停止，則堆疊將包含迷宮的解決方案。

實際上，我在這個網站上使用了兩個版本的該演算法：一個基於 LIFO 隊列的版本，用於在此頁面上生成迷宮；另一個基於遞歸的版本，用於解決迷宮，還有由其他演算法生成的迷宮（這就是製作帶有解決方案的地圖的方式）。擁有兩個不同版本只是為了運動，因為我是一個發現它很有趣的書呆子，任何一個都可以用於兩者;-)