平面迷宫地图随机生成树算法设计与实现

1 引言

迷宫问题是图形学、图论和数据结构等领域中广为人知的一个经典问题, 如何生成一个m×n的二维平面迷宫地图, 其实就是生成树的问题, 可以参考最小生成树的两个经典算法, Prim算法和Kruskal算法, 本文的算法就参考了Kruskal算法, 用图的导出连通子图来生成迷宫地图。

2 设计原理

假设WN= (V, {E}) 是一个含有n个顶点的连通网, 则按照Kruskal算法构造最小生成树的过程为:先构造一个只含n个顶点, 而边集为空的子图, 若将该子图中各个顶点看成是各棵树上的根结点, 则它是一个含有n棵树的一个森林。之后, 从图的边集E中选取一条权值最小的边, 若该条边的两个顶点分属不同的树, 则将其加入子图, 也就是说, 将这两个顶点分别所在的两棵树合成一棵树;反之, 若该条边的两个顶点已落在同一棵树上, 则不可取, 而应该取下一条权值最小的边再试之。依次类推, 直至森林中只有一棵树, 也即子图中含有n-1条边为止。根据Kruskal最小生成树算法, 我们首先可以把二维平面迷宫地图看成是空格与空格之间的墙壁组成的一个图, 其中每个空格看成一个点, 空格之间的墙壁看成一条边, 那么初始的迷宫就是一个无向图G=, 如图G所示 (其中左上角为起点, 右下角为终点) 。由于该图的边没有权值差异, 所以在该图中随机生成一棵树, 将所有的点都连通起来, 得出图G的随机导出子图, 就形成了迷宫地图。

怎样随机连通所有的点生成一棵树, 其实就是随机化Kruskal算法, 相当于去求一个图G的导出子图, 使得子图中的所有顶点都是连通的, 如图H所示, 具体算法步骤如下:

(1) 将图G中的所有空格看成是只有根节点的树构成的一个森林。

(2) 将图G中的所有边放入一个集合, 称为边集E。

(3) 随机选择边集E中的一条边e∈E, 判断e连接的两个顶点是否在同一棵树上, 如果不是, 将两个顶点所在树合并为一棵树, 并且把墙擦掉。

(4) 从边集E中去掉元素e, 即E=E-{e}。

(5) 如果E=Φ (空集) , 结束算法;反之, 转到 (3) 。

3 C++实现

首先定义存放迷宫空格和墙信息的二维字符数组char Map[2*MaxN-1][2*MaxN-1], 其中MaxN为迷宫地图最大空格数常量;同时还要定义存放迷宫各空格构成的森林中的各颗树的父节点及各节点对应的阶, 用一位数组实现int rank[100001], int parent[100001];此外, 还要定义存放迷宫所有墙的动态数组std::vectorEdge, 以及存放墙序号和其对应行列坐标的映射std::map>Hash。

有了这些基本数据, 接下来就可以调用函数void init (int width, int height) 初始化迷宫信息, 具体算法是:根据传入函数的迷宫空格宽度和高度, 计算出包括墙在内的所需的行数和列数, 再用循环, 根据偶数行并且偶数列的条件, 设置迷宫二维字符数组为空格, 或者为墙。

初始化迷宫信息后, 就可以调用随机化Kruskal算法, 生成迷宫地图了, 具体算法是:先从左到右从上到下的顺序将迷宫的所有可擦除的墙的序号加入到动态数组std::vectorE d ge中, 并将墙序号与它对应行列坐标存入映射st d::map>Hash中, 然后循环从墙集数组std::vectorEdge中随机选择一条墙, 求出该墙连接的两个空格房间, 并判断该两个房间是否在同一颗树上, 如果不在通一颗树上, 就把两个房间所在的两颗树合并为一颗树, 并在迷宫地图将该条墙设为空格后, 进入下一轮循环重新随机选墙;否则就直接进入下一轮循环重新随机选墙。这其中判断该两个房间是否在同一颗树上算法思想是:先递归查找某个房间的父节点, 直到找到该房间所在树的根节点为止, 才退出递归调用, 如果相邻两个房间分别所在的树的根节点相同, 这说明它们已经在同一颗树上, 否则就不在同一颗树上。而把两个房间所在的两颗树合并为一颗树算法思想是:比较两个房间所在树根的阶码大小, 把根节点的阶码小的树作为阶码大的树的子节点, 如果两根节点的阶码相同, 还要将父节点的阶码加一。

最后根据调用随机化Kruskal算法后得到的迷宫信息二维数组char Map, 循环输出迷宫地图, 其中墙输出为“■”, 空格房间输出为“”, 起点输出为“S”, 终点输出为“E”, C++实现代码运行结果如图H所示, 实现代码请向作者邮箱cico_yuan@hotmail.com发信索要。

摘要：迷宫问题是图形学、图论和数据结构等领域中的一个经典问题, 迷宫生成问题就是图到导出子图问题。本文借用Kruskal最小生成树算法思想, 用随机生成树生成图的导出连通子图, 连通图的所以顶点, 产生迷宫地图。主要算法过程:将二维平面迷宫地图看成是一个无向图, 随机从其边集中选择一条边, 判断该边连接的两个顶点是否在一个连通集合内, 如果不是, 将两个顶点所在集合合并, 并且把该边去除, 反之重新从集中随机选择一条边继续判断, 直至边集被选空, 所有点都连通到一个集合内为止。其特点是:算法原理简单, 实现容易, 数据量小, 运行高效, 可任意生成不同大小的迷宫地图。

关键词：迷宫地图生成,Kruskal算法,随机生成树

参考文献

[1] 杜凯;朱泽民基于图的深度遍历产生随机迷宫的算法研究《黄冈师范学院学报》2008年第S1期

[2] 严蔚敏、吴伟民《数据结构》清华大学出版社

[3] 涂海丽求迷宫中从入口到出口的路径的算法及实现《中国科技信息》2008年23期

[4] 徐守江迷宫算法综述《信息与电脑 (理论版) 》2009年10期

[5] Thomas H.Cormen、Charles E.Leiserson、RonaldL.Rivest、Clifford Stein, 潘金贵、顾铁龙、李成法和叶懋译《算法导论》机械工业出版社