埃勒演算法迷宮生成器

埃勒演算法是一種迷宮生成演算法，它採用逐行生成的方式，高效地產生完美迷宮（沒有環路且任兩點之間只有一條路徑的迷宮）。它產生的迷宮與克魯斯卡爾演算法類似，但它每次只產生一行，無需將整個迷宮儲存在記憶體中。這使得它非常適合在資源有限的系統上產生超大型迷宮，以及用於程式化內容生成。

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

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

關於埃勒演算法

埃勒演算法是由大衛·埃勒提出的。

該演算法以其高效的逐行迷宮生成方式而著稱，使其成為生成無限迷宮或即時迷宮的理想選擇。它在程序化內容生成和迷宮生成文獻中被廣泛引用，但我尚未找到詳細介紹其原始發表資訊的原始資料。

埃勒演算法如何產生迷宮

埃勒演算法一次處理一行，維護並修改連接的單元格集合。它確保了連通性，同時避免了循環，並能有效率地向下擴展迷宮。

理論上，它可以用來產生無限的迷宮，但是為了確保生成的迷宮實際上是可解的，需要在某個時候切換到「最後一行」邏輯來完成迷宮。

步驟 1：初始化第一行

• 為該行中的每個儲存格指派一個唯一的集合 ID。

步驟 2：水平連接一些相鄰單元格

• 隨機合併相鄰單元格，將它們設定為相同的集合 ID。這樣可以確保存在水平通道。

步驟 3：建立與下一行的垂直連接

• 對於行中出現的每個集合，至少有一個單元格必須向下連接（以確保連通性）。
• 從每組儲存格中隨機選擇一個或多個儲存格連接到下一行。

步驟 4：移至下一行

• 將相同的集合 ID 分配給下面的相應單元格，從而延續垂直連接。
• 為所有未指派的儲存格指派新的集合 ID。

步驟5：重複步驟2-4，直到到達最後一行。

• 繼續逐行處理。

步驟 6：處理最後一行

• 合併所有剩餘的獨立集合，確保最後一行中的所有單元格都屬於同一集合。

進一步閱讀

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

• 遞歸回溯迷宮生成器
• 威爾遜演算法迷宮生成器
• 狩獵與殺戮迷宮生成器