图的遍历迷宫算法浅析详解

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

2、 0 0 01111111（矩阵中1表示是障碍物，3、迷宫生成算法如图3.1所示为迷宫的初始化情形，迷宫如果除去其迷宫的外围框架就是一个7*7的矩阵，如果要生成一个完整的迷宫，那么就要遍历完 图3.1所示的每一个可以行走的点，其中遍历的点也包含了入口和出 口，如果每一个点都遍历完了就会生成一棵完整的遍历树，这棵遍历树包含了入口和出口所以这颗树所描述的迷宫是有解的（即：入口到出口时连通的。）图3.2就表示图1.1迷宫遍历所得到的遍历树，树包 含了入口和出口所以此迷宫有解。图3.3表示的是图3.2进一步的处理后得到的最终迷宫图，就是在图3.2的基础上把遍历树上的是墙壁的元素置为可行走的元素。3.1

3、元素的遍历图3.1.1描述了各个遍历点的连接关系其中1元素为起始遍历点，49 元素为终点遍历点我们声明一个 mazepoint类用来描述每一个遍历点 xtemp表示当前点在数组中的x坐标，ytemp表示当前点在数组中的 y坐标，定义为 mazepoint对象的next用来链表一个点的地址last用 来链表上一个地址。o- OO 甲(I) OO0图的遍历迷宫算法QQ:513696765作者：小牛public:int xtemp;class nazepoint 定义一个类用于存放每一个遍历点的坐标用于存放一个遍历点的下一个遍历点的地址 用手存翔一个遍玩病的上一个逋历点的地症用于存独一个遍历点的X坐

4、越 int ytemp; 用于存放一人遍历点的y坐标mazepoint *next:; mazepoint *last ;声明了两个mazepoint的变量head和tail用于存储迷宫的链表的头地址和尾地址由于在迷宫刚刚开始的时候初始化元素是第一个所以头尾是相同的在主函数中把head赋值给了 pl, （pl是我们声明的一个临时存储的变量；pl和p2用于新的链表元素生成）nazepoint *p1;mazepoint *p2；nazepoint *heari=NULL; nazepoint *tail=NULL; int nazenapRouCol=初次令，初始电“初始4娥耀稿院翻嫌狐 铁宫地

5、图毂组页5int main()有M所 .素 不示素值在 元赋它一 空唔唔个址基 存萋一地有b 内兀元有表俘只的始一 一化化类表开一 明始始始链刚T 声初初初把刚E /.xtemp=0;p1-ytemp=0;p1-last=NULL;head-p1;tail-p1;如图3.1.2所示元素1它连接到元素3和元素15,所以它可以遍历这 两个元素，假设遍历的方向是随机的，如果第一次现在向右遍历那么 元素3就被遍历并把它标志为flag （flag表示已经遍历过了不容许再 次遍历），所以元素1和元素3都标志位flag说明在其它元素想遍历 它们的时候是不能再次被遍历了。这就有可能会遍历成一棵完整的 树。图的

6、遍历迷宫算法QQ:513696765作者：小牛如图3.1.3所示图1.1迷宫在生成时前13步，据图我们可知在第13 步的时候遍历到元素19,但是元素19周围的点都已经遍历过但同时 还有其它元素还没有遍历到，所以要后退到上一个遍历过的元素判断 是否有遍历的方向，所以链表到元素17,但是此元素也没有可遍历的方向所以要一直往上链表直到链表到某一个可以重新遍历的点为 之。图 3.1.3图3.1.4是往上链表的示意图直到链表到元素 45发现此元素拥有可遍历的方向，所以又重新往下建立新的链表，即元素 47写tpfl $图 3.1.4图3.1.5是最终遍历完后的遍历路径，此时只要沿着遍历的方向把相 应的“墙

7、”拆掉就可以生成一个无外框的迷宫并且只能生成奇数行和 奇数列的迷宫。图 3.1.5图3.1.6是程序生成得33*33的迷宫页7图 3.1.6图的遍历迷宫算法4、编程思路QQ:513696765作者：小牛初始化pl变量成员变量并且把 pl的地址传递给head声明和初始化 mazepoint变量P1, p2, head, teil屏幕输出迷宫每一个点是否遍历完 即:pointcount=0?下一个点是否有方向可遍历把p1的地址赋给p2,同时把当刖点的 x, y坐标赋给p1,新建一个链表元素并且把其地址赋给p1,把p2的next连接至ij p1的地址，p1的last链接至U p2, p1的next

8、链接到NULL这样就生成了一个双向的动态链表在可以遍历的方向中随机选择一个方向遍历并且把选择 的元素标志为flag同时把x, y的坐标更新到和当前点的 坐标，说明当前点不可再一次遍历了pointcount-1说明有一个点已经遍历过了，再把 tail赋值为p1的地址链接到上一个点tail=tail-last页9图的遍历迷宫算法QQ:513696765作者：小牛页19用于定义用于定义/点的标志 flag就不能再次被访问；迷宫的起迷宫的起/初始初始化向/初始/初始初始化要定义可以5、源代码#include#include using std:cout;using std:cin;using std:

9、endl;#define Row 33迷宫的行必须为奇数，否则不能遍历到所以的点#define Col 33迷宫的列必须为奇数，否则不能遍历到所以的点#define flag 1位，如果找到符合条件的点就把它置为flag,只要某一个点置位为int x_row=0;始点位置的x坐标int y_col=0;始点位置的y坐标int Left=0;化向左的方向标志位Leftint Right=0;右的方向标志位 Rightint Up=0;化向上的方向标志位Upint Dwon=0;化向下的方向标志位Dwonint pointcount=(Row+1)*(Col+1)/ 4-1);遍历的点数，(因为第

10、一个点不要遍历了，所以总点数要减去1)int get_count();获得某一个点可以行走的方向数的函数class mazepoint/ 定 义一个类用于存放每一个遍历点的坐标public:int xtemp;/用于存放一个遍历点的x坐标int ytemp;用于存放一个遍历点的y坐标mazepoint*next;用于存放一个遍历点的下一个遍历点的地址mazepoint*last;用于存放一个遍历点的上一个遍历点的地址；mazepoint *p1;mazepoint *p2;初始化头初始化尾初始化迷1mazepoint *head=NULL;由于没有指向如何位置所以赋值为NULLmazepoin

11、t *tail=NULL;由于没有指向如何位置所以赋值为NULLint mazemapRowCol=宫地图数组； int main()p1=newmazepoint;/声明一片内存空间p1-xtemp=0;/初始化类元素x坐标p1-ytemp=0;/初始化类元素y坐标p1-last=NULL;/初始类只有一个元素没有前一个元素，链接到别的元素所以它的的上一个遍历点位空NULLhead=p1;/把链表的头地址赋值给p1tail=p1;/刚刚开始没有其它元素所以把链表的尾地址也是p1intmazenum=0;/用于统计遍历的次数srand(time(0);用当前时间做随机种子数while(poin

12、tcount)/ 如果没有遍历完所有的点就继续遍历，以确保每一次的随机数都不一样 int rdNo=rand();/ 获 得随机数int Randtemp;定义一个变量，用于存储处理后的随机数int tempflag;定义一个变量，用于存储某一个点可以行走的方向数tempflag=get _count();获得某一个点可以行走的方向数if(tempflag!= 0)/如果某一个点可以行走就处理随机数然后随机选择行走的方向Randtemp=r dNo%tempflag;根据返回的可以行走的方向提供行走方向数 else Randtemp=N ULL;/如果不能行走就赋值为NULL cout 电脑随

13、机数为： rdNoendl;输出电脑产生的随机数Randtemp+= 1; / 加1是为了和定义的方向Left,Right,Up,Dwon相匹配cout 随机数为： Randtempxtemp=x_row;保存当前点的x坐标p1-ytemp=y_col;保存当前点的y坐标p1=newmazepoint;/声明内存p2-next=p1;前一个遍历点链表到下一个点的地址p1-last=p2;后一个遍历点链表到上一个点的地址p1-next=NULL;新生产的点没有链表到下一个点所以设为NULL (新产生的点是链表的最后一个点)if(Randtemp=Left & mazemapx_rowy_col-

14、2!=flag)判 断左边是否可以走如果可以走就不为；flagRandtemp=Left表示随机数等于 Left*/ Jmazemapx_rowy_col;新遍历至U 的位置*/口一上一次确定的位置/T mazemapx_rowy_col+1;新遍历到位置的相同方向的临近元素*y_col-=2;如果可以左走就要把对应的坐标也要改变；也就是行值减 2mazemapx_rowy_col=flag；把遍历到的新的迷宫地图元素也要置flagmazemapx_rowy_col+1=flag;/把遍历到的新的迷宫地图元素相同方向的临近元素也要置flag-pointcount;遍历到新的一个点，那么遍历点的

15、总数pointcount减1coutIchoice Leftendl;elseif(Randtemp=Right & mazemapx_rowy_col+2!=flag)/ 判断右边是否可以走如果可以走就 不为；flagRandtemp=Right表示随机数等于 Right/*/mazemapx_rowy_col;新遍历至U 的位置/ 上一次 确定的位置一口/mazemapx_rowy_col-1;新遍历到位置的相同方向的临近元素/*y_col+=2;如果可以右走就要把对应的坐标也要改变；也就是行值加 2mazemapx_rowy_col=flag；把遍历到的新的迷宫地图元素也要置flagma

16、zemapx_rowy_col-1=flag;/把遍历到的新的迷宫地图元素相同方向的临近元素也要置flag-pointcount;遍历到新的一个点，那么遍历点的总数pointcount减1coutI choice Rightendl;elseif(Randtemp=Up & mazemapx_row-2y_col!=flag)/ 判断上边是否可以走如果可以走就不 为；flagRandtemp=Up表示随机数等于 Up*/ mazemapx_rowy_col;新遍历到的位置 */口 mazemapx_row+1y_col;新遍历到位置的相同方向的临近元素*/ 上一次 确定的位置一*/*x_row

17、-=2;/如果可以上走就要把对应的坐标也要改变；也就是列值减2mazemapx_rowy_col=flag；把遍历到的新的迷宫地图元素也要置flagmazemapx_row+1y_col=flag;/把遍历到的新的迷宫地图元素相同方向的临近元素也要置flag-pointcount;遍历到新的一个点，那么遍历点的总数 pointcount减1coutI choice Upendl;elseif(Randtemp=Dwon & mazemapx_row+2y_col!=flag)/判断下边是否可以走如果可以走就不为；flagRandtemp=Dwon表示随机数等于Dwon*/ 上一次确定的位置一*

18、/口 mazemapx_row-1y_col;新遍历到位置的相同方向的临近元素*/ mazemapx_rowy_col;新遍历到的位置*/*x_row+=2;/如果可以下走就要把对应的坐标也要改变；也就是列值加2mazemapx_rowy_col=flag;把遍历到的新的迷宫地图元素也要置flagmazemapx_row-1y_col=flag;把遍历到的新的迷宫地图元素相同方向的临近元素也要置flag-pointcount;遍历到新的一个点，那么遍历点的总数 pointcount减1coutI choice Dwonendl;tail=p1; /把链表的尾巴赋值给新产生的点。(新产生的点是链

19、表的最后一个点)else /如果不可以行走就链表到上一个点直到链表到的某一个点可以行走为止coutPop To Last Pointlast;链表到上一个点地址if(tail-last =NULL)tail=head;x_row=tail-xtemp;读取上一个遍历点的x坐标y_col=tail-ytemp;读取上一个遍历点的y坐标+mazenum;执行次数 加1coutStepis： mazenumendl;统计执行的步数coutLastPoint coordinate is x is:xtemp y is:ytempendl;输 出上一个点的X坐标和Y坐标coutNowPoint coor

20、dinate is x is:x_row y is:y_colendl;输出当前 点的X坐标和Y坐标if(pointcount=0)如果每一个遍历点都遍历到了就打印地图，生成得迷宫是没有边界，即：没有外围墙的迷宫for(intC=0;CCol+2;+C)/输出迷宫最上面的的围墙即：上边界cout ;coutendl;for(intR=0;RRow;+R)if(R=0) /人口不能输出围墙coutIN;打印入口else cout”;输出迷宫最左面的的围墙即：左边界for(intC=0;CCol;+C)/件丁 各迷宫数组的元素if(mazemapRC=flag)如果迷宫数组的元素是路的话就打印空白

21、coutelse/如果迷宫数组的元素是墙壁（flag）的话就打印墙cout ;if(R=Row-1)打印出口coutOUT；else cout ;/输出迷宫最右面的的围墙即：右边界coutendl; for( C=0;CCol+2;+C)输出迷宫最下面的的围墙即：下边界cout ;coutendl;return 0;int get_count()int count=0;初始化用 于某一个点可以行走的方向数，(count用于统计某一个点可以行走的方向数)count=0;if(y_col-20)判断往左是否越界；即：是否超出迷宫数组if(y_col0)y_col=0;Left=0;coutLeftnot is Directioncount is:countendl; 输出往左不能走elseif(mazemapx_rowy_col-2!=flag)判断往左是否可以走+count;Left=count; elsecoutLef