李丽惠，庄杨波



连连看游戏搜索算法的研究与改进

李丽惠，庄杨波

（漳州职业技术学院计算机工程系，福建漳州363000）

近几年，连连看游戏作为一个家喻户晓的大众化游戏，被广大玩家喜欢和接受，作为一款益智类的游戏，连连看更是一个百玩不厌的经典。对目前所常见的连连看游戏进行算法的研究与改进，使其在响应速度更快，更需要玩家采用更合适的策略以便得到更好的游戏成绩。重点是对地图绘制、连通消除、关卡设置、胜利目标等涉及到的相关算法进行了研究和讨论。

广度优先；算法；随机调度

1 引言

“连连看”游戏是一种流行广泛的单机版游戏，游戏规则是：在初始化的一定数量的图片中，选择图案相同的两张依次点击，若两张图片的位置满足一定的条件，则会被自动消除[1]。在规定的时间内给出的所有图片均被消除，则当前关卡结束，进入下一关，还在普通连连看的基础上增加了两个游戏策略：（1）如果将“障碍物”图标全部消除，则本关胜利。（2）当两个图标的连线碰到“炸弹”时，则游戏中的此种图标全部消除。本文主要是对“连连看”游戏算法进行了研究与改进，希望该研究使新版本的游戏得到更广泛的喜欢和应用。

2 算法分析

基本的游戏流程如图1。

图1 “连连看”游戏流程

对照流程图，涉及的主要算法有：

2.1 地图初始化

整个游戏区域主体部分可以看作是一张二维表格，使用二维数组Map[i][j]进行表示。游戏过程中，用户可以手动设置所需要的地图，根据保存在文件夹下的配置文件，用0和1分别表示地图中是否显示图片（0和1的设置数量应该均设为偶数），如果当前位置是1，则显示图片；如果是0，则不显示图片。图片的显示应该是随机并且成对出现，采用另一个二维数组IsFace[i][j]进行表示，初始值IsFace[i][j]均为0，表示尚未放置图片（如下图2所示，该地图为隔空放置图片，其中◎表示障碍物，※表示炸弹）。

（1）先处理“障碍物”图标的位置，随机产生一个i，j，若Map[i][j]=1且IsFace[i][j]=0，放置“障碍物”图标，并修改IsFace[i][j]的值，直到24个“障碍物”图标全部放置完毕。

（2）遍历整个Map[i][j], 若Map[i1][j1]=1且IsFace[i1][j1]=0，则随机从图库中挑一个图片，并且随机在另一个尚未放置图片的位置i2,j2处放置相同的图片, 放置好后修改两处的IsFace值为1。

（3）遍历整个Map[i][j], 若Map[i][j]=0且IsFace[i][j]=0，则随机找到一个i3, j3, 若IsFace[i3][j3]=0，则放置不多于15个“炸弹”图标。此处的IsFace[i][j]在每次进行消除一组对象之后都会重新置为1，刷新“炸弹”布局图。

Ⅲ◎Ⅳ ⅤⅥⅠⅠ ⅫⅢⅨ※ Ⅱ◎◎ ◎※Ⅺ◎ ⅫXI※Ⅱ◎

2.2 “炸弹”规则

“炸弹”不同于图片及“障碍物”，不可单独点击连接（不可点击），也不会影响图片及“障碍物”的连接判定。满足消除规则的前提下，若其连接线有“炸弹”，则把地图上所有该类图片，全部消除。

2.3 判断消除

要判断两张图片是否能被消除，要分3种情况来考虑，若其中一种情况达成的话，则消除图片，否则此次操作无效。

（1）两张图片处于同一行或者同一列，并且其直线连接线之间，不含其它图标及“障碍物”（可以包含“炸弹”），此位置关系称为“0折型”，如图2第二行的两个“I”图标所示。

（2）两张图片不处于同一行或者同一列，则以这两张图片作为矩形的对角点，沿着矩形从起点到终点就有两种方式，如果某一方式“沿途”不含其它图标及“障碍物”（可以包含“炸弹”），此位置关系称为“一折型”，如图2第四行第一列和第六行第五列的两个“II”图标所示。

（3）两张图片需要通过三条线（三条连接线之间，不含其它图标及障碍物，却可以包含“炸弹”）才能连接，此位置关系称为“两折型”，如图2第一行第二列和第三行第五列“III”图标所示。

2.3.1 广度优先搜索

在算法中，“0折型”和“一折型”采用的是较为简单的判断操作，排除掉这两种情况后，剩下的均采用广度优先搜索算法进行判断是否可消除。广度优先搜索算法，本质是一种建立搜索树然后剪枝的策略，它实现的是对整张图进行彻底的搜索，直到找到结果为止。它对图形采用层次结构进行遍历，先是根节点，然后是第二层子节点，依此进行下去，将每个节点放到一个队列中，按照“先进先出”的顺序，每次从队列中探出“首元素”，遍历后的点放入CloseArr数组(存放已经访问过的节点)，还未遍历的点放入OpenArr数组（存放即将访问的节点），当OpenArr数组到最后一个点时，则整个遍历完全。即寻找到从左上角的图片A到右下角的图片B之间不超过三折的最短路径。算法的思想是：首先在A的位置向四个方向（下，右，上，左）进行直线查找，如果在某一方向上找到图形B，则搜索结束，否则记录下所有这四个方向上的空格（没有图片的位置）位置，并在每一个空格的其他三个方向上进行进一步的直线搜索，如果仍未找到B，则再次记录下查找过程中沿途记录下来的空格（除了已经记录的空格），并继续在三个方向上进行搜索，依次递归搜索下去。若找到则返回并且消除，否则说明这两张图片之间不能进行消除。

2.3.2 消除判断的实现

按照上面定义的消除策略，可以对三种情况分别使用三个函数来进行数据的查找。

设定“0折型”的函数是bool GetLine（GetLine(GridNode[] GridNodes, GridNode fromNode, GridNode targetNode），循环查找同行或者同列中空白位置，直到目标图形所在的行或者列，一旦发现有一条直通线，则返回为真，否则返回为假。

设定“一折型”的函数是bool GetOneCorner(GridNode[] GridNodes, GridNode fromNode, GridNode targetNode)，取两个图片中较小的行号、列号和较大的行号、列号，构成一个矩形，进行判断。如果从图片A出发，经过一个拐弯能够直通到图片B，那么记录下拐点的信息及A、B点的位置信息，并且函数返回为真，否则返回为假。

设定“两折型”的函数为bool GetTwoCorner(GridNode[] GridNodes, GridNode fromNode, GridNode targetNode)，这个函数需要从四个方向进行逐一查找,每查找到一个新空格时，即调用“一折型”的函数bool GetOneCorner(GridNode[] GridNodes, GridNode fromNode, GridNode targetNode)，判断当前新空格是否可以与目标图形形成一个通路，如果该函数返回的是为真，则从图形A和图形B构成的通路就是“两折型”，如果该函数返回为假，则从下一个空格继续进行查找，直到全部遍历，遍历完后如果没有找到通路，则“两折型”函数返回为假。

炸弹消除的实现可以设定函数CollectBombsAndFaces()，当两个方格可以连接时，搜集连线所经过的炸弹的所有索引号和必须消除的所有方格的索引号，并将它们保存至数组bombIndexes和faceIndexes中[3]。一旦碰到所登记的炸弹，则图片对应的相同索引号的图片均被消除掉。

2.4 特殊情况的处理

每消除两张图片后，程序就会检测一次当前棋盘上是否还存在满足消除条件的图片，若没有则称为死锁[2]。若发生死锁，则调用前面的随机算法对当前棋盘上的图片重新排列一次，直到死锁解除。

3 结 论

本文考虑了单机版的连连看游戏的算法研究与改进，并增加了“炸弹”和“障碍物”图片以增加游戏的策略性，能够让玩家在玩的同时综合考虑策略的应用技巧，更具有一定的趣味性，可以同时应用在手机版和电脑板的连连看游戏上。不足之处是尚未深入考虑网络版的连连看采用双方对战的形式，当一方消除一组图片时则对方相应的增加一定量的“障碍物”，让游戏更具有一定的趣味性和挑战性。

[1]仇宾. 基于Java的“连连看”游戏[J]. 电脑编程技巧与维护, 2013(11): 72-77.

[2]赵海国，屈洋. 连连看游戏的设计及其实现[J]. 湖南理工学院学报, 2015(3): 39-42.

[3]毕文斌，孙明亮. C# Windows游戏设计[M]. 北京: 清华大学出版社, 2014.

（责任编辑：马圳炜）

Research and improvement of Lianliankan Game search algorithm

LI Li-hui, ZHUANG Yang-bo

(Computer Department of Zhangzhou Institute of Technology, Zhangzhou 363000, China)

Lianliankan game as a popular game known to every family this years, love and acceptance by the majority of game player, as a puzzle game, Lianliankan is a play for the classic. This paper is mainly on the current common game for the study and improvement of the algorithm to make it faster in response, but also requires the player to use a more appropriate strategy in order to get better results of the game. Focus is on map drawing, connectivity, the level set, the victory of the target and other related algorithms are studied and discussed.

breadth first; algorithm; random scheduling

1673-1417（2016）04-0017-04

10.13908/j.cnki.issn1673-1417.2016.04.0004

TP317.4

A

2016－09－15

李丽惠(1982—)，女，福建漳州人，高级工程师，硕士，研究方向：软件开发与应用。