迷宫游戏的设计与开发

齐齐哈尔大学学报JournalofQiqiharUniversity

Vol.30,No.1Jan.,2014

迷宫游戏的设计与开发

田翠华1,2，陈娅君1，陈玉明1

（1.厦门理工学院，福建厦门361024；2.沈阳工业大学，沈阳110023）

摘要：在Eclipse平台上，选择Java语言完成迷宫游戏的设计与开发。采用随机布点算法生成不规则迷宫地图，采用图的深度优先遍历算法随机生成规则地图。在相同的窗口，运用地图格的大小不同来生成较低、中等、较高三种不同难度的规则或不规则地图。把走迷宫的对象设置成角色方块，使用键盘的方向键控制当前移动点进行游戏。按照遍历规则地图的起点不同，把游戏分简单，中等，高难三种难易程度。运用回溯法从入口一步步进行探索，最后找到迷宫出口，并在界面上显示出该路径。编写画布类函数Canvas()实现游戏设置。游戏的成功开发表明，算法研究至关重要，应用这些算法开发游戏是有效的。关键词：迷宫游戏；深度优先遍历；算法设计；回溯法中图分类号：TP311.52

文献标志码：A

文章编号：1007-984X(2014)01-0001-05

迷宫游戏是最为经典的一款益智类游戏，曾经风靡全球。游戏构建出随机迷宫地图，玩家从入口进入迷宫，探索前行。往往是选择一个路口，走着走着走到死胡同，只能回来，选择其它路口。就这样，不断地折回，反复地寻找，最后才能找到出口，走出迷宫。当前的迷宫游戏研究，多是把目标放在寻路算法设计并验证其可行性和有效性上[1-3]。但游戏毕竟是用于娱乐的，应用算法、实现功能并具有耐玩性，才会受用户欢迎。所以，本文要解决的问题就是开发一款易玩有趣的迷宫游戏，最大限度的挑战与磨练人的好奇心和耐力，致使游戏过程乐趣无穷。同时，迷宫游戏开发[4-7]的特点是游戏种类繁多，算法设计比较复杂，非常锻炼人的编程能力和算法运用能力。所以，迷宫游戏的实现是很有挑战性的。这里，主要在Eclipse平台下并采用Java语言，使用深度优先遍历、随机布点等方法生成地图，运用回溯法寻找通路，最终，完成迷宫游戏系统的开发。

1绘制规则游戏地图

一般地，地图是有规则的。规则地图在文献[8]中有所描述。而这里迷宫规则地图又有所不同，是图论型地图，即符合图的定义，可用图的遍历来生成和访问。它在一个矩形区域上生成，该区域被水平垂直平均划分成小正方形为地图格，分别为墙和路两种，形成障碍物的为墙，能通过的为路，墙与路是相隔的。迷宫设有入口和出口，且从入口进到出口有唯一的通路路径。1.1

深度优先遍历现有图G，设定初始态为全部顶点都没被访问。一般地，在图G中选择源点即出发点V（可为任意点）。

先遍历V，并将其标记为被遍历；接下来,尽可能地先对纵深方向进行搜索，依次访问V的每个邻接点W。如果W没有被遍历，则从W出发继续递归使用深度优先遍历（Depth-firsttraversal,DFT），直至图中所有可达顶点V的顶点都被遍历。如果此时图G中还有没被遍历的顶点，则另选一个未被遍历的顶点作为新的出发点重复上述步骤，直到图中所有顶点均已被遍历为止。1.2

使用DFT绘制规则游戏地图

首先，定义画布类Canvas()。然后，调用NewMap()类，在画布上绘制地图，生成游戏窗口界面。以窗

口的左上角为原点，用MazeBox表示迷宫中的格，用其横纵坐标表示的二维数组定位。数组的值为格的状

收稿日期：2013-03-28

基金项目：厦门理工学院科学技术研究项目（YKJ11012R，YKT10037R）；国家自然科学基金项目（61103246）；厦门理工学院创新创业园项目

（201311062062）

作者简介：田翠华（1970-），女，博士，副教授，主要从事智能信息处理、云计算、物联网、算法

面的研究，2010110711@xmut.edu.cn。

·2·齐齐哈尔大学学报2014年

态，状态分为墙stock和背景back，墙为路障不可访问，背景构成通道可访问。初始地图的格都设为墙，不可达。接下来，将横纵坐标都为奇数的格存放在一数组中，将它们定义为未访问点并标记，marked=0表示未访问，marked=1表示访问过该点。然后，将横纵坐标均为奇数的格定义为背景（back），标记其为可访问，最后定义入口和出口，将它们设置为背景（back）。

结果，生成的画布中显示效果是每一个格的四面都是墙。开始遍历：从起始点开始向四个方向中的随机一个进行访问，每找到一个可访问的点，就去掉该点的那个方向上的墙，被访问的点继续以这种方式向下进行访问；对每个被访问的点都标记为已访问，当一个点对某个方向进行访问时，首先根据判断条件判断被访问的点是否已被访问，或者触到边界，如果该点四个方向都已被访问或无法访问，就退回上一个点，由上一个点继续重复进行这样过程。实际上，生成地图的过程就是拆墙的过程。这样一次遍历下来，就可以确定每个可访问的点都被访问过，而且由于每次访问的方向都是随机的，这就会形成很多种不同的遍历情况，也就形成了不同的迷宫，所以，迷宫地图是随机的。而且，从起点到终点只有唯一路径，这是由图的深度优先遍历算法的特点决定的。

在算法的实现上，主要是利用栈，第一次先把第一个起始点入栈，每访问到一个点，就把该点入栈，然后再对栈顶的点进行四个方向的随机访问，访问到新点时，就把新点入栈，直到这个点的各个方向都无法访问时，则让该点出栈。然后，用栈顶的点继续向四个方向访问，以此类推，直到栈里的点全部都退出，遍历就结束，地图也就形成了，算法流程见图1。

主要代码如下：

publicstaticvoiddft(Canvascanvas,int[][]pointArray,MyPointnow){//通常，首次引用该函数时now该为(1,1)入口xTem=now.getX();yTem=now.getY();pointArray[xTem][yTem]=1;//记录该点已访问pointStack.addLast(newMyPoint(xTem,yTem));//该点入栈now=findNextPoint(canvas,pointArray,now);//找下个点if(!(now.getX()==0&&now.getY()==0)){

/*必须判断能否找到下个点，即不能返回假坐标(0,0)*/

if(!(((xTem-now.getX())*(xTem-now.getX())+(yTem-now.getY())*(yTem-now.getY()))==4)){//如两点间坐标差平方和不为4则发生退栈事件

xTem=topreventDeleteTooMuch.getX();yTem=topreventDeleteTooMuch.getY();}

canvas.getBox((xTem+now.getX())/2,(yTem+now.getY())/2).setState(Enums.colors.BACK);//此点可通

//实现显示地图生成的过程

dft(canvas,pointArray,now);//深度优先递归运算}else}

//如果没有找到下一点则退出return;

图1

否

所有点是否都遍历过?是结束

使用DFT算法绘制规则地图

是

记录新点和路径随机找下个可访问的一个点，可达？

否

回退上一个点

从起始点开始进行深度优先遍历

开始

终点

第1期迷宫游戏的设计与开发·3·

深度优先搜索属于状态空间的盲目搜索，效率较低，耗费较多的时间与空间。而且，规模大时，栈容易溢出。

2随机布点绘制不规则游戏地图

随机布点是地图生成的一种，其中墙和路分布没有规则，是随机产生的。所以，是不规则地图，更不属于图论型地图。绘制过程：首先，利用循环将画布全部设定为背景（back），然后利用随机函数生成点（x，y），并将此点设定为墙（stock），编写一个算法来定义x与y的范围，让其产生的点足够多以至于能在画布上基本布满，然后将出口点定义为背景（back），接着再利用随机函数产生A和B两组点，每组10个，总共20个点，并将这些点全部定义为背景（back），系统状态定义为way，即定义为必可达点，方便后面生成迷宫出路，然后在产生的20个必可达点中，为了将处于第1组中的第1个点和入口点连接，应用随机递减的方法将第1个点坐标中的x与y随机依次递减1，直到横纵坐标x和y的值与入口点的坐标相同时，停止递减，而之中递减所生成的所有点都定义为背景（back），以实现入口点与随机产生的第1组中的第1点相连。然后，应用相同的坐标递减算法实现第1组中第2点与第1点相连，第3点与第2点相连，第4点与第3点相连。直到连接完第10个点。之后，将第2组中的10个点也按照此方法依次相连。然后，再将第2组的第10个点与出口相连。最后，利用随机函数，将第1组的点与第2组的点相连，以生成迷宫的一条路径，确保存在路径，得到不规则地图，而随机布点时可能生成了其他通路所以此地图的路径是不唯一的。

为了体现随机性，两组的10个点分别用两个二维数组储存，两组相连的时候将第1组A中的第2个2维数组随机生成一个点和第2组B中的第1个2维数组随机生成的点相连。代码如下：

inttemsOfUpandDown=rand.nextInt(A[1].length);Connect(canvas.getBox(A[1][temsOfUpandDown].getX(),A[1][temsOfUpandDown].getY()),

canvas.getBox(B[0][temsOfUpandDown].getX(),B[0][temsOfUpandDown].getY()),canvas);

A[0][1]A[0][2]A[0][3]A[0][4]A[0][5]

A[1][1]A[1][2]A[1][3]A[1][4]A[1][5]

B[0][1]B[0][2]B[0][3]B[0][4]B[0][5]

B[1][1]B[1][2]B[1][3]B[1][4]B[1][5]

起点（1,1）

由此可见，随机布点地图生成法过程归纳为：最初都是背景，随机生成墙；然后，在起点和终点之间随机生成20个必可达点；这些点相连打通通路，形成路径。此方法相对比DFT法是比较简单的。见图2。

终点（X,Y）

图2

使用随机布点绘制不规则地图

3采用回溯法显示路径

3.1

回溯法算法的基本思想

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择

并不优或达不到目标，就退回到上一步重新选择。这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。3.2

运用回溯法从迷宫入口开始寻找迷宫出口

首先，系统扫描当前地图。将所有地图格不是墙的点即背景back定义为系统状态way（系统使用），将所有墙stock的点定义为stock(系统使用)；其次，初始化一个栈，用来存放走过的路径即存放上下左右四个方向，此栈是为了在寻找出口时遇到“死路”的情况下使用；接着，再初始化一个栈，用来存放走过的点的坐标；然后从入口开始，向上下左右四个方向探测一步，看四个方向上的点的系统状态是否为way，若是，则将原来的点移动到该点，并将原来点的坐标标记为系统状态Been-Here（系统使用）已走过，再将其入栈，并将该方向入栈，利用移动后的点继续向后探索，以此类推。

当出现“死路”，无法再向下一个点探索时，运用回溯法进行回退。但由于往回的点是系统状态为

·4·齐齐哈尔大学学报2014年

Been-Here的点，按照上面的方法则无法退回，这时则调用方向栈顶的方向选择，调用该方向上的回退方法使该点回退，再将该方向出栈，并标记“死路”点为Dead，最后利用回退的点继续向四个方向探索。处理以上两个情况，最后找到出口，并在游戏中显示。显示路径算法流程图如图3所示。

起点开始探索

开始

4游戏实现

本游戏要实现的主要功能见图4，系统主界面见图5和图6。图5是DFT生成的规则地图，图6是随机布点生成的不规则地图。玩家可使用键盘方向键控制当前移动点进行游戏。

在游戏过程中可以改变游戏难度和DFT生成的地图的复杂度。方法：1）改变游戏难度：固定画布大小，可以通过改变出口坐标，从而改变迷宫中地图格的大小，得到简单、中等、高难三种不同难易程度的游戏；也可以同时改变画布和迷宫格的大小，但要求画布的大小一定要大于迷宫的最大横纵坐标。以随机布点生成不规则地图为例，图7是画布图格数目设成（91,103），难易程度要比图6是（49,55）时的情况要高难得多。鉴于篇幅未列出中等难度的图示。2）改变地图复杂度：通过选择不同起始点（即画布的左上角、右上角和右下角）开始DFT遍历，可以得到较低、中等、较高三种不同复杂度的游戏，图8是中等难度的遍历深度的游戏，比图9为较高难度遍历深度的游戏要容易。鉴于篇幅未列出其他游戏难度和地图复杂度的图示。

砖块背景所有颜色颜色颜色设置设置设置

颜色设置

游戏难度设置系统设置

找到下一个点，可达？

是

记录路径

否

终点是结束图3

否

回退上一节点

是

是否还有节点未被遍历？否

显示路径功能模块程序算法流程图

迷宫游戏系

统

地图生成游戏操作游戏帮助

关

随机布点

遍历深度

刷新地图

显示路径

播放音乐

退出游戏

于

简中高单等难

较低

中较等高

图4迷宫游戏功能模块图

图5简单游戏难度的DFT生成的较低复杂的规则地图的迷宫游戏界面

图6简单难度的随机布点生成的不规则迷宫游戏界面

第1期迷宫游戏的设计与开发·5·

图7高难游戏难度的随机布点方法生成的不规则迷宫游戏界面图8中等游戏难度的中等遍历深度的DFT生成的规则地图迷宫游戏界面

同时，玩家可根据自己的喜好使用鼠标点击进行设置。主要有：设置砖块颜色，玩家可以改变障碍物砖块的颜色；设置背景颜色，玩家可以改变背景的颜色；重置所有颜色，玩家可以根据自己喜欢的颜色对界面中的颜色进行重新设置。

最后，可以播放音乐。当玩家点击播放音乐时，接收信息，调用音乐进行播放。此模块的设计是为了让玩家可以一边玩游戏一边听音乐，享受视觉与听觉的结合。

5结束语

本文在Eclipse平台下，使用java语言，开发了迷宫游戏。方法是采用对图的深度优先遍历和随机布点法可生成地图，运用回溯法能够显示路径，同时，可以设置游戏。从而，完成一个真正的简单有趣耐玩的迷宫游戏的开发。经过反复游戏实测，最后，满足用户需求。

参考文献

[1]王桂平，孟宪虎.多因素制约的迷宫问题最优解的求解算法[J].计算机应用与软件，2012，29(3)：171-174.[2]遇娜，简广宁.回溯法求解迷宫问题[J].天津职业院校联合学报，2011，13(8)：46-49.

[3]李少保，赵春晓.基于多Agent遗传算法求解迷宫游戏[J].北京建筑工程学院学报，2011，27(3)：39-43.[4]胡正红.一种寻路算法在游戏中的应用[J].山西电子技术，2009(6)：53－54.

[5]徐，李仁发，颜一鸣.分支限界法在游戏地图寻径中的应用[J].计算机工程与应用，2007，43(1)：104-106.[6]邱仲潘.Java游戏编程[M].北京：科学出版社，2009.[7]田翠华.算法设计与分析[M].北京：冶金工业出版社，2007.

[8]Wikipedia.Regularmap(graphtheory)[P/OL].http://en.wikipedia.org/wiki/Regular_map_(graph_theory).

图9

中等游戏难度的较高遍历深度的DFT生成的规则地图迷宫游戏界面

（下转第24页）

·24·齐齐哈尔大学学报2014年

[6]BonehD，BoyenX.Efficientselective-IDsecureidentity-basedencryptionwithoutrandomoracles[C].AdvancesinCryptology-EUROCRYPT2004，Berlin：Springer-Verlag，2004：223-238.

[7]BonehD，BoyenX.Secureidentitybasedencryptionwithoutrandomoracles[C].AdvancesinCryptology-CRYPTO2004，Berlin：

Springer-Verlag，2004：443-459.

[8]WatersB.Efficientidentity-basedencryptionwithoutrandomoracles[C].AdvancesinCryptology-EUROCRYPT2005.Berlin：

Springer-Verlag，2005：114-127．

Asecuree-mailschemebasedonIBE

ZHANGLong，GUOYue

（SchoolofMathematicalSciences，HeilongjiangUniversity，Harbin150080，China）

Abstract：Atpresent，mostofthesecuree-mailschemesarebasedonPKI，theyneedtocompleteaseriesofoperationandmanagementofcertificateduringusing，andexisttheshortcomingsoftime-consumingandlowefficiency．Weproposeasecuree-mailschemebasedonIBE，itsolvestheproblemofverifythevoteridentityintheexistingschemes，andimprovestheefficiencyofthesecuree-mailscheme．Meanwhile，thenewschemeincreasestherecipient’scertificationprocesses，thesecurityofe-mailschemeisenhanced．Finally，wepointoutthattransportkeythatusestheplaintextdoesn’taffectthesecurityofthescheme，andeffectivelysolvesthetransmissionproblemofsecuritychannel．

Keywords：cryptography；identity-basedencryption；e-mail（上接第5页）

DesignanddevelopofmazegameTIANCui-hua1,2，CHENYa-jun1，CHENYu-ming1

（1.SchoolofComputer＆InformationEngineering，XiamenUniversityofTechnology，FujianXiamen361024，China；

2.SchoolofSoftware，ShenyangUniversityofTechnology，Shenyang110023，China）

Abstract：ThepaperdesignedanddevelopedaMazegameundertheEclipseplatformbyusingJavadevelopmenttool.Therandomdistributedpointalgorithmisusedtogenerateanirregularmap,andthealgorithmofdepth-firsttravelingisusedtogeneratearegularmap.Settingdifferentsizeofthemap’sgridinthemaponthesamegamewindowformsthreekindsofdegreeofdifficultywhicharelow,medium,andhigh.Setthegamewalkerasaroleobject,usethekeyboard’sarrowkeystocontrolthecurrentpointmove,andwecanplaythegame.Fromdifferentpointtotravelformthreelevelgamesonregularmapwhicharesimple,medium,anddifficulty.Takebacktrackingmethodtosearchthepathfromentrancetotheexitstepbystep,finditatlast,andshowthepathontheinterface.ProgramthefunctionCanvas()tosetthegameconfigurations.TheresultofsuccessfuldevelopmentoftheMazegameshowsthatalgorithmsareimportantandusingthemtodevelopthegameiseffective.

Keywords：mazegame；depth-firsttraversal；algorithmdesign；backtrackingmethod