埃勒演算法迷宮生成器

Eller 演算法是一種迷宮生成演算法，它使用逐行方法有效地產生完美迷宮（沒有環路且任意兩點之間只有一條路徑的迷宮）。它產生的迷宮類似於 Kruskal 演算法，但它每次只產生一行，而不需要將整個迷宮儲存在記憶體中。這使得它對於在非常有限的系統上產生非常大的迷宮以及程式內容生成非常有用。

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

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

關於埃勒演算法

Eller 演算法由 David Eller 提出。

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

埃勒演算法如何產生迷宮

Eller 演算法每次處理一行，維護和修改連接單元格集。它在確保連通性的同時避免了循環，並有效地向下延伸迷宮。

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

步驟 1：初始化第一行

• 為行中的每個單元格指派一個唯一的集合 ID。

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

• 透過將相鄰單元格設定為相同的集合 ID 來隨機合併它們。這確保了有水平通道。

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

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

步驟 4：移至下一行

• 透過為下方對應的儲存格指派相同的集合 ID 來延續垂直連接。
• 為任何未指派的儲存格指派新的集合 ID。

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

• 繼續逐行處理。

步驟 6：處理最後一行

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