基于C++生成树思想的迷宫生成算法【100010517】

> # ♻️ 资源 > **大小：** 102MB > **文档链接：**[**https://www.yuque.com/sxbn/ks/100010517**](https://www.yuque.com/sxbn/ks/100010517) > **➡️ 资源下载：**[**https://download.csdn.net/download/s1t16/87400294**](https://download.csdn.net/download/s1t16/87400294) > **注：更多内容可关注微信公众号【神仙别闹】，如当前文章或代码侵犯了您的权益，请私信作者删除！** >  ## 安装 - Dark Maze1.0目录下exe直接运行即可 - 或编译code目录下MazeF4的源码（MazeF4为原名），将resource文件夹复制到编译后exe的同目录（QMediaPlayer库不支持音乐导入资源文件，这里使用的相对目录），QT命令行中cd到编译目录，执行命令windeployqt DarkMaze.exe ## 游戏操作 WASD控制移动方向 ## 展示 **游戏加载：**  **主界面：**  **设置界面：**  **游戏界面：**  **算法演示界面：**  ## 算法解释 ### 迷宫生成算法 基于生成树思想 迷宫高M，宽N - 步骤 1. 迷宫是矩形的，将其每个格子视为一个点，上下左右视为边，即一张点为M*N，单点(除边)出度为4的图 2. 随机边的权值 3. 跑一边最小生成树 4. 就是这样，如果两个点相连，那么对应的两个格子是通路；如果两个点不想连，那么对应两个格子之间就是一面墙 - 注 1. 最小生成树有Prime和Kruskal，Prime是加点，用优先队列实现；Kruskal是加边，用并查集实现。这里最好用Prime，因为Prime能够从起点出发，获得一个以起点为根的树，并且能够得到每个点对应的父节点 2. 这样生成的迷宫格子与各自之间相邻的墙是一条线，如果想要相邻的墙是另外的格子的话，那么就需要扩大迷宫的长宽，任何相邻点都加上新格子，加上迷宫的边界就变为(2M+1)*(2N+1),这就是为什么本例生成的迷宫边长是**奇数** ### 寻路算法 - DFS **递归**实现。可以说DFS是最拟合人走迷宫的算法，没遇到一个岔口向一个方向转弯，知道搜到尽头，回来换一个方向继续搜索。 - BFS **队列**实现。每次把点周围相连的新点添加到队列，层层扩展，知道搜索到新点，适合求最短路，但不太适合迷宫寻路。 - 双向BFS **队列+集合**实现。BFS的扩展，BFS是先将起点入队，双向BFS是两个队列，起点和终点开始同时搜索，可以一定程度减少搜索空间，难点在于判断结束条件——两个队列相交，这里使用Set记录终点搜索过的位置，起点队列查找该Set。 这种算法类似于人玩游戏迷宫时的思想。对于开上帝视角的玩家来说，中等程度的地图，大部分人会选择从终点开始倒着看，找到某一片区域，接着从起点开始正着走，达到这片区域。 - LCA最邻近公共祖先 **这并不是正规寻路算法**，而是基于迷宫生成方式的一个快捷路径算法。 因为本例的迷宫是一棵树，如果以起点为根节点，终点为一个子节点，那么找起点到终点的路径只需从终点向上查找祖先的过程，保存这条路径。如果寻找任意一点到终点的路径，那么先找到该点和终点的最邻近公共祖先，根据树的性质，该公共祖先点一点在起点到终点的路径上。所以路径即为，点->最邻近公共最先->终点。 之前说生成树最好用Prime就是这个道理，因为跑完Prime更容易获得每个点的父节点，只需以起点为初始点，没次加点的时候记录前面的点为父节点即可。 ## QGraphicsWidget视图框架 本程序采用该视图框架 ### 与QWidget体系的联系和区别 1. QGraphicsView继承QWidget，但是这两种体系之间的区别非常非常大，以至于很多相同的操作在这两种架构下的设置方法都不一样 2. 举个例子：在手机中当你横竖屏转换时，你肯定希望此时打开的应用程序也跟着横竖屏旋转。如果这个程序是一个Qt程序，则是指：Qt中的窗口需要可以旋转。 对于这一点:QWidget是做不到的。亦即一个QWidget窗口无法实现旋转（顶多是上边刷的内容旋转，但是窗口本身不会旋转） 但是QGraphicsItem则可以直接旋转。基于很多这样的理由，还是需要我们好好学学QGraphicsWidget体系的。 3. 其实在后者的场景中我们不仅仅可以添加Item项，更可以直接添加QWidget。这样的话，我们平时开发完全可以还按照QWidget体系那一套来写，只不过最后将他们都挨个加到scene中即可。 ### 优势 1. 方便绘制并管理图形项 2. 可以检测图形的碰撞，叠加 3. 可以实现图形的拖动位置，缩放，旋转等一系列动画 ## 成员分工 ### 主要方向 | 成员 | 负责方向 | | --- | --- | | AllenTaken | 迷宫及迷宫算法 | | Woodencross | 加载界面及PPT制作 | | Joockie | 设置界面及图片加工 | | Lionelsey | 主界面，音乐加载及页面整合 | ### 代码归属 - AllenTaken ```c f4point.h/cpp 重载的点类 f4rect.h/cpp 重载的矩形类 f4edge.h/cpp 重载的边类 f4player.h/cpp 玩家类，继承QGraphicsItem f4mazemap.h/cpp 基础迷宫生成类，内涵Prime,Kruskal等算法 f4mazemapplus.h/cpp 进阶迷宫类，继承F4mazemap类，对基础迷宫类进行二维扩展 f4mazescene.h/cpp 迷宫场景类，继承QGraphicsScene，展示迷宫游戏界面 f4mazedemo.h/cpp 迷宫算法演示类，继承QgraphicsScene,内涵DFS,BFS,双BFS,LCA等算法，展示寻路算法 ``` - Woodencross ```c myloading.h/cpp 进度条加载界面，继承QSplashScreen类 ``` - Joockie ```c f4setitem.h/cpp 设置界面图形项类，继承QGraphicsItem f4setscene.h/cpp 设置界面场景类,继承QGraphicsScene f4overall.h 声明全局变量头文件，对音量大小进行调控 ``` - Lionelsey ```c music.h/cpp 音乐播放类 myitem.h/cpp 主界面图形项类,继承QGraphicsItem myscene.h/cpp 主界面场景类，继承QGraphicsScene myview.h/cpp 游戏视图类,继承QGraphicsView main.cpp 主函数 ``` ## 遇到的问题 - 关于QGraphicsView,QGraphicsScene,QGraphicsItem三级视图框架， 没错，这个框架有诸多优点，但是有一个缺点是一定的。**QG