埃勒算法迷宫生成器

埃勒算法是一种迷宫生成算法，它采用逐行生成的方式，高效地生成完美迷宫（没有环路且任意两点之间只有一条路径的迷宫）。它生成的迷宫与克鲁斯卡尔算法类似，但它每次只生成一行，无需将整个迷宫存储在内存中。这使得它非常适合在资源有限的系统上生成超大型迷宫，以及用于程序化内容生成。

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

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

关于埃勒算法

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

该算法以其高效的逐行迷宫生成方式而著称，使其成为生成无限迷宫或实时迷宫的理想选择。它在程序化内容生成和迷宫生成文献中被广泛引用，但我尚未找到详细介绍其原始发表信息的原始资料。

埃勒算法如何生成迷宫

埃勒算法一次处理一行，维护并修改连接的单元格集合。它确保了连通性，同时避免了循环，并能高效地向下扩展迷宫。

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

步骤 1：初始化第一行

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

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

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

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

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

步骤 4：移至下一行

• 将相同的集合 ID 分配给下面的相应单元格，从而延续垂直连接。
• 为所有未分配的单元格分配新的集合 ID。

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

• 继续逐行处理。

步骤 6：处理最后一行

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

进一步阅读

如果您喜欢这篇文章，您可能还会喜欢这些建议：

• 威尔逊算法迷宫生成器
• 狩猎与杀戮迷宫生成器
• 递归回溯迷宫生成器