连连看游戏设计与实现实现.docx
《连连看游戏设计与实现实现.docx》由会员分享，可在线阅读，更多相关《连连看游戏设计与实现实现.docx（60页珍藏版）》请在冰点文库上搜索。
连连看游戏设计与实现实现
连连看游戏设计与实现
摘要
“连连看”游戏是一款常见游戏。
游戏速度节奏快，画面清晰可爱，适合大众玩家。
本文主要介绍了游戏的设计过程，其中游戏主要分为4个模块，游戏界面模块、图片随机生成模块、图片消除路径判断、背景音乐模块。
游戏核心模块中图片随机生成采用了数字和图片绑定，运用随机函数以及数组交换的算法，实现了游戏图片初始化状态，有效的解决了图片排布问题，方案简单易行；另一核心模块图片消除路径判断，主要采用了分类判断的算法，将连连看图片的位置一一归类，分类设计函数判断位置，实现游戏的基本消除功能。
算法思路清晰，便于理解和编码。
本游戏实现了连连看的基本功能，可以准确的消除图片、记录分数、提示时间，同时设计了人性化的提示，解决僵局的功能，创新实现了新的连连看规则——消除图片后给予时间奖励，激发了玩家的积极性。
关键词:
QT；连连看；算法；数组
LinkGameDesignandImplementation
Abstract
Linkgameisacommongame.Thegamehasfast-pacedspeedandthecutepictureThatisfitforpublicplayers.Thispaperdescribesthedesignprocessofthegame,wherethegameisdividedintofourmodules,thegameinterfacemodule,themoduleofrandomlygeneratedpictures,eliminatingpathjudgment,backgroundmusicmodules.
GameCoremodule,themoduleofrandomlygeneratedpictures,bindpicturesandimages,usetherandomfunctionandaarrayexchangealgorithm,andachievegamepictureinitializationstate,effectivelysolvetheproblemofpicturearrangement,theplanissimple;anothercoremodulepictures,eliminatepathjudgment,mainlyusesclassificationalgorithmstodeterminethelocationoflinkgamepictureandclassifyit,classificationfunctionsjudgethelocation,andrealizethebasicfunctionofthegamecancellation.Algorithmisclear,easytounderstandandencoding.
Thegamerealizethebasicfunctionoflinkgame,itcaneliminatetheexactpicture,recordingscores,suggestingthattime,anddesignhumanetips,thefunctionofsolvingthedeadlock.Itachievesnewrules--aftereliminationofthepictureyoucanbegiventimebonus.Thatisstimulatingtheenthusiasmoftheplayers.
Keywords:
QT;Link;algorithm;Array
1.绪论
1.1游戏简介
1.1.1游戏背景
连连看游戏是游戏中经典中的经典，曾经风靡网络，无论是单机版的还是网络对战的，它以简单，容易上手，图片新颖的特点获得了大量的粉丝，它是一款经久不衰的休闲小游戏，适合闲来无事的大众，以供消遣。
游戏“连连看”顾名思义就是找出相关联的东西，这个连连看在网上基本是用在小游戏中，就是找出相同的两样东西，在一定的规则之内可以做为相关联处理。
“连连看”的发展经历了从桌面游戏、在线游戏、社交游戏三个过程。
游戏“连连看”是源自台湾的桌面小游戏，自从流入大陆以来风靡一时，也吸引众多程序员开发出多种版本的“连连看”。
这其中，顾方编写的“阿达连连看”以其精良的制作广受好评，这也成为顾方“阿达系列软件”的核心产品。
并于2004年，取得了国家版权局的计算机软件著作权登记证书。
随着Flash应用的流行，网上出现了多种在线Flash版本“连连看”。
如“水晶连连看”、“果蔬连连看”等，流行的“水晶连连看”以华丽界面吸引了一大批的女性玩家。
2008年，随着社交网络的普及和开放平台的兴起，“连连看”被引入了社交网络。
“连连看”与个人空间相结合，被快速的传播，成为一款热门的社交游戏，其中以开发者Jonevey在Manyou开放平台上推出的“宠物连连看”最为流行。
1.1.2游戏规则
连连看游戏规则简单，就是在游戏界面中找到两个相同的图片，用不超过3根直线能够连接起来，就可以成功消除图片，得到分数，获得时间奖励，在规定时间内将图片全部消除，便获得胜利。
1.2游戏功能
1.2.1美观大气的界面
本连连看游戏采用蓝色背景作为主色调，界面简洁大方，按钮及提示框排布合理，便于玩家的操作。
1.2.2背景音乐的添加
只要打开游戏，游戏的背景音乐就缓缓的流露出来，滋润心田，选择相应的按钮后，还会有提示音，成功连线消除图片后能播放消除的提示音。
1.2.3奖励时间的设置
玩家成功消除一对图片后，对应的时间进度条就会增加一定的奖励时间，来鼓励玩家消除。
1.2.4提示功能
当玩家陷入困境，不知道怎么消除图片，继续游戏时，提示按钮可以帮助他成功消除当前的图片，但是提示的次数有限，用完不再生效。
1.2.5僵局的重置
由于游戏的图片生成是随机的，因此，在消除到一定阶段的时候，可能会出现有图片但是不满足消除规则的情况，重排的按钮可以实现图片的重新加载，从而能够再次消除。
1.2.6得分记录、难度
为了提高玩家的游戏的积极性，以及为了保证游戏的完整性，游戏将统计玩家的得分情况，消除一对图片，就会得到相应的分数，以数据反应玩家的游戏完成进展。
同时为了给游戏增加一些可变因数，玩家在成功完成一轮游戏后，难度会增加，难度增加反应到游戏中就是缩短了一轮游戏的时间，但是图片的数量没有改变，这就无形中增添了游戏的可玩性。
1.2.7开始、重新开始、退出
开始，重新开始，退出等按钮实现相应的游戏控制。
1.3游戏设计的主要工作
1.3.1游戏设计需要解决的问题
开始制作游戏时，主要要解决的问题有以下几个方面：
如何设置整个游戏的界面；如何控制连连看游戏中随机图片的生成且每种图片必须为偶数个；游戏开始后，判断鼠标两次点击的图片能否消去，即图片是否相同且图片之间路径的判断；如何判断游戏是否结束以及输赢问题等。
1.3.2游戏设计需要使用的算法
针对游戏中最核心的两个问题，1连连看游戏中随机图片的生成且每种图片必须为偶数个，2图片是否相同且图片之间路径的判断，我们需要使用合适的算法来解决这两个棘手的问题。
1.图片成对出现而且随机，为了保证成对，我们可以在存放的时候按照顺序成组来存放，保证组的数量是偶数就可以实现，但是同时又存在一个问题，图片在哪里存放，怎么引用图片，为了简化图片的存放，结合连连看的表格形式，这里我们应用二维数组、采用转化的原则，将图片依次编号和二维数组对应，数组中的数字是0表示为空白，大于0的代表对应的图标编号，这样图标就可以容易替换成任何的图片或者文字，这就很好的解决了图片的按组存放规则；接下来还需要解决一个问题就是如何将图片的顺序打乱，这就需要应用到关键方法——随机函数，通过随机函数和对换的思路，我们可以将图片成功的随机排列，基本解决了随机性的问题。
2.图片是否相同且图片之间路径的判断，这是连连看中最重要和最基础的部分，我们主要采用分类判别的方法，这其实是一种递归的算法，把复杂的问题按照层次剥离出来，每次简化一个步骤，就是递归的实现过程，我们将连连看图片的位置归类，总结出3个类别，即通过0,1,2个转角连接，0个转角是直连的方式，是递归的第一步，1个转角的形式可以转化为两次直连的方式判断，2个转角同样可以转化为1次1个转角，1次0个转角的判断。
这样图片的位置模式大致就清晰了，1,2转角均可以用0个转角解决，递归的方式简单易行，便于理解，思路层次分明。
其他的问题均是围绕这两个问题产生的，由此可以这两个问题的重要性以及良好算法设计的必要性。
1.3.3游戏设计创新点
1.游戏规则创新，当玩家在成功消除图片之后，会给予时间的奖励，时间进度条增加，增强了玩家消除的积极性。
2.提示功能，当玩家无思路的时候，可以通过该功能，解决玩家的困惑。
3,重置功能，当游戏陷入僵局的时候，重置功能可以成功解除僵局，使游戏继续进行。
4.音乐，游戏在开始后，背景音乐就进行播放，当鼠标点击图片的时候，配对的点击音乐也进行播放，用于提示。
5.时间进度条，游戏开始以后，时间以进度条的方式提示，相比原来数字的提示更加清晰。
6.图片消除算法，算法设计合理、思路清晰，涵盖全部情况，采用递归的方式便于游戏编码的实现。
2.系统分析
2.1技术可行性分析
2.1.1算法分析
连连看程序的关键是判断用户点击两个图案能否消除，两张图片消除的条件有两个：
1.图片相同
2.图片间连线的转角数不能超过两个（即用不超过三根直线连接两张图片）
根据判断能否通过不超过三根直线连接两张图片的原则，有两种实用的算法，下面是讨论方案：
1.分类判断法：
这里实质上是一种递归的思想，要判断图片A与图片B能否通过一条有N个转角的路径相连，可以转化为判断能否找到图片C，C与A能直线相连，且C与B能用一条有N-1个转角的路径相连。
若这样的图片C存在，那么A与B就可以通过一条有N个转角的路径相连。
分类法一：
根据转角数不得超过2个的规则，我们可以分为转角数分别为0个、1个、2个这三种情况分别讨论。
a）0转角连通（直线连通）：
两个图片的纵坐标或横坐标相等，且两者连线间没有其他图案阻隔。
（红色块为欲消除块）如图2-1
图2-1
b）一个转角连通：
其实相当于两个图片划出一个矩形，这两个图片是一对对角顶点，另外两个顶点如果可以同时和这两个棋子直连，那就说明可以"一折连通"。
（红色块为欲消除块，黑色代表其他阻拦块，圆圈代表折点）如图2-2
图2-2
c）两个转角连通：
判断图片A与图片B能否经过有两个转角的路径连通实质上可以转化为判断能否找到一个点C，这个C点与A可以直线连通，且C与B可以通过有一个转角的路径连通。
这样就将问题转化为了0个转角和1个转角的情况，0个转角可以直接相连，1个转角可以转化为以C点和B点为对顶角的矩形中寻找另外两个对顶角之一，看能否分别和B、C相直连。
若能找到这样一个C点，那么A与B就可以经过有两个转角的路径连通。
判断是否经两个转角连通的算法需要做两个方向上的扫描：
水平扫描和垂直扫描。
水平扫描。
为了判断A，B能否通过2个转角连通，则从A开始在水平方向上向左右扫描，并判断经过的点能否与B点经过1个转角连通。
显然C点能与B点经1个转角连通，故A，B能经2个转角连通。
（红色块为欲消除块，黑色代表其他阻拦块，黄色c代表折点,绿色代表折线），如图2-3
图2-3
垂直扫描。
为了判断A，B能否通过2个转角连通，则从A开始在垂直方向上下扫描，并判断经过的点能否与B点经过1个转角连通。
显然C点能与B点经1个转角连通，故A，B能经2个转角连通（红色块为欲消除块，黑色代表其他阻拦块，黄色c代表折点,绿色代表折线），如图2-4
图2-4
2.分类法二：
也可以如下类别进行分析连连看的消除算法：
a）两张图片左右相邻，如图2-5
图2-5
b）两张图片上下相邻，如图2-6
图2-6
c）两张图片在同一行，它们中间相隔且没有其它图片遮挡，如图2-7
图2-7
两张图片在同一行，它们中间相隔且有其它图片遮挡，但是它们存在不超过2个转弯的路径，如图2-8
图2-8
d）两张图片在同一列，它们中间相隔且没有其它图片遮挡，如图2-9
图2-9
两张图片在同一列，它们中间相隔且有其它图片遮挡，但是它们存在不超过2个转弯的路径，如图2-10
图2-10
e）两张图片相邻，但是它们存在不超过2个转弯的路径，如图2-11
图2-11
f）两张图片不相邻，但是它们存在不超过2个转弯的路径，如图2-12
图2-12
总结：
分类法一和分类法二均涵盖了连连看图片全部位置情况，可以实现准确实现连连看的消除功能，但是分类二的细节太多，颗粒度太小，分类一的分支清晰明确，颗粒度合适，因此在这里我选择了分类法一。
2.以转角数为基准的广度优先搜索法：
这种算法参考《编程之美》
这种算法的动机：
若能将所有与图片A经过不多于2个转角的路径相连的图片找出来，加入一个集合S中。
那么判断B与A能否相连只需判断B是否存在于集合S中即可。
采用广度优先搜索算法可以方便的实现这一构想。
算法的思路如下：
（1）定义空集S与T，将A加入集合S
（2）找出所有与A能直接相连的点，将其加入集合S
（3）找出与集合S中的点能直接相连的点，加入集合T，然后将T中所有元素加入到集合S中，清空集合T
（4）找出与集合S中的点能直接相连的点，加入集合T，然后将T中所有元素加入到集合S中
（5）若B在集合S中，则A，B可以相连。
否则A,B不能相连
模仿图论中广度优先搜索的算法，可以写出以转角为基准的广度优先搜索的伪代码如下（实际编程实现这一算法时可以采取优化措施，不一定要搜索出所有与A转角不超过2的点。
）：
//判断图片A与图片B能否经过不多于2个转角的路径相连的算法
bool Match（PictureA，PictureB）
{
SetS; //已经搜索到的点的集合，集合S中每个元素与A都可以通过不多于个转角的路径连通
SetT; //临时存储搜索到的点
将A加入到S中
int crossNum=0; //用于记录当前搜索到节点的最大转角数
While（B不在S中&&crossNum<3）
{
for（S中每个元素e）
{
将所有与e能直线连通的点加入到集合T中
}
T中的所有元素加入到S中
crossNum++;
}
if（B在S中）
return true ;
else
return false ;
}
广度优先搜索算法，本质上是一种建立搜索树然后剪枝的策略。
具体过程如图2-13所示：
目标是要找到从左上角的圆形图形（设为图形1）到右下角的圆形图形（设为图形2）之间不超过3个弯的最短路径。
首先在图形1所在位置向四个方向进行直线查找，如果在某一方向上找到图形2则结束。
否则，记录下所有这四个方向上的空白格子，并在每一个空白格子的其他3个方向上进行直线搜索。
如果仍未找到图形2则再次记录下查找过程中沿途记录下来的空白格子（要去掉已经走过的空白格子），仍然在3个方向上进行搜索。
若找到则返回结果，若还未找到则说明两个图形之间不存在不超过3个弯的路径。
这个算法很直观，就是在有限的转弯次数内不断构建出更大的路径网络，看看能否“覆盖”到被连接的图形，但还可以进一步提高效率，下面进行讨论。
图2-13
以图2-14为例，我们的目标是找到图形1和图形2之间的最短路径，我们从图形1出发进行查找动作。
由于题目要求最短路径不能超过3个弯，并且我们知道：
“直线路径长度≤带有一个弯的路径长度≤带有两个弯的路径长度”，所以下面我们将分三种情况进行讨论。
图2-14
首先，应该判断是否存在图形1到图形2之间的直线路径。
这一点我们可以通过他们的位置信息直接得到，例如图形1的位置是[2,2]，图形2的位置是[4,5]，很显然二者不会在一条直线上，所以直接跳过这一步。
但如果二者在一条直线上的话，还需要判断他们之间是否有障碍物存在。
例如，如果图形2在[5,2]的话，我们可以断定二者在同一直线上，但我们还需要检查在二者的直线路径上是否还有其他图形存在。
因为两个图形同在第二列上，于是我们取图2-15左边结构的第二列变量C2（这里假设是一个8位的Byte变量），然后做val=C2&00110000，注意其中的两个1是用来测试在图2的第二列上是否有非空的格子。
如果val=0则说明两个图形间存在直线路径，否则说明二者之间不存在直线路径。
这一过程的时间复杂度为O
（1）。
第二步，查找二者之间是否存在转弯一次的路径。
从图中我们可以清楚地看到，这样的路径只有两条，他们组成了一个矩形，图2-15中蓝色的矩形就是两条路径的组合而成。
我们可以用上面的方法分别来测试这两条路径上是否有障碍存在，如果没有障碍则作为最短路径返回，否则就要进行第三步。
这一步的时间复杂度也是O
（1）。
为了加速程序运行，这里还引入了图2-15所示的两个辅助数据结构，其中每一个方块中都带有一个二进制位，用来表示在该位置上的格子是否是空格子，0代表是空格子，1代表有图形存在。
虽然左右两组数据结构的内容是一样的，但是其组织方式有所不同：
左边的二进制位是按列组织的，即一列的二进制位保存在一个int或者long型的变量中，多出来的位用0填满；右边的结构是按行组织的，其他与左边结构类似。
这两个结构具体的功能后面用到的时候会详细介绍。
图2-15
第三步，查找两个图形间是否存在转弯三次的路径。
首先我们用指定方法在蓝色矩形内部进行路径查找，但是限制只在“向右”和“向下”两个方向上进行操作。
如果没找到所需路径，则需要再次扩大搜索范围。
如图2-14所示，在这一步我们需要把搜索方向在“向上”和“向左”两个方向上扩展，所获得的路径分别用红色框和粉色框表示，这个动作类似于把蓝色框向上和向左拉伸。
对于获得的路径上的3条线段，我们只需用第一步所提到的方法来查找是否存在障碍即可，若3条线段都没有障碍则返回该路径作为最短路径；否则继续向两个方向扩展搜索范围直到搜索范围到达格子的边界，若仍未找到则认为两个图形间没有符合条件的最短路径。
可以看出，由于不需要对同时对4个方向上所有空闲格子进行广度优先搜索操作，第三步的时间复杂度应该低于书中所给出的算法。
（1）是否可以通过维护任意两个格子之间的最短路径来实现快速搜索。
（2）在每次消去两个格子之后，自然更新要更新需要维护的数据，这样的思路有哪些优缺点，如何实现。
粗略想来，由于用户每次只能消除一对图形，即只会用到一个最短路径，但由于实现并不知道用户会选择哪一对图形，所以需要事先计算出所有可能的最短路径并保存起来。
此外，采用这种方法的话似乎每次用户消去一对相同图像之后都需要重新计算出当前所有可能被连接的相同图形之间最短路径，这是因为当某些图像被消去之后可能会产生很多新路径，而我们又不能确定这些空出来的格子到底能够影响哪些路径，所以就只好都重新计算一遍。
其缺点很明显就是每次消去图形动作之后重新计算所有可能的最短路径所需要消耗的时间；而该方法的优点则是可以很快地判断两个相同图形之间是否存在满足条件的最短路径。
如果用户很厉害，每次都能选中可以消除的图形对，那么用这种方法浪费的时间就会相当可观，毕竟用户未选中的其他可以连接的图形对之间的最短路径都被浪费掉了；而如果用户很差劲，每轮选择的次数都远远大于当前可能的连接数量时，该方法就会比书中正文提到的方法高效。
但这种情况是比较少的，因为在整个游戏中用户主要是会用眼睛“找”而不是频繁的用鼠标去“试”。
所以总的来看，维护所有最短路径的方法的效率相对比较低。
总结：
考虑到第一种编程思路清晰明了，框架层次分明，能够将判断的种类全部概括，每一个分支的实现都比较容易，所以对于初次实现连连看的我来说是一条捷径，因此我选择了分类判断（分类法一）的方法来实现连连看的消除算法。
2.1.2开发语言分析
根据自己以前所学的关于C语言、C++、Java、以及Qt的相关知识，并通过网上查找相关资料，了解到C、C++、VB、Delphi、C#、Java等均可以游戏的设计。
下面简单介绍下VB、C++、Java、Qt各自的特点：
1.VB的特点
全称VisualBasic，它是以Basic语言作为其基本语言的一种可视化编程工具。
在中国乃至全世界都能看到它的身影，它曾是在中国最为流行的编程工具，到现在还占据着非常重要的地位，对于它的好坏大家都有一定的了解，VB作为一种较早出现的开发程序以其容易学习，开发效率较高，具有完善的帮助系统等优点曾影响了好几代编程人员，但是由于VB不具备跨平台这个特性，从而也决定了VB在未来的软件开发中将会逐渐地退出其历史舞台；它对组件技术的支持是基于COM和ActiveX,对于组件技术不断完善发展的今天，它也显出了它的落后性；同时VB在进行系统底层开发的时候也是相对复杂的，调用API函数需声明，调用不方便，不能进行DDK编程，不可能深入Ring0编程，不能嵌套汇编；而且面向对象的特性差；网络功能和数据库功能也没有非常突出的表现，综上所述，VB作为一种可视化的开发工具由于其本身的局限性，导致了它在未来软件开发中逐步被其他工具所代替。
2.C++的特点
C/C++的哲学就不一样了，同一份程序代码，只要在该平台重新Compile成该平台的执行档，就能在该平台执行，若文字模式下的程序，的确可以跨平台，程序完全不需修改，但GUI盛行以后，由于各GUI的Library都不一样且没有标准，所以GUI程序并没办法跨平台Compile，因为各平台都有专属的Library。
但是C/C++优势就是执行速度快，若能解决GUILibrary的问题，则跨平台即可解决。
除了GUILibrary需要统一外，还得看该Library设计的好不好才行，若在Windows平台，Borland的C++Builder使用Delphi的VCLLibrary，Microsoft的VisualC++可以用MFC和.NETFramework。
首先来看Borland的C++Builder，它使用标准的ANSIC++语言开发，利用VCL写出来的程序也算蛮漂亮的，执行速度很快，比较麻烦的是C++Builder当初为了缩短上市时间，并没有设计自己的Library，而是借用Delphi的Library，导致C++Builder在Compile时，是先用Delphi的Compiler将VCLcompile成objectfile后，再用C++Builder将你写的C++程序compile成objectfile，最后再用Linker将所有的objectfilelink起来，由于这都是IDE在做，对程序设计师似乎影响不大，但VCL由于是Delphi的Library，所以若想深入研究VCL的sourcecode时，则必须学Del
升级会员 