迷宫小游戏
基于 EasyX 的迷宫小游戏,有三种随机生成算法。
包含九个文件
- Maze.h : 初始化头文件
- Maze.cpp : 程序开端文件
- Game.h : 游戏类头文件
- Adventrue.cpp : 冒险模式类文件
- Forest.cpp : 冒险模式-森林系列类实现文件
- Dungeon.cpp : 冒险模式-地牢系列类实现文件
- Infernal.cpp : 冒险模式-地狱系列类实现文件
- Help.cpp : 帮助信息类实现文件
- Other.cpp : 刷新界面、放置按钮、输出对话框类实现文件
包含算法
- 森林系列:Prim 算法
- 地牢系列:图论 DFS 算法
- 地狱系列:暴力 DFS 算法
算法说明
以下对这些算法给出简单说明,详细请自行学习(比较有难度):
1. Prim 算法(请学习最小生成树):
初始时迷宫一墙一通路,将所有通路作为节点存入一张图中,每个上下左右相邻一格的通路(即节点)连上一条无向边,边权值为1。
然后在图中跑一遍 Prim 即可(这里要将 Prim 边权值和最小的条件改为随机化),这里就不对 Prim 算法进行赘述了,请自行学习。
2. 图论 DFS 算法:
初始时迷宫一墙一通路,将所有通路作为节点存入一张图中,每个上下左右相邻一格的通路(即节点)连上一条无向边,边权值为1。
然后在图中跑一遍随机化的 DFS 即可,这里就不对 DFS 算法进行赘述了,请自行学习。
3. 暴力 DFS 算法:
(0) 初始时迷宫全是墙,无通路。
(1) 选择一个方块(终点)作为当前扫描点。
(2) 挖开扫描点,并将扫描点周围的可挖的方块(不能为边界,不能为路,且挖开后不能形成一个闭合回路)记录到一个序列当中(不同扫描点有不同的序列)。
(3) 随机选择序列中的一个方块,挖开,并作为当前扫描点。
(4) 重复步骤(2),若无墙可挖,则退回一格作为当前扫描点,再重复步骤(2),若退回起点,则算法结束。
算法总结
1. Prim 算法:
Prim 算法生成的迷宫分支多,比较难走,但只要仔细观察,便可发现路径都比较靠近起点和终点的连线。
而且,容易看出 Prim 算法只能生成长宽为奇数的迷宫,这正是该算法的缺点之一。
本游戏限制了游戏视野,增大了迷宫难度,不过该算法生成的迷宫难度仍不如另两种算法生成的迷宫。
2. 图论 DFS 算法:
图论 DFS 算法生成的迷宫有明显的主路,比较好走,可本游戏的图论 DFS 算法是从终点开始的,使起点出来的路分支多,且限制了游戏视野,大大增加了它的难度。
容易看出图论 DFS 算法也只能生成长宽为奇数的迷宫,这正是该算法的缺点之一。
3. 暴力 DFS 算法:
没错它确实很暴力(暴力是一种算法,真的)。
暴力 DFS 算法生成的迷宫有明显的主路但蜿蜒扭曲,比较难走,可本游戏的暴力 DFS 算法是从终点开始的,使起点出来的路分支多,且限制了游戏视野,大大增加了它的难度。
由于该算法生成的迷宫可能无法连接起点终点,本蒟蒻已对其进行手动挖墙,导致起点终点处会有一片空地
容易看出暴力 DFS 算法可生成任意大小的迷宫,但生成的迷宫存在斜线和块状墙体,蜿蜒扭曲,很不美观,十分考验玩家的方向感。
其他说明
- 编译环境:(开始使用 VS2010 后来用 VS2017 修改) + EasyX_20200520(beta)。
- 其他详见 github 中的 README.md。
程序效果
源码和 Release
感谢
感谢 QQ 群 C语言革命7 全体成员为该项目的开发做了巨大的贡献,没有你们,该作品也不能有现在的情况!