Java的迷宫生成与求解GUI程序（2）

1、演示视频

2、项目截图

设计说明

3.1 整体架构设计

本项目采用模块化设计，将程序分为三个核心模块：数据模型模块、算法逻辑模块和界面展示模块，各模块之间通过接口交互，降低耦合度。

• 数据模型模块：使用二维数组存储迷宫的单元格状态，定义常量标记不同的单元格类型（墙壁、通路、路径、起点/终点、动画单元格），是程序的核心数据载体。
• 算法逻辑模块：包含DFS迷宫生成、DFS路径求解、BFS路径求解的核心算法，通过预计算步骤队列的方式实现分步动画，避免算法执行与界面渲染的冲突。
• 界面展示模块：使用Swing的JFrame、JPanel、JButton、JLabel等组件搭建图形界面，自定义MazePanel面板负责迷宫的绘制，通过Timer定时器控制动画的分步执行。

3.2 数据结构设计

3.3 界面设计

程序界面采用BorderLayout布局，分为三个部分：

• 北部（North）：控制面板，包含生成迷宫、DFS求解、BFS求解、重置迷宫四个功能按钮，用户可通过点击按钮触发对应操作。
• 中部（Center）：迷宫绘制面板，是程序的核心展示区域，负责绘制迷宫的所有单元格和动画效果。
• 南部（South）：状态栏，显示操作提示和结果信息，使用JLabel组件实现，设置内边距增强视觉效果。

3.4 状态常量设计

为增强代码的可读性和可维护性，定义了以下静态常量标记迷宫单元格的状态：

// 迷宫状态常量（用于二维数组标记） /** 通路 */ private static final int PATH = 0; /** 墙壁 */ private static final int WALL = 1; /** 求解出的路径 */ private static final int SOLVE_PATH = 2; /** 起点/终点 */ private static final int START_END = 3; /** 动画当前访问的单元格（高亮） */ private static final int ANIMATION_CELL = 4;

四、算法说明

4.1 DFS迷宫生成算法（随机回溯法）

4.1.1 算法原理

DFS迷宫生成算法的核心是深度优先遍历+随机回溯，通过遍历迷宫中的所有单元格并打通墙壁，生成单连通的迷宫（任意两个单元格之间有且仅有一条路径）。算法的本质是构建一棵生成树，将所有单元格连接起来，随机选择方向则保证了迷宫的随机性。

4.1.2 算法步骤

1. 初始化迷宫为全墙壁状态，标记起点单元格为已访问，并将其入栈。
2. 获取栈顶单元格，随机打乱四个移动方向（上、下、左、右，步长为2，跳过中间的墙壁）。
3. 遍历打乱后的方向，检查新单元格是否在迷宫范围内且未被访问：
   • 若满足条件，打通当前单元格与新单元格之间的墙壁（将中间的墙壁设为通路）。
   • 将新单元格标记为已访问并入栈，记录步骤后停止遍历方向。
4. 若当前单元格没有未访问的邻接单元格，将其出栈（回溯）。
5. 重复步骤2-4，直到栈为空（所有单元格都被访问）。
6. 标记起点和终点单元格，完成迷宫生成。

4.1.3 算法优化

采用迭代DFS替代递归DFS，避免递归栈溢出问题（尤其是当迷宫尺寸较大时），同时便于分步记录算法的执行步骤，实现动画效果。

4.2 DFS路径求解算法

4.2.1 算法原理

DFS路径求解算法通过深度优先遍历从起点出发，递归访问相邻的单元格，直到找到终点。若当前方向无法到达终点，则进行回溯，取消当前单元格的路径标记，尝试其他方向。该算法能找到任意一条可行路径，但不一定是最短路径。

4.2.2 算法步骤

1. 清空之前的路径标记，初始化访问标记数组。
2. 从起点开始，检查当前单元格是否为终点、超出边界、是墙壁或已访问：
   • 若满足终止条件，返回false。
   • 若到达终点，标记路径并返回true。
3. 标记当前单元格为已访问，并标记为路径（起点/终点除外）。
4. 递归遍历四个方向（上、下、左、右，步长为1），若某个方向返回true，则说明找到路径，直接返回true。
5. 若所有方向都无法找到路径，取消当前单元格的路径标记（回溯），返回false。
6. 遍历结束后，若找到路径则显示路径，否则提示未找到路径。

4.3 BFS路径求解算法

4.3.1 算法原理

BFS路径求解算法通过广度优先遍历从起点出发，逐层访问相邻的单元格，直到找到终点。该算法能保证找到的路径是最短路径，通过记录每个单元格的前驱坐标，可回溯得到从起点到终点的最短路径。

4.3.2 算法步骤

1. 清空之前的路径标记，初始化访问标记数组、前驱数组和BFS队列。
2. 将起点入队并标记为已访问。
3. 取出队列头部的单元格，遍历其四个方向的相邻单元格：
   • 若相邻单元格合法且未访问，标记为已访问并入队，记录其前驱坐标。
   • 若相邻单元格是终点，标记为找到终点并停止遍历。
4. 重复步骤3，直到队列为空或找到终点。
5. 若找到终点，从终点开始回溯前驱坐标，收集路径并反转（从起点到终点），标记路径。
6. 若未找到终点，提示未找到路径。

五、测试说明

5.1 测试环境

• 操作系统：Windows 10/11、Linux、macOS（支持Java的操作系统均可）
• JDK版本：JDK8及以上（推荐JDK8、JDK11、JDK17）
• 开发工具：Eclipse、IntelliJ IDEA、Notepad++（可编译运行Java代码的工具）

5.2 测试步骤

5.2.1 编译运行

1. 将程序代码保存为MazeGUI.java文件。
2. 打开命令行终端，进入代码所在目录，执行编译命令：javac MazeGUI.java（确保JDK环境变量配置正确）。
3. 执行运行命令：java MazeGUI，程序将启动并显示初始迷宫界面。

5.2.2 功能测试

1. 迷宫生成测试：点击“生成迷宫（DFS+动画）”按钮，观察是否能看到分步动画生成迷宫，状态栏是否显示“DFS生成迷宫完成”，迷宫是否为单连通结构。
2. DFS求解测试：点击“DFS求解路径（动画）”按钮，观察是否能看到DFS遍历和回溯的动画，求解完成后是否显示路径长度，路径是否从起点到终点。
3. BFS求解测试：点击“BFS求解路径（动画）”按钮，观察是否能看到BFS的扩散式遍历动画，求解完成后是否显示最短路径长度，路径是否为最短路径。
4. 迷宫重置测试：点击“重置迷宫”按钮，观察迷宫是否恢复为全墙壁状态，状态栏是否显示“迷宫已重置”。
5. 边界测试：修改迷宫行数和列数为更大的奇数（如51行、71列），测试程序是否能正常生成迷宫和求解路径，是否出现栈溢出或卡顿问题。
6. 异常测试：手动修改迷宫结构（如将起点和终点之间的通路改为墙壁），测试程序是否能提示“未找到有效路径”。

5.3 测试结果

在JDK8环境下，程序能正常编译运行，所有功能按钮响应正常，动画效果流畅，状态栏提示准确，迷宫生成和路径求解功能符合预期，边界测试和异常测试均能正确处理。

六、关键代码

6.1 DFS迷宫生成（迭代实现）

precomputeGenerateSteps方法：预计算DFS生成迷宫的步骤

private void precomputeGenerateSteps() { generateSteps.clear(); // 清空之前的步骤 boolean[][] visited = new boolean[ROWS][COLS]; // 标记单元格是否被访问过 Stack stack = new Stack<>(); // DFS的栈，存储当前访问的单元格坐标{row, col} // 起点入栈，标记为已访问 stack.push(new int[]{startRow, startCol}); visited[startRow][startCol] = true; // 记录起点的步骤：先标记为动画高亮，再标记为通路 generateSteps.add(new int[]{startRow, startCol, ANIMATION_CELL}); generateSteps.add(new int[]{startRow, startCol, PATH}); // 定义四个移动方向：上、下、左、右（步长为2，因为要跳过中间的墙壁） int[][] directions = {{-2, 0}, {2, 0}, {0, -2}, {0, 2}}; // DFS核心迭代逻辑：直到栈为空（所有单元格都被访问） while (!stack.isEmpty()) { int[] curr = stack.peek(); // 获取栈顶元素（不弹出） int row = curr[0]; int col = curr[1]; // 随机打乱方向，实现迷宫的随机生成（每次循环都打乱，增加随机性） shuffleArray(directions); boolean hasUnvisited = false; // 标记当前单元格是否有未访问的邻接单元格 // 遍历所有方向 for (int[] dir : directions) { int newRow = row + dir[0]; int newCol = col + dir[1]; // 检查新单元格是否在迷宫范围内，且未被访问 if (newRow > 0 && newRow < ROWS - 1 && newCol > 0 && newCol < COLS - 1 && !visited[newRow][newCol]) { // 计算当前单元格和新单元格之间的墙壁坐标（步长为1） int wallRow = row + dir[0] / 2; int wallCol = col + dir[1] / 2; // 记录步骤：打通中间墙壁（先高亮，再设为通路） generateSteps.add(new int[]{wallRow, wallCol, ANIMATION_CELL}); generateSteps.add(new int[]{wallRow, wallCol, PATH}); // 记录步骤：新单元格（先高亮，再设为通路） generateSteps.add(new int[]{newRow, newCol, ANIMATION_CELL}); generateSteps.add(new int[]{newRow, newCol, PATH}); // 标记新单元格为已访问，并入栈 visited[newRow][newCol] = true; stack.push(new int[]{newRow, newCol}); hasUnvisited = true; // 标记有未访问的单元格，停止遍历方向 break; } } // 如果当前单元格没有未访问的邻接单元格，弹出栈（回溯） if (!hasUnvisited) { stack.pop(); } } // 最后记录起点和终点的标记步骤（确保显示为红色） generateSteps.add(new int[]{startRow, startCol, START_END}); generateSteps.add(new int[]{endRow, endCol, START_END}); }

6.2 DFS路径求解（递归实现）

dfsSolveRecordSteps方法：递归记录DFS求解路径的步骤

private boolean dfsSolveRecordSteps(int row, int col, boolean[][] visited) { // 终止条件1：超出迷宫边界、是墙壁、已访问，返回false if (row < 0 || row >= ROWS || col < 0 || col >= COLS || maze[row][col] == WALL || visited[row][col]) { return false; } // 记录步骤：当前单元格被访问（高亮） solveSteps.add(new int[]{row, col, ANIMATION_CELL}); visited[row][col] = true; // 标记为已访问 // 终止条件2：到达终点，记录路径标记步骤，返回true if (row == endRow && col == endCol) { solveSteps.add(new int[]{row, col, SOLVE_PATH}); return true; } // 记录步骤：标记为路径（起点/终点除外） if (maze[row][col] != START_END) { solveSteps.add(new int[]{row, col, SOLVE_PATH}); } // 遍历四个方向：上、下、左、右（步长为1） int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int[] dir : directions) { // 递归访问相邻单元格，若找到路径则返回true if (dfsSolveRecordSteps(row + dir[0], col + dir[1], visited)) { return true; } } // 回溯：当前方向未找到路径，取消路径标记（起点/终点除外） if (maze[row][col] != START_END) { solveSteps.add(new int[]{row, col, PATH}); // 恢复为普通通路 } return false; }

6.3 BFS路径求解（迭代实现）

precomputeBFSSolveSteps方法：预计算BFS求解路径的步骤

private void precomputeBFSSolveSteps() { solveSteps.clear(); clearPath(); int[][] prev = new int[ROWS * COLS][2]; // 存储每个单元格的前驱坐标{row, col} // 初始化前驱数组为-1（表示无前驱） Arrays.stream(prev).forEach(a -> Arrays.fill(a, -1)); boolean[][] visited = new boolean[ROWS][COLS]; Queue queue = new LinkedList<>(); // BFS的队列 boolean found = false; // 是否找到终点 // 起点入队，标记为已访问 queue.offer(new int[]{startRow, startCol}); visited[startRow][startCol] = true; // 定义四个移动方向 int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 第一步：BFS遍历，记录访问步骤和前驱 while (!queue.isEmpty() && !found) { int[] curr = queue.poll(); int row = curr[0]; int col = curr[1]; // 记录当前单元格的访问步骤（高亮） solveSteps.add(new int[]{row, col, ANIMATION_CELL}); // 遍历相邻单元格 for (int[] dir : directions) { int newRow = row + dir[0]; int newCol = col + dir[1]; // 检查单元格是否合法且未访问 if (newRow >= 0 && newRow < ROWS && newCol >= 0 && newCol < COLS && maze[newRow][newCol] != WALL && !visited[newRow][newCol]) { visited[newRow][newCol] = true; queue.offer(new int[]{newRow, newCol}); // 记录前驱：当前单元格是新单元格的前驱 prev[newRow * COLS + newCol][0] = row; prev[newRow * COLS + newCol][1] = col; // 记录新单元格的访问步骤 solveSteps.add(new int[]{newRow, newCol, ANIMATION_CELL}); // 找到终点，停止遍历 if (newRow == endRow && newCol == endCol) { found = true; break; } } } } // 第二步：回溯前驱，记录路径标记步骤 if (found) { List path = new ArrayList<>(); int row = endRow; int col = endCol; // 从终点回溯到起点，收集路径坐标 while (row != -1 && col != -1 && (row != startRow || col != startCol)) { path.add(new int[]{row, col}); // 获取前驱坐标 int tempRow = prev[row * COLS + col][0]; int tempCol = prev[row * COLS + col][1]; row = tempRow; col = tempCol; } path.add(new int[]{startRow, startCol}); // 添加起点 Collections.reverse(path); // 反转路径，从起点到终点 // 记录路径标记步骤 for (int[] p : path) { solveSteps.add(new int[]{p[0], p[1], SOLVE_PATH}); } } else { // 未找到路径，添加特殊标记 solveSteps.add(new int[]{-1, -1, -1}); } }

6.4 迷宫绘制面板

MazePanel类：自定义面板绘制迷宫

class MazePanel extends JPanel { private static final long serialVersionUID = 1L; @Override protected void paintComponent(Graphics g) { super.paintComponent(g); // 调用父类方法，确保面板正常绘制 // 遍历所有单元格，逐个绘制 for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLS; j++) { // 计算单元格的像素坐标（x:列*单元格大小，y:行*单元格大小） int x = j * CELL_SIZE; int y = i * CELL_SIZE; // 根据单元格状态设置颜色 switch (maze[i][j]) { case WALL: g.setColor(Color.BLACK); // 墙壁：黑色 break; case START_END: g.setColor(Color.RED); // 起点/终点：红色 break; case SOLVE_PATH: g.setColor(Color.GREEN); // 求解路径：绿色 break; case ANIMATION_CELL: g.setColor(Color.YELLOW); // 动画高亮：黄色 break; default: // PATH g.setColor(Color.WHITE); // 普通通路：白色 break; } // 填充单元格的矩形区域 g.fillRect(x, y, CELL_SIZE, CELL_SIZE); // 绘制单元格的灰色边框，增强视觉效果 g.setColor(Color.GRAY); g.drawRect(x, y, CELL_SIZE, CELL_SIZE); } } } }