基于JAVA的迷宫游戏的设计与实现论文 - 豆丁网.docx

《基于JAVA的迷宫游戏的设计与实现论文 - 豆丁网.docx》由会员分享，可在线阅读，更多相关《基于JAVA的迷宫游戏的设计与实现论文 - 豆丁网.docx（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、职场大变样社区():下载毕业设计成品职场大变样社区():下载毕业设计成品全套资料，全部50元以下毕业设计(论文)任务书第1页毕业设计（论文）题目：基于JAVA的迷宫游戏的设计与实现毕业设计（论文）要求及原始数据（资料）：1. 综述基于Java的迷宫游戏的设计与实现；2. 深入了解Java的设计与实现的相关技术；| 3.熟练掌握Java开发工具的应用分析，训练编写游戏程序的能力;.丄4/営祸实现,游彗针对某-场景的设片;5. 深入分析游戏设计中的关键技术与Java编写语言；6. 训练检索文献资料和利用文献资料的能力；7. 训练撰写技术文档与学位论文的能力。第2页毕业设计（论文）主要内容：1. 综

2、述基于Java的迷宫游戏的设计与实现；2. 了解Java的设计与实现的相关技术；3. 熟练掌握Java开发工具的应用分析，训练编写游戏程序的能力；4. 设计并实现游戏中针对某一场景的设计；* 5:深入弟斤隸戏设#中的关键技术与Java编写语言；6. 熟练掌握基于Java语言的游戏编写；7. 设计与实现针对某一对象类的设计的程序。学生应交出的设计文件（论文）：1. 内容完整、层次清晰、叙述流畅、排版规范的毕业设计论文；2. 包括毕业设计论文、源程序等内容在内的毕业设计电子文档及其它相关 材料。第3页主要参考文献(资料)：1 侯强.基于JAVA的RPG教学游戏研究与设计J山东理工大学，20072

3、田翠华，陈娅君等.迷宫游戏的设计与开发J.厦门理工学院，2014, (01)3 金伟，谭劲.一种数字迷宫游戏程序设计J.中国计量学院，2012, (07)4 赵海燕，赵小雨.基于面向对象的迷宫游戏的设计与实现J.天津大学，20085 杜邦国.基于Java平台的中国象棋游戏的设计与实现J.大连理工大学，20136 雷丽娟，郑永彬.使用java制作贪吃蛇游戏D九江职业大学信息中心，2013 (04)7 赵霞迷宫游戏：猫捉老鼠J幼儿教育.20088 Alf Inge Wang, Bian Wu, Jihad ElSana Using Game Development to Teach Softwar

4、e ArchitectureJHindawi Journa1. 20119 Anonymous Avysol Launches Maze Game for iPhone and AndroidJProQuest Journal. 201010 Sangrok Kim Gamma radiation transmission along the multibend mazesJKorea Customs Servicel.2016基于Java的迷宫游戏的设计与实现摘要迷宫游戏是我们最常见的游戏之一，该游戏出现在手机游戏、掌上游戏机和电脑游 戏当屮，因此迷宫游戏也是一个十分经典的游戏。一般的迷宫游

5、戏比较简单，游戏屮随 机出现一些障碍，要求玩家能够找出一条从起点到终点的通路。它看似简单确变化无穷， 迷宫游戏上手及其简单，但要熟练的掌握其中的奥秘且快速找出一条通路,难度却不低。 作为家喻户晓老少皆宜的大众游戏，其普及程度可以说是史上任何一款游戏都无法比较 的。本设计是一款基于Java的迷宫游戏。目前用于游戏开发的计算机语言多种多样， 而Java只是其中一种。然而，Java是现在全球最时髦的开发工具之一，它拥有一套庞 大且完整的类库，内置了其他怨言需要靠库甚至是操作系统才能支持的功能。所以，程 序员可以很容易的用Java编写并运行基于Java的游戏。本游戏是一个基于java的迷宫游戏，利用e

6、clipse平台实现游戏的基本功能。关键词游戏；迷宫；JavaMaze game based on JavaAbsractMaze Game is one of the most common of our game , the game appeared in mobile games，handheld game consoles and conputer games which , therefore maze game is a very classic game. Generally relatively simple maze game , the game randomly som

7、e obstacles , requiring players to be able to find a path from start to finish It seems simple indeed enormous, and its sinple maze game started , but a skilled master mystery cut quickly identify a path，the difficulty really is not low As a well-known popular game for all ages , its popularity can

8、be said that the history of any game can not be compared.This design is a Java-based maze game Current computer language for a variety of game development，and Java is just one of them However 9 Java is now one of the worlds most fashionable development tools, it has a large and conplete library buil

9、t-in library or other complaints need to rely on the operating system to support functions Therefore, the programmer can easily written in Java and run Java-based games.This game is a maze game based on Java, the use of Eclipse platform to achieve the basic functions of the game.Keywords： game; maze

10、; Java目录1 绪论11.1课题的研究背景与意义112Java简介21.2.1名字起源21.2.2发展历史21.2.3语言特征21.2.4 开发平台42可行性研究52.1可行性分析52.1.1技术可行性52.1.2 经济可行性62.1.3 操作可行性62.1.4法律可行性62.2可行性分析62.2.1技术可彳性62.2.2 经济可行性63需求分析83.1 系统初步分析83.1.1用户需求分析83.1.2功能需求分析83.1.3系统的可靠性和可用性需求分析93.2用例分析93.2.1能义参与者93.2.2捕获用例94总体设计114.1 系统开发114.1.1系统开发的原则114.1.2系统设

11、计阶段124.1.3 结构设计阶段124.2相关算法介绍134.2.1深度优先算法生成迷宫介绍144.2.2普里姆算法生成迷宫介绍154.3 数据结构175详细设计205.1核心包的设计205.1.1 MazeFrame类的设计与实现205.1.2 MapPoint类的设计与实现225.1.3 SetDialog类的设计与实现235.1.4 MapPane 1类的设计与实现255.1.5 Ball类的设计与实现285.1.6 MazeMap类的设计与实现295.1.7 Info类的设计与实现305.1.8 SaveDialog类的设计与实现326 系统测试336.1测试的定义及其重要性336.

12、1.1 测试的定义336.1.2 测试的重要性336.2测试方法336.3 测试结果34结论37参考文献38致 谢39外文文献40中文翻译491绪论1. 1课题的研究背景与意义随着经济的快速发展，计算机的地位在人们生活中已日益突出，基于各种操作系统 的娱乐游戏也越来越多、越来越大众化，成为人们生活中必不可少的一部分。而随着人 们生活品质的提高，电脑游戏也越来越多元化，迷宫游戏就是其中的种。迷宫游戏操 作简单方便，也具有一定的思考力，能够引发人的思维及兴趣，老少皆宜，是一款经久 不衰的大众化游戏。游戏的最初目的就是让玩家在游戏中得到放松。游戏一直经久不衰，从早期游戏的 发展形态到如今的网络游戏等

13、，升级为更普及化的人众游戏，对人们的感官刺激愈加激 烈，同时也有更大的乐趣。对于编写游戏而言，Java已变得足够成熟。它现在是一种 开发能都在多种平台上运行的中小型游戏的很好的方式。此外，Java支持和其他库一 起工作，而且它的速度变得越来越快。由于Java游戏一般来说简单有趣，并冃对用户硬件要求极小，所以Java游戏通 常甲*85%的计算机用户都有吸引力 小 :迷宫的问题原本是一个经典的实验心理学的问题，其大概的内容是实验心理学家将 老鼠放入从没有顶的大盒子的入口处让其由此进入迷宫。迷宫屮被隔板隔成有很多的分 区设置，前进的方向可以形成很多的障碍，有可能某一次走入的那个位置，可能会将小 老鼠

14、带入到死胡同，从而要重新的探索新的方向去寻找到出口，而此时给老鼠动力的是 一位心理学家在迷宫的唯一的出口处放置的一块奶酪来吸引老鼠，从而给了老鼠外界的 动力，让其发现从迷宫屮通向迷宫的出口的位置。心理学家做这个实验最初时为了进行 学术研究而设置的，老鼠不知道出口的情况下，是如何识判断这条路是否走过，从而让 心理学家们可以研究老鼠的学习能力。有了这样一个启发，后來有的程序员开发出了各种迷宫的小游戏，这种迷宫的小游 戏是趣味性的游戏，可能不用太多的思考能力，但是要的是一种耐心，往往游戏者迟迟 走不出，或是走了很久，以为快到出口的地方吋，结果进入了死胡同，还要返回去再来， 会容易让人产生不耐烦的心态

15、，因为要逐一的去试探各种可能的方向。但是这种经典的 小游戏并没有因此而失去它的魅力，反而吸引了更多的玩家，现职场大变样社区():下载毕业设计成品在程序的设计者也更加注重提高游戏的趣味性，比如，游戏者的标志是很炫的卡通 人物，或是迷宫的障碍物设计的很有意思。所以综上所述我想到了用java编译一个迷宫游戏。1.2 Java 简介1.2. 1名字起源Java是印度尼西亚爪哇岛的英文名称。Java语言中的许多库类名称，多与咖啡有 关：如JavaBeans、NetBeans以及ObjectBeans等等。SUN和JAVA的标识也正是一杯 正冒着热气的咖啡。1.2.2发展历史 Java是一个通用计算机编程

16、语言，是并发的，类型，面向对象的。它的目的是让 应用程序开发者“一次编写，到处运行”，也就是说java可以在任何设备上开发，也 可以在任何装有Java虚拟机(JVM)设备上运行，而无需再次编译。截至2016年，Java是最流行的编程语言之一，特别是对于客户端，服务器的Web 应用程序，有报道称有900万开发者在使用Java语言进行开发。Java是由詹姆斯高 斯林在Sun Microsystems (这已经被甲骨文公司收购)创造的，并于1995年发布，作 为Sun Microsystems的Java平台的核心组件开发，Java语言多从C和C+中语法派生 出来的。1996 JAVA JDK 1.0

17、 一个小型的专注于网页的版本，可用于所有浏览器。1997 JAVA JDK 1. 1在用户界面上有所改进，重写了事件处理，增加JavaBeano1998 -JAVA JDK 1.2 (JAVA 2)重组了图形化界面、数据库互连等技术。2000JAVA JDK 1.3改进了多媒体，有更好的可访问性，编译也更快。2002. 2-JDK1. 4提升了 Java计算的性能与缩放能力，在性能上比1.3提升了将近 60%,基于图形界而的响应速度提升了 40%。至今在用。1.2.3语言特征1. 跨平台性所谓的跨平台性，是指软件可以不受计算机硬件和操作系统的约束而在任意计算机 环境下正常运行。这是软件发展的趋

18、势和编程人员追求的目标。之所以这样说，是因为 计算机硬件的种类繁多，操作系统也各不相同，不同的用户和公司有自C不同的计算机 环境偏好，而软件为了能在这些不同的环境里正常运行，就需要独立于这些平台。而在Java语言中，Java自带的虚拟机很好地实现了跨平台性。Java源程序代码 经过编译后生成二进制的字节码是与平台无关的，但是可被Java虚拟机识别的一种机 器码指令。Java虚拟机提供了一个字节码到底层硬件平台及操作系统的屏障，使得 Java语言具备跨平台性。2. 面向对象面向对象是指以对象为基本粒度，其下包含属性和方法。对象的说明用属性表达, 而通过使用方法来操作这个对象。面向对象技术使得应用

19、程序的开发变得简单易用，节 省代码。Java是一种面向对象的语言，也继承了面向对象的诸多好处，如代码扩展、代 码复用等。3. 安全性安全性可以分为四个层面，即语言级安全性、编译时安全性、运行时安全性、可执 行代码安全性。语言级安全性指Java的数据结构是完整的对象，这些封装过的数据类 型具有安全性。编译时要进行Java语言和语义的检查，保证每个变量对应一个相应的 值，编译后生成Java类。运行吋Java类需要类加载器载入，并经由字节码校验器校验 之后才可以运行。Java类在网络上使用时，对它的权限进行了设置，保证了被访问用 户的安全性。4. 多线程多线程在操作系统中已得到了最成功的应用。多线程

20、是指允许一个应用程序同时存 在两个或两个以上的线程，用于支持事务并发和多任务处理。Java除了内置的多线程 技术之外，还定义了一些类、方法等来建立和管理用户定义的多线程。5. 简单易用Java源代码的书写不拘泥于特定的环境，可以用记事本、文本编辑器等编辑软件来 实现，然后将源文件进行编译，编译通过后可直接运行，通过调试则可得到想要的结果。1.2.4 Ecl ipse 平台Eclipse是一个框架和一组服务,通过插件组件来扩展Eclipse.Eclipse提供了包含不 同插件的发行包,最典型的就是Java IDE开发工具(Java Development Tools,JDT).所以说 Eclip

21、se开发平台或者工具实质上就是插件的集合.尽管Eclipse是使用Java语言开发的，但它的用途并不限于Java语言，例如，支持诸如 C/C+和PHP等网站建设编程语言的插件己经可用,Eclipse框架还可用来作为与软件开 发无关的其他应用程序类型的基础，比如内容管理系统.但由于其开放源码，任何人都可 以免费得到，并可以在此基础上开发各自的插件，因此越来越受人们关注。近期还有包 括Oracle在内的许多大公司也纷纷加入了该项目，并宣称Eclipse将来能成为可进行任 何语言开发的IDE集大成者，使用者只需下载各种语言的插件即可。Eclipse 还包括插件开发环境(Plug-in Develop

22、ment Environment, PDE),这个组 件主要针对希望扩展Eclipse的软件开发人员，因为它允许他们构建与Eclipse环境无 缝集成的工具。由于Eclipse中的每样东四都是插件，对于给Eclipse提供插件，以及 给用户提供一致和统一的集成开发环境而言，所有工具开发人员都具有同等的发挥场 所。这种平等和一致性并不仅限于Java开发工具。尽管Eclipse是使用Java语言 开发的，但它的用途并不限于Java语言;例如，支持诸如C/C+、COBOL、PHP等编 程语言的插件已经可用，或预计将会推出。Eclipse框架还可用来作为与软件开发无关 的其他应用程序类型的基础，比如内

23、容管理系统。基于Eclipse的应用程序的一个突出例子是IBM Rational Software Architect, 它构成了 IBM Java开发工具系列的基础。2可行性研究可行性研究顾名思义，研究其的可行性。在软件开发实践中，为了避免盲目的软件 开发和不必要的损失，相关人员需要对开发特定软件项目的可行性进行研究，结合资金、 时间和环境等各方面的制约条件，对该软件产品是否能够解决存在的问题，是否能够带 来预期的效果和价值做出评估。可行性研究的目的不在于提出解决问题的方案，而在于 研究解决问题的必要性和可能性。2.1可行性分析2. 1. 1技术可行性开发本游戏的编程语言有多种，如：VC,

24、VB, Java等，但考虑到自身对语言的熟 悉程度和编写程序的困难度，选择Java语言进行游戏的开发。本游戏实在Windows环 境下开发的，一般机器配置就可以满足要求，对机器本身没有太高的要求，环境只需装 上jdk即可，Java是现在全球最流行的开发语言之一，他拥有一套庞大且完善的类库， 内置了其他语言所需要的靠库甚至是操作系统才能支持的功能，拥有一个虚拟机。 Eclipse是SUN公司开发的Java集成开发环境工具，是目前最优秀的Java集成开发工 具之一。2.1.2经济可行性由丁本系统使用到的工具一般机器都具冇，使用的环境也很简单，开发成本低。Java 一直以来由于其可以跨平台”以及“一

25、次编译，到处运行”等特点，且因为Java游 戏简单有趣，并且对用户硬性要求极小，所以Java游戏通常对85%的计算机用户都有 吸引力。配置较低的电脑也能进行java游戏的开发，一台电脑就行，开发成本低。由于java 具有跨平台以及一次编译，到处运行的特点，开发出来的游戏可以放到各人游戏平台上 发售，玩家可以在电脑，浏览器，手机等各种平台运行。而且软件维护简单，实用性强, 一次开发使用，即可长久使用，当软件满足不了用户需求时，只需对用户的需求进行添 加即可。2.1.3操作可行性由于整个系统的开发过程中从操作简便、界面美观、灵活使用、的用户要求为出发 点，界面设计是要充分考虑玩家的感受，界面比较直

26、观，互动性很好，操作起来简单明 To2. 1.4用户使用可行性本软件操作简单，对用户的要求，不需要多强技术能力。2.1.5法律可行性信息产业部已将游戏通用引擎研究及师范产品纳入国家“863计划”，这是屮国首 次将游戏技术纳入国家科技计划当中。文化部也想国内多家游戏业的实力厂商首次颁发 了网络文化经营许可证，加人对游戏的监管力度，进口游戏的审查制度，限制国内 对国外的受理措施。科技部指定科技发展计划，将把游戏开发的扶持力度加大。这样一 来，国内游戏厂商将可获得发展的核心技术平台，政策有利于保护中国游戏软件的自主 知识产权，这位游戏开发发展创造了良好的政策环境。2. 2游戏设计特点2. 2. 1设

27、计初衷人们总是有一颗好奇的心，想不断的挑战自我。不论在现实亦或是游戏，我个人认 为，迷宫总会勾起人们那颗跳动的心灵，大家都想征服它来证明自己。本游戏有预定的关卡，越到后面越难，极具有挑战性。而且在你挑战完关卡后，还 可以自定义更有难度的迷宫，会让你乐此不疲。2. 2. 2简要提示罗克说：“其实走迷宫可以不带线团，你按下面的三条规则去走，就能够走得进， 也能够走得出”第一条，进入迷宫后，可以任选一条道路往前走；第二条，如果遇到走不通的死胡同，就马上返冋，并在该路口做个记号；第三条，如果遇到了叉路口，观察一下是否还有没有走过的通道。有，就任选一条 通道往前走；没有，就顺着原路返回原来的叉路口，并做

28、个记号。然后就重复第二条和 第三条所说的走法，直到找到出口为止。如果要把迷宫所有地方都搜查到，还要加上一 条，就是凡是没有做记号的通道都要走一遍。553需求分析所谓系统分析，就是指在整个系统开发过程中，解决“做什么”的问题，把要解决哪 些问题，满足用户哪些具体的信息需求调查分析清楚，从逻辑上或者说从信息处理的功 能希求上提出系统方案，即逻辑模型，为下一阶段进行物理设计方案设计，解决怎么办 提供依据。3. 1系统初步分析3. 1. 1用户需求分析随着互联网的发展，进入信息吋代后，这是非常容易得到的网络资源共享。人们更 依赖于电脑产品。电脑的普及使得原本的生活不嫩更符合人们的需求，广大电脑爱好者

29、的迫切需要利用必要的娱乐活动电脑来丰富自己的生活，让电脑游戏产生的历史性时 刻。、- -Jvy据认为目前的游戏研究成果来看，在Java开发的游戏仍然是一个空白页，但它是 一个空口页，以不断填补。和Java语言，因为它的自然语言功能，很适合用于游戏开 发的应用程序，但由于在它的系统中的环境问题在游戏开发没有使用，更最近，由于 Java的的发展。它摆脱了束缚上升到游戏开发的表面。这也是玩家的迫切要求。3. 1.2功能需求分析系统功能的需求指定系统必须提供的服务。通过需求分析应该划分出系统必须完成 的所有功能。本作的功能模块主要包括游戏的后台设计，游戏的界面设计。游戏的引擎设计的需求分析：游戏后台是

30、游戏的灵魂，也就是这个游戏的框架,它的好坏直接决定着游戏的质量。 它是控制所有游戏功能的主程序，包括画面的处理，路径寻找算法的实现，接收玩家的 设置等。所以坚定一个游戏的好坏，从内部设计的原因上说，是从游戏的后台设计体现出来 的。一个游戏的后台设计，直接关系到游戏设计的其他方面，诸如游戏的图形系统、声 音系统及设计的物理模块等各方面。就如一台CPU样，游戏的后台也是直接牵制着 整个游戏的设计。它主要的作用是处理游戏的时间，运行游戏，输出相应提示，响应玩 家的游戏监听时间等。所以，游戏的后台设计是必要的功能模块，而且游戏的后台必须 设计好，这样游戏才具有更好的可玩性。游戏程序是一样精度要求很高的

31、程序系统，因 为其代码利用率很高。一个实时运行的最终作品，每秒都会运行成千上万的程序，且需 要极高频率在后台等待响应。因此，其伙计设计应当相当严谨。游戏界面设计的需求分析：作为一个游戏吸引玩家的最重要的方便就是几面。本作品界面简洁明了，是玩家人 容易上手操作，且适应性强。3.1.3系统的可靠性和可用性需求分析可靠性需求定量地指定系统的可靠性，例如，游戏在运行过程中不能频繁发生错误 而不得不中止游戏。可用性则与可靠性密切相关，它量化了用户可以使用系统的程度。例如，游戏的运 行必须保证随时可以，不能在一段时间内，游戏产生不可预见的错误而致无法运行等。3. 2用例分析用例分析就是捕捉系统、子系统、类

32、或者组件的行为，并通过用例图向外部用户展 示。统一开发过程作用主要是为了用例驱动。在迭代增量的基础上进行开发。用例既可 以对可能存在的需求加以捕获，又可以为分析提供了良好的测试基础。3.2.1定义参与者与系统，子系统或类参与者交互以外部用户，过程或理想化的作用的其他系统。可 能会出现代表一类的外部的用户交互与系统的参与者。通过分析证实，该系统的参与者： 管理员和用户。管理员具有所有权限的用户只有权进行查询。3.2.2捕获用例用例是一个外部可见的系统内聚功能单元，功能单元由一种被称为主体的类元提供，用例表示主体与系统单元的一个或多个参与者之间所交换的信息序列。下面对迷宫 游戏进行分析与说明，并列

33、举用例图。用户在系统中具有运行游戏、了解游戏规则、设置游戏、开始游戏、结束游戏五项 功能权限，如图所示3-2-2所示。图3-2-2用户模块4总体设计总体设计过程通常由两个主要阶段组成：系统设计阶段，确定系统的具体实现方案; 结构设计阶段，确定软件结构和功能模块。如图4为功能模块图：图4功能模块4.1系统开发4.1.1系统开发的原则系统开发是为了提供利益相关者有关测试的产品或服务的质量信息进行调查。软件 测试也可以提供一个客观的独立观点的软件，让企业休会和理解软件的风险实现。测试 技术包括执行程序或应用程序与发现的意图的过程屮软件错误(错误或其他缺陷)。软件测试涉及一个软件组件或系统组件的执行，

34、以评估所关注的一个或多个属性。 在一般情况下，这些特性表明该组件或系统在测试的程度：1满足该指导其设计和发展的需要。2. 正确响应各种投入。3. 在可接受的时间内履行其职能。4为能充分地使用、5. 可以安装并在其预定的运行环境。6. 实现了一般的结果及其利益相关者的愿望。由于即使简单的软件组件可以测试的数量是无限的几乎所有软件测试使用了一些 策略来选择对的时间和资源是可行的测试。其结果是，软件测试通常（但不排他）试图 执行个程序或应用程序以找到的意图软件错误（错误或其他缺陷）。测试的工作是 个反复的过程，当一个错误是固定的，它可以照亮其他更深层次的缺陷，甚至可以创建 新的。软件测试可以提供有关

35、软件的质量和风险未能给用户和/或赞助商的客观，独立的 信息。软件测试可以尽快可执行软件（即使部分完成）存在下进行。该软件开发总体思路 往往决定何时以及测试是如何进行的。例如，在分阶段的过程，经过系统的要求已被定 义，然后在可测试的程序来实现发生最测试。与此相反，一个下敏捷方法，要求，编程 和测试经常同时进行。4.1.2系统设计阶段系统设计阶段的主要口的是确定软件如何做的问题。主要任务是确定系统屮的大模 块和设计方法，确定软件的功能模块和模块作用、组成、关系等。本系统是一款较为传统的游戏，当玩家打开游戏，显示游戏界面，设置游戏难度之 后便可开始游戏。当玩家找不到通往出口的路径时，可以点击“显示路

36、径”按钮来显示一 条从入口到出口的通路，不过这样的机会只有一次。也可以在此选择电会制地图”，选择 同一难度的其他地图样式，重新开始游戏。当玩家自己找到出口时，游戏便会提醒“成 功！是否继续?”4.1.3结构设计阶段经过系统设计阶段的思考和实践，需要对功能结构进行细致的划分。一个程序的结 构设计的好坏也需要决定其发展的重要指标。对一个程序的模块划分往往也能是程序设 计变得简单。本游戏的模块大致分为后台引擎和用户界面两大块，界面模块包括总体界面设计和 设置界面设计。后台引擎模块包括深度优先迷宫生成算法和普里姆迷宫生成算法。除此之外，还包括一个主界面控制类，用于界面算法和界面生成之间的连接控制， 还

37、有一个点类，主要用于定义点的相关操作，一个迷宫生成的接口类，类中声明了迷宫 生成算法所需要定义的三个方法。以为不做具体定义，所以被称为接口类。其总体流程如图4-1 ：图4-1总体流程图4.2相关算法介绍算法是解题方案的准确而完整的描述，其代表着用系统的方法描述解决问题的策略机制。算法就相当于对一定规范的输入，在有限的时间内获得所要求的的输出。描述算 法的方法有好多种，常用的自然语言、结构化流稈图，伪代码等，其中最普遍的就是流 程图。本设计除了实现迷宫的相关功能之外，还着重就实现迷宫的算法进行研究，通过算 法及实现迷宫的特点比较深度优先算法和普里姆算法在迷宫生成方面的优劣性。4. 2.1深度优先

38、算法生成迷宫介绍DFSMap类使用深度优先算法得到地图的类。设置一个二维数组，数组的值为格子 的状态。初始地图的上所有的格都设为墙，不可达。之后，再定义出口和入口，也将其 设置为背景，可以被访问的通道。这样，生成的迷宫中显示的是每一个格子的四面都是 -Ute 丄回o从入口点开始向四个方向中的一个随机访问，每找到一个可被访问的点，就去掉该 点上的墙，可被访问的点继续以这样的方式向下进行下去。对每个已被访问的格子都设 置为已访问。当一个点对某一方向进行访问时，首先需要根据判断条件判断被访问的点 是否被访问过，或者处于边界，若该点的四个方向已经被访问或者无法访问，就退回上 一个点，而上一个点需重复进

39、行这一过程。这样一次遍历过后，可以确保每一个可被访 问的点均被访问过。由于每次访问的方向是随机的，这样导致许多种不同的遍历情况， 因为形成了不同的迷宫。所以迷宫的形成是堆积的，但是从起点到终点只有唯一路径。在算法上，只要是利用栈来实现。第一次先将第一个起始点入栈，之后每访问一个 点就将该点入栈，之后再对栈顶点的四个方向进行随机访问。若访问到新点，就将新点 入栈，直到这个点的四个方向都无法访问时，将该点出栈。然后利用栈顶的点继续朝着 四个方向访问。以此类推，直到所有的点全被遍历过，遍历就结束了，这样就形成了迷 宫地图。相关不意图如图4-2所小：图4-2深度优先算法生成迷宫4.2.2普里姆算法生成

40、迷宫介绍普里姆算法是图的最小生成树的一种构造算法。其构成最小生成树的过程为：在所 有“其一个顶点已经落在生成树上，另一个顶点尚未落在牛成树上”的边中取一条权值 为最小的边，逐条加在生成树上，直至生成树中含有n-1条边为止。PriMap类是利用普里姆算法实现迷宫的形成。首先，设置迷宫中的格子均为墙。 其次，选择入口点并将其设置为可行，然后将其邻墙放入列表中。当列表中有状态为不 可行的格子时，从列表中随机选释一个作为墙的格子。此时，如果它相邻的格子不是迷 宫的通路，则把墙打通，即设置此格子的状态为可行，让其成为迷宫的通路，再将该格 子的邻墙加入列表；如果墙的邻格已经是通路，则就从列表中删除这面墙。

41、两种算法都有各自的有点，从两种生成算法所生成的迷宫屮可以很清楚的看出。深度优先算法所生成的迷宫有些扭曲，曲折较多，但想要找出一条通路比较容易。所以 深度优先算法适用于较为简单的迷宫的生成。相较而言，普里姆算法比较复杂。其生成 的迷宫岔路较多，生成的迷宫看起来很自然，但是想要找出一条通路是比较有难度的。 所以相比，普里姆算法适用于难度较大的迷宫生成算法。相关示意图如图4-3o图4-3深普里姆算法生成迷宫4.3数据结构介绍数据结构对编写出一个高效的程序是非常有用的，它对分析即将处理的对象的特 性和各对象Z间的关系都有一种明确的思路。程序中最后用了数据结构中的递归，递归函数就是一个函数宜接的调用自己

42、或者是 通过系列的调用语句间接地调用自己，在程序设计中，递归函数是个非常好而且有 力的工具，通过调用它可以省去很多繁琐的步骤，这其中的原因有三条：1可以定义很多递归的数学函数。2有的数据结构的本身也具有递归的特性。3有时候用递归求解比I用迭代更加的简单和方便。有时候在用到递归函数时，通常需要多次的调用，递归 函数的执行有点类似于汇编程序中主程序和子程序这间的接口和信息的交换，而在高级 语言中，这种函数和被调用函数之间的信息交换是通过栈来执行的。在来看看，当一个 运行着的函数调用另一个函数时，系统做了哪些工作。首先，系统会将主调函数的所有 的实参数和返回地址等一些信息通过栈来保存起来。其次，系统

43、要为分配存储区给被调 用的函数的局部变量。最后，将控制权转移到被调用函数的入口。而当被调用函数返回参数到调用函数Z前，系统会做好这些工作：将被调用函数的 计算结果保存，将分配给被调用函数的存储区释放，根据被调用前保存的返回地址将控 制权重新交回到调用函数。当有多个函数嵌套调用时，都是按照后调用先返回的原则，而这些信息的传递和控 制权的移交都是通过栈来实现的，系统会安排一个栈自动保存的程序运行期间所需的数 据，当调用一个函数时，系统就会在栈顶为其分配一个存储区间，有函数退出来时，会 释放这个存储空间。而且当前的正在运行的函数的数据区总是在栈顶的。在实际的程序 的执行过程中，主被调函数之间传递的不

44、一定是一个数值，也有可能是参数的地址。递归函数的好处是可以使结构很清晰，可读性也高，对用户编程和调试程序都带来 了很大的方便，而且也不需要用户来管理栈。介绍了一下回溯算法，也被称为启发式方法，选择的搜索方法，通过最优选择条件 提出搜索，你可以达到预期的目标，但在探索下一个步骤，如果不是最优的选择或低于 目标，您可以返回到前一步骤，特别是退出这个死胡同返回到上一步重新开始的方法被 称为回溯和满足这一状态的点称为“回溯点”，这是一种方法，一个系统性寻找问题的 解决办法。回溯是一个相对简单的和常用的搜索策略。基本的想法是用假定的步骤来解决一 个问题可能会有N个步骤，每一步都多种的解决方案，那么一旦每

45、一步按照一定的顺 序来测试每一步的各种方法，所有这些方法都失败了，那么就回去测试其余的方式。简 言之，如果你不能进一步，你将冋返，从而对于其他道路在尝试。一般步骤使用回溯算法来解决这个问题:第一是定义一个解决方案空间，它包含问 题的解决办法，那就是，每一步都以不同的方式出现，然后使用适当的搜索的方法來组 织解决方案空间，然后用深度优先的方法对解空间进行搜索，然后使用评估函数来避免 转移到不可能生成子空间的解决方案。.解决方案空间通常是解决方案的动态搜索过程中产生的，这是回溯的一个特性。 完全访问分为两种情况:第一，没有考虑到问题的本质性质，按照预定的秩序，建立 个良好的规则，这是盲目搜索的方法

46、，如迷宫和八皇后问题。另一个是考虑问题给予独 特的性质，就耶辔*合适申规贝g来提高搜索的效率。即启发k搜索。I我们在解决一个迷宫问题时，使用试探或者回溯开始从入口，沿着一个方向前进 探索，如果我们穿过，你可以继续向前;否则返回沿着上一步的路线的另一个方向，继 续探索，直到所有可能的路径都已经试探完毕，也没有找到出口，这表明迷宫中不存在 f 1T1 f TYI从入口进入迷宫，无论哪个位置的迷宫,比如规定东是首选方向，如果在某一位 置我们可以通过并继续往东走，如果在一个位置，在往东走不通时，将向南、西、北、 在三个方向依次走去走一趟年盾哪个能走通，直到走向出口。一个位置，在四个方向上 都是死胡同，

47、可以返回到之前的位置，在这个位置，对别的方向，都试一次，如果这个 位置没有方向可以试，再后退步，所沿的四个方向试探过后，最后回到起点，这表明 这个迷宫根本不通。迷宫的障碍不仅是指墙壁封锁了道路，已走的道路不能重复去走，不有没有走过的 道路一旦经过。为了确保在任何位置都可以用相同的路线返回，就耍用一个结构栈来保 存路径，这个结构栈是后进先出的堆栈，可以将当前位置的入口到走出出口的一个正确 的路径保存在栈中。但在解决迷宫的路径中，该路径必须是一个简单的路径。该路径不 能重复的出现在同一位置。该算法的基本思想是：迷宫的当前位置通过堆栈可以被放置在这个位置即当前路 径，并继续移动到下一个地点，以探索，然而，如果现在的位置不可通，即将堆栈头部 的元素从堆栈弹出，以恢复原来的方向,然后继续往这个方向向另外的几个方向去探索， 如果四个方向的通道都是不可通的，就可以从堆栈中将当前路径上的这个路径上删 除。用回溯算法实现了迷宫，使用堆栈的方法可以有效地解决了路径识别和迷宫问题， 如果能走出迷宫的随机模拟矩阵，你可以给它的轨迹的路径。图是