Lost person

蒟蒻一枚,只能写写小程序,有BUG欢迎指出!

迷宫小游戏

基于 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 + EasyX20200315(beta)。
  • 其他详见 github 中的 README.md。

程序效果

源码和 Release

感谢

感谢 QQ 群 C语言革命7 全体成员为该项目的开发做了巨大的贡献,没有你们,该作品也不能有现在的情况!

Comments (1) -