Teternity

欢迎大家指出代码的不足,共同学习!

迷宫算法演示

这不是一个游戏,而是算法分享和算法演示。

通过简单绘图,使得算法的执行过程可视化。

包含两个文件:头文件 MazeAlgorithm.h 和 源文件 main.cpp。

main.cpp 给出基本控制和简单文字按钮。

MazeAlgorithm.h 给出算法的实现和演示绘图,包含算法如下:

一、迷宫生成:

        ① DFS(即深度优先)递归和非递归版本。

        ② 十字分割 递归和非递归版本。

        ③ 随机 Prim。

二、迷宫寻路:

        ① DFS(分为随机方向 和 指定优先遍历方向,是同一个接口)。

        ② A* 寻路。

这对于初学者而言或有难度,而且许多教程只是给出简陋的文字描述,很难上手代码。

若以后有时间,我尽量去完成一篇迷宫算法的博客,然后回头补链接。

以下对这些算法给出简单说明(注:这不足以让你深刻理解算法原理,或许你需要先看看别的文章进行学习)。

要求迷宫大小长宽均为奇数,外围必须为墙(外围是偶数,因为下标 0 开始)。

1. DFS 方法生成:

        像一只地鼠打洞一般,迷宫要求初始时全是阻碍(墙),然后随机方向打洞(挖墙)。

        要求,不能造成当前通路与另一通路打穿。

2. 十字分割方法生成:

        要求初始时迷宫内全是通路,然后随机十字建墙,然后随机在三面墙上打洞,使四个子空间连通。

        要求:十字点横纵坐标均要求为偶数,打洞点要求为奇数

3. 随机 Prim 方法生成:

        要求初始时迷宫是用墙隔开通路的形式,即 一墙一通路。

        通过挖墙方式将所有通路连通,具体实现参见代码。

4. DFS 方法寻路:

        随机方向前进,能前进就前进,否则后退寻找可行方向,直到找到目的地。

        为何要给出指定优先方向遍历顺序的 DFS 寻路?这已经有 A* 寻路的思想了。

        旨在有更快的速度,更短的路径去找到终点,程序只给出了固定方向遍历次序,

        可拓展使得遍历方向始终优先向着目的地方向前进,这会使算法更优。

5. A* 寻路:

        A* 寻路是寻找最短通路的方法,但是速度未必更快(也可能更快,因迷宫不同而不同),

        而有时迷宫从起点到终点仅有一条路可走,此时 A* 寻路的优势会有所降低。

其他说明:

        1. 递归 DFS 生成从该文学习提取(也是 EasyX 官网的游戏,表示感谢):走迷宫程序(含自动迷宫生成)

        2. 若觉得演示过快,可调整程序中 delayMs 值,用于调整延时时长。

        3. 三种迷宫生成方式生成的迷宫有较大差异,需要根据不同的游戏类型选择合适的方式去生成。

        4. 不要局限的认为迷宫算法只能用于迷宫。

                例如:你甚至可以使用迷宫寻路算法完成贪吃蛇的自动寻路。

                例如:你甚至可以将迷宫生成算法和寻路算法稍加改动,与贪吃蛇大作战类游戏结合创作。

                 ......

下面给出十字分割生成 且 A* 寻路后截图,其他情况可自行测试。

编译环境:VS2019 + EasyX_20200109(beta)。

源码包:MazeAlgorithm.zip

关于算法的详细说明已经完成,如有需要请转到博客:MazeAlgorithm.html

分享到