毕业设计（论文）-基于VC++的8数码游戏设计与开发.doc

学科分类号 本科学生毕业论文（设计）题目（中文）： 基于VC+的8数码游戏开发 （英 文）： The Development of 8 Digital Game Based on VC+ 姓 名： 学 号： 院 （系）： 计算机与通信工程系 专业、年级： 计算机科学与技术专业 指导老师： 2011年 月 日 目 录第1章 绪 论11.1课题背景及意义11.2八数码游戏的研究现状11.3本论文的研究内容21.4论文结构3第2章 游戏开发工具与关键技术介绍42.1 Visual C+概述42.2 MFC 应用程序框架52.3关键技术介绍6第3章 游戏的系统分析73.1需求分析73.2功能需求分析73.3可行性分析83.4游戏特色分析9第4章 游戏功能模块设计104.1系统模块设计104.2移动模块和鼠标交互模块流程图设计104.2.1移动模块设计104.2.2鼠标交互设计114.3详细设计124.3.1主窗体界面124.3.2图像的绘制124.3.3数据输入与输出134.3.4数据的移动134.3.5数据的检测144.3.6自动演示144.3.7游戏规则144.4算法分析154.4.1问题描述154.4.2算法设计15第5章 游戏功能模块的具体实现185.1可达性判断185.2移动模块的具体实现195.3自动演示模块的具体实现215.4路径搜索的实现225.5算法描述与实现235.5.1算法描述235.5.2算法的具体实现245.6鼠标交互操作的实现25第6章 游戏的数据测试266.1输入有效数据266.2输入不同为奇偶的数据286.3输入不符合规定的数据296.4测试总结30第7章 总结和展望31参考文献32致 谢33基于VC+的8数码游戏设计与开发摘 要八数码游戏是在33方格盘上,放有八个数码,剩下一个位置为空,每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置,要求通过一系列的数码移动,将初始状态转化为目标状态。作为本游戏的开发工具，Visual C+成为首选。它具有可视化的编程界面、详细的提示、以及完善的帮助文档，使得我在软件开发过程中少走了很多弯路，提高了我的开发效率。其中的MFC是由微软公司编写的一套专门用于 Windows 编程的 C+ 基础类库，它封装了 Windows API 的绝大多数功能，为用户开发 Windows 应用程序建立了一个非常灵活的应用程序框架。 本论文主要工作是该游戏的主要的功能模块的设计和实现：判断游戏是否有解，空白模块移动，自动演示模块，最优解搜索功能的实现，及鼠标交互操作的功能。其中最优解搜索功能主要是使用了A*算法来实现最短路径搜索。【关键词】 数码游戏 VC+ MFC A*算法 最短路径搜索 The Design and Development of8 Digital Game Based on VC+Abstract Digital games are eight 3 3 grid on the plate, placed eight digital, leaving a position is empty, its top and bottom of each box can be moved around the digital space.Problem given the initial position and target location, requiring a series of digital mobile, the initial state into a goal state. As the game development tools, Visual C+ preferred.It has a visual programming interface, the detailed tips, and complete help documentation, made me less in the software development process take a lot of detours, improve the efficiency of my development.MFC is one of a set of written specifically for Microsoft Windows Programming C+ based class library that encapsulates the vast majority of Windows API functions for users to develop Windows applications created a very flexible application framework. This thesis work is the games main function modules of the design and implementation: to determine whether the solvability of the game, move the blank module, automatic presentation module, the search function to achieve the optimal solution, and mouse interaction function.Search the optimal solution which is mainly used to achieve A * shortest path algorithm.【Key words】Digital Games MFC A * algorithm Shortest Path IV 第1章 绪 论随着世界经济的长足发展和计算机技术的日益成熟，计算机被应用到人类活动的各个领域，各种应用软件也相继问世，这其中有相当一部分是游戏软件。使用游戏软件自然是为了满足人们对娱乐性的要求，而有些软件大都采用3D设计对系统配置的要求较高。在众多游戏软件中，也不乏一些小游戏的身影，它们对系统的配置要求较低。能够满足人们对娱乐性的需求，是人们在完成工作娱乐时候的最好选择。现在越来越多的人投入到这种小游戏的开发当中，它已经成为一类必不可少的游戏软件。在各种操作系统中都附带了一些小的游戏，而这些游戏也成为电脑用户软件中不可或缺的一部分。如数码游戏、扫雷等。1.1课题背景及意义 1、背景说明8数码游戏操作能培养手眼协调能力游戏需要耐心的操作，以及手眼协调能力，只要一不协调就不能将数据块放在正确的位置。学习解决问题的方法及策略玩8数码游戏能学习推理思考能力，因为尝试不同的选择，到决定正确的一块放下去，也就是经过假设、判断到选择的过程，能让玩家学习运用逻辑来解决问题的方法。本程序使用的是微软最新开发的软件：Visual C+，VC+比C更简洁，为可视化界面操作，利用类实现各种不同的功能。2、课题意义在人工智能领域中，八数码问题一直都是一个游戏难题。介绍了八数码问题, 然后在启发式搜索算法上对A* 算法定义进行了解释，并在其旨在提高搜索效率的方面作了比较详尽的介绍，详细描述了基于图搜索算法的解决此类问题的一种启发式搜索算法A* 算法。再依据这种算法用可视化编程语言VC+ + 6.0 来实现八数码问题的求解过程，取得了预期的搜索解，提高了搜索效率。编译本程序的目的一是对自己所学知识的巩固，二是希望可以给玩家带来全新的感受。1.2 八数码游戏的研究现状在信息社会里，人们越来越依赖于搜索技术获取有用的信息，搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接关系到智能系统的性能和运行效率。在人工智能领域，所提供的每种问题求解方法，都需要某种对解答的搜索，从提出问题(即初始状态)到问题的解决(即最终状态)，有个求解的过程，也就是搜索过程。用于搜索的方法13主要有两大类：一类是盲目搜索，另一类是启发式搜索。盲目搜索是指在不具有对待定问题的任何有关信息的条件下，按固定的步骤进行的搜索，如深度优先搜索和广度优先搜索；启发式搜索是指在搜索中加入了与问题有关的启发性信息，这些信息可以指导搜索朝着最有希望的方向前进，加速问题的求解过程，并找到最优解，如A* 算法。八数码游戏的研究现状主要是如何选择更更快速、更高效地找到问题的解答。深度优先搜索是按照一定的顺序先搜索完一个分支，再搜索另一个分支，以至找到目标为止。由于一个有解的问题可能含有无穷分支，该搜索如果误入无穷分枝(即深度无限)，则不可能找到目标节点。所以，深度优先搜索策略是不完备的。另外，应用此策略得到的解不一定是最佳解。广度优先搜索是从初始状态一层一层向下找，直到找到目标为止。当我们发现目标节点时，可以同时找到从初始状态到达目标状态的一条最短路径。因此，这种策略是完备的。以上两种搜索有一个很大的缺陷，就是它们都是在一个给定的状态空间中穷举，极容易遇到以下问题：搜索中易出现循环，即访问某一个状态后又来访问该状态；搜索路径不佳便无法得到较好的中间状态集(即中间状态集的元素数量过大)；搜索过程中访问了过多的无用状态，这些状态对最后的结果无帮助。通过比较显示出启发式搜索的优越性：一方面，当发现目标节点时，可以同时找到从初始状态到达目标状态的一条最短路径；另一方面，由于搜索不是盲目的，因此不需要扩展每一层的所有节点，只需要扩展最有希望到达目标的节点即可。但是，对于这种搜索方式，使用正确的评估函数是相当重要的，评估函数选择的正确与否与搜索的效率直接相关。所以，在八数码游戏中，我选择了启发式搜索，即A*算法来实现最优解的搜索功能。1.3本论文的研究内容本文深入分析了课题的背景及意义、八数码游戏的现状和发展趋势、对游戏的需求分析(讲述游戏的功能和对操作进行分析)、游戏特色进行了分析说明。在前人的研究基础上结合算法处理对8数码游戏进行设计。本游戏在最优解搜索部分通过在对各种算法的可行性和效率进行了比较，最终选择了A*算法来实现该模块的功能。简单介绍了该游戏开发工具Visual C+和MFC，选择这两种开发工具简化了游戏的界面的设计与实现。通过系统的分析和策划，实现了游戏的主要功能。本论文主要工作内容是该游戏的主要的功能模块的设计和实现，如：判断游戏是否有解，空白模块移动，自动演示模块，最优解搜索功能的实现，及鼠标交互操作的功能。其中最优解搜索功能主要是使用了A*算法来实现最短路径搜索。在完成该游戏之后，还进行了部分的游戏数据测试，来判断该游戏的功能是否正确的实现。1.4论文结构第一章：主要介绍了课题的研究课题研究背景和意义、八数码游戏的发展现状、以及论文的研究内容，并介绍了本游戏的主要工作。第二章：主要是对游戏主要开发工具VisualC+、MFC的概述、使用的主要技术。第三章：主要介绍了游戏的系统分析，包括：需求分析、功能分析、可行性分析等。第四章：主要是对游戏进行设计，包括框架搭建、算法设计及分析。第五章：主要是进行游戏的实现，包括游戏的界面、核心功能、用户交互操作的实现。第六章：主要介绍了游戏的部分数据测试，以检测游戏的主要功能是否能够准确执行。第七章：对自己所做的工作进行总结，同时对数码游戏做了展望。第2章 游戏开发工具与关键技术介绍 本章通过介绍Visual C+和MFC的主要功能和关键技术介绍，并体现了这两种工具在该游戏的开发过程中的优势。2.1 Visual C+概述 Visual C+3为用户提供了一个可视化、通用的应用程序集成开发环境Developer Studio(也俗称Visual Studio)。Developer Studio包含了一个文本编辑器、资源编辑器、工程编译工具、一个增量连接器、源代码浏览器、集成调试工具以及一套联机文档(MSDN)。通过Developer Studio，开发人员可以完成项目工程的创建、程序的编辑、修改、运行和调试等各种操作。Developer Studio采用标准的多窗口用户界面，提供了大量实用工具以支持可视化编程的特性，包括项目工作区、AppWizard(应用程序向导)、ClassWizard(类向导)、WizardBar(向导工具条)、Component Gallery(组件画廊)等。1、项目工作区在Developer Studio中，项目工作区用于组织项目、元素以及项目信息在屏幕上的显示方式。在一个项目工作区中，可以处理一个工程和它所包含的文件、一个工程的子工程、多个相互独立的工程、多个相互依赖的工程。项目工作区底部有一组项目视图切换选项卡(包括3种视图)，用于从不同的角度查看项目中包含的工程和联机文档。在项目视图中，每个视图都有一个相应的文件夹，包含了关于该项目的各种元素。3种视图的含义如下所述。FileView(文件视图)：显示所创建的工程，展开文件夹可以查看工程中所包含的文件。ClassView(类视图)：显示项目中定义的C+类，可以查看工程中定义的所有类，展开类还可以查看类的数据成员、成员函数、全局变量、函数和类型定义。RourceView(资源视图)：显示项目中所包含的资源文件，展开文件夹可显示所有的资源类型。2、AppWizard(应用程序向导)AppWizard是一个标准的C+源代码生成器，它首先通过一系列的对话框来提示用户输入所需创建的程序信息。接着用户还可以指定其具有一些特性，如多文档接口或工具条、是否对数据库、OLE的支持等，然后AppWizard生成一些文件，这些文件构成程序的框架。由于AppWizard生成的程序是一个基本的Windows程序，用户可以直接编译并运行。AppWizard有为程序提供的功能性资源和代码，这样就节省了用户设计应用程序框架的时间和精力，用户所要做的工作只是直接往框架中添加自己的处理代码。 3、ClassWizard(类向导)ClassWizard是一个交互式工具，用来建立新的类、定制类，把消息映射成类成员函数，或者把控制框映射为类变量成员。ClassWizard所能识别的类必须在ClassWizard数据库文件(.CLW)中登记。在开发程序时，可用ClassWizard建立程序所需要的类，包括消息处理和消息映射例程(用于定位处理消息的代码)。使用ClassWizard，可以将成员函数或变量加入到一个类中，或修改已经存在的函数和变量。Wizard使函数或变量放在何处，如何称呼它们以及其他一些细节问题大大简化。使用ClassWizard可以实现创建新类，映射消息到函数，新建或删除消息处理函数，查看已被处理的消息并跳到消息处理代码处，定义成员变量。执行对话框数据检验、创建新类时，会自动加入方法和属性，建立整个类对象的框架模型，处理现有的类和类库。 4、WizardBar(向导工具条)WizardBar是一个可停泊的工具条，用于快速访问一些Developer Studio最实用的功能，比如ClassWizard或ClassView的一些功能。WizardBar还可以自动跟踪用户 程序的上下文，例如，当文本编辑器中的光标从一个函数移动到另一个函数时，WizardBar的显示会自动更新。实用WizardBar还可以增加一个新类，建立一个新的函数或方法，跳到一个已存在的函数或方法。WizardBar使得处理类、成员和资源更加方便。WizardBar包含了3个相关的下拉列表框，分别是类(Class)、过滤器(Filter)和成员(Member)。 5、Component Gallery(组件画廊)Component Gallery是一个组件库，保存着可以共享和重用的代码。这些代码包括由Visual C+自带的组件和从用户工程中增加到Gallery中去的用户自定义组件。2.2 MFC 应用程序框架 1、MFC 简介： MFC4(Microsoft Foundation Class)是由微软公司编写的一套专门用于 Windows 编程的 C+ 基础类库，VC+ 编程基本上都是围绕着 MFC 类库来进行的。它封装了 Windows API 的绝大多数功能，为用户开发Windows 应用程序建立了一个非常灵活的应用程序框架。其中CObject 是MFC类库的根类。 2、MFC 类库包括： (1)CCmdTarget 类：是 CObject 类的子类，它是 MFC 库中所有具有消息映射属性的类的公共基类。它的子类有 CWinThread 类， CWnd 类、 CDocument 类，从 CCndTarget 类派生的类能在程序运行时动态创建对象，并处理命令消息。 (2)CWinThread 类：是 CCmdTarget 的子类。CWinThread是所有线程类的基类，封装了应用程序操作的多线程功能。应用程序类CWinApp是CWinThread 的子类，封装了初始化、运行、终止应用程序的代码。 (3)CWnd 类：窗口类，是 CcmdTarget 类的子类，从 CWnd 派生的类可以拥有自己的窗口，并对它进行控制。窗口框架类 CFrameWnd 和 CView 类是 CWnd 的子类，前者创建和维护窗口的边框、菜单栏、工具栏、状态栏，负责显示和搜索用户命令，后者负责为文档提供一个或几个视图。视图的作用是为修改、查询文档等任务提供人机交互的界面。 (4)文档类 CDocument 类：是 CCmdTarget 类的子类，负责封装和维护文档。文档包括应用程序的工作成果或环境设置数据等，可以是程序需要保存的任何内容。 2.3 关键技术介绍该游戏主要的功能模块是最优解搜索功能。在该功能中，通过分析比较，选择了A*算法来实现该功能。A*算法是一种常用的启发式搜索算法。所谓启发式搜索就是在搜索中要对每一个搜索的位置进行评估，从中选择最好、可能容易到达目标的位置，再从这个位置向前进行搜索，这样就可以在搜索中省略大量无关的结点，提高了效率。其相对于广度搜索减少搜索的盲目性引，增加试探的准确性。 A*算法是利用一个评估函数，对状态空间中的搜索中的每一个搜索位置的价值进行评估，来决定每一次扩展中，哪一个是最有希望到达目标的节点。然后, 搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。其核心思想是通过引入一个启发式函数(或称为评估函数)，为了有利于回溯到早期路径的搜索，可以为评估函数增加一个深度因子，如果能够给定一个比较合适的评估函数，将会大大的减少搜索工作量。对于八数码问题的求解，可以用错位码的个数作为状态描述好坏的一个度量g(n)：即节点的错位码个数(即和目标节点比较, 位置不正确的数字个数)。另外，为了避免由于过分的优化试探而进入到无目的的漫游，加上一个深度因子h(n)：即搜索中节点n 的深度。则评估函数为f(n )=g(n)+h(n)：表示从初始节点到节点n的一条最佳路径的实际代价h(n)加上从节点n到目标节点的一条最佳路径的代价之和，最终可以找到一条从初始节点到目标节点的最佳路径的代价。第3章 游戏的系统分析3.1需求分析 当前各种游戏软件层出不穷。因为游戏的开发成本非常大，所以游戏的开发具有一定的风险性，但是一些小游戏的开发具有成本小，编写简单的优势，所以这些小游戏在游戏开发中也占有一席之地。在这类小游戏中主要是益智类游戏，它以游戏方法简单的特点得到大家的认可。成为人们在工作之余不可或缺的好伙伴。针对真种情况我用Visual C+编写了8数码这款小游戏。8数码游戏是广受欢迎的一种智力游戏，能够锻炼人的思维能力，动手能力。， 1、功能描述该数码游戏的基本功能：对于这个具有移动拼凑功能的游戏，其功能描述如下：玩家通过手动设置数字的初始状态和最终状态，玩家主要是对设置的初始状态进行移动，使其最终排列成为玩家设置的最终状态排列，玩家也可以选择机器功能让电脑自动进行排列，并可以自动演示其搜索过程，玩家还可以自己设置搜索的深度，一旦超过玩家设置的深度则算无解。 2、 操作特性分析 八数码是在33方格盘上,放有八个数码，剩下一个位置为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始状态转化为目标状态。状态转换的规则：空格周围的数移向空格，我们可以看作是空格移动，它最多可以有4个方向的移动，即上、下、左、右。九宫重排问题的求解方法,就是从给定的初始状态出发，不断地空格上下左右的数码移至空格，将一个状态转化成其它状态,直到产生目标状态。玩家可以选择人工，自主进行空格的移动以达到最终状态排列；也可以选择机器功能让电脑自动进行排列，实现数字的最终状态排列。3.2 功能需求分析通过分析，该游戏需要完成的功能有界面的设计、数字的移动、最优解的搜索。其中最主要模块是实现数字移动模块和最优解搜索模块。界面设计分析，该游戏可以由用户实现输入数据初始状态和目标状态、选择实现方式、移动功能、选择自动演示、设置搜索深度的功能。所以，可以把这些功能划分为区域，设计成按钮的形式，通过鼠标交互功能呢，实现用户的各种功能操作。数字移动分析，通过分析空白滑块的可移动方向，设计程序。当空白滑块位于中间时，其可以向任意方向移动；当空白滑块位于边界时，需要根据其边界的位置，进行分析其可移动的方向。最优解搜索分析，通过分析各种搜索算法10的特点，选择合适的搜索算法，提高搜索效率。通过比较，该游戏选择了A*算法来实现该功能。3.3 可行性分析在本节中主要介绍A*算法的可行性。 A*算法是一个很重要的启发式搜索算法。如果一般图搜索过程进行如下限制,则它就成为A*算法： (1) 把OPEN表中的节点按估价函数f(x)= g(x)+h(x)的值从小到大进行排序； (2) g(x)是对g*(x)的估计,g(x)0； (3) h(x)是h*(x)的下界，即对所有的x均有：h(x) h*(x) 其中,g*(x)是从初始节点到节点x 的最小代价，h*(x)是节点x到目标节点的最小代价，若有多个目标节点，则为其中最小的一个。 一般来说，对任意一个状态空间图,当从初始节点到目标节点有路径存在时，如果搜索算法能在有限步内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可纳的。 A*算法是可纳的，即它能在有限步内终止并找到最优解。我们分三步用以下三个定理来证明这一结论。 定理1 对有限图，如果从初始节点S0到目标节点Sg有路径存在，则算法A*一定成功结束。 证明： 首先证明算法必定会结束。由于搜索图为有限图，如果算法能找到解，则会成功结束；如果算法找不到解，则必然会由于Open表变空而结束。因此,A*算法必然会结束。 然后证明算法一定会成功结束，由于至少存在一条由初始节点到目标节点的路径,设此路径 S0= n0,n1 ,nk =Sg 算法开始时，节点n0在Open表中，而且路径中任一节点ni离开Open表后,其后继节点ni+1必然进入Open表，这样，在Open表变为空之前，目标节点必然出现在Open表中。因此,算法必定会成功结束。 引理1：对无限图，如果从初始节点S0到目标节点Sg有路径存在，且A*算法不终止的话,则从Open表中选出的节点必将具有任意大的f值。 引理2 在A*算法终止前的任何时刻，Open表中总存在节点n，它是从初始节点S0到目标节点的最佳路径上的一个节点,且满足：f(n) f*(S0) 定理2 对无限图,若从初始节点S0到目标节点t有路径存在，则A*算法必然会结束。证明：(反证法)假设A*算法不结束，又引理1知Open表中的节点有任意大的f值，这与引理2的结论相矛盾，因此,A*算法只能成功结束。 定理3：A*算法是可采纳的，即若存在从初始节点S0到目标节点Sg的路径，则A*算法必能结束在最佳路径上。 证明：证明过程分以下两步进行： 先证明A*算法一定能够终止在某个目标节点上。由定理1和定理2可知，无论是对有限图还是无限图，A*算法都能够找到某个目标节点而结束。 再证明A*算法只能终止在最佳路径上(反证法)。假设A*算法未能终止在最佳路径上，而是终止在某个目标节点t处，则有f(t)=g(t)f*(S0) 但由引理2可知，在A*算法结束前,必有最佳路径上的一个节点n在Open表中，且有f(n) f*(S0)f(t), 这时，A*算法一定会选择n来扩展,而不可能选择t，从而也不会去测试目标节点t，这就与假设A*算法终止在目标节点t相矛盾。因此，A*算法只能终止在最佳路径上。3.4游戏特色分析 该游戏看起来有点类似拼图游戏，该游戏与拼图游戏都是基于回溯算法的基础上设计。但该游戏的实现不同于拼图游戏：该游戏是用户输入一些没有规律数据，再由用户输入数据的最终排列状态，选择人工则由玩家自己进行空白模块移动，而选择机器则可以由机器自动搜索最优解；而拼图游戏是把图像分割，然后打乱图像，再由玩家拼成原来的图像。 第4章 游戏功能模块设计4.1系统模块设计8数码游戏程序的整体功能模块6，里面包含数据输入、功能选择、输出模块等。选择模块含人工和机器两个选项，而人工和机器下各有自己的功能模块。具体的模块设计如图4-1所示。输入模块初始状态目标状态输出模块步数输出最优解八数码游戏选择模块人工机器自动演示数字移动自动演示显示走步图 4-1 8数码游戏模块图4.2移动模块和鼠标交互模块流程图设计4.2.1 移动模块设计8数码游戏选择人工按钮时，需要判断空白模块的移动方向趋势，如果可以则按玩家的选择移动空白模块，如果不能则不允许移动，并给出提示。流程图如图4-2所示。是是否结 束空白模块是否能移动开 始判断移动方向趋势移动位置，修改数据状态图4-2 边界判断流程图4.2.2 鼠标交互设计鼠标左键单击事件，鼠标左键事件7是点击可移动的数据块，使得数据块可进行移动，如果达到边界，则不可移动；反之，则可以继续移动，如图4-3所示。鼠标左键事件结束单击移动功能中的方向键判断该空白块是否可以移动判断是否到达边界 移 动图4-3 鼠标左键流程图4.3详细设计详细设计是对整个程序的整体设计2，它包含窗体的设计、主窗体界面的设计、数字排列初始态和终态的设置、选择功能及搜索过程的显示等，以及本游戏最有特点的搜索最优解和自动演示功能。4.3.1 主窗体界面主窗体界面是游戏的最主要界面，它是各个功能模块实现的主窗体，同时也控制着整个程序的运行与结束，如图4-4所示。图4-4 主窗体界面4.3.2 图像的绘制游戏区域的视图绘制6较为简单。只需要根据当前游戏一维数组的内部数据，来对每一个数据进行绘制。先载入一个内存位图，再从源视图像位图中选择适当的区域将其拷贝到内存位图中，当所有这些图像方块都绘制到内存位图后，再一次性地将整体图像从内存位图拷贝到屏幕去。图像绘制流程如图4-5：开始结束获取文档内部数据的访问操作权限创建用于中介的内存设备环境以及与其其关联的内存位图在内存位图中进行数字的拼凑绘制图4-5 8数码游戏图像绘制流程图 根据上面的设计，可以开始绘制游戏区域了，游戏区域视图绘制也需要在其相关的视图类中重写图像绘制处理函数到jiugong中去重写，添写相应代码。4.3.3数据输入与输出 该游戏的数据输入是通过键盘进行操作的，限制只能输入08的数字。点击输入初始状态按钮，玩家可以在编辑框中输入08九个数字，则输入的数据排列为初始态，游戏并把数字为0的模块设置为可移动的空白模块；然后在点击输入目标状态按钮，玩家可以输入想要达到的目标状态排列顺序。 另外，该游戏还可以由玩家设置搜索深度，如果玩家输入的数据初始态到达数据的目标态超过用户设置的搜索深度，则按无解计算。 该游戏的数据输出部分主要是在状态提示编辑框中可以输出玩家走的步数和方向、最优解的步数及消息提示等。4.3.4数据的移动对于空白方块的移动，将用如下方法：在原始初始化好的地图数据的基础上，先将分割后的数据区域中数字为0的一块地方设置成为可移动模块，以便腾出一个方块位置，供相邻的数字移动。当某一数字从一个位置移动去填补另一个位置的空缺时，其原先位置又变成了空缺区域了。空白模块的移动是通过鼠标左键移动。鼠标左键的移动是点击操作区域的方向按钮，使空白滑块进行移动。需要注意的是，数字要根据事件做出反应，根据移动方向，进行移动处理。并且在作真正的位置移动前，需判断其是否到了边界而不能移动，当检测到没有到达边界时才开始作真正的移动操作。4.3.5数据的检测前面实现的众多功能都是围绕着位置这一关键物件来运作的，而数字排序胜利状态的检测自然也不例外了。数字排列的胜利检测很简单，就是从哪里来，到哪里去。当所有数字方块的排列顺序与游戏开始设置的排列顺序完全一致时，游戏就胜利结束了。函数体对所有方块元素进行了检测，只有当该数字位置区域所容纳的图片方块物件的ID与该区域下标数完全吻合，才证明这些方块又返回源点位置，游戏胜利结束。4.3.6 自动演示自动演示是由游戏自动完成的。玩家在能力不足时或想知道怎么能完成时，点击菜单中的自动拼图，系统将自动完成拼图。自动演示6的原理是：是在游戏开始之前，记录各个数字的原始位置，及其目的位置，根据最短路径算法，走一条最省时的路径，然后连一条虚拟的线。当玩家想要实现自动演示功能时，需要先选择机器按钮，再点击搜索最优解按钮，此时游戏将会判断数字排列实现的最少步数及该游戏是否有解。若有解则点击自动演示按钮进行演示，游戏将自动开始数字排列，并在搜索过程显示的窗口中显示数字移动过程。如图4-6所示。 图4-6 自动拼图4.3.7 游戏规则关于游戏的简介，如玩家不会使用本游戏，可以参照游戏规则察看游戏的操作方法。该游戏规则的说明位于主窗体界面的右侧，如图4-7所示。图4-7 游戏规则4.4算法分析4.4.1问题描述8数码问题又称9宫问题，与游戏“华容道”类似。意在给定的棋格的8个格子内分别放一个符号，符号之间互不相同，余下的一格为空格。并且通常把8个符号在棋格上的排列顺序称作8数码的状态。开始时，规则给定一个初始状态和一个目标状态，并要求被试者对棋格内的符号经过若干次移动由初始状态达到目标状态，这个过程中只有空格附近的符号可以朝空格的方向移动，且每次只能移动一个符号。 为方便编程和表示，本文中8个格子内的符号分别取18的8个数字表示，空格用0表示。并给定8数码的初始状态和目标状态分别如图4-8、4-9所示。382105764图4-8 初始状态 123804756 图4-9 目标状态 则要求以图4-8为初始状态，通过交换0和0的上、下、左、右四个方位的数字（每次只能和其中一个交换），达到图4-9所示目标状态。4.4.2算法设计根据任务要求，本文采用A*搜索算法12。但要在计算机上通过编程解决该问题，还应当解决该问题在计算机上表示的方式，并设计合适的启发函数，以提高搜索效率。(1)状态的表示在A*算法中，需要用到open表和closed表，特别是在open表中，待扩展节点间有很严格的扩展顺序。因此在表示当前状态的变量中，必须要有能指向下一个扩展节点的指针，以完成对open表中元素的索引。从这一点上看，open表中的元素相互间即构成了一个线性表，因此初步选定使用结构体表示问题的状态。表示问题的结构体包括表示当前节点状态的DATA和指向open表中下一个待扩展节点的指针NEXT。现在进一步考虑DATA中包括的内容：8数码问题的提出是以一个数表表示的，因此本文中采用一个的二维数组s33表示当前状态的具体信息。而为了保证在搜索到目标状态后能够顺利复现寻优路径，当前状态的DATA中还应该包括一个指向其父节点的指针father，这样，才能在达到目标状态后，通过指针father逐层回溯到初始状态，即复现寻优路径。另一方面，A*搜索算法是通过考察节点的代价值来决定open表的排序的，因此在表示当前状态的DATA中还应该有对当前节点代价值的描述。根据A*算法的定义，当前节点的代价值由估价函数给出，即：f(n)=(n)+h(n)其中：g(x)是从初始节点到节点x 的最小代价；h(n)是启发函数。因此，在DATA还应包括表示当前节点代价、最小代价和启发信息的f、h。最后，为提高程序的运行效率，减少程序扩展节点时搜索量，将当前0所处位置(i_0：0在s33中所处行号，j_0：0在s33中所处列号)也存储在DATA中。(2)启发函数的设计根据A*算法的定义，启发函数应满足：h(n)h*(n)。其中：h*(n)表示从当前节点n到目标节点s_g的最优路径的实际代价。并且，在满足h(n)h*(n)的条件下，h(n)的值越大它所携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索效率就越高。在8数码问题中，常用的启发函数为：“不在位”数码个数，或数码“不在位”的距离和。显然，后者的h(n)不小于前者，因此本文中采用数码“不在位”的距离和作为启发函数。(3)规则库设计0在某一位置时，能选择向左、向右、向上、向下移动中的哪几种策略进行移动，主要是由当前0所处位置（更具体地说是当前位置的行列号）和其祖父节点（为提高搜索效率，新扩展的节点应当至少不为其祖父节点）所决定的。当然，按照A*算法的思想，每扩展出一个新节点，都要判断其是否为有效子节点，不为有效子节点的不能加入到open表中。这一段的具体过程可以参考程序流程部分。算法流程图如图4-10所示：YYN开始初始化s_0，把s_0送入open表open表为空？把open表中的首节点，从open表中移出，放人closed表节点为目标节点？拓展节点n，将有效子节点加入open表，无效子节点删除成功，退出失败，退出N图 4-10 算法流程图其中，扩展节点n的具体步骤如下：a) 首先判断其是否在closed表已经出现过, 如果出现过，并且新节点的代价值比其小，则应将其从closed表删除，同时将新节点加入到open表；如果没有出现过，则转b。b) 判断其是否已经存在于open表中待扩展，如果出现过，并且新节点的代价值比其小，则应将其从open表删除，同时将新节点加入到open表；如果没有出现过，则说明该节点为一个全新的节点，转c。c) 将该节点加入open表。 第5章 游戏功能模块的具体实现 5.1可达性判断 可达性是指8数码的最初状态能否通过有限次的变化最终得到终态。为了保证算法的可行性，需要对不可达的8数码问题进行过滤。以往的算法都以未找到解决方案且open表为空来作为当前给定的初始与终结状态互不可达的判断依据。本文采用通过判断两状态各自逆序数之和的奇偶性是否相同来判断两状态之间是否可达。 判断该游戏是否有解得原理是根据初始态和目标态的秩序计算数字的逆序奇偶性，若不同为奇数或同为偶数，则无路径。判断有无解，通过返回0为偶，返回1为奇.，判断是否有路径。具体代码如下：int CJiuG:ComputeJO(JGState *jo)int result=0;int i,j;int k=0;int temp8;/除去0，将其余8个数依次加入到数组中for(i=0;i3;i+)for(j=0;jstateij!=0)tempk=jo-stateij;k+; /判断奇偶性for(i=0;i7;i+)for(j=i+1;jtempj)result+; result=result%2;return result;5.2移动模块的具体实现 空格移动16的代码比较简单，只要计算是否会移动到框外面就可以了，并在移动的时候顺便计算一下是不是已经是目标结果，这是用来给用户手工移动是给与提示用的，代码：bool CJiuG:MoveLeft(JGState *src,JGState *result) /左移 int x,y,tempx,tempy;for(x=0;x3;x+)for(y=0;ystatexy=0)tempx=x;tempy=y; if(tempy=0)return false;for(int i=0;i3;i+)for(int j=0;jstateij=src-stateij; result-statetempxtempy = src-statetempxtempy-1;result-statetempxtempy-1 = 0;result-curdistance=src-curdistance+1;result-prestate=src;result-nextstate=NULL;return true;bool CJiuG:MoveRight(JGState *src,JGState *result) /右移 int x,y,tempx,tempy;for(x=0;x3;x+)for(y=0;ystatexy=0)tempx=x