# 迷宫寻路算法

**Repository Path**: ricocosoul_admin/maze-routing-algorithm

## Basic Information

- **Project Name**: 迷宫寻路算法
- **Description**: 图论的应用，演示深度优先/广度优先算法运行的过程
- **Primary Language**: C++
- **License**: GPL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 5
- **Forks**: 1
- **Created**: 2022-03-24
- **Last Updated**: 2025-01-15

## Categories & Tags

**Categories**: Uncategorized

**Tags**: Qt6, Cpp, Xmake, cmake

## README

<div align="center">
<h1 align="center">迷宫寻路算法说明文档</h1>
</div>

# 迷宫寻路算法说明文档
## 一、项目概述
迷宫寻路算法项目是图论在实际场景中的生动应用，旨在通过多种算法解决迷宫寻路问题，并以直观的图形界面展示算法运行过程。当前版本为1.5.0，在以往版本基础上新增了A*算法，为迷宫寻路提供了更高效的解决方案。项目涉及C++11编程语言、Qt6图像界面，并借助vscode + GCC + XMake的组合进行测试运行与项目构建。

## 二、开发环境
1. **编程语言**：采用C++11，其强大的面向对象编程特性和丰富的标准库为算法的实现和数据结构的构建提供了便利。
2. **图像界面**：Qt6用于创建用户交互界面，可呈现迷宫地图、算法运行结果以及各类控制组件，增强用户体验。
3. **测试运行IDE**：vscode作为代码编辑工具，结合GCC编译器将C++代码转换为可执行文件，XMake负责项目的构建与管理，其配置为`xmake f -p mingw --mingw=x:/Qt/Tools/mingw900_64 -c迷宫自动寻路算法演示`，指定了MinGW工具链及安装路径，便于项目构建。
 ![演示](https://gitee.com/ricocosoul_admin/maze-routing-algorithm/raw/master/img/主界面.png) \
 ![演示](https://gitee.com/ricocosoul_admin/maze-routing-algorithm/raw/master/img/DFS.png) \
 ![演示](https://gitee.com/ricocosoul_admin/maze-routing-algorithm/raw/master/img/BFS.png) \
 ![演示](https://gitee.com/ricocosoul_admin/maze-routing-algorithm/raw/master/img/DBFS.png) 
 ![演示](https://gitee.com/ricocosoul_admin/maze-routing-algorithm/raw/master/img/Astar.png) 
## 三、功能实现
1. **搜索算法**
    - **DFS算法**：深度优先搜索算法，从起始点开始，尽可能深入地探索迷宫，直到无法继续或找到目标点，随后回溯继续搜索。该算法能快速深入迷宫，但找到的路径不一定是最优解。
    - **BFS算法**：广度优先搜索算法，以起始点为中心逐层向外扩展搜索，直至找到目标点，确保找到的路径为从起始点到目标点的最短路径。
    - **双向BFS算法**：从起始点和目标点同时进行广度优先搜索，当两个搜索过程相遇时，便找到最短路径，相比普通BFS算法，通常能更快地定位最短路径，降低搜索的时间和空间复杂度。
    - **A*算法**：新增的A*算法是一种启发式搜索算法，通过评估函数$f(n) = g(n) + h(n)$来寻找最短路径。其中，$g(n)$表示节点$n$到起点的实际代价，$h(n)$是节点$n$到目标点的估计代价（启发式函数），$f(n)$为节点的综合优先级。算法每次选择$f(n)$值最小的节点进行扩展。启发式函数的设计至关重要，常见的如曼哈顿距离或欧几里得距离，需满足无过估计和一致性条件，以保证算法能找到最优解。算法流程如下：
        - 将起点节点放入开放列表，关闭列表初始为空。
        - 从开放列表中选取$f(n)$值最小的节点作为当前节点。
        - 若当前节点为目标节点，则结束搜索，构建并返回路径。
        - 将当前节点从开放列表移除，加入关闭列表。
        - 遍历当前节点的邻居节点，跳过已在关闭列表中的节点，计算邻居节点的$g(n)$、$h(n)$和$f(n)$值。若邻居节点不在开放列表，将其加入并设置当前节点为父节点；若已在开放列表且通过当前节点到达的路径更优，则更新父节点及相关代价。
2. **地图相关功能**
    - **地图生成**：具备随机生成迷宫地图的功能，为算法测试提供多样化的场景，可生成不同规模和复杂度的迷宫。
    - **重置地图**：在v1.4.0版本中，将重置地图方式改为拷贝对象，摒弃原有的循环重置数据方法，显著提升了运行速度，用户可将地图恢复到初始状态。
3. **界面交互功能**
    - **时间控制**：记录算法运行的游戏时间，帮助用户直观对比不同算法的执行效率。
    - **步数统计**：统计寻路过程中的最短步数，用于评估算法性能。
    - **坐标显示**：实时展示当前所处坐标位置，便于用户跟踪算法的搜索轨迹。
    - **绘图时间控制**：可对绘图时间进行控制，调整算法可视化的节奏，方便用户观察算法运行细节。
    - **进度条显示**：v1.4.0版本后采用进度条展示算法运行进度，相比之前的显示方式更加直观，让用户实时了解算法执行进度。

## 四、版本更新说明
1. **v1.5.0更新**：新增A*算法，丰富了迷宫寻路算法体系，该算法利用启发式信息，在大多数情况下能更高效地找到最短路径，提升了项目的寻路能力和实用性。
2. **v1.4.0更新（优化）**
    - 优化基础框架，增强项目的适用性和简易性，方便后续功能扩展与维护。
    - 再次优化绘图方式，解决延迟导致的运行效率低问题，进一步提升绘图运行效率，使算法可视化更流畅。
    - 更改重置地图方式，通过拷贝对象替代循环重置数据，提高运行速度。
    - 采用进度条显示进度，使进度展示更直观。
3. **v1.3.0更新（修复）**：修复双向BFS搜索导向错误问题，确保算法能准确找到最短路径。
4. **v1.2.0更新（重要）**
    - 更改绘图方法，采用双缓冲绘图且每次只绘制一个坐标点位，大幅提升绘图效率，减少卡顿。
    - 增加路径路线的回溯导向，方便用户理解算法寻路过程。
5. **v1.1.0更新**：更新BFS和DBFS路径记录方式为`unordered_map`，提高路径记录与查询效率，优化算法性能。
6. **v1.0.0更新**
    - 实现双向BFS算法，丰富寻路算法种类。
    - 实现时间控制功能，便于评估算法性能。

## 五、致谢
双向BFS算法的关键中间状态确认得到好友cribug_one的指导，在此对其表示衷心感谢。同时感谢所有为项目提供帮助的人员，他们的贡献推动了项目的顺利发展。