游戏简介与算法核心
迷宫生成与求解是计算机图形学和算法教学中的经典主题。完美迷宫指任意两点间有且仅有一条路径的迷宫，等价于一棵生成树。本文用Java实现DFS回溯法生成完美迷宫，以及BFS求解最短路径，同时介绍Wilson随机游走算法生成均匀随机迷宫。
迷宫的图论表示
将迷宫视为网格图，每个格子是一个节点，相邻格子间有边。完美迷宫对应于此网格图的生成树——包含所有节点且无环的连通子图。
import java.util.*;
/**
* 方向枚举，包含行列偏移
*/
enum Direction {
NORTH(-1, 0, 'N'), SOUTH(1, 0, 'S'),
EAST(0, 1, 'E'), WEST(0, -1, 'W');
final int dr, dc;
final char symbol;
Direction opposite;
static {
NORTH.opposite = SOUTH;
SOUTH.opposite = NORTH;
EAST.opposite = WEST;
WEST.opposite = EAST;
}
Direction(int dr, int dc, char symbol) {
this.dr = dr; this.dc = dc; this.symbol = symbol;
}
}
/**
* 迷宫格子
*/
class MazeCell {
final int row, col;
boolean visited = false;
// 四面墙：true=有墙, false=无墙（通路）
boolean northWall = true, southWall = true, eastWall = true, westWall = true;
MazeCell(int row, int col) {
this.row = row; this.col = col;
}
void removeWall(Direction dir) {
switch (dir) {
case NORTH: northWall = false; break;
case SOUTH: southWall = false; break;
case EAST: eastWall = false; break;
case WEST: westWall = false; break;
}
}
boolean hasWall(Direction dir) {
switch (dir) {
case NORTH: return northWall;
case SOUTH: return southWall;
case EAST: return eastWall;
case WEST: return westWall;
}
return true;
}
}
/**
* 迷宫类
*/
class Maze {
private final int rows, cols;
private final MazeCell[][] grid;
public Maze(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.grid = new MazeCell[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
grid[r][c] = new MazeCell(r, c);
}
}
}
public boolean isValid(int r, int c) {
return r >= 0 && r < rows && c >= 0 && c < cols;
}
public MazeCell get(int r, int c) { return grid[r][c]; }
public int getRows() { return rows; }
public int getCols() { return cols; }
/**
* 打通两个相邻格子之间的墙
*/
public void carve(int r, int c, Direction dir) {
if (!isValid(r, c)) return;
MazeCell cell = grid[r][c];
cell.removeWall(dir);
int nr = r + dir.dr, nc = c + dir.dc;
if (isValid(nr, nc)) {
MazeCell neighbor = grid[nr][nc];
neighbor.removeWall(dir.opposite);
}
}
/**
* 检查两个相邻格子之间是否有通路
*/
public boolean isPassable(int r, int c, Direction dir) {
if (!isValid(r, c)) return false;
return !grid[r][c].hasWall(dir);
}
/**
* 获取某格子的未访问邻居及方向
*/
public List<Map.Entry<MazeCell, Direction>> getUnvisitedNeighbors(int r, int c) {
List<Map.Entry<MazeCell, Direction>> neighbors = new ArrayList<>();
for (Direction dir : Direction.values()) {
int nr = r + dir.dr, nc = c + dir.dc;
if (isValid(nr, nc) && !grid[nr][nc].visited) {
neighbors.add(new AbstractMap.SimpleEntry<>(grid[nr][nc], dir));
}
}
return neighbors;
}
/**
* 获取某格子的已访问邻居（用于求解）
*/
public List<MazeCell> getAccessibleNeighbors(int r, int c) {
List<MazeCell> neighbors = new ArrayList<>();
for (Direction dir : Direction.values()) {
if (isPassable(r, c, dir)) {
int nr = r + dir.dr, nc = c + dir.dc;
if (isValid(nr, nc)) neighbors.add(grid[nr][nc]);
}
}
return neighbors;
}
/**
* 重置访问标记
*/
public void resetVisited() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
grid[r][c].visited = false;
}
}
}
/**
* 文本可视化
*/
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
// 顶边
sb.append("+");
for (int c = 0; c < cols; c++) sb.append("---+");
sb.append("\n");
for (int r = 0; r < rows; r++) {
// 格子内容行
sb.append("|");
for (int c = 0; c < cols; c++) {
sb.append(" ");
sb.append(grid[r][c].eastWall ? "|" : " ");
}
sb.append("\n");
// 底边行
sb.append("+");
for (int c = 0; c < cols; c++) {
sb.append(grid[r][c].southWall ? "---+" : " +");
}
sb.append("\n");
}
return sb.toString();
}
/**
* 带路径的可视化
*/
public String toStringWithPath(Set<MazeCell> path) {
StringBuilder sb = new StringBuilder();
sb.append("+");
for (int c = 0; c < cols; c++) sb.append("---+");
sb.append("\n");
for (int r = 0; r < rows; r++) {
sb.append("|");
for (int c = 0; c < cols; c++) {
String content = path.contains(grid[r][c]) ? " * " : " ";
sb.append(content);
sb.append(grid[r][c].eastWall ? "|" : " ");
}
sb.append("\n");
sb.append("+");
for (int c = 0; c < cols; c++) {
sb.append(grid[r][c].southWall ? "---+" : " +");
}
sb.append("\n");
}
return sb.toString();
}
}
DFS回溯法生成迷宫
/**
* 深度优先搜索回溯法生成完美迷宫
* 算法：从起点开始，随机选择未访问邻居，打通墙壁并递归，
* 当无未访问邻居时回溯，直到所有格子都被访问
*/
class DFSMazeGenerator {
private final Random random = new Random();
public void generate(Maze maze, int startRow, int startCol) {
maze.resetVisited();
dfs(maze, startRow, startCol);
}
private void dfs(Maze maze, int r, int c) {
MazeCell cell = maze.get(r, c);
cell.visited = true;
// 随机打乱邻居顺序，保证迷宫随机性
List<Map.Entry<MazeCell, Direction>> neighbors =
maze.getUnvisitedNeighbors(r, c);
Collections.shuffle(neighbors, random);
for (Map.Entry<MazeCell, Direction> entry : neighbors) {
MazeCell neighbor = entry.getKey();
Direction dir = entry.getValue();
if (!neighbor.visited) {
// 打通当前格子和邻居之间的墙
maze.carve(r, c, dir);
// 递归访问邻居
dfs(maze, neighbor.row, neighbor.col);
}
}
}
}
BFS最短路径求解
/**
* BFS最短路径求解器
*/
class BFSSolver {
/**
* 使用BFS寻找从起点到终点的最短路径
* 返回路径上的格子集合（不包含起点和终点时需单独处理）
*/
public List<MazeCell> solve(Maze maze, int startRow, int startCol,
int endRow, int endCol) {
maze.resetVisited();
Queue<MazeCell> queue = new LinkedList<>();
Map<MazeCell, MazeCell> parent = new HashMap<>();
MazeCell start = maze.get(startRow, startCol);
MazeCell end = maze.get(endRow, endCol);
start.visited = true;
queue.add(start);
while (!queue.isEmpty()) {
MazeCell current = queue.poll();
if (current == end) {
// 找到终点，重建路径
return reconstructPath(parent, start, end);
}
for (MazeCell neighbor : maze.getAccessibleNeighbors(current.row, current.col)) {
if (!neighbor.visited) {
neighbor.visited = true;
parent.put(neighbor, current);
queue.add(neighbor);
}
}
}
return Collections.emptyList(); // 无解
}
private List<MazeCell> reconstructPath(Map<MazeCell, MazeCell> parent,
MazeCell start, MazeCell end) {
List<MazeCell> path = new ArrayList<>();
MazeCell current = end;
while (current != null) {
path.add(current);
if (current == start) break;
current = parent.get(current);
}
Collections.reverse(path);
return path;
}
}
Wilson随机游走算法
/**
* Wilson算法：通过循环擦除随机游走生成均匀随机生成树
* 即所有可能的生成树被等概率选中，产生最"公平"的随机迷宫
*/
class WilsonMazeGenerator {
private final Random random = new Random();
public void generate(Maze maze) {
int rows = maze.getRows();
int cols = maze.getCols();
// 先重置所有墙
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
MazeCell cell = maze.get(r, c);
cell.northWall = true; cell.southWall = true;
cell.eastWall = true; cell.westWall = true;
}
}
Set<MazeCell> inTree = new HashSet<>();
// 随机选一个起点加入树中
MazeCell start = maze.get(random.nextInt(rows), random.nextInt(cols));
inTree.add(start);
// 对每个不在树中的格子，执行循环擦除随机游走
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
MazeCell cell = maze.get(r, c);
if (inTree.contains(cell)) continue;
// 从当前格子开始随机游走，直到碰到树中的格子
List<MazeCell> walk = loopErasedRandomWalk(maze, cell, inTree);
// 将路径加入生成树
for (int i = 0; i < walk.size() - 1; i++) {
MazeCell from = walk.get(i);
MazeCell to = walk.get(i + 1);
carveBetween(maze, from, to);
inTree.add(from);
}
inTree.add(walk.get(walk.size() - 1));
}
}
}
/**
* 循环擦除随机游走
*/
private List<MazeCell> loopErasedRandomWalk(Maze maze, MazeCell start,
Set<MazeCell> targetSet) {
Map<MazeCell, MazeCell> nextInWalk = new HashMap<>();
MazeCell current = start;
while (!targetSet.contains(current)) {
List<MazeCell> neighbors = getAllNeighbors(maze, current);
MazeCell next = neighbors.get(random.nextInt(neighbors.size()));
// 如果形成环，擦除环（覆盖掉环的起点）
nextInWalk.put(current, next);
current = next;
}
// 重建无环路径
List<MazeCell> path = new ArrayList<>();
current = start;
while (true) {
path.add(current);
if (targetSet.contains(current)) break;
current = nextInWalk.get(current);
}
return path;
}
private List<MazeCell> getAllNeighbors(Maze maze, MazeCell cell) {
List<MazeCell> neighbors = new ArrayList<>();
for (Direction dir : Direction.values()) {
int nr = cell.row + dir.dr, nc = cell.col + dir.dc;
if (maze.isValid(nr, nc)) neighbors.add(maze.get(nr, nc));
}
return neighbors;
}
private void carveBetween(Maze maze, MazeCell a, MazeCell b) {
for (Direction dir : Direction.values()) {
if (a.row + dir.dr == b.row && a.col + dir.dc == b.col) {
maze.carve(a.row, a.col, dir);
return;
}
}
}
}
A*启发式求解（扩展）
/**
* A*求解器，使用曼哈顿距离作为启发函数
*/
class AStarSolver {
public List<MazeCell> solve(Maze maze, int startRow, int startCol,
int endRow, int endCol) {
maze.resetVisited();
PriorityQueue<AStarNode> openSet = new PriorityQueue<>(
Comparator.comparingInt(n -> n.fScore));
Map<MazeCell, MazeCell> parent = new HashMap<>();
Map<MazeCell, Integer> gScore = new HashMap<>();
MazeCell start = maze.get(startRow, startCol);
MazeCell end = maze.get(endRow, endCol);
gScore.put(start, 0);
openSet.add(new AStarNode(start, heuristic(start, end)));
while (!openSet.isEmpty()) {
AStarNode current = openSet.poll();
MazeCell cell = current.cell;
if (cell == end) {
return reconstructPath(parent, start, end);
}
if (cell.visited) continue;
cell.visited = true;
int currentG = gScore.getOrDefault(cell, Integer.MAX_VALUE);
for (MazeCell neighbor : maze.getAccessibleNeighbors(cell.row, cell.col)) {
int tentativeG = currentG + 1;
int neighborG = gScore.getOrDefault(neighbor, Integer.MAX_VALUE);
if (tentativeG < neighborG) {
parent.put(neighbor, cell);
gScore.put(neighbor, tentativeG);
int fScore = tentativeG + heuristic(neighbor, end);
openSet.add(new AStarNode(neighbor, fScore));
}
}
}
return Collections.emptyList();
}
private int heuristic(MazeCell a, MazeCell b) {
return Math.abs(a.row - b.row) + Math.abs(a.col - b.col); // 曼哈顿距离
}
private List<MazeCell> reconstructPath(Map<MazeCell, MazeCell> parent,
MazeCell start, MazeCell end) {
List<MazeCell> path = new ArrayList<>();
MazeCell current = end;
while (current != null) {
path.add(current);
if (current == start) break;
current = parent.get(current);
}
Collections.reverse(path);
return path;
}
private static class AStarNode {
final MazeCell cell;
final int fScore;
AStarNode(MazeCell cell, int fScore) {
this.cell = cell;
this.fScore = fScore;
}
}
}
主程序与演示
public class MazeMain {
public static void main(String[] args) {
int rows = 15, cols = 25;
System.out.println("=== 完美迷宫生成与求解 ===\n");
// 1. DFS生成迷宫
System.out.println("--- DFS回溯法生成迷宫 ---");
Maze dfsMaze = new Maze(rows, cols);
DFSMazeGenerator dfsGen = new DFSMazeGenerator();
dfsGen.generate(dfsMaze, 0, 0);
System.out.println(dfsMaze);
// 2. BFS求解
System.out.println("--- BFS最短路径求解 ---");
BFSSolver bfs = new BFSSolver();
List<MazeCell> bfsPath = bfs.solve(dfsMaze, 0, 0, rows-1, cols-1);
System.out.println("BFS路径长度: " + bfsPath.size());
Set<MazeCell> pathSet = new HashSet<>(bfsPath);
System.out.println(dfsMaze.toStringWithPath(pathSet));
// 3. Wilson算法生成迷宫
System.out.println("--- Wilson随机游走算法生成迷宫 ---");
Maze wilsonMaze = new Maze(rows, cols);
WilsonMazeGenerator wilsonGen = new WilsonMazeGenerator();
wilsonGen.generate(wilsonMaze);
System.out.println(wilsonMaze);
// 4. A*求解
System.out.println("--- A*最短路径求解 ---");
AStarSolver astar = new AStarSolver();
List<MazeCell> astarPath = astar.solve(wilsonMaze, 0, 0, rows-1, cols-1);
System.out.println("A*路径长度: " + astarPath.size());
Set<MazeCell> astarPathSet = new HashSet<>(astarPath);
System.out.println(wilsonMaze.toStringWithPath(astarPathSet));
// 5. 算法对比
System.out.println("\n=== 算法特性对比 ===");
System.out.println("DFS生成：快速O(N)，但有明显长廊偏向");
System.out.println("Wilson生成：均匀随机O(N^2)，但最公平");
System.out.println("BFS求解：保证最短路径，时间O(N)，空间O(N)");
System.out.println("A*求解：通常比BFS快，最坏情况相同");
}
}
算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| DFS生成迷宫 | O(V) = O(R×C) | O(V) 递归栈 |
| Wilson生成迷宫 | O(V²) 期望 | O(V) |
| BFS最短路径 | O(V) | O(V) |
| A*最短路径 | O(V log V) ~ O(V) | O(V) |
| 路径重建 | O(L)，L=路径长度 | O(L) |
| 可视化输出 | O(V) | O(1) |
其中V = R×C 为格子总数。
总结
本文实现了完美迷宫的生成与求解系统，核心算法包括：
- DFS回溯生成：将迷宫视为生成树，通过深度优先搜索随机选择邻居并打通墙壁，形成有偏但快速的随机迷宫
- Wilson随机游走：通过循环擦除随机游走产生均匀随机生成树，确保每个可能的迷宫结构等概率出现，是最公平的随机生成算法
- BFS最短路径：在无权图上进行广度优先搜索，保证找到从入口到出口的最短路径
- A*启发搜索：使用曼哈顿距离作为启发函数，在大型迷宫中通常比BFS更高效
迷宫生成算法的本质是在网格图上构建生成树。DFS方法偏好产生长走廊，而Wilson算法则产生更均匀分布的迷宫结构。求解方面，BFS适合教学和理解图遍历，A*则在实际游戏中更为实用。
