迷宫的生成算法有很多种：DFS 回溯产生长走廊、Prim 产生大量分支、Wilson 算法保证均匀分布。Hunt-and-Kill（猎杀算法）是一个位置尴尬但极其好用的选择——它没有 Wilson 那样的理论优雅，也不像 DFS 那样简单，却能用非常少的状态内存生成高质量的无偏迷宫，且天然适合并行化与增量生成。本文用 Java 实现 Hunt-and-Kill 迷宫生成器，并配上求解器做出一个可玩的迷宫游戏。
一、为什么需要生成算法
先明确”好迷宫”的标准。一个理想迷宫应满足三个性质：
- 完美性（Perfect）：任意两个格之间存在且仅存在一条路径，即生成树
- 无偏性（Unbiased）：所有可能的生成树被等概率选中
- 形态质量：死胡同不过多、通路不至于像个广场
DFS 回溯满足完美性，但产生的迷宫有明显的”长走廊偏置”——只要还有未访问邻居就一直往下走，导致迷宫里死胡同极少、路径极长，玩家体验单调。Wilson 算法严格满足无偏性，但需要维护完整的树集合，内存开销大，实现也复杂。
Hunt-and-Kill 取两者之间：随机游走阶段（Kill）产生随机性强的路径，扫描阶段（Hunt）系统性地找下一个起点，保证所有格子都被覆盖。它的随机性不如 Wilson 严格，但形态质量比 DFS 好很多，实现却只比 DFS 复杂一点点。
二、算法核心：两个阶段的交替
Hunt-and-Kill 的执行流程如下：
- 随机选一个起始格子，标记为已访问
- Kill（游走）阶段：从当前格子出发，不断随机选一个未访问的相邻格子，打通墙壁，走过去，直到当前格子没有未访问邻居
- Hunt（猎杀）阶段：按行优先（或扫描线）顺序遍历所有格子，找到第一个”已访问但存在未访问邻居”的格子，把它作为新的起点，打通它和一个随机未访问邻居之间的墙，回到 Kill 阶段
- 重复 2-3，直到所有格子都被访问
两个阶段的名字来源就是”打死一条路，再去猎下一个起点”。这个结构带来一个很实用的性质：Hunt 阶段可以随时中断。如果用户只需要迷宫的一部分（比如做分块加载），可以先 Kill 一阵再保存状态，下次从断点继续 Hunt，不需要重算整个迷宫。
三、数据结构与墙壁表示
迷宫用”墙壁位掩码”表示比用独立的墙数组更紧凑。每个格子存一个 4 位整数，四位分别代表上、右、下、左是否有墙：
/**
* 迷宫单元格：使用位掩码表示四面墙壁
* bit 0 = 上, bit 1 = 右, bit 2 = 下, bit 3 = 左；置 1 表示该方向有墙
*/
public class MazeCell {
public static final int UP = 1;
public static final int RIGHT = 2;
public static final int DOWN = 4;
public static final int LEFT = 8;
public static final int ALL_WALLS = UP | RIGHT | DOWN | LEFT;
private int walls = ALL_WALLS;
private boolean visited;
public boolean hasWall(int dir) {
return (walls & dir) != 0;
}
/** 移除某方向的墙 */
public void clearWall(int dir) {
walls &= ~dir;
}
public boolean isVisited() {
return visited;
}
public void visit() {
visited = true;
}
}
墙壁的对称性必须手工维护：打通 A 的右侧墙时，必须同时打通 B 的左侧墙。这是实现迷宫生成时最容易漏掉的一步，漏了就会出现”能从 A 走到 B，却无法从 B 走回 A”的单向走廊，求解器会惊奇地报告迷宫不连通。
/**
* 迷宫网格：负责坐标换算与双向拆墙
*/
public class MazeGrid {
private final int rows;
private final int cols;
private final MazeCell[][] cells;
public MazeGrid(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.cells = new MazeCell[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
cells[r][c] = new MazeCell();
}
}
}
/** 拆除相邻两格之间的墙，必须双向拆除 */
public void removeWallBetween(int r1, int c1, int r2, int c2) {
if (r1 == r2) {
if (c2 == c1 + 1) {
cells[r1][c1].clearWall(MazeCell.RIGHT);
cells[r2][c2].clearWall(MazeCell.LEFT);
} else if (c2 == c1 - 1) {
cells[r1][c1].clearWall(MazeCell.LEFT);
cells[r2][c2].clearWall(MazeCell.RIGHT);
} else {
throw new IllegalArgumentException("非相邻格子: (" + r1 + "," + c1 + ") (" + r2 + "," + c2 + ")");
}
} else if (c1 == c2) {
if (r2 == r1 + 1) {
cells[r1][c1].clearWall(MazeCell.DOWN);
cells[r2][c2].clearWall(MazeCell.UP);
} else if (r2 == r1 - 1) {
cells[r1][c1].clearWall(MazeCell.UP);
cells[r2][c2].clearWall(MazeCell.DOWN);
} else {
throw new IllegalArgumentException("非相邻格子: (" + r1 + "," + c1 + ") (" + r2 + "," + c2 + ")");
}
} else {
throw new IllegalArgumentException("对角线不是邻居: (" + r1 + "," + c1 + ") (" + r2 + "," + c2 + ")");
}
}
public MazeCell cell(int r, int c) {
return cells[r][c];
}
public int getRows() {
return rows;
}
public int getCols() {
return cols;
}
}
用抛异常而不是静默返回，可以在早期就抓出坐标越界或非相邻的调用错误。这类错误如果不报，会以”迷宫看起来还行但求解路径诡异”的形式延迟暴露，排查成本很高。
四、Hunt-and-Kill 主体实现
有了网格，主算法就很直接。注意 Hunt 阶段的扫描指针要顺着上一次的位置继续推进，而不是每轮从头扫——这是性能上的关键优化，否则大迷宫会退化成 O(rows * cols * 轮数)。
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class HuntAndKillGenerator {
private final MazeGrid grid;
private final Random random;
/** Hunt 指针，避免每轮从 (0,0) 重新扫描 */
private int huntRow;
private int huntCol;
public HuntAndKillGenerator(MazeGrid grid, long seed) {
this.grid = grid;
this.random = new Random(seed);
}
public void generate() {
int rows = grid.getRows();
int cols = grid.getCols();
// 起点随机
int curR = random.nextInt(rows);
int curC = random.nextInt(cols);
grid.cell(curR, curC).visit();
while (true) {
// ---------- Kill 阶段：一路随机游走，直到无未访问邻居 ----------
boolean walked = true;
while (walked) {
walked = false;
for (int dir : shuffledDirections()) {
int nr = curR + dr(dir);
int nc = curC + dc(dir);
if (inBounds(nr, nc) && !grid.cell(nr, nc).isVisited()) {
grid.removeWallBetween(curR, curC, nr, nc);
grid.cell(nr, nc).visit();
curR = nr;
curC = nc;
walked = true;
break;
}
}
}
// ---------- Hunt 阶段：找下一个起点，返回 null 表示全图已访问 ----------
int[] start = huntForStart();
if (start == null) {
return;
}
curR = start[0];
curC = start[1];
}
}
/**
* 按行优先扫描，找到第一个"已访问且有未访问邻居"的格子，
* 将其与一个随机未访问邻居连通，并返回该邻居坐标。
* 扫描指针 huntRow/huntCol 单调前进，不回头，保证总复杂度 O(V)。
*/
private int[] huntForStart() {
int rows = grid.getRows();
int cols = grid.getCols();
while (huntRow < rows) {
while (huntCol < cols) {
int r = huntRow;
int c = huntCol++;
if (!grid.cell(r, c).isVisited()) {
continue;
}
for (int dir : shuffledDirections()) {
int nr = r + dr(dir);
int nc = c + dc(dir);
if (inBounds(nr, nc) && !grid.cell(nr, nc).isVisited()) {
grid.removeWallBetween(r, c, nr, nc);
grid.cell(nr, nc).visit();
return new int[]{nr, nc};
}
}
}
huntRow++;
huntCol = 0;
}
return null;
}
/** 打乱四个方向，等价于随机选取邻居 */
private int[] shuffledDirections() {
int[] d = {0, 1, 2, 3};
for (int i = 3; i > 0; i--) {
int j = random.nextInt(i + 1);
int tmp = d[i];
d[i] = d[j];
d[j] = tmp;
}
return d;
}
private int dr(int dir) {
return dir == 0 ? -1 : (dir == 2 ? 1 : 0);
}
private int dc(int dir) {
return dir == 1 ? 1 : (dir == 3 ? -1 : 0);
}
private boolean inBounds(int r, int c) {
return r >= 0 && r < grid.getRows() && c >= 0 && c < grid.getCols();
}
}
这里有两个实现要点直接决定性能与形态质量。其一，Hunt 阶段的扫描指针必须单调前进：huntRow/huntCol 只增不减，扫描过一次的格子不再重扫，否则大迷宫会退化成 O(rows * cols * 轮数)。其二，Hunt 找到的起点必须真正用于下一轮 Kill：如果 huntForStart() 返回的坐标没被写回 curR/curC，算法依然能生成完美迷宫（每格只访问一次），但游走会从旧位置重新出发，形态明显退化——这是实现 Hunt-and-Kill 时最容易踩的隐性坑。
五、完美性验证：并查集的 O(1) 判定
生成完成后必须自检。一个完美迷宫应当满足：所有格子连通，且连通边数恰好为 cells – 1（生成树性质）。用并查集（Union-Find）验证最直接，同时还能顺手抓出”单面拆墙”的对称性错误——如果只拆了一侧，邻接关系里就找不到这条边，连通性检查会失败。
/**
* 并查集：带路径压缩与按秩合并
*/
public class DSU {
private final int[] parent;
private final int[] rank;
public DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
/** @return true 表示原本不连通，本次成功合并 */
public boolean union(int a, int b) {
int ra = find(a);
int rb = find(b);
if (ra == rb) {
return false;
}
if (rank[ra] < rank[rb]) {
parent[ra] = rb;
} else if (rank[ra] > rank[rb]) {
parent[rb] = ra;
} else {
parent[rb] = ra;
rank[ra]++;
}
return true;
}
}
/**
* 迷宫校验器：检查完美性（连通 + 无环）
*/
public class MazeValidator {
public static void validate(MazeGrid grid) {
int rows = grid.getRows();
int cols = grid.getCols();
int total = rows * cols;
DSU dsu = new DSU(total);
int edges = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
MazeCell cell = grid.cell(r, c);
// 只检查右和下两个方向，避免重复计数
if (c + 1 < cols && !cell.hasWall(MazeCell.RIGHT)) {
MazeCell right = grid.cell(r, c + 1);
if (right.hasWall(MazeCell.LEFT)) {
throw new IllegalStateException(
"墙体不对称: (" + r + "," + c + ") 右侧已通但邻格左侧未通");
}
dsu.union(index(r, c, cols), index(r, c + 1, cols));
edges++;
}
if (r + 1 < rows && !cell.hasWall(MazeCell.DOWN)) {
MazeCell down = grid.cell(r + 1, c);
if (down.hasWall(MazeCell.UP)) {
throw new IllegalStateException(
"墙体不对称: (" + r + "," + c + ") 下侧已通但邻格上侧未通");
}
dsu.union(index(r, c, cols), index(r + 1, c, cols));
edges++;
}
}
}
int components = 0;
for (int i = 0; i < total; i++) {
if (dsu.find(i) == i) {
components++;
}
}
if (components != 1) {
throw new IllegalStateException("迷宫不连通，连通分量数 = " + components);
}
if (edges != total - 1) {
throw new IllegalStateException("迷宫存在环，边数 = " + edges + "，期望 " + (total - 1));
}
System.out.println("校验通过：连通且无环，边数 = " + edges + "，格子数 = " + total);
}
private static int index(int r, int c, int cols) {
return r * cols + c;
}
}
“连通 + 边数 = n-1″这两条同时成立，就等价于生成树，也就等价于完美迷宫。这个检查只要几毫秒，但能挡掉绝大多数实现错误。
六、求解与游戏化：BFS 最短路径
生成之后要能玩，需要求解器。迷宫里所有边权重相同，BFS 就是最优解。把 BFS 的前驱数组存下来，就能还原路径并做动画演示。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class MazeSolver {
/** @return 从 (sr,sc) 到 (tr,tc) 的格子序列，不可达则返回空列表 */
public static List<int[]> bfs(MazeGrid grid,
int sr, int sc, int tr, int tc) {
int rows = grid.getRows();
int cols = grid.getCols();
int[] prev = new int[rows * cols];
java.util.Arrays.fill(prev, -1);
boolean[] seen = new boolean[rows * cols];
int start = sr * cols + sc;
int target = tr * cols + tc;
Deque<Integer> queue = new ArrayDeque<>();
queue.add(start);
seen[start] = true;
while (!queue.isEmpty()) {
int cur = queue.poll();
if (cur == target) {
break;
}
int r = cur / cols;
int c = cur % cols;
MazeCell cell = grid.cell(r, c);
// 只走没有墙的方向
if (!cell.hasWall(MazeCell.UP) && r > 0) {
tryVisit((r - 1) * cols + c, cur, seen, prev, queue);
}
if (!cell.hasWall(MazeCell.DOWN) && r + 1 < rows) {
tryVisit((r + 1) * cols + c, cur, seen, prev, queue);
}
if (!cell.hasWall(MazeCell.LEFT) && c > 0) {
tryVisit(r * cols + (c - 1), cur, seen, prev, queue);
}
if (!cell.hasWall(MazeCell.RIGHT) && c + 1 < cols) {
tryVisit(r * cols + (c + 1), cur, seen, prev, queue);
}
}
if (!seen[target]) {
return new ArrayList<>();
}
// 反向还原路径
List<int[]> path = new ArrayList<>();
int node = target;
while (node != -1) {
path.add(0, new int[]{node / cols, node % cols});
if (node == start) {
break;
}
node = prev[node];
}
return path;
}
private static void tryVisit(int next, int from, boolean[] seen,
int[] prev, Deque<Integer> queue) {
if (!seen[next]) {
seen[next] = true;
prev[next] = from;
queue.add(next);
}
}
}
注意 prev 的初值必须是 -1 而不是 0，否则路径回溯会在 0 号格子上死循环。这是 BFS 实现里最常见的隐蔽错误，症状是”路径莫名其妙绕回左上角”。
七、形态质量对比：死胡同比例
不同的生成算法产出的迷宫”手感”差别很大。一个简单的量化指标是死胡同比例（只有一个通路的格子占比）。DFS 回溯通常在 10% 左右，Hunt-and-Kill 约 25%-30%，Prim 可高达 40%。
/**
* 统计死胡同比例：作为迷宫"手感"的量化指标
*/
public class DeadEndStats {
public static double ratio(MazeGrid grid) {
int rows = grid.getRows();
int cols = grid.getCols();
int deadEnds = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
MazeCell cell = grid.cell(r, c);
int open = 0;
if (!cell.hasWall(MazeCell.UP)) {
open++;
}
if (!cell.hasWall(MazeCell.DOWN)) {
open++;
}
if (!cell.hasWall(MazeCell.LEFT)) {
open++;
}
if (!cell.hasWall(MazeCell.RIGHT)) {
open++;
}
if (open == 1) {
deadEnds++;
}
}
}
return (double) deadEnds / (rows * cols);
}
}
若想得到更多死胡同（增加探索感），可以在 Kill 阶段加入”随机回退”——遇到死胡同时不回退到上一个格子，而是随机跳到路径中的某个较早格子继续。若想减少死胡同（增加绕路感），可以在 Kill 阶段偏向于直行，用权重控制方向选择。这两个微调都只需要改动一个方法，不必重写算法。
八、复杂度分析
| 阶段 | 时间复杂度 | 说明 |
|---|---|---|
| Kill 游走 | O(V) 总摊还 | 每条边最多被走一次，格子访问后不再回访 |
| Hunt 扫描 | O(V) | 指针单调前进，不回溯 |
| 双向拆墙 | O(V) | 每格恰好拆一次墙 |
| 完美性校验 | O(V α(V)) | 并查集近线性 |
| BFS 求解 | O(V + E) = O(V) | 树结构下 E = V – 1 |
总计 O(V)，V = rows * cols。空间上只需要一个 visited 布尔数组和墙位掩码，不需要维护边界列表或树集合，这是它相比 Wilson 算法最大的优势。对于 1000×1000 的大迷宫（100 万格），内存约 5 MB，生成时间在普通笔记本上是亚秒级。
九、小结
Hunt-and-Kill 用”随机游走 + 系统扫描”这两个简单阶段，换来了比 DFS 更好的形态与比 Wilson 低得多的实现成本。本文用 Java 完成了从位掩码数据结构、双向拆墙、扫描指针优化、并查集完美性校验，到 BFS 求解与死胡同量化的完整链路。三个最值得记住的工程细节是：拆墙必须双向且用异常暴露错误、扫描指针必须单调前进、prev 初值必须是 -1。这三个地方错了都不会崩溃，只会让迷宫”看起来还行但就是有点怪”，而真正的调试成本全在那种”有点怪”上。
