资源描述：
《随机迷宫生成算法浅析.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、摘要本文对随机迷宫生成进行了初步的研究和分析，并给出了两种不同的生成算法。最终的算法结合了图的深度优先遍历。通过対比两种算法之间，可发现，在实际问题中，结合了离散数学的方法往往非更有效率且效果更佳。关键词:随机地图生成(randommazegenerating)>深度优先遍(depth-firstsearch)1.引言在平滋的游戏中，我们常常会碰到随机生成的地图0这里我们就来看看一个简单的随机迷宫是如何生成。2.迷宫描述随机生成一个m*n的迷宫,可用一个矩阵maze[m][n]来表示,如图：[][][][][J□□[][〕[][][][〕[][][][][][][][][][][J[][][
2、][][][][][][][][][][][][][][][][JLJ[][][][][][][〕[][]这里是两个迷宫的例子，其中“『农示障碍物(Obstacleblock)o以图中第一个迷宫为例,我们可用一个7*7的矩阵來表示：1111111000000111111011000101101110110000001111111(0-可移动；1—障碍物)3.迷宫生成算法随机生成迷宫的方法有很多，这里介绍两种，第i种是作者没有结合离散知识所想出的方法；第二种是作者同学结合了离散数学后所采用的方法。3.1一种简单的迷宫生成算法假定起点在左上角，终点在右下角。方法就是：从起点开始，随机选择一个方向
3、移动,•直移动到终点，则移动的路径便是迷宫的路径。移动过程川要保证路径不要相交，不要超出边界。卜面用图例具体演示一•下实现的步骤。以下用BlueBlock代衣障碍物（obstacleblock）,WhiteBlock代表刖移动区•域（blankblock）o先假设幣个迷宫都为BlueBlock（初始点、结束点除外）。＞当有多个方向都有可能变为WhiteBlock时，需要随机选取一个方向，这就是随机迷宫的來源，如图:■■（这时，有下、左、右，三种可选的方向）二、这里，我们假设随机选了右作为路径的下一步。判断某一方向（黄点）是否可变为WhiteBlock,只要这一块都周围有三块为BkieBloc
4、k就可行，这样就保证了不会出现路径相交的情况，如图：（绿点有且仅有一个）三、如果产生到了一个死胡同（红点），则需冋退一格（绿点），再重复上而的步骤，如图。当然，为了实现这要求，需要一•个C通过路径的表（PathList）,依次记录所产生的WhileBlock的坐标，当走入死胡同吋，只需pop掉最后一个坐标（设为n）,这现在表中最后一个坐标（n・l）即为所需要的。上面是基本的思路，但有一个问题：如果出现如下情况，如图，则路径表会将所有的元素pop掉，而永远到不了出口。（永远到不了终点）解决方案双路径搜寻，即从入口、出口同时搜寻路径，如图。山于产生那种情况需要WhiteBlock越过对角线（如上
5、图，这里是左下角、右上角），所以双路径搜寻可以解决问题（问题没有出现的机会）。以上是通过很直接的思考方式得来的随机迷宫之实现。3.2结合图论的迷宫生成算法3.2.1图的深度优先遍历简介例如，要遍历上面这个图采収深度优先算法（从1开始）准备一个Stacks,预定义三种状态：A未被访问B止准备访问CC.经访问一、访问1,把它标记为12经访问，然后将于它相邻的并口标记为未被访问的点压入s中并标记为正准备访问此时系统状态：己经被访问的点：1还没有被访问的点：34678910止准备访问的点：25（存放在Stack之中）一.、从Stack中拿出第一个元素2,标记为12经访问，然后将于它柑邻的并口标记为未
6、被访问的点压入s中并标记为止准备访问，如图：此时系统状态：已经被访问的点：12还没有被访问的点：4678910止准备访问的点：35（存放在Stack之中）三、从Stack中拿出第一个元素3,标记为已经访问，然后将于它相邻的并且标记为未被访问的点压入s中并标记为正准备访问,如图:此时系统状态：己经被访问的点：1234还没有被访问的点：8910止准备访问的点：765（存放在Stack之中）依此类推，重复上面的动作，立到Stack为空，即所有的点都被访问。最后口J能的遍历情况,如图:3.2.2深度优先遍历之迷宫生成算法那么，这样该如何生成迷宫呢？不知大家注意到了没有，这种算法每一个步骤都要执行一个
7、操作，把刚刚访问过的点的柑邻的并口没有标记为被访问过的点压入Stacks中，然后下一步访问的就是Stack中的第一个元素。那么，当一个点有多个相邻点的话，该按什么顺序压入呢？随机.这就是随机生成迷宫的核心所在！现在我们换个角度看待问题。例如需要生成一个5*5的迷宫。坐标为(1,1)(3,1)(1,3)(3,3)的①、②、③、④分别代表节点，它们肯定可让人通过，然后，如果(2,1)设置成可通过，就代表①?②可通
