揭阳市网站建设_网站建设公司_CMS_seo优化

目录

1 引言：为什么“生成迷宫”不是画几堵墙那么简单

1.1 迷宫的“数学骨架”：图、生成树与可解性

1.2 “好迷宫”的工程指标：结构风格、偏置、性能与可控性

2 表示法与统一框架：先把“迷宫这件事”表示清楚

2.1 两种主流表示：格子墙（cell-walls）与像素栅格（odd-even grid）

2.2 一个可复用的 Python 迷宫骨架：可插拔算法、可视化、可复现

3 随机深度优先（递归回溯）：最常用、最“长走廊”的完美迷宫

3.1 从 DFS 到迷宫纹理：为什么它总爱“走到黑”

3.2 递归实现与显式栈实现：避免 Python 递归深度问题

4 随机 Prim：像“边界起火”一样扩张的迷宫生长

4.1 从最小生成树到迷宫：为什么它更“碎”、岔路更多

4.2 Python 实现：用“前沿边”而不是“前沿点”

5 随机 Kruskal：并查集驱动的“全局打乱后逐条连通”

5.1 生成树的另一条路：先把所有墙打乱，再决定拆不拆

5.2 并查集实现：路径压缩与按秩合并让大迷宫也能快

6 递归分割：先造房间再开门的“建筑师式”迷宫

6.1 它为什么看起来更“规整”：长直墙与强几何感

6.2 Python 实现：在 cell-walls 上做“加墙等价变换”

7 Sidewinder 与 Binary Tree：带偏置的极简算法与“可预测纹理”

7.1 偏置不是缺点：当你需要“方向性”与“可控风格”

7.2 Sidewinder：一行一行地“横向跑团”，偶尔往上打一个洞

7.3 Binary Tree：每格只在两个方向里选一个，形成“斜向树根”

8 Eller：只看一行也能生成无限高完美迷宫的“集合魔法”

8.1 为什么它值得学习：流式生成、线性复杂度与行级状态

8.2 Python 实现：可读性优先的 Eller（适合学习与改造）

9 Aldous–Broder 与 Wilson：走向“均匀生成树”的随机游走系算法

9.1 “无偏”到底是什么意思：均匀生成树与算法偏置

9.2 Aldous–Broder：最简单的均匀生成树，但常被吐槽“慢得令人痛苦”

9.3 Wilson：循环擦除随机游走（LERW），更快、更优雅

10 让算法变成“可用系统”：入口出口、加环、难度调参与验证

10.1 入口出口并不是“开两个洞”这么简单

10.2 从“完美迷宫”到“更像现实的迷宫”：加少量回路（braiding）

10.3 难度与风格调参：你真正能控制的变量是什么

11 把一切串起来：一个可运行示例与输出

11.1 最小示例：生成、开口、打印

12 结语：选择算法，其实是在选择“随机性的哲学”

本文提供了多种迷宫生成算法，大家在设计迷宫游戏时可以将其中一种算法交给Claude，然后就能设计出窗体化的迷宫游戏或网页游戏。这种比较小的游戏设计用Claude Haiku 4.5足够。

1 引言：为什么“生成迷宫”不是画几堵墙那么简单

1.1 迷宫的“数学骨架”：图、生成树与可解性

在程序里谈迷宫，最容易踩的坑就是把它当成“画图问题”：随机画几条墙、留几条通道，看起来像迷宫就行。可一旦你希望迷宫“必定可解”“难度可控”“风格稳定”“能复现同一随机种子”，甚至希望它满足“只有唯一解”的性质时，迷宫立刻就变成一个严格的图论构造问题。经典二维格子迷宫通常把每个房间（cell）当作图的节点，把相邻房间之间“可以打通的墙”当作边。你要做的事，等价于从这张候选边组成的连通图里挑出一部分边作为通道，让整张图保持连通，同时又不要出现让人绕晕的多条等价路线。所谓“完美迷宫（perfect maze）”，指任意两格之间恰好只有一条通路，这在图论里就是“生成树”：连通、无环、覆盖全部节点。很多迷宫生成算法本质上就是“随机生成树算法”的不同实现路线。(维基百科)

1.2 “好迷宫”的工程指标：结构风格、偏置、性能与可控性

同样是生成树，不同算法的迷宫观感会差很多：有的偏爱长走廊、分支少，像洞穴深处一条路走到黑；有的分叉密集、回头路多，像在树冠里穿梭；有的出现大段笔直隔墙，像建筑平面图；有的“无偏”（更严格地说是对生成树空间做均匀采样），让每一种可能的迷宫结构出现的概率相同，但代价是更慢、更难实现。Jamis Buck 的系列文章把这些算法当作“同一问题的不同审美答案”来讨论：递归回溯（深度优先）、Prim、Kruskal、Eller、Aldous–Broder、Wilson、递归分割、hunt-and-kill 等都各有“纹理”。(巴克博客) 你如果只把它们当作步骤列表，很快就会写出“能跑但难用”的代码；真正工程化的关键在于统一数据结构、统一接口、可视化验证、以及对随机性和偏置的认识。

2 表示法与统一框架：先把“迷宫这件事”表示清楚

2.1 两种主流表示：格子墙（cell-walls）与像素栅格（odd-even grid）

迷宫实现里最常见的两套表示法，各有利弊。第一种是“格子墙”模型：每个 cell 有四面墙（N/S/E/W），打通就是把相邻两格对应方向的墙置为打开。这种模型抽象层更高，算法表达自然，尤其适合 Wilson、Kruskal 这类“在 cell 图上做生成树”的算法。第二种是“像素栅格”模型：把最终输出当作由 0/1 组成的矩阵，1 表示路、0 表示墙，并用奇偶坐标把 cell 与墙分开（例如 cell 在奇数坐标，墙在偶数坐标）。这种模型非常利于打印、绘图与导出，也能让“挖墙”动作变成对矩阵的赋值。很多教学代码用 odd-even grid，就是因为它能把“拆墙”写成“把中间那一格也置 1”。这两套表示法并不冲突：工程上常见做法是内部用 cell-walls，输出时再渲染成矩阵或图像；或者内部直接用 odd-even grid，算法在奇数格上走、在偶数格上挖墙。

2.2 一个可复用的 Python 迷宫骨架：可插拔算法、可视化、可复现

下面给出一套偏工程化、但仍然易读的 Python 框架：用 cell-walls 表示迷宫；每种算法只负责“打开哪些墙”；最后统一渲染为字符画或 numpy 矩阵。注意：这不是“把所有算法写成一堆函数然后复制粘贴”，而是让算法实现只关注它们各自的核心逻辑，这样你扩展到六边形网格、三维迷宫、或加入“编织迷宫（weave）”时，改动会很小。

from __future__ import annotations from dataclasses import dataclass from typing import Dict, List, Optional, Tuple, Iterable import random Dir = Tuple[int, int] N, S, W, E = (0, -1), (0, 1), (-1, 0), (1, 0) DIRS: List[Dir] = [N, S, W, E] OPP: Dict[Dir, Dir] = {N: S, S: N, W: E, E: W} DIR_NAME: Dict[Dir, str] = {N: "N", S: "S", W: "W", E: "E"} @dataclass class Cell: x: int y: int # True=墙存在, False=墙被打通 walls: Dict[Dir, bool] def __init__(self, x: int, y: int): self.x = x self.y = y self.walls = {d: True for d in DIRS} class Maze: """ cell-walls 表示法：width*height 个 cell，每个 cell 有四面墙。 算法只负责调用 carve(a, b) 打通相邻 cell 之间的墙。 """ def __init__(self, width: int, height: int, seed: Optional[int] = None): if width <= 0 or height <= 0: raise ValueError("width/height must be positive") self.w = width self.h = height self.grid: List[List[Cell]] = [[Cell(x, y) for x in range(width)] for y in range(height)] self.rng = random.Random(seed) def cell(self, x: int, y: int) -> Cell: return self.grid[y][x] def in_bounds(self, x: int, y: int) -> bool: return 0 <= x < self.w and 0 <= y < self.h def neighbors(self, x: int, y: int) -> Iterable[Tuple[Dir, Cell]]: for d in DIRS: nx, ny = x + d[0], y + d[1] if self.in_bounds(nx, ny): yield d, self.cell(nx, ny) def carve(self, ax: int, ay: int, bx: int, by: int) -> None: """打通相邻两格之间的墙""" dx, dy = bx - ax, by - ay d = (dx, dy) if d not in DIRS: raise ValueError("cells are not adjacent") a = self.cell(ax, ay) b = self.cell(bx, by) a.walls[d] = False b.walls[OPP[d]] = False def to_ascii(self) -> str: """ 经典 ASCII 渲染：+---+ 框架。 输出尺寸约为 (2*h+1) 行。 """ lines: List[str] = [] # 顶边 lines.append("+" + "---+" * self.w) for y in range(self.h): # 中间行（竖墙） row1 = ["|"] for x in range(self.w): row1.append(" ") row1.append("|" if self.cell(x, y).walls[E] else " ") lines.append("".join(row1)) # 底边行（横墙） row2 = ["+"] for x in range(self.w): row2.append("---" if self.cell(x, y).walls[S] else " ") row2.append("+") lines.append("".join(row2)) return "\n".join(lines) def open_entrance_exit(self, entrance: Tuple[int,int], exit_: Tuple[int,int]) -> None: """ 在外边界开两个口。入口出口必须在边界上。 """ ex, ey = entrance ox, oy = exit_ for (x, y) in [entrance, exit_]: if not self.in_bounds(x, y): raise ValueError("entrance/exit out of bounds") if x not in (0, self.w - 1) and y not in (0, self.h - 1): raise ValueError("entrance/exit must be on boundary") # 入口开口 if ey == 0: self.cell(ex, ey).walls[N] = False elif ey == self.h - 1: self.cell(ex, ey).walls[S] = False elif ex == 0: self.cell(ex, ey).walls[W] = False else: self.cell(ex, ey).walls[E] = False # 出口开口 if oy == 0: self.cell(ox, oy).walls[N] = False elif oy == self.h - 1: self.cell(ox, oy).walls[S] = False elif ox == 0: self.cell(ox, oy).walls[W] = False else: self.cell(ox, oy).walls[E] = False

这套骨架背后最重要的思想是：你把“迷宫”定义为一个 cell 图，把“生成迷宫”定义为在这张图上选择边，最终得到一个生成树或近似生成树的子图。Wikipedia 的总结非常直接：迷宫生成常被视作随机生成树问题；若你想引入回路，也是在生成树基础上再添加一些边。(维基百科) 下面所有算法都会围绕carve()这一个动作展开，但每个算法选择“下一条 carve 的边”的策略完全不同，于是迷宫呈现出完全不同的纹理。

3 随机深度优先（递归回溯）：最常用、最“长走廊”的完美迷宫

3.1 从 DFS 到迷宫纹理：为什么它总爱“走到黑”

随机深度优先（randomized depth-first search）也叫递归回溯（recursive backtracker）。它的逻辑不是“同时在许多边界上扩张”，而是从一个起点出发，沿着随机挑选的未访问邻居不断深入，直到走进死胡同才回退；回退到某个仍有未访问邻居的分叉点时，再挑一条新路继续深入。因为它倾向于在同一条路径上尽可能走远，才会形成肉眼可见的“长走廊、分叉少”的风格。Wikipedia 对这种风格也有明确描述：DFS 生成的迷宫分支因子低、长通道多。(维基百科) Jamis Buck 也把它当作最容易上手、最常被人当作“默认迷宫生成法”的算法之一。(巴克博客)

3.2 递归实现与显式栈实现：避免 Python 递归深度问题

递归写法最直观，但 Python 默认递归深度有限；网格稍大就可能触发RecursionError。工程上更稳妥的做法是显式栈。两者生成分布相同，差异只是控制流形式。下面给出显式栈版本，它会在性能和稳定性上更可靠。

from typing import Set, Tuple def generate_dfs_backtracker(maze: Maze, start: Tuple[int,int] = (0,0)) -> None: rng = maze.rng sx, sy = start visited: Set[Tuple[int,int]] = set() stack: List[Tuple[int,int]] = [(sx, sy)] visited.add((sx, sy)) while stack: x, y = stack[-1] # 收集未访问邻居 cand: List[Tuple[int,int]] = [] for d, nb in maze.neighbors(x, y): if (nb.x, nb.y) not in visited: cand.append((nb.x, nb.y)) if not cand: stack.pop() continue nx, ny = rng.choice(cand) maze.carve(x, y, nx, ny) visited.add((nx, ny)) stack.append((nx, ny))

如果你在 ASCII 输出里观察，会发现 DFS 生成的迷宫很“像树”：从入口往里走，经常遇到很长的单通道，然后突然出现一个分叉点，分叉点后又各自延伸出长通道。这种纹理有时很讨喜，因为它对人类解迷宫来说更像“探洞”，但如果你要的是“每走几步就要做选择”的高分叉迷宫，DFS 可能就显得太“线性”。

4 随机 Prim：像“边界起火”一样扩张的迷宫生长

4.1 从最小生成树到迷宫：为什么它更“碎”、岔路更多

Prim 算法本来用于最小生成树：从一个起点开始，不断从“已连通集合”到“未连通集合”的边界上挑一条最小权重边加入。随机 Prim 迷宫把“权重”替换成随机选择：它维护一组边界候选边（或候选墙），每次随机选一条，如果它能把一个未访问 cell 接入已访问集合，就打通它并把新 cell 的边界加入候选集。与 DFS 相比，Prim 并不执着于“一路走到黑”，而是在不断扩张的边界上随机挑边，因此迷宫更容易出现很多短分支、岔路密集的感觉。Wikipedia 把它作为“图论方法”中典型示例之一。(维基百科)

4.2 Python 实现：用“前沿边”而不是“前沿点”

这里的关键是：前沿存的是“边（a->b）”，不是 cell。这样每次取出一条边时，你能判断它是否连接了一个新 cell。实现里我们用列表当作简化版的随机队列，想更快可以换成deque或者用“随机索引删除”的技巧。

from typing import Set, Tuple def generate_random_prim(maze: Maze, start: Tuple[int,int] = (0,0)) -> None: rng = maze.rng sx, sy = start visited: Set[Tuple[int,int]] = set() visited.add((sx, sy)) frontier: List[Tuple[int,int,int,int]] = [] # (ax,ay,bx,by) def add_frontier(x: int, y: int) -> None: for _, nb in maze.neighbors(x, y): if (nb.x, nb.y) not in visited: frontier.append((x, y, nb.x, nb.y)) add_frontier(sx, sy) while frontier: i = rng.randrange(len(frontier)) ax, ay, bx, by = frontier.pop(i) if (bx, by) in visited: continue maze.carve(ax, ay, bx, by) visited.add((bx, by)) add_frontier(bx, by)

你会发现它生成的迷宫，整体更“颗粒化”：因为前沿在整个已访问区域周围摆动，随机挑选会在空间上更均匀地扩张，这种感觉在视觉上接近“灌木丛式的分叉”。如果你做游戏关卡，希望玩家在较短时间内频繁做选择，随机 Prim 往往比 DFS 更合适。

5 随机 Kruskal：并查集驱动的“全局打乱后逐条连通”

5.1 生成树的另一条路：先把所有墙打乱，再决定拆不拆

Kruskal 的精神和 Prim 完全不同：Prim 是“从一个连通块长出去”，Kruskal 是“全局把所有边随机排序，然后从前到后扫一遍，遇到能连通两个不同集合的边就加入”。迷宫语境下就是：列举所有相邻 cell 的墙（边），随机打乱；依次拿出来，如果这堵墙两侧 cell 还不在同一个连通分量里，就拆墙并合并集合，否则保留墙以避免产生环。Wikipedia 给了这种“带集合的迭代随机 Kruskal”描述，核心就是“不同集合才拆墙”。(维基百科)

5.2 并查集实现：路径压缩与按秩合并让大迷宫也能快

并查集（Union-Find）是这类算法的发动机。没有并查集也能写，但会慢到让你怀疑人生。下面是一个足够工程化、但仍然短小的实现。

class UnionFind: def __init__(self, n: int): self.parent = list(range(n)) self.rank = [0] * n def find(self, a: int) -> int: while self.parent[a] != a: self.parent[a] = self.parent[self.parent[a]] a = self.parent[a] return a def union(self, a: int, b: int) -> bool: ra, rb = self.find(a), self.find(b) if ra == rb: return False if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra self.parent[rb] = ra if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1 return True def generate_random_kruskal(maze: Maze) -> None: rng = maze.rng w, h = maze.w, maze.h uf = UnionFind(w * h) def idx(x: int, y: int) -> int: return y * w + x edges: List[Tuple[int,int,int,int]] = [] for y in range(h): for x in range(w): if x + 1 < w: edges.append((x, y, x+1, y)) if y + 1 < h: edges.append((x, y, x, y+1)) rng.shuffle(edges) for ax, ay, bx, by in edges: if uf.union(idx(ax, ay), idx(bx, by)): maze.carve(ax, ay, bx, by)

随机 Kruskal 的迷宫通常会呈现一种“全局均匀随机”的气质：因为它不是从单点扩张，而是从全局随机边集合里筛边，所以结构分布更散。很多人会把 Prim 和 Kruskal 放在一起比较纹理差异；你如果做可视化动画，会发现 Prim 像“长出一片森林”，Kruskal 像“给整块玻璃裂纹随机连通”。这类对比也经常出现在迷宫算法讨论中。(维基百科)

6 递归分割：先造房间再开门的“建筑师式”迷宫

6.1 它为什么看起来更“规整”：长直墙与强几何感

如果说前面三类算法都是“在 cell 图上挑边”，递归分割（recursive division）更像“在连续空间里画墙”：先从一片空地开始，在某个方向上画一道横墙或竖墙，然后在墙上留一个或多个门洞，再把空间分成两个子区域，对每个子区域递归重复。Wikipedia 介绍这种方法时强调的是“从无墙开始，逐步加墙并留洞”。(维基百科) 它生成的迷宫往往具有明显的“建筑平面图”气质：长直墙很多，局部像房间与走廊的组合。某些游戏（尤其偏写实或偏解谜的室内场景）会更喜欢这种纹理，因为它比“树状洞穴”更像人造结构。

6.2 Python 实现：在 cell-walls 上做“加墙等价变换”

递归分割的传统实现通常在“像素栅格”上更直观，因为它是加墙；而我们目前的 Maze 类是“默认四周有墙，然后拆墙”。这两者看似矛盾，但可以转个视角：我们可以先把迷宫初始化为“全通”（把所有相邻墙都打开），然后递归地“关上某些墙”，只在门洞处保持打开。为了不破坏框架，这里我给一个简洁做法：先全通，再用递归分割关闭。

def make_all_open(maze: Maze) -> None: for y in range(maze.h): for x in range(maze.w): for d, nb in maze.neighbors(x, y): # 只向东南开，避免重复 if (d == E) or (d == S): maze.carve(x, y, nb.x, nb.y) def generate_recursive_division(maze: Maze, min_room: int = 1) -> None: rng = maze.rng make_all_open(maze) def close_between(ax: int, ay: int, bx: int, by: int) -> None: dx, dy = bx - ax, by - ay d = (dx, dy) a, b = maze.cell(ax, ay), maze.cell(bx, by) a.walls[d] = True b.walls[OPP[d]] = True def divide(x0: int, y0: int, x1: int, y1: int) -> None: # 区域为 [x0,x1]×[y0,y1] 的 cell 坐标闭区间 width = x1 - x0 + 1 height = y1 - y0 + 1 if width <= min_room or height <= min_room: return # 选择分割方向：尽量沿更长的一边切，也可以纯随机 if width > height: cut_vertical = True elif height > width: cut_vertical = False else: cut_vertical = rng.choice([True, False]) if cut_vertical: # 在 x = cut 处竖切：左区 [x0..cut] 右区 [cut+1..x1] cut = rng.randint(x0, x1 - 1) hole = rng.randint(y0, y1) # 关闭 cut 与 cut+1 之间的所有连接，唯独 hole 行留门 for y in range(y0, y1 + 1): if y == hole: continue close_between(cut, y, cut + 1, y) divide(x0, y0, cut, y1) divide(cut + 1, y0, x1, y1) else: # 在 y = cut 处横切：上区 [y0..cut] 下区 [cut+1..y1] cut = rng.randint(y0, y1 - 1) hole = rng.randint(x0, x1) for x in range(x0, x1 + 1): if x == hole: continue close_between(x, cut, x, cut + 1) divide(x0, y0, x1, cut) divide(x0, cut + 1, x1, y1) divide(0, 0, maze.w - 1, maze.h - 1)

递归分割常被用来做“有房间感”的关卡雏形：你可以把门洞从“留一个”变成“留两个”，就会出现更多回路与房间连通；你也可以对某些子区域停止分割，天然形成大房间。这就是它在工程上很实用的原因：它不仅生成迷宫，还天然生成“空间结构”。

7 Sidewinder 与 Binary Tree：带偏置的极简算法与“可预测纹理”

7.1 偏置不是缺点：当你需要“方向性”与“可控风格”

有些迷宫算法在 Wikipedia 的分类里被叫做“简单算法”，比如 Sidewinder、Binary Tree。(维基百科) 它们之所以在生产上仍然常见，不是因为“学术上更高级”，恰恰相反，是因为它们非常便宜、非常稳定，并且纹理偏置强到可以当作一种美术风格。你在做像素风游戏时可能就想要这种“倾斜的树状纹理”，而不是高随机性的自然洞穴。更重要的是，这类算法非常适合“流式生成”：只需要处理一行或局部，不必把全图状态都存起来。

7.2 Sidewinder：一行一行地“横向跑团”，偶尔往上打一个洞

Sidewinder 的直觉是：第一行全开通道；从第二行开始，每行维护一个“run”（连续的横向通道段），你在这一行里不断向东打通，把 cell 加进 run；但你会在随机时刻“收束”这个 run，从 run 中随机挑一个 cell 向北打通，然后清空 run，继续新的 run。因为它总能向北连通到上一行，所以最终是完美迷宫；同时它天然带有“水平偏置”。Wikipedia 也提到它的行级生成方式和结构特性。(维基百科)

def generate_sidewinder(maze: Maze) -> None: rng = maze.rng w, h = maze.w, maze.h # 第一行：一路向东打通 for x in range(w - 1): maze.carve(x, 0, x + 1, 0) for y in range(1, h): run: List[int] = [] for x in range(w): run.append(x) at_eastern_boundary = (x == w - 1) # 随机决定是否“收束 run” close_out = at_eastern_boundary or rng.choice([True, False]) if close_out: carve_x = rng.choice(run) # 向北打通 maze.carve(carve_x, y, carve_x, y - 1) run = [] else: # 继续向东延伸 run maze.carve(x, y, x + 1, y)

7.3 Binary Tree：每格只在两个方向里选一个，形成“斜向树根”

Binary Tree 更极端：对每个 cell，只在“北”和“西”（或你选择的两方向）里随机打通一面墙，于是所有路径都会倾向某个角落，整体看起来像一棵朝某方向生长的树。Wikipedia 对它的描述强调了这种“每个 cell 只连上或左”的偏置特征。(维基百科)

def generate_binary_tree(maze: Maze, bias: Tuple[Dir, Dir] = (N, W)) -> None: rng = maze.rng d1, d2 = bias for y in range(maze.h): for x in range(maze.w): options: List[Tuple[int,int]] = [] for d in (d1, d2): nx, ny = x + d[0], y + d[1] if maze.in_bounds(nx, ny): options.append((nx, ny)) if options: nx, ny = rng.choice(options) maze.carve(x, y, nx, ny)

这类算法的价值在于：你几乎不用调参就能得到稳定风格，而且能非常快地产生大迷宫；缺点也同样明显：偏置强，会让迷宫某些方向“永远不可能出现死路”，对解题者而言可被利用，难度上限受限。但如果你反过来需要“可被玩家学习和掌握的规律”，那它反而是优点。

8 Eller：只看一行也能生成无限高完美迷宫的“集合魔法”

8.1 为什么它值得学习：流式生成、线性复杂度与行级状态

Eller 算法经常被称为“能流式生成的完美迷宫算法”：它只需要维护当前行的集合信息，就能一行一行地往下生成，而且能做到“无限高度”的概念（当然现实里你还是会有高度）。Jamis Buck 对它的评价非常直白：它既疯狂又快，并且只需看一行。(巴克博客) Wikipedia 也提到它通过集合避免回路，并能仅存一行信息完成生成。(维基百科)

Eller 的核心在于“集合（set id）”：同一集合表示这些 cell 在已经生成的部分里是连通的。你在一行内随机决定横向连接（合并集合），然后必须保证每个集合至少有一个 cell 向下打通，否则下一行会出现被隔绝的连通块，最终迷宫不连通。到最后一行时，你再强制把所有集合横向连通成一个集合，结束。

8.2 Python 实现：可读性优先的 Eller（适合学习与改造）

def generate_eller(maze: Maze) -> None: rng = maze.rng w, h = maze.w, maze.h next_set_id = 1 sets = [0] * w # 当前行每列的 set id for y in range(h): # 为空的列分配新集合 for x in range(w): if sets[x] == 0: sets[x] = next_set_id next_set_id += 1 # 行内横向连接（除最后一行外随机，最后一行强制合并） for x in range(w - 1): if y == h - 1: # 最后一行：强制把所有不同集合连通 if sets[x] != sets[x + 1]: maze.carve(x, y, x + 1, y) old = sets[x + 1] new = sets[x] for k in range(w): if sets[k] == old: sets[k] = new else: # 非最后一行：随机决定是否横向打通，且避免同集合产生环 if sets[x] != sets[x + 1] and rng.choice([True, False]): maze.carve(x, y, x + 1, y) old = sets[x + 1] new = sets[x] for k in range(w): if sets[k] == old: sets[k] = new if y == h - 1: break # 决定向下开口：每个集合至少开一个 new_sets = [0] * w # 按集合分组列索引 groups: Dict[int, List[int]] = {} for x in range(w): groups.setdefault(sets[x], []).append(x) for set_id, xs in groups.items(): # 该集合中随机选若干个向下打通，至少一个 rng.shuffle(xs) open_count = rng.randint(1, len(xs)) for x in xs[:open_count]: maze.carve(x, y, x, y + 1) new_sets[x] = set_id sets = new_sets

这段实现的好处是直观：你能清楚看到“行内合并集合”和“确保每集合至少一个向下连接”的两个关键约束。它也非常容易改造成“在线生成”：每次生成一行就输出一行，尤其适合流式地图、无限跑酷、或者需要在内存极小环境下跑的场景。

9 Aldous–Broder 与 Wilson：走向“均匀生成树”的随机游走系算法

9.1 “无偏”到底是什么意思：均匀生成树与算法偏置

到目前为止，我们介绍的 DFS、Prim、Kruskal、Eller、Sidewinder 等，虽然都能生成完美迷宫，但它们对“哪一种生成树更容易被生成”都有偏好：有的更爱长走廊，有的更爱碎分叉，这种“偏置”是纹理来源，也是风格来源。而另一条路线是：我不想要风格偏置，我想在所有可能的生成树中做均匀采样，让每一棵生成树出现概率相同。Wikipedia 在介绍 Aldous–Broder 与 Wilson 时，直接把它们放在“能产生均匀生成树”的算法里。(维基百科) Jamis Buck 也强调 Aldous–Broder 的重要性质：它从所有生成树中等概率选择，但效率很差。(巴克博客)

这种“均匀生成树”的严肃数学背景来自随机游走与马尔可夫链理论。Aldous 的论文讨论了随机游走构造均匀生成树的性质，并给出“每棵生成树概率相同”的命题。(CMU计算机科学学院) 你不需要读完论文才能用算法，但知道“无偏”意味着什么，会让你在做内容生成时更清醒：你要的是“某种美术风格”，还是要的是“统计意义上的公平随机”。

9.2 Aldous–Broder：最简单的均匀生成树，但常被吐槽“慢得令人痛苦”

Aldous–Broder 非常好理解：在图上做随机游走；当你第一次走到一个从未访问过的节点时，就把这一步的边加入生成树；直到所有节点都被访问。它慢的原因也直观：随机游走覆盖整个图的“覆盖时间”可能很大，尤其在大网格上会走很多无用步。Wikipedia 与 Jamis Buck 都提到它效率差。(维基百科)

from typing import Set, Tuple def generate_aldous_broder(maze: Maze, start: Optional[Tuple[int,int]] = None) -> None: rng = maze.rng if start is None: x, y = rng.randrange(maze.w), rng.randrange(maze.h) else: x, y = start visited: Set[Tuple[int,int]] = {(x, y)} total = maze.w * maze.h while len(visited) < total: # 随机走到一个邻居 d, nb = rng.choice(list(maze.neighbors(x, y))) nx, ny = nb.x, nb.y if (nx, ny) not in visited: maze.carve(x, y, nx, ny) visited.add((nx, ny)) x, y = nx, ny

9.3 Wilson：循环擦除随机游走（LERW），更快、更优雅

Wilson 算法同样生成均匀生成树，但通常比 Aldous–Broder 高效得多。它从一个已在树中的集合开始，然后对一个不在树中的起点做随机游走，直到碰到树；在游走过程中如果形成回路，就把回路“擦除”（loop-erased random walk），最后把擦除后的路径整体并入树。这个算法在很多可视化资源里都被当作“美学最强”的一种，因为它的循环擦除过程很有戏剧性。Mike Bostock 的说明简洁点出它的关键性质：Wilson 用循环擦除随机游走生成均匀生成树，很多其他算法不具备这种“无偏”性质。(Gist)

from typing import Dict, Set, Tuple def generate_wilson(maze: Maze, root: Optional[Tuple[int,int]] = None) -> None: rng = maze.rng all_cells = [(x, y) for y in range(maze.h) for x in range(maze.w)] if root is None: root = rng.choice(all_cells) in_tree: Set[Tuple[int,int]] = {root} # 便利：从 (x,y) 随机取邻居 def rand_neighbor(x: int, y: int) -> Tuple[int,int]: _, nb = rng.choice(list(maze.neighbors(x, y))) return nb.x, nb.y for start in all_cells: if start in in_tree: continue # 随机游走并做 loop-erased：用 next 指针记录路径，若形成环就擦除 path_next: Dict[Tuple[int,int], Tuple[int,int]] = {} x, y = start while (x, y) not in in_tree: nx, ny = rand_neighbor(x, y) path_next[(x, y)] = (nx, ny) x, y = nx, ny # 将 loop-erased 路径并入树：从 start 顺着 next 走到树 x, y = start while (x, y) not in in_tree: nx, ny = path_next[(x, y)] maze.carve(x, y, nx, ny) in_tree.add((x, y)) x, y = nx, ny in_tree.add((x, y))

Wilson 的实现细节比 DFS/Prim 更“绕”，但它一旦写对，就会给你一个非常强的能力：你能在“纹理偏置”和“统计无偏”之间做明确选择。对于程序生成内容来说，这不是小事，因为偏置意味着某些结构更常出现，玩家会潜移默化地学会利用；而无偏意味着玩家更难凭经验投机取巧。

10 让算法变成“可用系统”：入口出口、加环、难度调参与验证

10.1 入口出口并不是“开两个洞”这么简单

很多人生成完迷宫后随便在边上开两个洞就完事，但如果你做的是游戏关卡，你经常会希望入口与出口之间的主路径足够长，或者希望出口距离入口在图上的最短路超过某个阈值。做法并不复杂：生成迷宫后做一次 BFS/DFS 求最远点对（在树上就是找直径近似），然后把入口出口开在这对点上。即便你不做最远点对，至少也应当允许由外部指定入口出口位置，然后在外边界对应方向开口；上面open_entrance_exit()已经支持。Stack Overflow 上也有人讨论“如何选择入口出口点”的问题，本质就是把入口出口当作边界节点，并在生成后做路径长度控制。(Stack Overflow)

10.2 从“完美迷宫”到“更像现实的迷宫”：加少量回路（braiding）

完美迷宫的特征是唯一解，但现实里很多迷宫并非如此。你可以在生成树基础上再随机拆掉少量“不会破坏外墙”的墙，让迷宫出现回路；这会显著改变体验：死胡同减少，路线选择增加，AI 寻路也更接近一般图。Wikipedia 也提到回路可通过“额外添加随机边”引入。(维基百科) 工程上常见做法是：统计所有死胡同（度为 1 的 cell），对其中一部分随机打通一面邻墙，把死胡同“编织”成回路。调参时你会发现，回路比例不是越高越好；太高会让迷宫失去“迷”的味道，变成普通网格通道。

10.3 难度与风格调参：你真正能控制的变量是什么

迷宫“难不难”并不只取决于大小。DFS 生成的长走廊，可能让玩家走很久但做选择很少；Prim 生成的碎分叉，可能让玩家频繁做选择但每次代价不大；递归分割生成的长直墙，会让玩家更依赖空间感与“房间逻辑”。你能控制的变量，往往是“算法选择 + 算法内随机策略 + 后处理（加环/加房间/加权）”。你如果想定量化难度，可以从图指标入手：平均分支度、死胡同比例、入口到出口的最短路长度、路径上的决策点数量、以及“错误路线的代价”（比如从岔路走到死胡同的平均距离）。这类指标一旦和算法绑定，你就能做“风格库”：同样大小，同样入口出口，不同算法就是不同关卡味道。

11 把一切串起来：一个可运行示例与输出

11.1 最小示例：生成、开口、打印

def demo(): m = Maze(20, 10, seed=20251224) # 选择一种算法 generate_dfs_backtracker(m, start=(0, 0)) # generate_random_prim(m, start=(0, 0)) # generate_random_kruskal(m) # generate_recursive_division(m) # generate_sidewinder(m) # generate_binary_tree(m, bias=(N, W)) # generate_eller(m) # generate_aldous_broder(m) # generate_wilson(m) m.open_entrance_exit((0, 0), (m.w - 1, m.h - 1)) print(m.to_ascii()) if __name__ == "__main__": demo()

你会得到一张 ASCII 迷宫。接下来你可以很自然地加上 matplotlib 或 pygame 做渲染；也可以把walls导出成 tilemap（例如 Tiled JSON），用于游戏引擎。只要你的内部表示足够干净，算法越多，你的系统反而越稳，因为每个算法都在用不同方式“折腾”同一套数据结构，这就是最好的回归测试。

12 结语：选择算法，其实是在选择“随机性的哲学”

迷宫生成算法的世界表面上像“十几种经典算法供你挑”，但真正的分水岭其实就两条：一条是把迷宫当作随机生成树，接受算法偏置，把偏置当作风格；另一条是追求均匀生成树，把“无偏”当作目标，接受更复杂的实现与更高的成本。Wikipedia 的总述把这两条路线都讲得很清楚：迷宫生成可以视作生成树；回路可以后加；Aldous–Broder 与 Wilson 提供均匀生成树，而 DFS/Prim/Kruskal 更偏向工程常用。(维基百科) Jamis Buck 的系列则告诉你：不要只问“哪个最好”，要问“我想要什么纹理”。(巴克博客)