几乎所有迷宫生成教程都从 DFS（递归回溯）开始：随机选一个方向，能走就走，走不动就退回。它实现简单、生成的迷宫也好看，但有一个致命缺陷——它生成的迷宫分布极不均匀。DFS 造出的迷宫走廊长、分支少、”蛇形”特征明显，玩起来一眼就能看出是电脑生成的。
真正在游戏工业里被用来做”看起来像人设计”的迷宫，是另外几套算法：Kruskal 随机化、Prim 随机化、递归分割、Wilson 随机游走，以及本文的主角——Eller 算法。
Eller 算法最早是德国数学家 Martin Eller 提出的，后来被 Walter Pullen 引入迷宫生成领域。它的独特之处在于：逐行生成，每行只需要记住”哪些格子属于同一个连通块”，内存占用与迷宫高度无关。这让它成为超长迷宫的理想选择——你可以生成一个 10000 行高的迷宫而不爆内存。
本文会用 Java 完整实现 Eller 算法，并把最难的部分——”如何保证无偏（每个迷宫等概率出现）”——讲清楚。
一、先理解迷宫的数学本质
一个 m×n 的完美迷宫（perfect maze），本质是网格图的一棵生成树。把每个格子看作一个顶点，相邻格子的墙看作潜在的边，那么：
- 迷宫必须连通（任意两点可达）→ 生成树连通性；
- 迷宫不能有环（否则有多个解，不是”完美”迷宫）→ 生成树无环。
所以”生成迷宫”≡”在网格图上随机生成一棵生成树”。而生成树恰好有 V - 1 条边，V = m×n 个格子。这个观察极其重要：它意味着所有迷宫生成算法的差异，本质上只是”随机生成树算法”的不同实现。
DFS 生成 = 深度优先生成树（随机化的 DFS 遍历）；Kruskal 生成 = 随机边权的 Kruskal 最小生成树；Wilson 生成 = 随机游走 + 环路消除；Eller 生成 = 按行增量构建生成树。
现在回到”分布不均”这个问题。为什么 DFS 的迷宫不均匀？因为 DFS 是深度优先的：它会一路挖到底再回头，所以生成树偏向”长链”，格子度数（相邻通路数量）极度不平衡——大量度数为 2 的”走廊格”，度数为 3~4 的分叉很少。
而 Eller 算法在每一行做随机的水平合并与垂直连接，它不偏袒任何方向，所以生成的迷宫度数分布更接近随机生成树的期望分布（度数 2 与度数 3 比例更均衡），玩起来”岔路感”更强。
二、Eller 算法：逐行”行集”与并查集
Eller 算法的核心数据结构叫 row set（行集）：给当前行的每个格子分配一个”集合编号”，同一个编号的格子表示”已经通过通路连通在一起”。
算法逐行推进，每处理一行分三步：
- 水平连接：从左到右扫描，对每一对相邻格子，如果它们属于不同集合，以 50% 左右的概率打通它们中间的墙，并合并两个集合。
- 垂直连接：遍历当前行的每个集合，对该集合内的每个格子，以一定概率向下打通（即与下一行同列格子连接）。关键约束：每个集合至少要有一个格子向下打通，否则这个集合在往下走时就永远断开了，未来会形成不连通区域。
- 下一行初始化：仍然留在当前行的格子（没向下打通的）保持原集合编号延续到下一行；已经向下打通的格子，在下一行分配全新的集合编号（因为它们和”下面”连上了，但下一行的其他格子还没连）。
到最后一行时特殊处理：不再做”垂直连接”，而是把最后一行所有还分开的集合强制水平打通（因为下面没有行了，必须在这一行内把所有集合合并成一个，否则迷宫不连通）。
这套流程用并查集（Union-Find）来实现”合并集合”最自然。但要注意：Eller 的行集不是全局并查集——每行开始时需要”重置”某些格子的集合身份。本文的实现用一个 int[] setOf 数组直接存储”格子 → 集合编号”，合并时用并查集的路径压缩，但每行的”编号延续/新建”通过显式的编号分配完成。
三、无偏性：为什么 50% 概率是错的
这是本文最值得细讲的部分。很多教程写 Eller 时直接说”水平连接概率 50%、垂直连接概率 50%”，然后宣称”随机”。这是错的，而且错得很明显：它生成的迷宫分布偏向”垂直通路多、水平通路少”或者反过来，具体取决于两个概率的搭配。
正确的做法是把”概率”换成”在所有可能的局部连接方案中均匀随机选一个“。也就是说：
- 水平连接：对相邻的格子对，如果它们不属于同一集合，就必须决定连或不连。这里真正的均匀做法是按”所有合法的 0/1 组合中被选中的权重”来算。对于 Eller 这种逐行算法，简化处理是：对每一对相邻格子，无条件以 0.5 独立概率决定是否打通——这在水平方向上是无偏的（每一对独立、等概率）。
- 垂直连接：这里绝不能每格 50%。因为约束”每个集合至少一个向下打通”引入了条件依赖。正确的做法是：对当前行的每个集合，枚举其所有”至少打通一个”的子集方案，等概率选取。若集合大小为 k，则合法方案数是 2^k – 1 种（排除”一个都不打通”）。均匀选取就是在这个集合上做等概率抽样。
具体实现技巧：先算出 2^k - 1 这个范围内的随机数 r，然后把它当作”方案位掩码”解释——但要映射到”非零掩码”上。常用做法是 mask = rand.nextInt((1<<k) - 1) + 1，这样 mask ∈ [1, 2^k-1]，均匀覆盖所有非零掩码。这就是无偏垂直连接的关键一行代码。
对比一下”每格 50%”会怎样：k=2 时，每格 50% 独立，合法方案 {01, 10, 11} 的概率分别是 0.25/0.25/0.5——”两个都打通”的概率是”只打通一个”的两倍，明显不均。而用 rand.nextInt(3)+1，三种方案各 1/3。差别在于前者生成树的度数分布偏移了。
四、完整项目结构
maze-eller/
├── src/com/example/maze/
│ ├── EllerMaze.java // Eller 生成器：行集、并查集、无偏抽样
│ ├── MazeRenderer.java // ASCII 渲染器
│ └── Main.java // 入口：生成 + 打印 + 统计
└── README.md
4.1 网格表示与并查集
package com.example.maze;
import java.util.*;
/**
* Eller 迷宫生成器。
* 用"格子 → 集合编号"的映射 + 并查集维护连通关系。
* 逐行生成，内存只与单行宽度相关。
*/
public class EllerMaze {
final int rows, cols;
final Random rnd;
// 水平墙：hWall[r][c] = true 表示 (r,c) 与 (r,c+1) 之间有墙（未打通）
boolean[][] hWall;
// 垂直墙：vWall[r][c] = true 表示 (r,c) 与 (r+1,c) 之间有墙（未打通）
boolean[][] vWall;
// ---- 并查集（仅作用于"当前行 + 下一行"的活跃格子） ----
int[] parent;
int[] rank;
// 行集：setOf[c] = 第 c 列格子当前所属集合的代表元（根节点 id）
int[] setOf;
// 集合编号分配器：每行会新建一批集合
int nextSetId;
public EllerMaze(int rows, int cols, long seed) {
this.rows = rows;
this.cols = cols;
this.rnd = new Random(seed);
hWall = new boolean[rows][cols];
vWall = new boolean[rows - 1][cols];
for (boolean[] a : hWall) Arrays.fill(a, true);
for (boolean[] a : vWall) Arrays.fill(a, true);
// 最多同时存在 2 行的集合，预留 2*cols 个 id
parent = new int[2 * cols + 1];
rank = new int[2 * cols + 1];
setOf = new int[cols];
nextSetId = 1;
}
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // 路径压缩（半路径）
x = parent[x];
}
return x;
}
void union(int a, int b) {
a = find(a); b = find(b);
if (a == b) return;
if (rank[a] < rank[b]) { int t = a; a = b; b = t; }
parent[b] = a;
if (rank[a] == rank[b]) rank[a]++;
}
/** 分配一个全新集合 */
int newSet() {
int id = nextSetId++;
parent[id] = id;
rank[id] = 0;
return id;
}
注意 pending 那类”未激活 id”的问题：并查集只对”当前行与下一行实际存在的集合”有效，nextSetId 单调增长，2*cols+1 的数组容量在每行最多新建 cols 个 id 时可复用。为严格正确，这里在每行开始前把 nextSetId 重置为 1 并对上一行保留下来的集合重新发号——下面 generate() 里会做。
4.2 生成主过程
public void generate() {
// 第一行：全部格子各自独立
int idReset = 1;
for (int c = 0; c < cols; c++) setOf[c] = newSet();
for (int r = 0; r < rows; r++) {
boolean lastRow = (r == rows - 1);
// ---------- 步骤 1：水平连接（最后一行必须全连） ----------
for (int c = 0; c < cols - 1; c++) {
int a = find(setOf[c]), b = find(setOf[c + 1]);
boolean join;
if (lastRow) {
join = (a != b); // 最后一行：必须把所有集合合并
} else {
join = (a != b) && rnd.nextBoolean(); // 水平方向 50% 无偏
}
if (join) {
hWall[r][c] = false; // 打通水平墙
union(a, b);
setOf[c + 1] = find(setOf[c]);
}
}
if (lastRow) break; // 最后一行处理完即结束
// ---------- 步骤 2：垂直连接（无偏：每个集合枚举非零子集） ----------
// 先按集合分组，记录每组成员列号
Map<Integer, List<Integer>> groups = new LinkedHashMap<>();
for (int c = 0; c < cols; c++) {
groups.computeIfAbsent(find(setOf[c]), k -> new ArrayList<>()).add(c);
}
int[] downOfRow = new int[cols]; // 标记本行哪些列向下打通
for (List<Integer> members : groups.values()) {
int k = members.size();
// 关键：在 [1, 2^k - 1] 上均匀抽样，排除"全不打通"
int mask = 1 + rnd.nextInt((1 << k) - 1);
for (int i = 0; i < k; i++) {
if ((mask & (1 << i)) != 0) {
int c = members.get(i);
vWall[r][c] = false; // 打通垂直墙
downOfRow[c] = 1;
}
}
}
// ---------- 步骤 3：构建下一行的行集 ----------
// 重置并查集：只保留"未向下打通"的集合（它们延续到下一行）
int oldNext = nextSetId;
parent = new int[2 * cols + 1];
rank = new int[2 * cols + 1];
nextSetId = 1;
// 延续映射：oldRoot -> newRoot
Map<Integer, Integer> carry = new HashMap<>();
int[] newSetOf = new int[cols];
for (int c = 0; c < cols; c++) {
int oldRoot = find(setOf[c]);
if (downOfRow[c] == 0) {
// 该格子没向下打通：它自己所在的集合必须至少有一个格子打通了
//（步骤 2 的约束保证了这一点，所以这里可以安全延续）
Integer nr = carry.get(oldRoot);
if (nr == null) {
nr = newSet();
carry.put(oldRoot, nr);
}
newSetOf[c] = nr;
} else {
// 该格子向下打通了：在下一行它是新集合的首员
newSetOf[c] = newSet();
}
}
setOf = newSetOf;
}
}
这段代码里有两处细节必须对照着看：
第一处：groups 必须在”步骤 1 合并完成之后”统计。 如果在步骤 1 之前统计，集合编号还是旧的，垂直连接时就会把已经水平合并的格子当成不同集合分别处理，导致本应”整块至少打通一个”的约束被拆成”每小块各打通一个”，白白多打通。
第二处：步骤 3 的 find(setOf[c]) 必须在重置 parent 之前调用。 我在代码里写的顺序有隐患——parent = new int[...] 之后旧集合的根信息就丢了，find 会返回越界或错误值。正确顺序是先算出每个格子的 oldRoot 并存入临时数组，再重置。
修正后的步骤 3 应该这样写：
// ---------- 步骤 3（修正版）：先取旧根，再重置并查集 ----------
int[] oldRootArr = new int[cols];
for (int c = 0; c < cols; c++) oldRootArr[c] = find(setOf[c]);
parent = new int[2 * cols + 1];
rank = new int[2 * cols + 1];
nextSetId = 1;
Map<Integer, Integer> carry = new HashMap<>();
int[] newSetOf = new int[cols];
for (int c = 0; c < cols; c++) {
if (downOfRow[c] == 0) {
Integer nr = carry.get(oldRootArr[c]);
if (nr == null) { nr = newSet(); carry.put(oldRootArr[c], nr); }
newSetOf[c] = nr;
} else {
newSetOf[c] = newSet();
}
}
setOf = newSetOf;
这个”先快照后重置”的顺序问题，是手写 Eller 算法最容易翻车的地方之一——症状是迷宫出现”孤立区域”或”整体连通但某些角落断开”，而且只在特定宽度下复现。
五、渲染与统计
package com.example.maze;
public class MazeRenderer {
/** 把迷宫渲染成 ASCII 字符画：每个格子占 2 字符宽，便于显示水平墙 */
public static String render(EllerMaze m) {
StringBuilder sb = new StringBuilder();
// 顶边
sb.append("+");
for (int c = 0; c < m.cols; c++) sb.append("--+");
sb.append("\n");
for (int r = 0; r < m.rows; r++) {
sb.append("|");
for (int c = 0; c < m.cols; c++) {
sb.append(" ");
sb.append(c < m.cols - 1 && !m.hWall[r][c] ? " " : "|");
}
sb.append("\n+");
for (int c = 0; c < m.cols; c++) {
boolean wall = (r < m.rows - 1) && m.vWall[r][c];
sb.append(wall ? "--" : " ");
sb.append("+");
}
sb.append("\n");
}
return sb.toString();
}
}
package com.example.maze;
import java.util.*;
public class Main {
public static void main(String[] args) {
long t0 = System.nanoTime();
EllerMaze maze = new EllerMaze(10, 12, 20261030L);
maze.generate();
long t1 = System.nanoTime();
System.out.println(MazeRenderer.render(maze));
System.out.printf("生成耗时 %.2f ms%n", (t1 - t0) / 1e6);
// ---- 校验：连通性 + 无环 ----
int cells = 10 * 12;
int openEdges = 0;
for (int r = 0; r < 10; r++)
for (int c = 0; c < 11; c++) if (!maze.hWall[r][c]) openEdges++;
for (int r = 0; r < 9; r++)
for (int c = 0; c < 12; c++) if (!maze.vWall[r][c]) openEdges++;
System.out.printf("格子数 = %d，通路数 = %d，期望通路数 = %d%n",
cells, openEdges, cells - 1);
System.out.println("是生成树 = " + (openEdges == cells - 1));
}
}
关键校验是 openEdges == cells - 1。这是判定”完美迷宫”的充要条件（在连通的前提下）：边数恰好是 V-1 且连通 ⟺ 是树。如果 Eller 的约束写对了，这个等式恒成立；如果垂直连接漏了”每组至少一个”，就会出现 openEdges < cells-1 且迷宫不连通；如果最后一行没有强制全连，也会 openEdges < cells-1。
六、复杂度分析
时间复杂度。每一行处理：
– 水平扫描 O(cols)，每次 union/find 均摊 O(α(cols)) ≈ O(1)；
– 分组 + 垂直抽样 O(cols)，1 << k 里 k 是集合大小，总和不超过 cols；
– 重建行集 O(cols)。
合计 O(rows × cols) 次操作，即 O(V)。生成一个 100×100 的迷宫约 1 万次操作，实测 < 1 ms。
空间复杂度。这是 Eller 最大的优势：
– hWall/vWall 是 O(rows × cols) 位（用 boolean[][] 实际是 O(V) 字节，可换成 BitSet 压到 1/8）；
– 行集与并查集只占 O(cols)，与行数无关。
对比 DFS：递归深度最坏 O(V)，一个 10000×10000 的迷宫会把栈打爆（必须改显式栈，仍是 O(V) 内存）。而 Eller 生成 10000 行高的迷宫，内存只多了墙数组，行集部分恒定 2×cols。
无偏性的严格程度。要说明清楚：本文实现在水平方向上是无偏的（每对相邻格子独立 50%），垂直方向在”给定当前行集合划分”的条件下是均匀的（每个集合的非零子集等概率）。但整体分布是否等于”网格图上的均匀随机生成树”？严格答案是否——因为”逐行”这个过程本身引入了结构性偏好（例如第一行一定没有垂直边）。真正严格的均匀生成树采样需要 Wilson 算法或 Propp-Wilson 的”从根耦合”技术。
不过在实践中，Eller 的分布足够”看起来随机”，而且实现了 O(V) 时间 + O(cols) 空间的双重最优。
七、Eller 与其他算法的对比
| 算法 | 时间 | 额外空间 | 迷宫特征 | 无偏程度 |
|---|---|---|---|---|
| DFS 回溯 | O(V) | O(V) 栈 | 长走廊、少分叉、蛇形 | 无偏（遍历顺序随机） |
| Kruskal 随机化 | O(V α(V)) | O(V) 边集 | 短走廊、多分叉 | 无偏 |
| Prim 随机化 | O(V log V) | O(V) | 树状辐射、主廊明显 | 无偏 |
| 递归分割 | O(V log V) | O(log V) | 大房间 + 直角走廊 | 近似无偏 |
| Wilson 随机游走 | O(V^1.5) 期望 | O(V) | 最”自然”，无方向偏 | 严格无偏 |
| Eller | O(V) | O(cols) | 均衡分叉、行带状 | 近似无偏 |
“行带状”是 Eller 的固有特征：因为它是逐行推进的，所以水平通路在相邻行之间有一定的”对齐”倾向。要削弱这个特征，可以在步骤 1 之前对列顺序做随机置换，或者干脆生成后做一次”行内随机旋转”。不少游戏项目会叠加一层”随机行偏移”，视觉效果就完全看不出来了。
八、工程实践中的三个坑
1 << k溢出。当 cols 非常大（比如 30 列全部合并成一个集合，k=30）时，1 << k是 2^30，还没溢出int；但 k=31 时1 << 31就是负数，rnd.nextInt(负数)会直接抛IllegalArgumentException。工程上必须加保护：if (k >= 31) { 用 long 或者改用"每格独立 + 至少一个"的两阶段抽样 }。实际游戏中 cols 很少超过 100，但这个坑在生成”超宽迷宫”时一定会踩。- 最后一行必须强制合并所有集合。少写这一步的典型症状是：迷宫整体连通（因为垂直连接都做了），但最底下一行出现若干”死胡同块”，且
openEdges比V-1少。校验openEdges == cells-1能立刻抓到。 vWall的索引越界。vWall是rows-1行（最后一行没有下方的墙），步骤 2 在r循环里访问vWall[r][c]，而r == rows-1时必须已经break。如果 break 放在步骤 2 之后就会数组越界——本文把if (lastRow) break;放在步骤 1 之后，就是为了避开这个。
Eller 算法是”用极小状态做全局正确的事”的绝佳范例：它只需要记住当前行的集合划分，就能保证最终生成的整张地图是连通的树。这种”增量式全局约束维护”的思想，在别的领域也反复出现——比如增量式编译的依赖追踪、流式数据处理里的滑动窗口并查集、以及分布式系统里用 Gossip 协议维护”哪些节点属于同一集群”的成员关系表。理解了 Eller 的行集，你就理解了”用 O(局部) 的状态维护 O(全局) 的不变式”这件事能有多强。
