项目代码传送门
1. 基于图的遍历
算法思想：
我们把迷宫看成一个图网络结构——迷宫中每个像素点构成图的顶点集，每个顶点与其相邻的上下左右至多4个顶点连通，其连通边构成图的边集。
迷宫路径就是图的一个连通子图，即一次遍历的结果。故其生成的迷宫的起点到终点的路径是唯一的。
一般地，因为生成图的边集和点集的规模大小相近，所以是一个稀疏图，应该使用邻接表存储，但python中，numpy的矩阵处理的速度总体上比较快，所以我代码里面使用邻接矩阵进行存储
1.1. 随机BFS
上图中，白色是路径，黑色为障碍物
广度优先很少用来生成迷宫。因为即使每次都可以随机选择下一步的方向，但实际上迷宫是按层生成的，每一步可选择的方向基本都被遍历过了，可选择方向的自由度是很少的，且往往只有一个选择的空间。故可以看出来，其生成的迷宫呈规则的条型状，并不适合迷宫的生成。
1.2. 随机DFS
1.3. 随机最小生成树
应用的是prim算法。
2. 基于图的连通性
算法思想：
我们把迷宫看成一个凸多边形。对于一个凸多边形，我们可以使用两条相交的直线，将其划分为为至多4个小区域。设该多边形划分为n个小区域，则在任意n-1个公共边上开一个小洞，即可将所有的区域连通。
对划分后的区域不断重复上述划分和开洞操作，直到划分后的区域不可以再分割，则形成一个连通的迷宫。
其起点到终点的路径是唯一的。
2.1. 递归分割
3. 附：各种算法生成迷宫比较
 |
 |
|---|---|
 |
 |
4. 下一步工作
迷宫寻路、给迷宫上色以及生成roguelike类型的迷宫等工作，后面有时间再慢慢填这个坑了~
