# maze-demo **Repository Path**: hhf002/maze-demo ## Basic Information - **Project Name**: maze-demo - **Description**: 这是一个用Java实现的迷宫生成和寻路算法演示项目，包含了多种经典算法的实现和对比 - **Primary Language**: Java - **License**: MIT - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2025-09-10 - **Last Updated**: 2025-09-10 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 迷宫生成和寻路算法演示项目 这是一个用Java实现的迷宫生成和寻路算法演示项目，包含了多种经典算法的实现和对比。 ## 项目特色 - 🏗️ **两种迷宫生成算法**：Kruskal算法（并查集）和递归分割法 - 🔍 **三种寻路算法**：DFS（深度优先）、BFS（广度优先）、A*（启发式搜索） - 📊 **性能对比**：路径长度、访问节点数、执行时间的详细对比 - 🎨 **双重可视化**：ASCII控制台输出 + Swing GUI动画演示 - 🎬 **寻路动画**：实时可视化算法执行过程，支持暂停、停止、速度控制 - 💻 **图形界面**：友好的Swing GUI，支持交互式操作和参数调整 - ✅ **完整测试**：JUnit5单元测试和集成测试 - 🛠️ **工程实践**：标准Maven结构、日志、异常处理、分包分层 ## 算法实现 ### 迷宫生成算法 #### 1. Kruskal算法（并查集） - **原理**：将迷宫看作图，用最小生成树生成完美迷宫 - **特点**：生成的迷宫较为复杂，分叉较多 - **时间复杂度**：O(E log E)，其中E是边数 #### 2. 递归分割法 - **原理**：递归地将区域分割，在分割线上留通道 - **特点**：生成的迷宫有明显的房间结构 - **时间复杂度**：O(N)，其中N是单元格数 ### 寻路算法 #### 1. DFS（深度优先搜索） - **实现**：使用栈的迭代实现 - **特点**：优先探索深处，找到的路径不一定最短 - **空间复杂度**：O(h)，其中h是最大深度 #### 2. BFS（广度优先搜索） - **实现**：使用队列的实现 - **特点**：按层次搜索，保证找到最短路径 - **空间复杂度**：O(w)，其中w是最大宽度 #### 3. A*算法 - **实现**：使用优先队列，f(n) = g(n) + h(n) - **特点**：结合最优性和效率，启发式函数为曼哈顿距离 - **空间复杂度**：O(b^d)，其中b是分支因子，d是解的深度 ## 项目结构 ``` maze-demo/ ├── src/main/java/com/example/maze/ │ ├── generator/ # 迷宫生成器 │ │ ├── MazeGenerator.java │ │ ├── KruskalGenerator.java │ │ └── DivisionGenerator.java │ ├── solver/ # 寻路算法 │ │ ├── MazeSolver.java │ │ ├── SolverResult.java │ │ ├── DFSSolver.java │ │ ├── BFSSolver.java │ │ └── AStarSolver.java │ ├── swing/ # GUI组件（新增） │ │ ├── MazeSwingApp.java # 主GUI应用 │ │ ├── MazePanel.java # 迷宫显示面板 │ │ ├── SwingAnimationController.java # 动画控制器 │ │ ├── AnimatedMazeSolver.java # 动画求解器接口 │ │ ├── SwingAnimatedDFSSolver.java # DFS动画实现 │ │ ├── SwingAnimatedBFSSolver.java # BFS动画实现 │ │ ├── SwingAnimatedAStarSolver.java # A*动画实现 │ │ ├── SolverStep.java # 求解步骤 │ │ ├── AnimatedSolverResult.java # 动画求解结果 │ │ └── Consumer.java # 兼容性接口 │ ├── model/ # 数据模型 │ │ ├── Coordinate.java │ │ ├── Cell.java │ │ └── Maze.java │ ├── util/ # 工具类 │ │ ├── UnionFind.java │ │ └── MazeVisualizer.java │ └── Main.java # 控制台程序入口 ├── src/test/java/ # JUnit5测试 └── README.md ``` ## 快速开始 ### 环境要求 - Java 8+ 包含 Java 8 - Maven 3.6+ ### 编译和运行 ```bash # 编译项目 mvn clean compile # 运行测试 mvn test # 打包 mvn package # 运行程序 java -jar target/maze-demo-1.0.0.jar [width] [height] [algorithm] ``` ### 使用示例 #### 控制台模式 ```bash # 生成默认20x20迷宫，运行所有算法 java -jar maze-demo-1.0.0.jar # 生成30x20迷宫，使用A*算法 java -jar maze-demo-1.0.0.jar 30 20 a-star # 生成40x40迷宫，运行所有算法，启用交互模式 java -jar maze-demo-1.0.0.jar 40 40 all -i ``` #### GUI模式（推荐） ```bash # 启动GUI界面 java -cp target/maze-demo-1.0.0.jar com.example.maze.swing.MazeSwingApp ``` 或者 ```bash java -jar target/maze-demo-2.0.0.jar ``` 或者直接运行编译后的类： ```bash # 开发环境中直接运行 mvn compile exec:java -Dexec.mainClass="com.example.maze.swing.MazeSwingApp" ``` ### 参数说明 - `width`: 迷宫宽度 (5-100，默认20) - `height`: 迷宫高度 (5-100，默认20) - `algorithm`: 寻路算法 - `dfs`: 深度优先搜索 - `bfs`: 广度优先搜索 - `a-star`: A*算法 - `all`: 运行所有算法对比（默认） - `-i`: 启用交互模式 ### GUI界面功能 #### 🎬 寻路动画演示 - **实时可视化**：观察算法如何逐步探索迷宫 - **动画控制**：支持开始、暂停、停止、重置操作 - **速度调节**：可调节动画播放速度（10ms-1000ms） - **步骤显示**：实时显示当前算法执行的步骤 #### 🎛️ 交互式控制 - **参数设置**：图形化设置迷宫尺寸和算法选择 - **即时生成**：一键生成新的迷宫 - **算法切换**：轻松切换不同的寻路算法 - **结果展示**：详细显示算法执行结果和性能数据 #### 🎨 可视化特性 - **彩色显示**：不同颜色表示墙、路径、访问过的节点、解路径 - **高亮当前位置**：实时显示算法当前探索的位置 - **路径追踪**：清晰显示最终找到的路径 - **状态反馈**：实时状态信息和操作提示 ## 演示效果 ### 💻 GUI界面演示 #### 主界面功能 GUI版本提供了更直观的可视化体验： **控制面板**： - 迷宫参数设置（宽度、高度、生成算法） - 寻路算法选择（DFS、BFS、A*） - 动画速度控制滑块（10ms-1000ms） - 操作按钮（生成、开始、暂停、停止、重置） **可视化特性**： - 🟩 **绿色**：可通行路径 - ⬛ **黑色**：墙壁 - 🔴 **红色**：起点 - 🔵 **蓝色**：终点 - 🟡 **黄色**：当前探索位置 - 🟢 **浅绿**：已访问节点 - 🔶 **紫色**：最终解路径 **动画效果**： - 实时高亮显示算法当前探索的位置 - 逐步显示算法的搜索过程和访问轨迹 - 最终路径高亮显示，清晰展示找到的路径 - 支持随时暂停和继续观察 **状态信息**： - 实时显示算法执行状态 - 当前步骤描述 - 详细的结果统计（路径长度、访问节点、执行时间等） #### 操作流程 1. **生成迷宫**：设置参数后点击“生成迷宫” 2. **选择算法**：从下拉菜单中选择DFS、BFS或A* 3. **调节速度**：拖动滑块设置合适的动画速度 4. **开始演示**：点击“开始寻路”观察算法执行 5. **控制演示**：随时暂停、继续或停止动画 ### 📟 Swing输出演示 DFS算法寻路动画 ![dfs.gif](dfs.gif) BFS算法寻路动画 ![bfs.gif](bfs.gif) A*算法寻路动画 ![astar.gif](astar.gif) ### 📟 控制台输出演示 ### 迷宫可视化 ``` ================================================== 迷宫大小: 20 x 20 生成算法: Division 起点: (13,7) 终点: (18,5) ================================================== 原始迷宫 ---- ┌────────────────────┐ │████████████████████│ │█ █ █ █ █ █ █│ │█ █ █ █ █ █ █ █│ │█ █ █ █ █ █│ │█ █ █ █ ████ ██│ │█ █████████ █ █│ │█ █ █ █ █████ █│ │█ █ █ █ █ █ █ █│ │█ █ █ █ █ █ ██│ │█ █ ██ ██ █ █ █│ │█ █ █ █ █ █ █│ │███████ ███████ ████│ │█ █ █ █ █ █│ │█ █ S█ █ ████ ██│ │██ ██ █ █ █ █│ │█ █ ███ █ █ █│ │█ ████ █│ │██ ██ █ █ █ █│ │█ █E █ █ █ █│ │████████████████████│ └────────────────────┘ === 寻路算法对比 === 算法 状态 路径长度 访问节点 耗时(ms) ──────────────────────────────────────────── DFS 成功 10 109 2 BFS 成功 8 24 2 A* 成功 8 10 5 === 各算法路径对比 === DFS算法路径 (长度: 10) ---------------- ┌────────────────────┐ │████████████████████│ │█ █ █ █ █ █ █│ │█ █ █ █ █ █ █ █│ │█ █ █ █ █ █│ │█ █ █ █ ████ ██│ │█ █████████ █ █│ │█ █ █ █ █████ █│ │█ █ █ █ █ █ █ █│ │█ █ █ █ █ █ ██│ │█ █ ██ ██ █ █ █│ │█ █ █ █ █ █ █│ │███████ ███████ ████│ │█ █DDD█ █ █ █│ │█ █D S█ █ ████ ██│ │██ ██D █ █ █ █│ │█ █D███ █ █ █│ │█ D ████ █│ │██ ██D █ █ █ █│ │█ █E █ █ █ █│ │████████████████████│ └────────────────────┘ BFS算法路径 (长度: 8) --------------- ┌────────────────────┐ │████████████████████│ │█ █ █ █ █ █ █│ │█ █ █ █ █ █ █ █│ │█ █ █ █ █ █│ │█ █ █ █ ████ ██│ │█ █████████ █ █│ │█ █ █ █ █████ █│ │█ █ █ █ █ █ █ █│ │█ █ █ █ █ █ ██│ │█ █ ██ ██ █ █ █│ │█ █ █ █ █ █ █│ │███████ ███████ ████│ │█ █ █ █ █ █│ │█ █ S█ █ ████ ██│ │██ ██BBB█ █ █ █│ │█ █B███ █ █ █│ │█ B ████ █│ │██ ██B █ █ █ █│ │█ █E █ █ █ █│ │████████████████████│ └────────────────────┘ A*算法路径 (长度: 8) -------------- ┌────────────────────┐ │████████████████████│ │█ █ █ █ █ █ █│ │█ █ █ █ █ █ █ █│ │█ █ █ █ █ █│ │█ █ █ █ ████ ██│ │█ █████████ █ █│ │█ █ █ █ █████ █│ │█ █ █ █ █ █ █ █│ │█ █ █ █ █ █ ██│ │█ █ ██ ██ █ █ █│ │█ █ █ █ █ █ █│ │███████ ███████ ████│ │█ █ █ █ █ █│ │█ █ S█ █ ████ ██│ │██ ██AAA█ █ █ █│ │█ █A███ █ █ █│ │█ A ████ █│ │██ ██A █ █ █ █│ │█ █E █ █ █ █│ │████████████████████│ └────────────────────┘ === 所有路径合并显示 === 所有算法路径对比 -------- ┌────────────────────┐ │████████████████████│ │█ █ █ █ █ █ █│ │█ █ █ █ █ █ █ █│ │█ █ █ █ █ █│ │█ █ █ █ ████ ██│ │█ █████████ █ █│ │█ █ █ █ █████ █│ │█ █ █ █ █ █ █ █│ │█ █ █ █ █ █ ██│ │█ █ ██ ██ █ █ █│ │█ █ █ █ █ █ █│ │███████ ███████ ████│ │█ █DDD█ █ █ █│ │█ █D S█ █ ████ ██│ │██ ██DBB█ █ █ █│ │█ █D███ █ █ █│ │█ D ████ █│ │██ ██D █ █ █ █│ │█ █E █ █ █ █│ │████████████████████│ └────────────────────┘ 路径统计: DFS: D 标记, 长度 10 BFS: B 标记, 长度 8 A*: A 标记, 长度 8 === 图例 === █ - 墙 - 通路 S - 起点 E - 终点 . - 已访问 * - 解路径 ``` ### 算法性能对比 典型的性能对比结果： | 算法 | 路径长度 | 访问节点 | 特点 | |------|----------|----------|------| | DFS | 较长 | 中等 | 快速但非最优 | | BFS | **最短** | 较多 | 保证最优路径 | | A* | **最短** | **最少** | 最优且高效 | ## 核心特性 ### 1. 完美迷宫生成 - 任意两点间有且仅有一条路径 - 无环路，保证迷宫的挑战性 - 随机生成，每次运行结果不同 ### 2. 算法可视化 - ASCII字符显示迷宫结构 - 不同字符表示墙、通路、起终点 - 寻路过程可视化（访问节点和最终路径） ### 3. 性能分析 - 路径长度对比 - 访问节点数统计 - 执行时间测量 - 算法效率评估 ### 4. 交互模式 - 实时选择不同算法 - 重置迷宫状态 - 动态对比效果 ### 5. GUI动画演示 - 可视化算法执行过程 - 支持暂停/继续/停止控制 - 可调节动画播放速度 - 实时显示执行状态和统计信息 ## 开发特点 ### 工程实践 - **分包分层**：按功能模块组织代码结构 - **接口设计**：生成器和求解器都实现统一接口 - **异常处理**：完善的输入验证和错误处理 - **日志记录**：使用SLF4J+Logback记录关键操作 - **单元测试**：JUnit5测试覆盖核心功能 ### 设计模式 - **策略模式**：不同的生成和寻路算法 - **模板方法**：统一的算法执行流程 - **工厂模式**：算法选择和创建 ### 代码质量 - 详细的JavaDoc文档 - 一致的代码风格 - 合理的命名规范 - 适当的注释说明 ## 扩展功能 该项目已经实现了丰富的功能，同时可以很容易地继续扩展： ### 已实现的高级功能 ✅ **图形界面**：Swing GUI动画演示 ✅ **寻路动画**：实时可视化算法执行过程 ✅ **交互控制**：暂停、停止、速度调节 ✅ **多种可视化**：ASCII控制台 + GUI界面 ### 未来可扩展方向 1. **新的生成算法**：Prim算法、Wilson算法等 2. **新的寻路算法**：Dijkstra、双向BFS等 3. **更多图形界面功能**：JavaFX版本、更丰富的动画效果 4. **迷宫类型**：支持不同的迷宫拓扑 5. **输出格式**：图片输出、视频导出等 6. **性能优化**：多线程处理、更高效的数据结构 ## 学习价值 这个项目非常适合学习： - **数据结构**：栈、队列、优先队列、并查集 - **算法设计**：搜索算法、图算法、启发式算法 - **Java编程**：面向对象设计、泛型、集合框架 - **GUI开发**：Swing组件、事件处理、动画实现 - **软件工程**：项目结构、测试驱动开发、文档编写 - **可视化技术**：算法动画、交互式演示、用户体验设计 - **性能分析**：算法复杂度、性能对比、优化技巧 ## 许可证 MIT License ## 作者 maze-demo 项目团队 --- ## 🎆 特别推荐：GUI动画演示 新增的 [`MazeSwingApp`](src/main/java/com/example/maze/swing/MazeSwingApp.java) 提供了突破性的可视化体验： - 🔄 **实时动画**：观察算法如何逐步搜索迷宫，每一步都清晰可见 - ⏸️ **灵活控制**：随时暂停来仔细观察算法在某个特定时刻的状态 - 🎯 **教学价值**：完美展示 DFS 的深度搜索、BFS 的层次遭历、A* 的智能搜索 - 📡 **性能对比**：直观对比不同算法的效率和路径质量 这不仅仅是一个演示项目，更是一个绝佳的算法学习工具！ *这个项目展示了经典算法在实际问题中的应用，通过可视化演示帮助理解不同算法的特点和性能差异。*