随机迷宫生成算法浅析_第1页
随机迷宫生成算法浅析_第2页
随机迷宫生成算法浅析_第3页
随机迷宫生成算法浅析_第4页
随机迷宫生成算法浅析_第5页
已阅读5页,还剩9页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、摘要 本文对随机迷宫生成进行了初步的研究和分析,并给出了两种不同的生成算法。最终的算法结合了图的深度优先遍历。通过对比两种算法之间,可发现,在实际问题中,结合了离散数学的方法往往非更有效率且效果更佳。 关键词:随机地图生成(random maze generating)、深度优先遍历(depth-first search) 1. 引言 在平常的游戏中,我们常常会碰到随机生成的地图。这里我们就来看看一个简单的随机迷宫是如何生成。 2. 迷宫描述 随机生成一个m * n的迷宫,可用一个矩阵mazemn来表示,如图: 这里是两个迷宫的例子,其中“”表示障碍物(Obstacle block)。以图中第

2、一个迷宫为例,我们可用一个7 * 7的矩阵来表示: 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 ( 0 可移动;1 障碍物 ) 3. 迷宫生成算法 随机生成迷宫的方法有很多,这里介绍两种,第一种是作者没有结合离散知识所想出的方法;第二种是作者同学结合了离散数学后所采用的方法。 3.1 一种简单的迷宫生成算法 假定起点在左上角,终点在右下角。方法就是:从起点开始,随机选择一个方向移动,一直移动到终点,则移动的路径便是迷宫的路径。移动过程中要保证路

3、径不要相交,不要超出边界。 下面用图例具体演示一下实现的步骤。以下用Blue Block代表障碍物(obstacle block),White Block代表可移动区域(blank block)。先假设整个迷宫都为Blue Block(初始点、结束点除外)。 一、当有多个方向都有可能变为White Block时,需要随机选取一个方向,这就是随机迷宫的来源,如图: (这时,有下、左、右,三种可选的方向) 二、这里,我们假设随机选了右作为路径的下一步。判断某一方向(黄点)是否可变为White Block,只要这一块都周围有三块为Blue Block就可行,这样就保证了不会出现路径相交的情况,如图:

4、 (绿点有且仅有一个) 三、如果产生到了一个死胡同(红点),则需回退一格(绿点),再重复上面的步骤,如图。当然,为了实现这要求,需要一个已通过路径的表 (PathList),依次记录所产生的White Block的坐标,当走入死胡同时,只需pop掉最后一个坐标(设为n),这现在表中最后一个坐标(n-1)即为所需要的。 上面是基本的思路,但有一个问题:如果出现如下情况,如图,则路径表会将所有的元素pop掉,而永远到不了出口。 (永远到不了终点) 解决方案 双路径搜寻,即从入口、出口同时搜寻路径,如图。由于产生那种情况需要White Block越过对角线(如上图,这里是左下角、右上角),所以双路径

5、搜寻可以解决问题(问题没有出现的机会)。 以上是通过很直接的思考方式得来的随机迷宫之实现。 3.2结合图论的迷宫生成算法 图的深度优先遍历简介 例如,要遍历上面这个图 采取深度优先算法(从1开始) 准备一个Stack s,预定义三种状态:A未被访问 B正准备访问 C已经访问 一、访问1,把它标记为已经访问,然后将于它相邻的并且标记为未被访问的点压入s 中并标记为正准备访问 此时系统状态: 已经被访问的点:1 还没有被访问的点:3 4 6 7 8 9 10 正准备访问的点:2 5 (存放在Stack之中) 二、从Stack中拿出第一个元素 2,标记为已经访问,然后将与它相邻的并且标记为未被访问的

6、点压入s 中并标记为正准备访问,如图: 此时系统状态: 已经被访问的点:1 2 还没有被访问的点: 4 6 7 8 9 10 正准备访问的点:3 5 (存放在Stack之中) 三、从Stack中拿出第一个元素 3,标记为已经访问,然后将于它相邻的并且标记为未被访问的点压入s 中并标记为正准备访问,如图: 此时系统状态: 已经被访问的点:1 2 3 4 还没有被访问的点:8 9 10 正准备访问的点:7 6 5 (存放在Stack之中) 依此类推,重复上面的动作,直到Stack为空,即所有的点都被访问。 最后可能的遍历情况,如图: 深度优先遍历之迷宫生成算法 那么,这样该如何生成迷宫呢? 不知大

7、家注意到了没有,这种算法每一个步骤都要执行一个操作,把刚刚访问过的点的相邻的并且没有标记为被访问过的点压入Stack s中,然后下一步访问的就是Stack中的第一个元素。那么,当一个点有多个相邻点的话,该按什么顺序压入呢?随机。这就是随机生成迷宫的核心所在! 现在我们换个角度看待问题。 例如需要生成一个5 * 5的迷宫。坐标为(1,1) (3,1) (1,3) (3,3)的、分别代表节点,它们肯定可让人通过,然后,如果(2,1)设置成可通过,就代表?可通过,结合图的遍历算法,我们看到,当 我们从访问到时,就把(2,1)设置为可通过,就相当开辟了一条道路,等到遍历结束,迷宫就生成了。 上图中的,

8、我们可看为一个2 * 2的矩阵,如图: 关键是在什么时候“开辟这条道路”。以上节中图的深度优先遍历简介为例子。假设依次访问到的点是:1 2 3 4 7 10 9 8 6 5 当刚刚访问到 9 时,会把8 6 压入Stack中,所以应该开通 9 到 8和6的道路,这样就可自动生成迷宫了。 迷宫路径的唯一性 这个算法,大家应该很清楚地看到,从起点到终点的路是唯一的(可以任选两点作为起点和终点) 算法的缺点 算法只能生成一个m * n的迷宫,其中m、n都是奇数。 4. 两个算法的对比分析 方法一生成的迷宫: 方法二生成的迷宫: 很显然,结合了深度优先遍历(Depth-first search)的算法

9、生成的迷宫要细致许多。 5. 结论 通过对一个简单问题的分析,可以看到,要将离散数学的方法与实际的具体问题相结合,可真正发挥出离散数学的威力。当然,如何将理论与实践相结合,那还需要个人自己去体味。本文仅起抛砖引玉的作用。两种迷宫生成算法技术文章 2011-02-23 11:18:26 阅读228 评论0 字号:大中小 订阅 .这里要介绍两种迷宫生成的算法,Recursive Backtracking和Ellers Algorithm。它们都生成的是Perfect maze,也就是说每个区域都连通,并且没有环的迷宫。我们现在说Recursive backtracking:迷宫的初始状态是墙壁都存

10、在。选择一个开始区域。随机得选择一个没有访问过的邻接区域,并打通与它之间的墙壁。此邻接区域称为当前区域。如果所有周围的区域都是访问过的,则退回上一个区域进行挖据墙壁,一直重复。当开始的区域被退回的时候,算法结束。 重新生成Ellers Algorithm是个节省内存的算法,在迷宫宽度固定的情况下,它能够使用固定的内存生成无限的迷宫。它一行一行的生成迷宫,并且生成当前行的时候,只考察上一行的数据。步骤如下:首先是第一行,将每个区域分别放入一个集合。当然区域之间的墙壁都是存在的。如果相邻的两个区域不在同一个集合,则随机得打通它们之间的墙壁(随机意味着可以打通也可以不打通)。并且合并它们所在的集合,

11、表示它们之间都是连通的。对于每个区域,随机的向下打通墙壁。并且每个集合至少要有一个区域打通向下的墙壁。生成下一行区域,并且将相应的区域(正好上面那个区域打通了向下的墙壁的)合并到上一行的集合。其它区域则将在它们自己的集合。这一步骤很关键,在这里可以舍弃上上行的数据了,也就是刚才的集合中只要包含上一行和当前行的区域。重复直至生成最后一行。对于随后一行,打通所有不在同一个集合的邻接区域,并忽略所有向下的墙壁。 一个在图像生成迷宫的代码技术文章 2011-02-22 16:35:04 阅读996 评论5 字号:大中小 订阅 .一个在图像上随机生成迷宫图,粉红色代表围墙。 代码如下,HANDLE CI

12、mageWaterMarkTest:ImageMaze(HANDLE hImage) if(hImage=NULL) WriteLog(TRA_LEVEL_WARN,_T("CImageWaterMarkTest:ImageMaze, Image is null"); return NULL; HANDLE hNewImage=NULL; int i, j; int nScale = 8; BITMAPINFOHEADER ds; memcpy(&ds,hImage, sizeof(ds); int effwdt = (ds.biBitCount * ds.biWi

13、dth ) + 31) / 32) * 4); int nPad = effwdt - (ds.biWidth * ds.biBitCount) + 7) / 8); BYTE* pbBits = (BYTE*)hImage + *(DWORD*)hImage + ds.biClrUsed * sizeof(RGBQUAD); WriteLog(TRA_LEVEL_DEBUG,_T("CImageWaterMarkTest:ImageMaze, Pic's width=%d, height=%d"),ds.biWidth,ds.biHeight); long lWi

14、dth = ds.biHeight/nScale;/ long lHeight = ds.biWidth/nScale; if(lWidth<4|lHeight<4) WriteLog(TRA_LEVEL_WARN,_T("CImageWaterMarkTest:ImageMaze, Maze's size is so small"); return NULL; BYTE *Maze = new BYTElWidth*lHeight; CreateMaze(Maze,lHeight-2,lWidth-2,lHeight,lWidth); int w,h;

15、 if(ds.biBitCount=8) for (i=0; i<lHeight; i+) for (j=0; j<lWidth; j+) for (int r=0;r<nScale;r+) for (int c=0;c<nScale;c+) h = i*nScale; w = j*nScale; if(Mazei*lWidth+j=0) pbBits(ds.biHeight-h-r)*effwdt + w+c=0; else /pbBits(h+r)*effwdt + w+c=255; else if(ds.biBitCount=24) m_ipFramework-&

16、gt;ShowProgressCtrl(); for (i=0; i<lHeight; i+) for (j=0; j<lWidth; j+) for (int r=0;r<nScale;r+) for (int c=0;c<nScale;c+) h = i*nScale; w = j*nScale; if(Mazei*lWidth+j=0) pbBits(ds.biHeight-h-r)*effwdt + (w+c)*3=0; pbBits(ds.biHeight-h-r)*effwdt + (w+c)*3+1=0; pbBits(ds.biHeight-h-r)*e

17、ffwdt + (w+c)*3+2=255; else /pbBits(h+r)*effwdt + w+c=255; m_ipFramework->SetPosProgressCtrl(int(i+1)*100/lHeight); m_ipFramework->SetPosProgressCtrl(100); m_ipFramework->HideProgressCtrl(); else WriteLog(TRA_LEVEL_WARN,_T("CImageWaterMarkTest:ImageMaze, no support this format");

18、delete Maze; return hNewImage;/ maze的实际大小是外围加一圈既,m+2,n+2void CreateMaze(BYTE *maze, int m, int n, int nRows, int nCols) int i,j; /int m,n; /迷宫行,列 srand(time(0); for(i=1;i<=m;i+) for(j=1;j<=n;j+) mazei*nCols+j = 2; /mazeij = rand()%2; /scanf("%d",&mazeij); / 设置起点和终点 int nStartm,nS

19、tartn;/ 入口 nStartm = 1; nStartn = 1; mazenStartm*nCols+nStartn=0; int nEndm,nEndn;/ 出口 nEndm = m; nEndn = n; mazenEndm*nCols+nEndn=0; printf("你建立的迷宫为o(_)o.n"); for(i=0;i<=m+1;i+) /加一圈围墙 mazei*nCols=1; mazei*nCols+n+1=1; for(j=0;j<=n+1;j+) maze0*nCols+j=1; maze(m+1)*nCols+j=1; int nCo

20、unt=0; int dx4=0;/ 下标:0-上, 1-下, 2-左, 3-右 int dy4=0; / 初始化路径 int nRdm = nEndm; int nRdn = nEndn; int nFindm = nEndm; int nFindn = nEndn; while (nFindm>=1&&nFindn>=1) nCount = 0; dx0 = 0; dy0 = 0; if(nFindm-1=nStartm&&nFindn=nStartn)/ 当前位置的'上'节点是入口 break; else if(maze(nFi

21、ndm-1)*nCols+nFindn=2)/|mazenFindm-1nFindn=0)/ 加入待查节点 dx0 = nFindn; dy0 = nFindm-1; nCount+; dx1 = 0; dy1 = 0; if(nFindm+1=nStartm&&nFindn=nStartn)/ 当前位置的'下'节点是入口 break; else if(maze(nFindm+1)*nCols+nFindn=2)/|mazenFindm+1nFindn=0)/ 加入待查节点 dx1 = nFindn; dy1 = nFindm+1; nCount+; dx2 = 0; dy2 = 0; if(nFindm=nStartm&&nFindn-1=nStartn)/ 当前位置的

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论