基于分支限界法的连连看局域网对战游戏的开发_毕业设计论文(编辑修改稿)

基于分支限界法的连连看局域网对战游戏的开发_毕业设计论文(编辑修改稿)内容摘要：

.................................................. 12 表 游戏的运行平台 ............................................................................................ 12 • 概述 连连看游戏简介 电脑游戏在人类的发展史中一直扮演着极其重要的角色，尤其是在工作日趋紧张、经济不断发展的现代社会中，电脑游戏已经不是传统意义中孩子的专利。 伴着游戏产业日益壮大，现代人类日常生活中经常用游戏来休闲娱乐，游戏市场有很大的潜力，很多国家都对游戏市场十分重视。 游戏大致分为两大类，即单机游戏（ Console Game）和网络游戏（ Online Game）。 所谓单机游戏指仅使用一台计算机或者其它游戏平台就可以独立运行的 电子游戏。 如 Windows 操作系统自带的纸牌、扫雷等小游戏程序，这一类游戏操作简单，难度比较低，对硬件的环境要求不高。 而网络游戏又称 “ 在线游戏 ” ，简称 “ 网游 ”。 指以 互联网 为传输媒介，以 游戏运营商 服务器和用户计算机为处理终端，以游戏客户端软件为 信息交互 窗口的旨在实现娱乐、休闲、交流和取得虚拟成就的具有可持续性的个体性多人在线游戏。 连连看游戏就是很经典的小游戏。 连连看来源于街机游戏 “ 四川麻将 ” 和“ 中国龙 ” ，是给一堆图案中的相同图案进行配对的简单游戏， 20xx 年，一个叫做朱俊的网友将这种形式搬到了 PC 上，立刻成为办公一族的新宠，并迅速传遍了世界各地 [1]。 饱受工作压力的人们没有太多的时间进行复杂的游戏，而对于这种动动鼠标就能过关的游戏情有独钟。 之后村子的连连看风靡版，阿达的连连看奥运版，连连看反恐版，还有敏敏连连看，水晶连连看等遍地开花，造就了一个连连看的新世界。 连连看游戏规则简单，在一个摆放了游戏牌的棋盘内，只要将相同花色的两个游戏牌 用三根以内的直线连在一起就可以消除，在规定的时间内消除了棋盘内的所有游戏牌，即可获得游戏胜利，否则游戏失败。 连连看游戏并没有绚烂的画面和庞大的场景，操作简单，对硬件和环境要求不高，但是却变化无穷，容易上手，男女皆宜，节奏很快，令人上瘾。 适度游戏，不仅能增强思维能力，提高智力，锻炼眼力，还能起到健脑益智的效果。 局域网连连看对战这样的智力游戏也被人们所接受，从而连连看从棋盘也走向了网络，局域网连连看对战不限制地点的模式深受连连看爱好者的喜爱。 连连看游戏上手极其简单，但是要熟练地掌握其中的操作与图案消除技巧，难度却不低，其普及程度也是非常高。 连连看游戏很快成为家喻户晓的大众游戏之一，也成为电脑游戏发展史上的一个经典。 由于连连看游戏具有的数学性、动态性与知名度，也经常拿来作为程序设计的练习题材。 传统的连连看游戏的最初运行界面如图 所示。 图 传统连连看游戏运行界面 状态空间搜索简介 状态是指在系统中决定系统状态的最小数目的变量的有序集合。 而所谓状态空间也叫做解空间，是指该系统的全部可能状态的集合 [2]。 状态空间搜索就是通过在状态空间中的初始状态出发，按照一定的顺序和条件对空间中的状态进行遍历，最终找到目标状态 [2]。 由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，称为状态空间。 问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。 这个寻找的过程就是状态空间搜索。 状态空间搜索广泛应用于优化问题中，如经典的 “ 01 背包问题 ” 、 “ 旅行商问题 ” 、 “ 迷宫问题 ” 、 “ 最大团问题 ” 、 “ n 皇后问题 ” 等，在计算机求解的过程中，都需要进行状态空间 搜索。 状态空间至少包含问题的一个最优解。 如对于有 n 种可选物品的 01 背包问题，其解空间由长度为 n 的 01 向量组成，该解空间包含了对变量所有可能的 01 赋值。 如当 n=3 时，其解空间为 {(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}，这个解空间可以用一颗完全二叉树来表示，如图 所示。 可以把解空间看作树或者图的形式，叶节点表示一个可能的解，从根节点 到叶节点的任一路径表示解空间的一个元素。 图 仅 3 个物品的 01 背包问题的状态空间树 面向对象方法简介 随着软件形式化方法及新型软件的开发，传统的软件工程方法的局限性逐渐暴露出来 [3,4]。 传统的软件工程方法是面向过程的，将数据和处理过程分离，增加了软件开发的难度。 由于问题空间与解空间的模型、描述方式的不同，它们之间存在着复杂的转换过程，尤其对于复杂系统及普遍存在的需求变化，就更难适应。 同时，传统的软件工程方法难于支持软件复用。 面向对象的方法则是将软件系统看作一系列离散的解空间对象的集合，并使问题空间的对象与解空间对象尽量一致，这些解空间对象相互 之间发送消息而相互作用，从而获得问题空间的解 [3,4]。 这样，问题空间与解空间的结构、描述的模型十分一致，减少了软件系统开发的复杂度，使系统易于理解和维护。 如果是按照以下 4 个概念设计和实现的系统，称为是面向对象的，即：面向对象 =对象 +类 +继承 +通信 [3,4]。 面向对象编程 （ Object Oriented Programming， OOP， 面向对象程序设计 ）是一种计算机编程架构。 面向对象程序设计的一些显著的特性包括 [3,4]： 1．程序设计的重点在于数据而不是过程； 2．程序被划分为所谓的对象； 3．数据结构为表现对象的特性而设计； 4．函数作为对某个对象数据的操作，与数据结构紧密的结合在一起； 5．重要数据被隐藏起来，不能为外部函数访问； 6．对象之间可以通过函数沟通； 7．新的数据和函数可以在需要的时候轻而易举的添加进来； 8．在程序设计过程中遵循由下至上（ bottomup）的设计方法。 论文内容与结构 本章为第 1 章，即绪论部分，本章之后，各章安排如下。 第 2 章，标题为 “ 面向对象分析与设计 ” ，阐述待开发的连连看游戏的面向对象分析与设计过程，包括用例建模、活动图建模、对象状态建模、对象交互建模、类图建模，并详细介绍了游戏中类 的设计。 第 3 章，标题为 “ 算法设计 ” ，重点阐述分支限界法对两张游戏牌进行 “ 寻路 ” 的算法，来判断两张游戏牌能否消去，同时给出了自动找出一对能消去的游戏牌、游戏牌重新排列、随机发牌、处理选中游戏牌、服务端套接字处理数据包、客户端套接字处理数据包等主要过程的算法设计。 第 4 章，标题为 “ 面向对象实现 ” ，阐述待开发的连连看游戏的面向对象实现过程，并给出编程时使用到的具体技术，如： Windows GDI 双缓冲、 Socket套接字编程。 结论部分，总结开发出来的连连看游戏系统的特点，并论证面向对象方法和分支限界算法思想在连连看游戏开发的可行性，并分析了开发出的连连看游戏的优势和不足。 • 面向对象分析与设计 用例图建模 用例建模与用例图的概念 用例建模是用于描述一个系统的功能（即系统应该做什么）的建模技术，用例建模不仅用于获取新系统的客户需求，还可以作为对已有系统进行升级时的指南。 建立用例模型的目的是为了寻找需求规约，需要通过开发者和客户之间进行多次交互完成。 用例模型（ Use Case Model） [4]是表达系统外部事物（执行者）与系统之间交互的可视化工具。 一个系统的用例模型由若干用例图组成，主要用于需求分析阶段，它的建立是系统开发者和用户反复讨论的结果，表明了开发者和用户对需求规格说明达成的共识。 用例模型驱动了需求分析之后各阶段的开发工作，不仅在开发过程中保证了系统所有功能的实现，而且被用于验证和检测所开发的系统，从而影响到开发工作的各个阶段。 用例图的主要成分有用例、执行者和系统，它用简单的图符准确地描述了执行者与系统的交互情况以及系统的功能。 在用例模型中，功能以用例来表示，每个用例指明了一个完整的功能。 系统由若干用例组成，系统的边界定义了一个系统所具有功能。 通过执行者与系统中的用例进行交互，具体描述系统是如何提供这些功能来完成相应的服务的 [4]。 用例模型的步骤包括 [4,5]：定义系统，寻找执行者和用例，描述用例，定义用例之间的关系，最后确认模型。 用例图（ Use Case Diagram） [4,5]描述了各种外部执行者与系统所提供的用例（ use case）之间的连接。 在用例图中标识用例名和执行者名，用例图中使用连线描述执行者和用例之间的关系。 用例与用例之间也可以发生联系 —— 通过它们之间的连线表示，并在连 线附近用文字描述联系的内容。 执行者（ actor）[4,5]是指在系统外部与系统交互的人或其他系统，他以某种方式参与系统内用例的执行。 “ 与系统交互 ” 是指执行者向系统发送消息，或从系统那里接收消息，或与系统交换信息。 游戏的用例图 待开发的连连看局域网对战游戏系统，支持单人游戏，也支持在一台机器上或者局域网不同的两台机器上最多有两个玩家同时游戏，但这两个玩家的性质完全相同，因此处于系统边界之外的参与者只有一个，就是玩家。 而系统需要提供单人游戏模式、局域网双人对战模式，这显然是处于系统内。 玩家通过选 择游戏模式，与 “ 进行单人游戏 ” 用例、 “ 进行局域网双人对 战 ” 用例这两个用例进行交互。 在进行局域网双人对战时，首先要设置局域网连接，因此 “ 局域网连接 ” 用例应作为 “ 局域网双人对战 ” 用例的扩展用例。 连连看局域网对战游戏的用例图，如图 所示。 图 连连看局域网对战游戏用例图 用例说明 获得用例图后，至少要给出于执行着直接关联的类的描述。 下面将给出“ 进行单人游戏 ” 用例、 “ 进行局域网双人对战游戏 ” 用例、 “ 设置局域网连接 ” 用例的用例，与其有关联的扩展用例和包含用例、子用例将会在这三个用例中一并描述。 “ 进行单人游戏 ” 用例的用例描述如表 所示。 表 “进行单人游戏 ” 用例的用例描述 名称 描述 用例名称 进行单人游戏 执行者 玩家 目的 在单价模式下进行游戏 类型 基本的、主要的 过程描述 1．选择 “ 游戏 ” 菜单中的 “ 开始单人游戏 ” 选项，启动开始单人游戏。 2．在棋盘内除了最上方和最下方两行，最左边和最右边一列，其余每一个位置随机摆一张花色的游戏牌，每一种花色的游戏牌出现的次数必须是偶数，并且满足存在一对能够消去的游戏牌（花色相同、存在一条拐弯次数不超过 2 的路径），启动计时器的秒数，游戏开始。 3．每隔 1 秒钟，计时器自动减 1，如果时间耗尽，转 14； 4．如果玩家用鼠标选中一张游戏牌，转 5，否则转 3； 5．搜索玩家上一次选中的并且未消去的游戏牌，如果不存在玩家上一次选 中的并且未消去的游戏牌，转 12，否则，转 6； 6．如果玩家当前选中的游戏牌和上次选中的并且未消去的 游戏牌不是同一张游戏牌，转 7；否则，转 13； 7．判断当前选中的游戏牌和上次选中的并且未消去的游戏牌能否消去，如果不能，转 8，如果能，转 9； 8．将玩家上一次选中的并且未消去的游戏牌取消选中，将当前选中的游戏牌指为选中状态，并罚时 4 秒钟，转 3； 9．将当前选中的游戏牌指为选中状态，消去这一对游戏牌，并加时 2 秒钟，转 11； 10．如果棋盘内所有的游戏牌都被消去，转 15，否则，转 14； 11．如果不存在一对能够消去的游戏牌，则在原有位置重新摆放未消去的游戏牌，直到存在一对能够消去的游戏牌，转 3； 12．将当前选中的游戏牌置为选中状态，转 3； 13．将上一次选中的并且未消去的游戏牌置为未选中状态，转 3； 14．游戏失败，则给出相应的失败信息提示，转 16； 15．游戏胜利，则给出相应的胜利信息提示； 16．游戏结束。 “ 进行局域网双人对战游戏 ” 用例的用例描述如表 所示。 表 “进行局域网双人对战游戏 ” 用例的用例描述 名称 描述 用例名称 进行局域网双人对战游戏 执行者 玩家 目的 在局域网双人对战模式下进行游戏 类型 主要的 过程描述 1．玩家选择作为同时作为服务端和客户端，还是仅作为客户端。 如果是同时作为服务端和客户端的玩家，转 2，否则转 3； 2．服务端启动局域网对战模式，设置创建监听，等待客户端连接，如果客户端连接上服务端，转 4； 3．客户端启动局域网对战模式，进行连接服务端的操作，等待服务端启动游戏； 4．服务端启动游戏，在棋盘内除了最上方和最下方两行，最左边和最右边一列，其余每一个位置随机摆一张花色的游戏牌，每一种花色的游戏牌出现的次数必须是偶数，并且满足存在一对能够消去的游戏牌（花色相同、存在一条拐弯次数不超过 2 的路径），启动计时 器的秒数，游戏开始； 5．每隔 1 秒钟，计时器自动减 1，如果时间耗尽，转 14； 6．对每个玩家，执行下述步骤： 7．如果某一个玩家用鼠标选中一张游戏牌，转 8； 8．搜索玩家上一次选中的并且未消去的游戏牌，如果不存在玩家上一次选中的并且未消去的游戏牌，并将当前状态通过数据包发送给服务端，服务 端将该玩家。