引言
迷宫的生成与求解是图论算法最直观的可视化场景之一。传统的深度优先搜索（DFS）回溯法虽然能生成完美的迷宫，但其路径存在明显的偏置——长走廊过多，分支结构过于规则。本文介绍随机 Prim 算法（Randomized Prim’s Algorithm），它能生成更加自然、分支分布更均匀的迷宫；随后使用双向 BFS 快速求解最短出口路径。两种算法的组合，让迷宫从生成到求解都充满了图论之美。
核心算法思想
1. 随机 Prim 迷宫生成
将迷宫视为一个网格图，每个格子是一个节点，相邻格子之间有边。随机 Prim 算法从任意起点开始，维护一个”前沿边集合”（frontier）：
- 从起点出发，将其所有邻接边加入前沿集合
- 随机从前沿集合中选取一条边，如果该边连接了一个未访问节点，则打通这条边（移除墙壁），并将新节点的邻接边加入前沿
- 重复步骤 2 直到所有节点都被访问
与 DFS 回溯相比，随机 Prim 的优势在于：
– 更均匀的分支分布：不会偏爱某一分支深度
– 更短的最短路径期望：因为生成过程天然倾向于扩展边界
– 更自然的视觉效果：类似自然洞穴的纹理
2. 双向 BFS 最短路径
在生成的迷宫中，从入口和出口同时开始 BFS。两个搜索前沿相遇时，即得到最短路径。对于 $V$ 个节点、$E$ 条边的迷宫图：
- 标准 BFS：$O(V + E)$
- 双向 BFS：$O(\sqrt{V} + \sqrt{E})$（实际运行中通常快 2-5 倍）
3. 迷宫完美性保证
随机 Prim 算法生成的迷宫是”完美迷宫”（Perfect Maze）：任意两点之间有且仅有一条简单路径，无环也无不可达区域。这是因为算法本质上是在网格图上构建了一棵生成树。
Java 实现
import java.util.*;
/**
* 迷宫生成与求解系统
* 生成：随机 Prim 算法（均匀分支分布）
* 求解：双向 BFS（最短路径加速）
*/
public class MazePrimBidirectional {
private final int rows, cols;
// cellWalls[r][c][d] = true 表示 (r,c) 在方向 d 上有墙
// d: 0=上, 1=右, 2=下, 3=左
private final boolean[][][] cellWalls;
private final Random rand;
public MazePrimBidirectional(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.cellWalls = new boolean[rows][cols][4];
this.rand = new Random();
// 初始时所有墙都存在
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
Arrays.fill(cellWalls[r][c], true);
}
}
}
/**
* 随机 Prim 算法生成完美迷宫
*/
public void generatePrim() {
boolean[][] visited = new boolean[rows][cols];
// 前沿边列表：每个元素为 {fromR, fromC, toR, toC}
List<int[]> frontier = new ArrayList<>();
// 从左上角开始
int startR = 0, startC = 0;
visited[startR][startC] = true;
addFrontier(startR, startC, frontier, visited);
while (!frontier.isEmpty()) {
// 随机选取一条前沿边
int idx = rand.nextInt(frontier.size());
int[] edge = frontier.remove(idx);
int fr = edge[0], fc = edge[1], tr = edge[2], tc = edge[3];
if (visited[tr][tc]) continue; // 目标已访问，跳过
// 打通这条边：移除两面墙
removeWall(fr, fc, tr, tc);
visited[tr][tc] = true;
// 将新节点的邻接边加入前沿
addFrontier(tr, tc, frontier, visited);
}
// 确保边界墙完整（与外部世界的隔离）
for (int r = 0; r < rows; r++) {
cellWalls[r][0][3] = true; // 左边界
cellWalls[r][cols - 1][1] = true; // 右边界
}
for (int c = 0; c < cols; c++) {
cellWalls[0][c][0] = true; // 上边界
cellWalls[rows - 1][c][2] = true; // 下边界
}
}
/**
* 将 (r,c) 的所有未访问邻居的边加入前沿集合
*/
private void addFrontier(int r, int c, List<int[]> frontier, boolean[][] visited) {
int[][] dirs = {{-1,0,0}, {0,1,1}, {1,0,2}, {0,-1,3}};
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (inBounds(nr, nc) && !visited[nr][nc]) {
frontier.add(new int[]{r, c, nr, nc});
}
}
}
/**
* 移除 (r1,c1) 和 (r2,c2) 之间的墙
*/
private void removeWall(int r1, int c1, int r2, int c2) {
if (r1 == r2) {
if (c1 < c2) { cellWalls[r1][c1][1] = false; cellWalls[r2][c2][3] = false; }
else { cellWalls[r1][c1][3] = false; cellWalls[r2][c2][1] = false; }
} else {
if (r1 < r2) { cellWalls[r1][c1][2] = false; cellWalls[r2][c2][0] = false; }
else { cellWalls[r1][c1][0] = false; cellWalls[r2][c2][2] = false; }
}
}
/**
* 双向 BFS 求解从入口 (0,0) 到出口 (rows-1,cols-1) 的最短路径
*/
public List<int[]> solveBidirectionalBFS() {
int[] start = {0, 0};
int[] end = {rows - 1, cols - 1};
if (start[0] == end[0] && start[1] == end[1]) {
return Collections.singletonList(start);
}
Queue<int[]> qStart = new LinkedList<>();
Queue<int[]> qEnd = new LinkedList<>();
Map<String, String> parentStart = new HashMap<>();
Map<String, String> parentEnd = new HashMap<>();
String sKey = key(start), eKey = key(end);
qStart.offer(start);
qEnd.offer(end);
parentStart.put(sKey, null);
parentEnd.put(eKey, null);
String meeting = null;
while (!qStart.isEmpty() && !qEnd.isEmpty() && meeting == null) {
// 平衡扩展：优先扩展队列较小的一端
if (qStart.size() <= qEnd.size()) {
meeting = expandBFS(qStart, parentStart, parentEnd, true);
} else {
meeting = expandBFS(qEnd, parentEnd, parentStart, false);
}
}
if (meeting == null) return null;
return reconstructPath(meeting, parentStart, parentEnd);
}
/**
* 扩展一层 BFS，检查是否与另一端相遇
*/
private String expandBFS(Queue<int[]> queue, Map<String, String> myParent,
Map<String, String> otherParent, boolean fromStart) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cur = queue.poll();
String curKey = key(cur);
// 获取可通行的邻居（墙为 false 的方向）
List<int[]> neighbors = getPassableNeighbors(cur[0], cur[1]);
for (int[] nb : neighbors) {
String nKey = key(nb);
if (myParent.containsKey(nKey)) continue;
myParent.put(nKey, curKey);
if (otherParent.containsKey(nKey)) {
return nKey; // 相遇
}
queue.offer(nb);
}
}
return null;
}
/**
* 获取 (r,c) 所有可通行的邻居
*/
private List<int[]> getPassableNeighbors(int r, int c) {
List<int[]> list = new ArrayList<>();
int[][] dirs = {{-1,0,0}, {0,1,1}, {1,0,2}, {0,-1,3}};
for (int[] d : dirs) {
if (!cellWalls[r][c][d[2]]) { // 该方向无墙
int nr = r + d[0], nc = c + d[1];
if (inBounds(nr, nc)) list.add(new int[]{nr, nc});
}
}
return list;
}
/**
* 重构双向 BFS 路径
*/
private List<int[]> reconstructPath(String meeting,
Map<String, String> pStart,
Map<String, String> pEnd) {
LinkedList<int[]> path = new LinkedList<>();
String cur = meeting;
while (cur != null) {
path.addFirst(decode(cur));
cur = pStart.get(cur);
}
cur = pEnd.get(meeting);
while (cur != null) {
path.addLast(decode(cur));
cur = pEnd.get(cur);
}
return path;
}
/**
* 打印迷宫（ASCII 艺术）
*/
public void printMaze() {
// 顶部边界
for (int c = 0; c < cols; c++) System.out.print("+---");
System.out.println("+");
for (int r = 0; r < rows; r++) {
// 单元格内容行
System.out.print("|");
for (int c = 0; c < cols; c++) {
char ch = ' ';
if (r == 0 && c == 0) ch = 'S';
else if (r == rows - 1 && c == cols - 1) ch = 'E';
System.out.print(" " + ch + " ");
System.out.print(cellWalls[r][c][1] ? "|" : " ");
}
System.out.println();
// 底部墙行
System.out.print("+");
for (int c = 0; c < cols; c++) {
System.out.print(cellWalls[r][c][2] ? "---+" : " +");
}
System.out.println();
}
}
/**
* 在迷宫上打印路径
*/
public void printMazeWithPath(List<int[]> path) {
Set<String> pathSet = new HashSet<>();
for (int[] p : path) pathSet.add(key(p));
for (int c = 0; c < cols; c++) System.out.print("+---");
System.out.println("+");
for (int r = 0; r < rows; r++) {
System.out.print("|");
for (int c = 0; c < cols; c++) {
char ch = ' ';
if (r == 0 && c == 0) ch = 'S';
else if (r == rows - 1 && c == cols - 1) ch = 'E';
else if (pathSet.contains(key(r, c))) ch = '*';
System.out.print(" " + ch + " ");
System.out.print(cellWalls[r][c][1] ? "|" : " ");
}
System.out.println();
System.out.print("+");
for (int c = 0; c < cols; c++) {
System.out.print(cellWalls[r][c][2] ? "---+" : " +");
}
System.out.println();
}
}
// 工具方法
private boolean inBounds(int r, int c) { return r >= 0 && r < rows && c >= 0 && c < cols; }
private String key(int[] p) { return p[0] + "," + p[1]; }
private String key(int r, int c) { return r + "," + c; }
private int[] decode(String s) { String[] p = s.split(","); return new int[]{Integer.parseInt(p[0]), Integer.parseInt(p[1])}; }
// 演示
public static void main(String[] args) {
MazePrimBidirectional maze = new MazePrimBidirectional(10, 15);
maze.generatePrim();
System.out.println("===== 随机 Prim 迷宫 =====");
maze.printMaze();
List<int[]> path = maze.solveBidirectionalBFS();
if (path != null) {
System.out.println("\n===== 双向 BFS 最短路径（长度=" + path.size() + "） =====");
maze.printMazeWithPath(path);
} else {
System.out.println("无解（理论上不应发生）");
}
}
}
复杂度分析
| 阶段 | 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 迷宫生成 | 随机 Prim | $O(V \log V)$ | $O(V)$ |
| 路径求解 | 标准 BFS | $O(V + E)$ | $O(V)$ |
| 路径求解 | 双向 BFS | $O(\sqrt{V} + \sqrt{E})$ | $O(\sqrt{V})$ |
对于 $R \times C$ 的迷宫，$V = R \cdot C$，$E \approx 2V$（完美迷宫）。双向 BFS 在 100×100 的迷宫中通常比标准 BFS 快 3-4 倍。
总结
随机 Prim 算法通过维护前沿边集合并随机选取，生成了分支分布更均匀、视觉上更自然的完美迷宫。作为生成树算法的一种，它保证了迷宫的连通性与无环性。双向 BFS 则从两端同时搜索，将求解的最坏情况时间大幅削减。读者可以在此基础上继续探索：将 Prim 替换为 Kruskal 并配合随机权重生成不同风格的迷宫、引入” braid “机制在生成树中选择性加环以降低死胡同密度、或使用 A* 替代 BFS 并在启发函数中引入” 转弯惩罚 “，生成更符合人类直觉的” 自然路径 “。
