毕业设计（论文）-基于android的连连看游戏.doc

装订线长 春 大 学 毕业设计（论文）纸序号（学号）： 041140325长 春 大 学毕 业 设 计（论 文）基于Android的连连看游戏姓 名学 院计算机科学技术学院专 业软件工程班 级软件11403班指导教师）2015年6月5日基于android的连连看游戏摘 要 近年来，随着移动互联网和电子信息技术的飞速发展，手机游戏市场也得到了很大的发展。移动应用市场和移动互联网形势的快速发展让Android应运而生，它是由谷歌公司推出的，因为它的开放性的基于Linux的开源手机操作系统的内核，不受运营商的束缚，丰富的硬件选项，开发商没有任何限制，并可以无缝集成谷歌应用服务优良的特性，很快就占据了智能手机平台系统领域。进行研究和Android平台的手机游戏发展，已成为一个非常有趣的巨大发展空间的区域。在本文中，我们通过对Android系统架构和应用程序开发的初步研究设计了一个小游戏叫连连看。它确定基于该系统的详细的要求分析系统的功能和性能要求。而游戏的菜单界面，屏幕绘图，时间控制，布局算法，算法的连接，水平集，声音和动画一直细节设计。在本场比赛的详细设计阶段。首先，我们必须建立一个良好的游戏开发，包括下载必要的环境和安装Eclipse开发环境下载和intall ADT扩展。之后，我们已经建立了开发环境，那么我们就必须实现对游戏的单一功能。这些功能包括消除连接后，游戏countdowned开始游戏，暂停游戏，并选择游戏模式。然后自定义游戏视图，可以根据由控制器提供的数据的布局显示图片，并提供功能包括，选择的亮点，连接和消除。然后，我们将设计，它实现了主控制逻辑的游戏控制器。最后，还有一个是该算法的设计，在本文，我们描述参与游戏包括游戏布局算法，连接算法和死锁判定算法的算法的最关键的部分。完成这些步骤后，一个叫做人性，高效，稳定的和有趣的益智游戏，连连看已经实现。关键词 Android 连连看 游戏 JavaLianliankan game based on androidAbstract In recent years, with the rapid development of mobile Internet and electronic information technology, mobile games market has been greatly developed. Android is in the rapid development of mobile application market and the mobile Internet situation arises at the historic moment, and it is from Google launched a open source mobile phone operating system based on Linux kernel, because of its openness, is not subject to the bondage of operators of the rich hardware selection, developers is not subject to any restrictions and can seamlessly combine the characteristics of excellent Google applications, soon will dominate in the field of smart machine platform system. The research and development of Android platform mobile games is a very interesting and very interesting field.This paper preliminarily studies the architecture and application development of Android system, and designs a game of games and games with Java language. On the basis of the system needs to conduct a detailed analysis to determine the functional and performance requirements of the system, detailed design of the game menu interface, drawing on the screen, time control, layout algorithm, connectivity algorithm, set up checkpoints, sound and animation. In the detailed design stage of the game, first, we must build a good game development environment, including download and install the development environment Eclipse and install ADT Expansion Kit. After the development of the environment, and then the game individual features: the elimination of the game, the game countdown, the game, pause game and game mode select these features. Then customize the game view, defined view to display the layout data provided by the controller, and provide the feature selected, connection and elimination. Then the part of the design game controller is designed, the main control logic is realized. At last, it is the most critical algorithm for the algorithm design. The game layout algorithm, connectivity algorithm and deadlock decision algorithm are introduced. After completing these steps, the final realization of a user-friendly, efficient and stable and full of entertainment mobile phone again and again to see the puzzle game.Key words Android Lianliankan game Java目录1 引 言12 需求分析22.1 系统功能需求分析22.2 可行性分析22.2.1操作可行性22.2.2技术可行性22.2.3经济可行性32.2.4社会可行性32.3技术以及开发工具介绍32.3.1 JAVA与ANDROID的关系32.3.2 JAVA简介42.3.3 JAVA语言特性42.3.4 ANDROID开发技术简介52.3.5开发工具简介63 系统总体设计83.1 系统基本流程设计83.2 系统模块设计84详细设计114.1 算法设计114.1.1 游戏布局114.1.2 连通算法124.1.3 僵局判定184.2主要功能的实现194.2.1图案选中放大效果实现194.2.2 刷新地图道具功能实现204.2.3 消除提示按钮功能实现224.2.4 判断消除图片234.2.5 游戏中声音的配置294.3 系统运行界面图305结 论361 引 言Android是基于Linux内核的开放式移动平台的操作系统。它与Symbian，Windows等其它手机操作系统在同一水平。对于设备制造商，Android是一个免费的平台。 Android操作系统，使设备制造商能够免除每出一次手机，手机操作系统都将限制手机厂商。对于硬件厂商来说, Android也是一个开放的平台。只要厂商有自由加入了独特的设备或功能在这个平台上的能力，就不会被手机操作系统厂商限制。对于手持设备开发者，Android是一个先进的平台。该平台的应用程序可与各种型号的Android手机兼容。 Android平台支持多种先进的网络、与图形、3D处理能力，可以为用户提供更好的体验。对于用户来说，Android是一个手机的操作系统。用户只需申请一个免费的谷歌帐户即可。当用户想换一部手机，就可以使用相同的Android操作系统，不同品牌的手机选择的平台，而且很容易之间通讯录和其他个人数据转换到新的手机上。Android提供了多种库和完整的应用程序框架。和用于商业限制的Apache版权。在基于谷歌提供的自制应用程序运行时环境（称为Dalvik，和sun的J2ME不同），并提供基于Eclipse的集成开发环境（IDE）的免费，跨平台（Windows，Mac OS X、Linux）的开发套件（SDK），这是便于应用开发学习和使用。免费的跨平台的开发工具让某些面向对象概念或windows编程经验的开发人员可以在一定时间内上手。从不同的角度来看，Android代表一个新的开源代码的操作系统平台，是一种免费的应用程序开发环境，一个与世界各地的开发者，有公平竞争的机会，有同样的起点。基于Android平台的游戏连连看游戏作为一款经典的益智游戏，一直是游戏爱好者喜欢的游戏，男女老少皆宜。游戏的吸引力主要在于：连连看游戏是游戏的休闲兴趣，不仅规范了精神，而且在游戏中锻炼我们的视力，注意力集中程度，我们的发展思维能力，还可以充实自己，高层次的挑战，我们在困难面前训练的时候，他有克服困难的信心。手机游戏，是指消费者使用便携和无线网络的智能移动终端设备可以随时随地玩游戏。手机游戏最大的特点是它的方便随时随地玩。近几年，手机游戏市场有很大的发展，手机游戏已经成为移动娱乐应用率最高，占比重78.4移动娱乐应用。在日本，手机游戏市场已经经历了多年的稳定增长，市场规模已超过850亿日元。在美国，手机游戏作为美国最喜爱的移动应用，智能终端，如Android和iPhone推出后发展迅速的移动电话用户中的一个。该设计将使用Java和Android开发技术，实现了基于Android的平台，可以在模拟器上，Android手机游戏再次运行，再次看到游戏。2 需求分析2.1 系统功能需求分析本次设计是基于一般连连看游戏规则和游戏模式完成的。在游戏体验和游戏模式方面又有了一些改进，目的在增加游戏的趣味性和挑战性。游戏设计出来之后，经过测试需要实现下面的游戏基本功能：基本游戏功能。就是说，设计完成的游戏可以正常启动运行。在游戏初始化阶段，首先要有排除死锁能力，所谓死锁就是游戏初始化完成后，新生成的消除图案列表中不存在一对可以消除的图案。或者是玩家在游戏过程中出现无法继续消除的情况。这时游戏应该提供刷新的按钮，玩家点击后能够重新打乱布局继续游戏。这个功能保障了游戏的可玩性和人性化设计。游戏开始功能。进入游戏界面后，会看见一副背景图。然后在游戏界面中间有一个开始按钮。玩家点击后可以切换进入游戏界面。游戏开始时由函数调用来完成游戏图片加载，程序会载入游戏图片，同时随机产生图片的任意排列。背景音乐和计时功能。一开始进入游戏界面时，会自动播放背景音乐。随着优美的音乐响起，玩家们更觉身心愉悦。顿时感到兴趣大增。另外游戏还有计时功能。游戏开始时，屏幕上方有一个个黄色的进度条，随着时间的流逝逐渐的变短。如果进度条消失之后，玩家没有将所有的图片消除，则弹出对话框提示“失败！”以及所用的时间。反之，则该局游戏成功。弹出对话框，提示“胜利！”以及所用时间，之后可以选择退出、从新玩或者进入下一关。2.2 可行性分析2.2.1操作可行性游戏操作可行性其实是游戏成功与否的关键，在很多出色游戏中游戏操作合理性往往成为玩家讨论的焦点，所以说游戏设计合理性既是需要考虑的关键所在也是对玩家选择此游戏时的主要吸引力。游戏时间不能过长亦不能过短，在经过反复的思考和老师的指导后，决定将时间做成第一关100秒左右，往后每一关减少10秒。这个决定保证了游戏可以正常完成，同时也考虑到了制作时间的限制。2.2.2技术可行性Android以Java为开发语言，JDK是进行Java开发时必备的开发包。进行开发前首先要建立合适的开发环境，其中基于Java的可扩展平台Eclipse是我们的首选。Eclipse是一个非常优秀的开源IDE，Google官方也为我们提供了基于Eclipse的Android开发插件ADT，Android平台为开发者们提供了源码开放的软件开发包(SDK)，里面包含了使用Java语言开发Android平台应用的必要工具和组件(API)。在大量插件的配合之下，完全可以满足开发者们从企业级Java应用到手机终端Java游戏的开发。Eclipse是一个很好的动画游戏制作软件。它完全符合面向对象编程的要求，可以大大的提升程序编写的能力。而且在Eclipse软件里，它自带了一些经常用的组件。这为我们对这各组件开发提供了非常大的帮助。因此在技术上还是可行的。 2.2.3经济可行性开发该系统所需的相关资料我们可以通过已存在的相关系统进行调查采集，所需的一些其他应用软件、硬件系统也易于获得.因此,开发的成本较低。而且引进使用本系统后，与传统的方式相比，具有高效率、低成本、高质量的特点，可以节省人力、物力及财力。所以，从经济的角度看，该系统可行。2.2.4社会可行性本游戏丰富道具的加入，增强了游戏的竞争性。因为Android游戏的大量玩家是年轻人，而且现在年轻人的巨大消费潜力使得本游戏开发具有社会可行性。2.3技术以及开发工具介绍2.3.1 Java与Android的关系Android是以LINUX KERNEL为底层的一个操作系统，但是它的开发利用是基于Java语言的。将Android和Java相比较，会发现它们具有很多的相当性：（1）相当的类/字节码格式Android应用程序是用Java语言编写成的，它首先生成.java文件，然后再使用JDK的javac工具进行编译从而产生标准Java字节码即.class文件。这些文件最终再转化成专为Dalvik（Android平台的Java虚拟机）设计的.dex格式文件。.dex格式可以认为是一种被设计的更加优化的.class格式，好比是把一个GIF格式的图像转换成一个更高级而等效的PNG格式，虽然它们拥有着完全不同的字节流。（2）Java APIs与Android Runtime相当Android Runtime使用了一个很大的JavaSE APIs子集。这些都来自于Harmony项目的APIs。虽然都是全新的实现，但是它们都是参考JavaSE APIS发展而来的。（3）Dalvik与JVM相当经过相关人士尝试发现，Android可以支持一个不完整的（但规模很大的）Java 1.5 类库子集。其大到能让一个复杂的JRuby项目几乎不用做任何修改就能在Android平台上运行起来。由此得知，作为Android平台的Java虚拟机Dalvik和纯Java虚拟机JVM是如此的兼容，例如Android可以完全支持Java风格的线程和并发，甚至已经深入到了高级的java.util.concurrent包。 2.3.2 Java简介Java是一个跨平台面向对象的高级程序设计语言，最早是由Sun公司在1995年5月推出，并且作为Java程序设计语言和Java平台的总称。按应用领域可以将Java平台划分为三种类型：JavaSE,是Java各应用平台基础，主要由Java语言、JDK、JRE和JVM四大部分构成； JavaEE, 以JavaSE为基础，定义了一系列协议、服务及API等，可以用于开发多层式、分布式、以组件或WEB为基础的应用程序；JavaME，是Java平台版本中最小的一个，目的是作为小型数字设备上开发及部署应用程序的平台，像手机、PDA和股票机等类似的嵌入式系统或消费型电子产品。因为Java拥有各种丰富资源与各种活跃的论坛，来自各领域的开发人员及大师们都对Java做出了贡献，促使Java在广大开发者们的支持下发展至今。2.3.3 Java语言特性作为一个高级程序开发语言，Java拥有许多重要的特性，主要表现有：（1）简单的Java语言在设计的时候参考了许多C/C+的语法和特性，使得学习过C/C+的开发者可以在短时间内熟悉Java的使用。与此同时，Java舍弃了C/C+ 中的一些较少使用、难以掌握、可能不安全的功能，如操作符重载、指针和多重继承等。（2）面向对象的Java语言是一个纯面向对象高级程序设计语言，它可以让您可以用面向对象的思考方式来设计并编写程序。面向对象的好处就在于您可以设计可重用的组件或直接接用别人已经设计好的组件来开发出更有弹性并更易维护的软件。Java是通过提供类、接口实现和继承等机制来体现出这种面向对象特色的。较C+只可以对虚函数实现动态绑定，Java则是全面支持动态绑定。（3）网络的Java本身就是诞生于网络中的，从最初的Applet、Socket、JSP/Servlet直到如今热门的Web Service,这都说明Java在网络服务等相关领域有着突出贡献。例如在B/S的开发方面，Java程序语言就远远优于C+程序语言。（4）解释的程序如果要在一个平台上运行，首先得编译成这个平台所能理解的原始机器语言，但事实上不同平台所能理解的原始机器语言不尽相同。为了解决这个在不同平台间都可以运行的问题，Java又引入了JVM（可以执行Java字节码文件的虚拟操作系统），当运行Java程序的时候，JIT（Java实时编译器）就会把字节码编译成目标平台所能理解的原始机器语言。（5）安全的C+的内存空间或指针总是必须在不需要的时候由开发者编写代码予以回收，否则就可能会导致程序或系统崩溃。然而Java提供了一个垃圾回收机制，让开发者不再需要担心对象资源回收问题。此外，Java还设计了一个异常处理架构，这使得开发者可以很好的掌握程序中各种突发的异常情况。（6）可移植的要想让程序移植到另外一个平台上运行不是一件容易的事情，这需要考虑到诸多因素，例如数据类型在不同的平台上所占内存长度就是一个问题，而Java的数据类型在不同的平台上所占内存长度都是统一的，这是C/C+达到不了的。因此对于“一次编写，四处运行”的这种梦想，Java为人们提供了更高的可能性。2.3.4 Android开发技术简介要想快速地掌握Android技术，开发出Android的App，首先要对其开发技术的基础知识有一个大概的了解，而Android程序都是通过各种组件开发出来的，现将其重要组件总结如下：（1）当前活动的程序Activity:这是Android开发中经常使用到的应用程序组件。只要是要通过窗口和用户进行互动交流的都离不开Activity。Activity有生命周期，停止、运行、暂停等几个状态则贯穿了整个生命周期，这些状态之间的转换能够通过调用一系列的函数来完成，这些函数包括onStop()、onCreate()、onRestart()、onStart()、onPause()、onFreeze()、onResume()、onDestory()等。如果想开启一个新的activity的话可以调用startSubActivity(Intent，int)或者startActivity(Intent)，前者通常是和函数onActivityResult(int，int, String，Bundle)联合在一起使用的，这样能够通过函数返回结果传递给调用者需要的信息。（2）图像显示View: android.view.View是Android中用来描绘块状视图的一个基类，在块状区域内还可以包含对图像事件的处理。View是全部Widgets的基类，它的子类能够用来显示文本和图像等内容。通常进行View方法调用有: 填充View，调用 onDraw (Canvas)； 用XML 文件生成View调用inflate()；测量View的高度值和宽度值调用onMeasure (int， int)；onLayout()函数能够完成View的布局；当View中有按键操作的时候调用onKeyDown(int， KeyEvent)；当View得到或者失去关注时调用函数onFocusChanged (boolean，int)；要设置View点击事件监听器的话可以调用setOnClilckListener()。（3）Intent: Intent主要是用来解决Android各应用组件之间的通讯。它对应用中某种操作进行的抽象描述，包括操作的动作和该动作涉及到的数等，Android再依据这种描述寻找相应的组件，并将Intent传递给它，进而完成相关的组件的调用。Intent还能加载activity，进而对不同activity起到桥梁作用。它除了action和data两大重要的属性之外，还具有一些如category(类别)和type (数据类型)等附加属性。经常用到的Intent方法有： 获取intent动作getAction()；构造intent， intent()；添加intent类型，addcategory()；获取intent数据，getData()等。（4）ContentProvider:作为Android的数据的存取与共享机制，它为Android应用程序提供了几个访问方法，主要包括:获取数据类型的函数Get type (Uri)，实现数据信息的查询的Query(Uri，String ，String，String ，String，String，String) ，实现数据更新的update(Uri， Contentvalues，String，String )，给Content provider插入新数据的insert (Uri，Contentvalues)，用来删除数据的delete(Uri，String，String )。其中， ContentProvider存储的数据类型是由参数Uri来标示，在调用方法的时候都需根据Uri来标识路径来确定要访问的ContentProvider。(5) Service: Service作为后台服务，并不是直接与用户进行交互，而是一种在后台运行的一个Android应用程序组件。当前活动程序能够通过调用函数Context. bindService()来实现与后台服务间的通信，也能够调用方法Context. StartService()来开启一项后台服务。2.3.5开发工具简介Eclipse是市场占有率非常高的Java IDE工具，Android推荐使用Eclipse开发Android应用，并为它提供了专门的插件：Android Development Tools（ADT）。Android的底层是建立在Linux系统之上的，它采用软件叠层的方式来进行构建。这种软件层结构使层与层之间相互分离，分工明确。确保了层与层之间的低耦合，当下层的层下或层内发生改变时，上层应用程序无须做出任何改变。应用程序层是系统的核心应用程序，例如浏览器、电子邮件客户端和地图等。这些程序主要都是用Java来编写，玩家则主要通过这些应用程序来实现对手机的一系列操作。应用程序框架为开发者提供了大量API。开发者自己所开发的应用的功能模块，主要遵循了框架的约定，那么其他的应用程序也能够使用这个功能模块。函数库里面包含了一套被不同组件所使用的C/C+库的集合。通常来说，Android开发者不可以直接调用这套C/C+库集，但是可以通过它上面的应用程序框架调用此库。Android操作系统运行的时候是由2个部分组成： Dalvik虚拟机和Android核心库。其中Android核心库主要是为Java语言提供了大部分的功能，而虚拟机则是负责运行Android应用程序。Linux内核系统是基于Linux2.6之上搭建的。在Android平台上Linux内核提供了和驱动模型、安全性、内存管理、进程管理和网络协议栈等核心系统服务。而且linux也是硬件层和软件层之间的抽象层。共 38 页 第 38 页 3 系统总体设计3.1 系统基本流程设计本系统实现的是一款基于Android平台的“连连看”游戏，玩家们打开游戏，进入游戏欢迎界面，显示开始游戏的图像按钮。当玩家点击开始游戏的图像按钮后，进入游戏界面。这时，如果在系统规定的时间内消去全部图片则弹出成功对话框，否则的话弹出失败对话框，这两个对话框上都附带菜单界面：如果玩家点击该界面上进入下一关的图像按钮，则进入下一个关卡；如果玩家点击该界面上的退出游戏的图像按钮，则退出连连看游戏程序；如果玩家点击该界面上的重新本关游戏的图像按钮，则重新开始本关游戏。在游戏的过程中，玩家还能够使用道具，一种是系统帮助自动消除图案，另一种则是重新刷新地图，每个道具都只可以使用三次。3.2 系统模块设计从总体出发，可以将该系统划分为四大模块：“算法设计”，“界面设计”，“消息响应设计”和“菜单设计”。如图3-1所示：图3-1 系统总体设计这四大模块又可以进一步划分：菜单设计，可进一步划分成三个模块，分别是：“退出游戏”，“重新开始”和“进入下一关”，如图3-2所示。图3-2 菜单设计（2）界面设计，可以进一步划分为： “地图设计”，“进度条设计”和“框架设计”，如图3-3所示。图3-3 界面设计（3）算法设计，它可继续划分出两个模块分别是：“消除算法设计”和“画线设计”，如图3-4所示。图3-4 算法设计 其中，消除算法设计是这个系统的核心算法，现对它分析如下：每当用户选择两个图案的时候，假如这两个图案完全一样，而且这两个图案之间存在着不受其它图案阻拦的折角少于3的路径，那么这两个图案就可以被消除。给定任意有相同图案的两个格子，我们需要先找出这两个格子之间能够直角转弯最少的路径，如果这个最优路径的折型数小于3 ，那么这两个格子可以被成功消除。从其折型数出发，具体又可分以下三种情况：(1）零折型。直接连接并消除。(2）一折型。若1失败，则尝试在第一个格子的同行，第二个格子的同列寻找一个空格子，看这个空格子与两个目标格子能否零折型连接；或者在第二个格子的同行，第一个格子的同列寻找一个空格子，看这个空格子和两个目标格子能否零折型连接。成功就可将两格子“一折型”连接消除。(3）两折型。若2失败以后，再进行如下的尝试：在第一个格子的同行找一个空格子，看它能否与目标格子2以“一折型”方式连接消除；或者是在第一个格子的同列找到一个空格子，看它能否与目标格子2以“一折型”的方式连接消除。如果成功则两个格子“两折型”消除，如果所有的尝试都失败，那么说明这两个格子不能消除。4详细设计4.1 算法设计4.1.1 游戏布局下面是一个游戏布局例子，玩家看到的是一个8x10的游戏界面（中间涂色部分），实际上在外面有一圈隐藏空白路径，所以实际上节点总数为16x12。游戏布局图如图4-1所示。图4-1 游戏布局图(1)首先定义每个节点的数据结构，用来记录每个节点的信息：typedef struct _CELL_NODE int value;char row; char column;int connect_flag;int boundary_flag; struct _CELL_NODE *next;CELL_NODE;其中用 int value 来表示节点的值。它决定了玩家看到的每个方格里的内容。根据界面的显示结果，把所有的节点分为两类, 一类是图案的节点，即待消除的节点；另一类节点是路径节点，图案节点成功消除后，变成路径节点，游戏布局外围的隐藏的节点也是“路径”节点。如果是路径节点，则value的值为-1；如果是图案节点，则其范围为0，Enum,在本次设计的连连看游戏中 Enum的数值是所有配对的可消除图案的组数。我们可以通过调整Enum的大小，来控制游戏的难易程度：Enum越大，游戏中的单元种类也就越多，随之相应的游戏难度也就越大。Char row是节点所在的行号0, HEIGHT+2，HEIGHT是玩家可以看见的列数。Char column 是节点所在的列号0, WIDTH+2， WIDTH是玩家可以见的行数。 int connect_flag 表示连通标记，在路径的搜索中将会被用到。int boundary_flag是边界标记，在路径搜索中要用到的。struct _CELL_NODE *next 用来表示指向下一个节点（并不一定是相邻的），这个在后面的节点列表中将会用的到。(2) 节点列表的数据结构。将同value的节点串联(不包含空白节点)：typedef struct _CELL_LISTint count; /链表中节点个数。CELL_NODE *link; /相同value的节点。 CELL_LIST;说明：在程序的实现中，用一个数组:CELL_ST g_cell_listENUM, 数组中每一个元素对应1种value的链表；这个数据结构在游戏布局确定后生成。随着游戏的进行，节点将逐渐被从列表中移除，成为“路径”节点；最后在游戏结束时该链表为空；该链表的作用有3个：一个是初始化游戏布局时；二是需要判断游戏是否“死锁”时；三是发生“死锁”需要重新生成游戏的布局时。(3) 代表整个布局的二维数组g_cellWIDTH+2HEIGHT+2，里面的每个元素就是CELL_NODE指针，指向布局中相对应位置的节点：a指定行和列，可以得到对应该位置的节点指针。CELL_NODE *get_cell(int column, int row)return g_cell + (WIDTH+2)*row + column;b从某个节点(src_cell)出发，访问相邻其他节点(dst_cell)。上节点： dst_cell = src_cell (WIDTH+2)；下节点： dst_cell = src_cell+ (WIDTH+2)；左节点： dst_cell = src_cell 1；右节点： dst_cell = src_cell+ 1。4.1.2 连通算法这次设计的“连连看”中的连通有三种，分为一线连通、二线连通和三线连通：(1) 一线连通它的充分必要条件是：a两节点同行或者同列；b两节点相邻或之间的全部节点都是路径节点。一线连通实例如图4-2所示。图4-2 一线连通图实现的函数如下：int check_1_line_connect(CELL_NODE *first, CELL_NODE *second)int column1 = first-column;int row1 = first-row;int column2 = second-column;int row2 = second-row;int step;CELL_NODE *temp_cell;if(row1 = row2)step = column2column1?1:-1; /同行，根据两个节点的左右关系来计算从first-second的步长。else if(column1 = column2)step = row2row1?(WIDTH+2):-(WIDTH+2); /同列，根据个两节点的上下关系来计算从first-second的步长。else return MAYBE_CONNECT;/不同行不同列的肯定不是一线连通。temp_cell = first + step;while(temp_cell != second)if(temp_cell-value != CELL_VALUE_PATH) MAYBE_CONNECT;/在从first到second的遍历过程中，如果遇到一个节点不是空白路径，则肯定不是一线连通，则返回。temp_cell += step;return ONE_LINE_CONNECT;/两个节点间不存在图案节点，一线连通成功。说明：a在上图4-2中，从A遍历到B, 它的步是为1， 反之是-1；从C遍历到D, 它的步长是(WIDTH+2), 反之是 -(WIDTH+2)；b CELL_VALUE_PATH是一个常量，它的值为-1，表示该节点是路径节点；c MAYBE_CONNECT，表示当前不能判断是否连通；ONE_LINE_CONNECT,表示能够一线连通。(2) 二线连通它的充分必要条件是：a. 两节个点不同行且不同列；b. 两个节点的折型节点是路径节点；c. 折型节点与两个节点都可以一线连通。A与B是两个待定的节点，而C和D就是他们的折型节点，显然C、D的坐标可以通过A，B的坐标推导出来，二线连通如图4-3所示。图4-3 二线连通图具体实现函数如下：int check_2_line_connect(CELL_NODE *first, CELL_NODE *second, CELL_NODE *ret_corner) CELL_NODE *corner;if(first-column = second-column)/同列，一定不是二线连通。 return MAYBE_CONNECT;if(first-row = second-row)/同行，一定不是二线连通。return MAYBE_CONNECT;corner = get_cell(first-column, second-row);/得到其中的一个折型的节点if(corner-value=CELL_VALUE_PATH)/判断折型节点与两节点能否可以一线连通。if(check_1_line_connect(first, corner)=ONE_LINE_CONNECT& check_1_line_connect(second,corner)=ONE_LINE_CONNECT)*ret_corner = corner; /二线连通成功，返回该折型的节点，以便输出连通的路径。return TWO_LINE_CONNECT;corner = get_cell(second-column, first-row);/得到另一个折型的节点。if(corner-value=CELL_VALUE_PATH)if(check_1_line_connect(first,corner)=ONE_LINE_CONNECT& check_1_line_connect(second, corner)=ONE_LINE_CONNECT)*ret_corner = corner;return TWO_LINE_CONNECT; return MAYBE_CONNECT; /当前不能肯定是否连通；(3) 三线连通节点A和B能够三线连通的充分必要条件是：a.存在两个路径节点C跟D；b.A和C可以一线连通， B和D可以一线连通；c. C和D可以一线连通。所以，三线连通的关键是找出符合上述条件的C和D。下图4-4包含了三线连通的所有六种可能的情况。图4-4 三线连通仔细分析上图4-4可以看到，我们需要找的C和D肯定是在以A和B为中心的两个十字线上， 即如下图4-5所示。图4-5 C和D的位置这些标记的节点就是C、D的候选节点。因为C和D是可以一线连通的，所以如果C点在线段X上，那么D点一定在线段W上；而如果C点是在线段Y上，那么D点肯定在线段Z上。所以接下来，我们只要沿着平行线X/W和Y/Z来判断候选节点C跟D是否一线连通就可以了。 该函数会确定节点first 和 second是否三线连通，如果是的话，就将折型节点保存在corner1和corner2。现在把三个过程串联起来就可以判断任意两个节点是否连通：int check_connect(CELL_NODE *first, CELL_NODE *second, PATH *path)int ret=0;CELL_NODE *corner1=NULL, *corner2=NULL;ret = check_0_line_connect(first, second);/该函数做一些初始的检查，例如玩家输入的两个节点的值不同，显然是不可能连通，那么也就不需要再进行下面的判定了。if(ret=NO_CONNECT)goto CHECK_CONNECT_RETURN;ret = check_1_line_connect(first, second);if(ret = ONE_LINE_CONNECT)goto CHECK_CONNECT_RETURN;ret = check_2_line_connect(first, second, &corner1);if(ret = TWO_LINE_CONNECT)goto CHECK_CONNECT_RETURN;ret = check_3_line_connect(first,second, &corner1, &corner2)if(ret = THREE_LINE_CONNECT)goto CHECK_CONNECT_RETURN;return NO_CONNECT;CHECK_CONNECT_RETURN:produce_path(first, second, corner1, corner2, path, ret);return ret;至此我们就完成了连连看中的连通算法。通过查看质料了解的连连看的连通算法有很多，但是我认为这个算法的最大好处是逻辑清晰，不需要过多地考虑节点的位置关系，所以看起来更简洁，代码量也比较少。认真分析之后我发现这个算法还有一定的优化空间：在三线连通的判断时，在水平或者垂直方向上，总是遍历平行线上所有的点，实际上还可以缩小遍历范围（只遍历平行线重合的部分就可以）。如下图4-6所示。图4-6遍历范围(2)为了表述清晰而将一线连通、二线连通、三线连通分开，实际上，一线连通和二线连通都可以看作三线连通的特例：在三线连通里，如果其中一个折型节点与一个待消节点重合，就成为二线连通；如果两个折型节点分别与两个待消节点重合，就变成了一线连通。4.1.3 僵局判定当游戏中所有同类型的节点都互相不连通时，就是所谓的僵局。僵局举例如图4-7所示。图4-7 僵局举例如上图4-7所示，图中有4对节点，但是认真观察可以发现，图中所有相同类型的节点都不能满足连通算法的要求，即不可连通。所以没办法消除，这时就形成了僵局，游戏无法正常继续进行下去。下面将给出怎样判断僵局的详细算法实现。关于僵局的判断：(1) 僵局判的定就是要及时的发现僵局，以便程序能产生新的游戏布局，使游戏可以继续下去；(2) 僵局判断的过程就是遍历游戏剩下的所有图案的节点，把它们两两配对，检查是否可以连通；(3) 为了提高程序的效率，一般僵局判断在找到一对可连通的节点后就退出；(4) 而找到的这对连通节点还有另外一个作用：那就是当玩家需要提示的时候，可以作为提示点显示给玩家。启动僵局判断的条件：(1) 每局开始的时候，需要判断初始布局是否是僵局；(2) 或者当上一次僵局判断找到的两个提示节点中任何一个节点发生变化时，包括位置变化或被消掉，则需要启动僵局判断。由于僵局判断需要对同类型节点进行两两遍历，这就要用到前面说到的g_cell_list数据结构，它的定义如下：typedef struct _CELL_LISTint count; /链表中节点个数。CELL_NODE *link;/相同value节点。 CELL_LIST;CELL_LIST g_cell_listNUMBER;/NUMBER是一个常量，在本