遞歸回溯迷宮生成器

遞歸回溯演算法其實是一種通用的深度優先搜尋演算法。當用於迷宮生成時，它會稍作修改，隨機選擇路徑；而用於實際搜尋時，通常會按線性順序逐層搜尋。這種演算法往往會產生具有長而蜿蜒的走廊以及非常長且曲折的解的迷宮。

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

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

遞歸回溯演算法是一種深度優先搜尋方法，用於產生完美迷宮（無環且任兩點之間只有一條路徑的迷宮）。它簡單高效，能夠生成具有蜿蜒長廊且視覺效果極佳的迷宮。

儘管名稱中帶有“遞歸”二字，但迷宮演算法並非必須使用遞歸來實現。它通常採用迭代的方式，並使用後進先出（LIFO）佇列（即堆疊）來實現。對於非常大的迷宮，使用遞歸更容易導致呼叫堆疊溢出，這取決於程式語言和可用記憶體。 LIFO佇列更容易適應處理大量數據，即使記憶體不足，也可以將佇列保存在磁碟或資料庫中。

工作原理

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

1. 選擇一個起始儲存格並將其標記為已存取。
2. 當存在未存取的儲存格時：查看尚未存取的相鄰儲存格。如果至少存在一個未存取的相鄰儲存格：隨機選取一個未存取的相鄰儲存格。移除目前儲存格與所選相鄰單元格之間的隔間牆。移動到所選相鄰單元格並將其標記為已存取。將目前單元格壓入堆疊中。如果不存在未存取的相鄰單元格：回溯，從堆疊中彈出最後一個單元格。
3. 重複此過程，直到堆疊為空。

這個演算法的一個有趣之處在於它既可以作為迷宮生成器，也可以作為迷宮解算器。如果你在一個已經生成的迷宮上運行它，並在到達預設的終點時停止，那麼堆疊中就會包含迷宮的解。

實際上，我在這個網站上使用了兩個版本的演算法：一個是基於後進先出隊列的演算法，用於生成本頁上的迷宮；另一個是基於遞歸的演算法，用於求解迷宮，以及其他演算法生成的迷宮（這就是帶有解的地圖的生成方式）。使用兩個不同的版本純粹是為了好玩，因為我是一個技術宅，覺得這很有趣，其實任何一個版本都足以滿足需求 ;-)

進一步閱讀

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

• Kruskal 演算法迷宮生成器
• 狩獵與殺戮迷宮生成器
• 生長樹演算法迷宮生成器