埃勒算法迷宫生成器

Eller 算法是一种迷宫生成算法，它使用逐行方法高效生成完美迷宫（没有环路且任意两点之间只有一条路径的迷宫）。它生成的迷宫类似于 Kruskal 算法，但它每次只生成一行，无需将整个迷宫存储在内存中。这使得它适用于在非常有限的系统上生成非常大的迷宫以及程序内容生成。

完美迷宫是指从迷宫中的任何一点到其他任何一点都只有一条路径的迷宫。这意味着你不会兜圈子，但你会经常遇到死胡同，不得不掉头回去。

这里生成的迷宫地图包括一个没有起点和终点位置的默认版本，因此您可以自行决定起点和终点位置：从迷宫中的任何一点到其他任何一点都有解法。如果你想获得灵感，可以启用建议的起点和终点位置，甚至可以查看两者之间的解法。

关于埃勒算法

Eller 算法由 David Eller 提出。

该算法以其高效的逐行迷宫生成方法而闻名，使其成为无限迷宫或实时生成的迷宫的理想选择。它在程序内容生成和迷宫生成文献中被广泛引用，但我无法找到详细介绍其原始出版物的主要来源。

埃勒算法如何生成迷宫

Eller 算法每次处理一行，维护和修改连通单元集。该算法在避免循环的同时确保连通性，并有效地向下延伸迷宫。

理论上它可以用于生成无限的迷宫，但是为了确保生成的迷宫实际上是可解的，需要在某个时候切换到“最后一行”逻辑来完成迷宫。

步骤 1：初始化第一行

• 为行中的每个单元格分配一个唯一的集合 ID。

步骤 2：水平连接一些相邻单元格

• 通过将相邻单元格设置为相同的集合 ID 来随机合并它们。这确保了存在水平通道。

步骤 3：创建到下一行的垂直连接

• 对于行中出现的每个集合，至少一个单元格必须向下连接（以确保连接性）。
• 从每组中随机选择一个或多个单元格连接到下一行。

步骤 4：移至下一行

• 通过为下方相应的单元格分配相同的集合 ID 来延续垂直连接。
• 为任何未分配的单元格分配新的集合 ID。

步骤 5：重复步骤 2-4，直到到达最后一行

• 继续逐行处理。

步骤 6：处理最后一行

• 通过合并所有剩余的单独集合，确保最后一行的所有单元格属于同一集合。