小时候玩过一款3D版迷宫，那时还是功能机时代，黑白界面拼凑的伪3D效果还是给我带来了很多快乐。后来出现了智能机，却再也没找到过那样纯粹的迷宫游戏。总算自己找时间做一个出来。

 本文主要介绍一下深度优先，Kruskal,Prim几种方式生成迷宫地图的算法，还有一种递归算法，生成的迷宫多长直路，不太适合纯粹的迷宫，所有暂时没有去实现。源码地址：https://github.com/LogicMonst/mazepath

深度优先算法：

 思路：从起点出发，随机选择周围没有被遍历过的点，如果周围都被遍历过，则回溯到上一个遍历点，随机选择周围没有被遍历过的点，如此往复，直到遍历所有点。

Kruskal算法:

思路：来源于最小生成树的Kruskal算法。 算法导论里说的很清楚了：

Prim算法：

思路：同样的，引用算法导论的内容：

几种方式比较：

        深度优先的方式，虽然有可能路径弯弯曲曲，路径比较长，但是存在着一条明显的主路，分岔路基本不深，对于走迷宫来说，难度不算很大：

上图表示了从坐下出发，到达右上的路径，基本上主路的分岔路都不是很深。

        Kruskal和Prim的方式，虽然路径不算很长，但是路径存在着比较多的分岔路，且分岔有时还挺深，走进去发现不通，再回头找到上次分岔的地方，对于走迷宫来说，还是比较有难度的：

这里介绍了生成迷宫的几种方式， 源码https://github.com/LogicMonst/mazepath 可以导出成dll，配合unity，就可以实现开头GIF展示的那种迷宫游戏了。