连连看算法分析分享
开发环境
- Windows 7 64bit
- Quick-Cocos2d-x 3.2rc0
章节内容
本章主要介绍连连看常用的算法，包括连连看的地图生成算法和匹配消除算法，不涉及具体的代码实现。
相信很多同学在游戏生涯中都玩过连连看游戏，那么连连看游戏是如何实现的呢？如何使用 Quick-Cocos2d-x 实现一个连连看游戏呢？接下来的几篇文章将为大家介绍简单连连看游戏的实现方法。在本章中，我们先介绍连连看常用的一些算法。实际上，连连看使用的算法并不多，主要集中在地图生成算法和匹配消除算法。下面我们先来看看地图生成算法。
地图生成算法
连连看的地图可以简单地看作一个二维数组，数组的大小取决于所要绘制的元素个数。但需要保证元素成对出现，即若显示数组的长为 $m$，宽为 $n$，则必须满足 $m \times n \bmod 2 = 0$。
随机复制打乱法
现在我们来看地图生成的一种算法，以 $5\times6$ 的数组为例。 具体步骤是先生成一个大小为 $m\times n/2$ 的数组，然后将数组的前一半复制到数组的后一半，最后随机打乱。
以下是使用 Lua 语言的示例代码：
matrix = {}
total_row = 5
total_col = 6
total_type = 5
-- 生成前半部分数组
for i = 1, (total_row * total_col) / 2 do
matrix[i] = math.random(1, 5)
end
-- 复制前半部分到后半部分
for i = 1, (total_row * total_col) / 2 do
table.insert(matrix, matrix[i])
end
生成的数据示例如下：
1,3,1,5,3,3,
2,5,5,4,1,5,
4,3,2,1,3,1,
5,3,3,2,5,5,
4,1,5,4,3,2,
从生成的数据可以看出，这种方法生成的数据离散度不强，所以我们还需要再次随机打乱原有数据。以下是打乱数据的代码：
for seq = 1, 13 * 2 do
for i = 1, #matrix do
local row_org = math.random(1, total_row)
local col_org = math.random(1, total_col)
local row_dest = math.random(1, total_row)
local col_dest = math.random(1, total_col)
local index_org = (row_org - 1) * total_col + col_org
local index_dest = (row_dest - 1) * total_col + col_dest
matrix[index_org], matrix[index_dest] = matrix[index_dest], matrix[index_org]
end
end
再次打乱后的数据示例如下：
5,2,1,3,1,3,
3,5,1,3,3,4,
3,5,4,1,2,4,
3,2,1,1,5,5,
5,2,3,5,5,4,
模板法
所谓模板法，就是手动或者使用工具建立一个模板，在生成地图时，根据模板的设置来生成地图。例如，我们生成一个如下格式的地图：
map = {
1,2,3,4,5,6,
5,4,3,2,1,6,
1,2,3,4,5,5,
3,5,4,2,1,6,
2,4,3,5,2,1
}
我们可以根据上面的地图模板生成对应的精灵并显示出来。实际上，这种方法是最有效的生成地图的方法，能适应各种需求。
地图有解性问题
在上述方法中，我们都没有确定地图是否有解。对于模板法，我们在生成地图时就可以生成一个有解的地图；而对于随机生成法来说，情况就比较麻烦，我们必须对地图进行求解。而求解地图就要用到下面要讲述的匹配消除算法。
匹配和消除算法
玩过连连看游戏的同学都知道，连连看游戏的基本规则有两条：
- 两个图片相同。
- 两个图片之间的连接拐角不能超过两次。
只有同时满足这两个条件，图片才能消除。我们以这两个条件作为判断的依据。判断两个图片是否相同比较简单，这里不再赘述，我们主要来分析如何判断两个图片的连接是否超过两次拐角。
由于连接拐角不能超过两次，所以自然会有三种情况：
- 一条直线直接连通。
- 一个拐角，两条直线连通。
- 两个拐角，三条直线连通。
下面我们逐一进行分析：
一条直线直接连通
一条直线连通有以下几种情况，分别是纵向相邻（如 $(1,2)$）、横向相邻（如 $(3,4)$）、横向中间为空（如 $(5,6)$）、纵向中间为空（如 $(7,8)$）。 如果两个元素相邻，我们只需判断它们在行或者列上的差值是否为 1。同样，对于中间为空的两个元素，我们只需判断它们之间是否有其他元素存在。
一个拐角，两条直线连通
两个图片通过一个拐角连接的例子可以参考下面的示意图（此处缺少图片，可自行补充）。图中，背景为白色的方框表示没有元素，背景为黄色的方框表示起点和终点，绿色的方框表示有图片。我们从左边开始查找，找到的第一个图片为空时，再检测它是否能和图片 2 连通，如果能连通，说明图片 1 和图片 2 可以通过一个拐角连通。其他情况都可以按照上述步骤向四个方向扩展检查。
两个拐角，三条直线连通
对于两个拐角的情况，我们可以基于前面的步骤进行扩展。例如，假设图片 2 位于图片 1 的正下方第二个位置。这时我们可以分别从图片 1 和图片 2 出发，向四个方向执行一个拐角连通的判断步骤。
- 从图片 1 往左判断该位置是否为空，若为空，则根据一个拐角连通的方法判断这个位置和图片 2 是否能经过一个拐角连通。如果不能连通，则继续往左遍历。
- 从图片 1 往右判断该位置是否为空，若为空，则根据一个拐角连通的方法判断这个位置和图片 2 是否能经过一个拐角连通。如果不能连通，则继续往右遍历。
- 从图片 1 往上判断该位置是否为空，若为空，则根据一个拐角连通的方法判断这个位置和图片 2 是否能经过一个拐角连通。如果不能连通，则继续往上遍历。
- 从图片 1 往下判断该位置是否为空，若为空，则根据一个拐角连通的方法判断这个位置和图片 2 是否能经过一个拐角连通。如果不能连通，则继续往下遍历。
以上内容基本上涵盖了基本的连连看算法，如果大家还有更高阶的算法，欢迎分享。在下一篇文章中，我们将介绍如何基于以上算法实现一个连连看游戏。