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

图的遍历迷宫算法浅析.docx1 .引言
在平常的游戏中，我们常常会碰到随机生成的地图。这里我们就 来看看一个简单的随机迷宫是如何生成。
迷宫描述
随机生成一个m * n的迷宫，可用一个矩阵maze[m][n]来表示，如图:


这里是两个迷宫的例子，其中〈I〃表示障碍物(Obstacle block)。以图
，我们可用一个9 *9的矩阵来表示:
ill
0 0 0
111
10 0
10 1
10 1
10 1
10 0
111
0 0 0
111
0 0 0
111
0 0 0
0 11
0 0 0
111 0 0 1 10 1 10 1 10 1 0 0 1 111 0 0 0
1 11111111
(矩阵中1表示是障碍物，0表示可以行走)
3、迷宫生成算法
（蓝色表示可以行走，棕色表示是墙壁）
，迷宫如果除去其迷宫的外围框架 就是一个7*7的矩阵，如果要生成一个完整的迷宫，那么就要遍历完 ，其中遍历的点也包含了入口和出 口，如果每一个点都遍历完了就会生成一棵完整的遍历树，这棵遍历 树包含了入口和出口所以这颗树所描述的迷宫是有解的（即：入口到 出口时连通的。），树包 含了入口和出口所以此迷宫有解。
，就是在图
。

，49 元素为终点遍历点我们声明一个mazepoint类用来描述每一个遍历点 xtemp表示当前点在数组中的x坐标，ytemp表示当前点在数组中的 V坐标，定义为mazepoint对象的next用来链表一个点的地址last用 来链表上一个地址。
© e ©
class mazepoint 〃定义一个类用于存放每一个遍历点的坐标
public:
int xtenp; 〃用于存放一个遍历点的x坐标
int ytenp; 〃用于存放一个遍历点的y坐标
mazepoint *next; 〃用于存放一个遍历点的下一个遍历点的弛址
mazepoint *last; 〃甫手存放一个遍厉点的上一个遍历点的地任
声明了两个mazepoint的变量head和tail用于存储迷宫的链表的头地 址和尾地址由于在迷宫刚刚开始的时候初始化元素是第一个所以头 尾是相同的在主函数中把head赋值给了 pl, （pl是我们声明的一个 临时存储的变量；pl和P2用于新的链表元素生成）
mazepoint *p1;
mazepoint *p2;
"绥仅囹 于于弛 由由宫 头壕 化化化 始始始 初初初 / / /
NuNU
郁郁
值值
有P1所 整素 元赋它4 空袍姓个址其」 存霍一地有一 内元元<■为佟
的始“ 一化化类表开" 明始始始链刚_ 声初初初把刚E //////
mazepoint *head=NULL;
mazepoint *tail=NULL;
int mazenap[Row][Col]=
1 int main()
p1=new mazepoint;
p1->xtenp=0;
p1->ytenp=0;
p1->last=NULL;
head=p1;
tail=p1;
,所以它可以遍历这 两个元素，假设遍历的方向是随机的，如果第一次现在向右遍历那么 元素3就被遍历并把它标志为flag （flag表示已经遍历过了不容许再 次遍历），所以元素1和元素3都标志位flag说明在其它元素想遍历 它们的时候是不能再次被遍历了。这就有可能会遍历成一棵完整的 树。
图
，据图我们可知在第13 步的时候遍历到元素19,但是元素19周围的点都已经遍历过但同时 还有其它元素还没有遍历到，所以要后退到上一个遍历过的元素判断 是否有遍历的方向，所以链表到元素17,但是此元素也没有可遍历 的方向所以要一直往上链表直到链表到某一个可以重新遍历的点为 之。
图

历的方向，所以又重新往下建立新的链表，即元素47
图
，此时只要沿着遍历的方向把相 应的“墙”拆掉就可以生成一个无外框的迷宫并且只能生成奇数行和 奇数列的迷宫。
S