图的遍历迷宫算法浅析

《图的遍历迷宫算法浅析》由会员分享，可在线阅读，更多相关《图的遍历迷宫算法浅析（24页珍藏版）》请在金锄头文库上搜索。

1、图的遍历迷宫算法QQ:513696765 作者：小牛页 11. 引言在平常的游戏中，我们常常会碰到随机生成的地图。这里我们就来看看一个简单的随机迷宫是如何生成。2. 迷宫描述随机生成一个 m * n 的迷宫，可用一个矩阵 mazemn来表示，如图：图 1.1 图 1.2 这里是两个迷宫的例子，其中“ ” 表示障碍物 (Obstacle block)。以图1.1 迷宫为例，我们可用一个9 * 9 的矩阵来表示：1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0

2、1 0 0 0 0 0 1 1 0 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 11 1 1 1 1 1 1 1 (矩阵中 1 表示是障碍物， 0 表示可以行走 ) 图的遍历迷宫算法QQ:513696765 作者：小牛页 23、迷宫生成算法(蓝色表示可以行走，棕色表示是墙壁) 图 3.1 如图 3.1 所示为迷宫的初始化情形，迷宫如果除去其迷宫的外围框架就是一个 7*7 的矩阵，如果要生成一个完整的迷宫，那么就要遍历完图 3.1 所示的每一个可以行走的点，其中遍历的点也包含了入口和出口，如果每一个点都遍历完了就会生成一棵完整的遍历树，这棵遍历树包含了入口和出口所以这颗树所描

3、述的迷宫是有解的（即：入口到出口时连通的。）图 3.2 就表示图 1.1迷宫遍历所得到的遍历树， 树包含了入口和出口所以此迷宫有解。图 3.2 图的遍历迷宫算法QQ:513696765 作者：小牛页 3图 3.3图 3.3 表示的是图 3.2 进一步的处理后得到的最终迷宫图，就是在图3.2 的基础上把遍历树上的是墙壁的元素置为可行走的元素。3.1 元素的遍历图 3.1.1 描述了各个遍历点的连接关系其中1 元素为起始遍历点， 49元素为终点遍历点我们声明一个mazepoint类用来描述每一个遍历点xtemp 表示当前点在数组中的x 坐标， ytemp 表示当前点在数组中的y 坐标，定义为 ma

4、zepoint对象的 next 用来链表一个点的地址last 用来链表上一个地址。图 3.1.1 图的遍历迷宫算法QQ:513696765 作者：小牛页 4声明了两个 mazepoint的变量 head和 tail 用于存储迷宫的链表的头地址和尾地址由于在迷宫刚刚开始的时候初始化元素是第一个所以头尾是相同的在主函数中把head赋值给了 p1， （p1 是我们声明的一个临时存储的变量； p1 和 p2 用于新的链表元素生成）如图 3.1.2 所示元素 1 它连接到元素 3 和元素 15，所以它可以遍历这两个元素，假设遍历的方向是随机的， 如果第一次现在向右遍历那么元素 3 就被遍历并把它标志为f

5、lag（flag 表示已经遍历过了不容许再次遍历） ，所以元素 1 和元素 3 都标志位 flag 说明在其它元素想遍历它们的时候是不能再次被遍历了。这就有可能会遍历成一棵完整的树。图的遍历迷宫算法QQ:513696765 作者：小牛页 5图 3.1.2 如图 3.1.3 所示图 1.1 迷宫在生成时前13 步，据图我们可知在第13步的时候遍历到元素19，但是元素 19 周围的点都已经遍历过但同时还有其它元素还没有遍历到， 所以要后退到上一个遍历过的元素判断是否有遍历的方向，所以链表到元素17，但是此元素也没有可遍历的方向所以要一直往上链表直到链表到某一个可以重新遍历的点为之。图 3.1.3

6、图 3.1.4是往上链表的示意图直到链表到元素45发现此元素拥有可遍历的方向，所以又重新往下建立新的链表，即元素47图的遍历迷宫算法QQ:513696765 作者：小牛页 6图 3.1.4 图 3.1.5 是最终遍历完后的遍历路径，此时只要沿着遍历的方向把相应的“墙”拆掉就可以生成一个无外框的迷宫并且只能生成奇数行和奇数列的迷宫。图 3.1.5 图 3.1.6 是程序生成得 33*33 的迷宫图的遍历迷宫算法QQ:513696765 作者：小牛页 7图 3.1.6图的遍历迷宫算法QQ:513696765 作者：小牛页 84、编程思路开 始声明和初始化mazepoint变量 P1，p2，head

7、，teil 初始化 p1 变量成员变量并且把p1 的地址传递给head 每一个点是否遍历完即：pointcount=0 ？下一个点是否有方向可遍历把 p1 的地址赋给p2，同时把当前点的x，y 坐标赋给p1，新建一个链表元素并且把其地址赋给p1，把 p2 的next 连接到 p1 的地址，p1 的 last 链接到 p2， p1 的 next链接到 NULL ，这样就生成了一个双向的动态链表在可以遍历的方向中随机选择一个方向遍历并且把选择的元素标志为flag 同时把 x， y 的坐标更新到和当前点的坐标，说明当前点不可再一次遍历了pointcount-1说明有一个点已经遍历过了，再把tail

8、赋值为 p1 的地址链接到上一个点tail=tail-last 屏幕输出迷宫结 束图的遍历迷宫算法QQ:513696765 作者：小牛页 95、源代码#include #include using std:cout; using std:cin; using std:endl; #define Row 33 / 用 于 定 义迷宫的行必须为奇数，否则不能遍历到所以的点#define Col 33 / 用 于 定 义迷宫的列必须为奇数，否则不能遍历到所以的点#define flag 1 / 点 的 标 志位，如果找到符合条件的点就把它置为flag，只要某一个点置位为flag 就不能再次被访问；i

9、nt x_row=0; / 迷 宫 的 起 始点位置的x 坐标int y_col=0; / 迷 宫 的 起始点位置的y 坐标int Left=0; / 初 始化向左的方向标志位Left int Right=0; / 初 始 化 向右的方向标志位Right int Up=0; / 初 始化向上的方向标志位Up int Dwon=0; / 初 始 化向下的方向标志位Dwon int pointcount=(Row+1)*(Col+1)/ 4-1); / 初 始 化 要遍历的点数， (因为第一个点不要遍历了，所以总点数要减去1) int get_count(); / 定 义 可 以获得某一个点可以行

10、走的方向数的函数class mazepoint / 定 义 一 个类用于存放每一个遍历点的坐标 public: int xtemp; / 用于存放一个遍历点的x 坐标int ytemp;/ 用 于 存 放一个遍历点的y 坐标mazepoint *next; / 用 于 存 放 一个遍历点的下一个遍历点的地址mazepoint *last; / 用 于 存 放图的遍历迷宫算法QQ:513696765 作者：小牛页 10一个遍历点的上一个遍历点的地址; mazepoint *p1; mazepoint *p2; mazepoint *head=NULL; / 初 始 化 头由于没有指向如何位置所以

11、赋值为NULL mazepoint *tail=NULL; / 初 始 化 尾由于没有指向如何位置所以赋值为NULL int mazemapRowCol= / 初 始 化 迷宫地图数组 1 ; int main() p1=new mazepoint; / 声 明一片内存空间p1-xtemp=0;/初始化类元素x 坐标p1-ytemp=0;/初始化类元素y 坐标p1-last=NULL; /初始类只有一个元素没有前一个元素，链接到别的元素所以它的的上一个遍历点位空NULL head=p1; /把链表的头地址赋值给p1 tail=p1; /刚刚开始没有其它元素所以把链表的尾地址也是p1 int m

12、azenum=0; /用于统计遍历的次数srand(time(0); /用当前时间做随机种子数while(pointcount) / 如 果没有遍历完所有的点就继续遍历，以确保每一次的随机数都不一样图的遍历迷宫算法QQ:513696765 作者：小牛页 11 int rdNo=rand(); / 获 得 随 机数int Randtemp; / 定 义一个变量，用于存储处理后的随机数int tempflag; / 定 义一个变量，用于存储某一个点可以行走的方向数tempflag=get_count();/ 获得某一个点可以行走的方向数if(tempflag!=0) / 如 果某一个点可以行走就处

13、理随机数然后随机选择行走的方向Randtemp=rdNo%tempflag; / 根 据 返 回的可以行走的方向提供行走方向数else Randtemp=NULL; /如果不能行走就赋值为NULL coutxtemp=x_row; / 保 存 当 前 点的 x 坐标p1-ytemp=y_col; / 保 存 当 前点的 y 坐标p1=new mazepoint; / 声明内存p2-next=p1;/ 前 一个遍历点链表到下一个点的地址p1-last=p2;/ 后 一个遍历点链表到上一个点的地址p1-next=NULL; / 新 生产的点没有链表到下一个点所以设为NULL 。 (新产生的点是链表

14、的最后一个点) if(Randtemp=Left / 如 果 可 以左走就要把对应的坐标也要改变；也就是行值减2 mazemapx_rowy_col=flag; / 把 遍 历 到 的新的迷宫地图元素也要置flag mazemapx_rowy_col+1=flag;/ 把遍历到的新的迷宫地图元素相同方向的临近元素也要置flag -pointcount;/ 遍 历 到 新的一个点，那么遍历点的总数pointcount 减 1 coutlast;/ 链 表 到 上一个点地址if(tail-last =NULL) tail=head;x_row=tail-xtemp; / 读 取 上 一个遍历点的x

15、 坐标y_col=tail-ytemp; / 读 取 上 一个遍历点的y 坐标 +mazenum;/ 执 行 次 数加 1 coutxtempytempCol) / 判 断 往 右 是否越界；即：是否超出迷宫数组 if(y_colCol) y_col=Col; Right=0; coutRow) / 判 断 往 下是否越界；即：是否超出迷宫数组 if(x_rowRow) x_row=Row; Dwon=0; cout“Dwo图的遍历迷宫算法QQ:513696765 作者：小牛页 24n not is Direction “count is:“countendl; / 输 出 往 下不能走 else if(mazemapx_row+2y_col!=flag)/判断往下是否可以走 +count; Dwon=count; else cout“Dwon not is Direction “count is:“countendl;/输出往下不能走 return count;