图的遍历迷宫算法浅析.doc

《图的遍历迷宫算法浅析.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1.引言在平常的游戏屮，我们常常会碰到随机生成的地图。这里我们就来看看一个简单的随机迷宫是如何生成。2.迷宫描述随机生成一个m*n的迷宫，可用一个矩阵maze[m][n]来表示，如图:这里是两个迷宫的例子，其屮〃〃表示障碍物(Obstacleblock)o以图1丄迷宫为例，我们可用一个9*9的矩阵来表示:ill000111100101101101100111000111000111000011000111001101101101001111000111111111(矩阵表示是障碍物，0表示可以行走)3、迷宫生成算法（蓝色表示可以行走

2、，棕色表示是墙壁）如图3.1所示为迷宫的初始化情形，迷宫如果除去其迷宫的外围框架就是一个7*7的矩阵，如杲要生成一个完整的迷宫，那么就要遍历完图3.1所示的每一个可以行走的点，其中遍历的点也包含了入II和出口，如果每一个点都遍历完了就会生成一棵完整的遍历树，这棵遍历树包含了入口和岀口所以这颗树所描述的迷宫是有解的（即：入口到出口时连通的。）图3.2就表示图1.1迷宫遍历所得到的遍历树，树包含了入口和出口所以此迷宫有解。123p4567/I•1Ek11k/IitKkw891011121321516—171819J2022I232425

3、26272829

4、303132333435

5、■kI036I37381394041424314445146474849✓111Wk11V・图3.3图3.3表示的是图3.2进一步的处理后得到的最终迷宫图，就是在图3.2的基础上把遍历树上的是墙壁的元素置为可行走的元素。3.1元素的遍历图3.1.1描述了各个遍历点的连接关系其中1元素为起始遍历点，49元素为终点遍历点我们声明一个mazepoint类用来描述每一个遍历点xtemp表示当前点在数组中的x坐标，ytemp表示当前点在数组中的y坐标，定义为mazepoint对象的next用来链表一

6、个点的地址last用来链表上一个地址。oe~~e~~e图3.1.1classnazepoint〃定义一个类用于存放每一个遍历点的坐标public:intxtenp;〃用于存职一个遍历点的x坐梅intytenp;〃用于存放一八遍历点的y坐标nazepoint*next;〃用于存敬一个遍历点的下一个遍历点的地址nazepoint*last;〃庙于存放一个遍历点的上一个遍历点的地址声明了两个mazepoint的变量head和tail用于存储迷宫的链表的头地址和尾地址由于在迷宫刚刚开始的时候初始化元素是第一个所以头尾是相同的在主函数中把he

7、ad赋值给了pl,（pl是我们声明的一个临时存储的变量；P1和P2用于新的链表元素生成）mazepoint*p1;mazepoint*p2;mazepoint*head=NULL;mazepoint*tail=NULL;intnazenap[Rovj][Col]=头展化化化始始始8S谡仪图于于地由由宫向向位位何何n口文文LLNuNU直直intmain()<•••・接链泰元个一前有P1所舊素示示素直兀S元赋它亠空啤毗个址其“存事一地有b内元元亠勺茨佟iOK只的始〔一化化类表开(明始始始链刚十声初初初把刚E/F/r/r/r/T•p1=n

8、ewmazepoint;p1->xtenp=0;p1->ytenp=0;p1->last=NULL;head=p1;tail=p1;如图3.1.2所示元素1它连接到元素3和元素15,所以它可以遍历这两个元素，假设遍历的方向是随机的，如果第一次现在向右遍历那么元索3就被遍历并把它标志为flag（flag表示已经遍历过了不容许再次遍历），所以元素1和元素3都标志位flag说明在其它元素想遍历它们的吋候是不能再次被遍历了。这就有可能会遍历成一棵完整的树。图3.1.2如图3.1.3所示图1.1迷宫在生成时前13步，据图我们可知在第13步的时

9、候遍历到元素19,但是元素19周围的点都已经遍历过但同时还有其它元素还没有遍历到，所以要后退到上一个遍历过的元素判断是否有遍历的方向，所以链表到元素17,但是此元素也没有可遍历的方向所以要一直往上链表直到链表到某一个可以重新遍历的点为之。图3.1.3图3丄4是往上链表的示意图直到链表到元素45发现此元素拥有可遍历的方向，所以又重新往下建立新的链表，即元素47Slrp4Slep9图3.1.4图3.1.5是最终遍历完后的遍历路径，此时只要沿着遍历的方向把相应的“墙”拆掉就可以生成一个无外框的迷宫并且只能生成奇数行和奇数列的迷宫。Step

10、3Step4Step12Step13Pop]Step11Pop3%p5Step9图3.1.5图3.1.6是程序生成得33*33的迷宫图3.1.64、编程思路初始化pl变量成员变量并且把pl的地址传递给head下一个点是否有方向可遍历r