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

1. 引言 　　在平常的游戏中，我们常常会碰到随机生成的地图。这里我们就来看看一个简单的随机迷宫是如何生成。2. 迷宫描述 随机生成一个m * n的迷宫，可用一个矩阵maze[m][n]来表示，如图： 图1.1 图1.2 这里是两个迷宫的例子，其中“”表示障碍物(Obstacle block)。以图迷宫为例，我们可用一个 * 9的矩阵来表示： 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 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 1 1 1 1 1 1 1 1 (矩阵中1表示是障碍物，0表示可以行走) 3、迷宫生成算法 声明了两个mazepoint的变量head和tail用于存储迷宫的链表的头地址和尾地址由于在迷宫刚刚开始的时候初始化元素是第一个所以头尾是相同的在主函数中把head赋值给了p1，（p1是我们声明的一个临时存储的变量；p1和p2用于新的链表元素生成） 如图3.1.2所示元素1它连接到元素3和元素15，所以它可以遍历这两个元素，假设遍历的方向是随机的，如果第一次现在向右遍历那么元素3就被遍历并把它标志为flag（flag表示已经遍历过了不容许再次遍历），所以元素1和元素3都标志位flag说明在其它元素想遍历它们的时候是不能再次被遍历了。这就有可能会遍历成一棵完整的树。 图3.1.2 如图3.1.3所示图1.1迷宫在生成时前13步，据图我们可知在第13步的时候遍历到元素19，但是元素19周围的点都已经遍历过但同时还有其它元素还没有遍历到，所以要后退到上一个遍历过的元素判断是否有遍历的方向，所以链表到元素17，但是此元素也没有可遍历的方向所以要一直往上链表直到链表到某一个可以重新遍历的点为之。 图3.1.3 图3.1.4是往上链表的示意图直到链表到元素45发现此元素拥有可遍历的方向，所以又重新往下建立新的链表，即元素47 图3.1.4 图3.1.5是最终遍历完后的遍历路径，此时只要沿着遍历的方向把相应的“墙”拆掉就可以生成一个无外框的迷宫并且只能生成奇数行和奇数列的迷宫。 图3.1.5 图3.1.6是程序生成得33*33的迷宫 图3.1.6 4、编程思路 5、源代码 #includeiostream #include time.h using std::cout; using std::cin; using std::endl; #define Row 33 //用于定义迷宫的行必须为奇数，否则不能遍历到所以的点 #define Col 33 //用于定义迷宫的列必须为奇数，否则不能遍历到所以的点 #define flag 1 //点的标志位，如果找到符合条件的点就把它置为flag，只要某一个点置位为flag就不能再次被访问； int 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(); //定义可以获得某一个点可以行走的方向数的函数 class mazepoint //定义一个类用于存放每一个遍历点的坐标 { public: int xtemp; //用于存放一个遍历点的x坐标 int ytemp; //用于存放一个遍历点的y坐标 mazepoint *next; //用于存放一个遍历点的下一个遍历点的地址 mazepoint *last; //用于存放一个遍历点的上一个遍历点的地址 }; mazepoint *p1; mazepoint *p2; mazepoint *head=NULL; //初始化头由于没有指向如何位置所以赋值为NULL mazepoint *tail=NULL; //初始化尾由于没有指向如何位置所以赋值为NULL int mazemap[Row][Col]= //初始化迷宫地图数组 { 1 }; int