---
title: "连连看的思路"
author: "winzenghua"
date: "2005-04-29T15:35:00Z"
tags: []
slug: "untitled"
draft: false
lastmod: "2005-04-29T15:35:00Z"
id: 988168
url: "https://java4gis.iteye.com/blog/988168"
---

目 录  
一 连连看的要求  
二 任意两点能否连通  
三 地图无解提示  
四 连接提示功能  
五 道具问题  
六 地图问题

一、连连看的要求

1：要连接的两点上的图形是相同的。  
2：两点间存在一条没有“障碍”的并且折点不超过两个的路线。  
那么分析一下可以看到，一般分为三种情况

【图例说明】  
假设以一个2维数组来表示一张连连看的地图，数组中  
元素值为0的代表游戏界面中的空格子，值大于0的代表游戏  
中的各种连接对象（1代表星星、2代表企鹅之类）

情况一：要连接的两点在同一条直线上

0 0 0 0 0 0  
0 2 0 0 0 2 * ------ *  
0 0 0 0 0 0

情况二：经过一个折点相连（+号代表折点）

0 0 0 0 0 0  
0 2 0 0 0 + * ------ +  
0 + 0 0 0 2 + ------ *  
（两条路都可连通）

情况三：经过两个折点相连（针对企鹅来说，即数字2）

0 + 0 0 0 + 0 0 0 0 0 0  
0 2 0 1 0 2 0 2 0 1 0 2  
0 0 0 0 0 0 或者 0 + 0 0 0 +

由于有1这个障碍，所以需要两个折点才能连通

二、任意两点能否连通

寻路算法是整个游戏的核心算法。网上实现的版本也很多，这里  
的方法是我比较容易理解的一个方法^o^ ，还希望大家能提出宝  
贵的批评意见和建议，谢谢了。

思路如下：

1 一条直线上两点能否相连是好判断的（一个简单的循环判断即可）

2 对于上面图例的情况二，折点的坐标是固定的，即折点要么是

\[连点1的坐标x，连点2的坐标y]要么是\[连点1的坐标y，连点2的坐标x]

y

|  
|  
| * ------ +  
| + ------ *  
\---------------- x

所以，我们只需判断连点1到折点能否连通，连点2到折点能否连通即可  
得知连点1和连点2能否连通。并且由于折点与两个连点分别是在同一条  
直线上，所以可以由第一步轻松判断得出结论。  
3 将情况三转化为情况二，（这一步是该算法中最影响性能和需要改进的地方）  
怎么转化？

0 + 0 0 0 +  
0 2 0 1 0 2  
0 0 0 0 0 0 （情况三）

将和其中一个连点在同一条直线上的折点当作该连点，那么情况三就转化为  
了情况二

0 2 0 0 0 +  
0 * 0 1 0 2 （星号为原先的连点）  
0 0 0 0 0 0 （转化后的情况三，最左上的折点已经被替换）

现在两个连接对象2之间的情形，已经变为情况二了。

4 由上可知，寻找这个被替换的折点就成了关键。因为其坐标不固定，所以只  
好递归一个一个寻找了。寻找这个点需要做很多的优化（偶也没想到多少）

2 0 0 0 0 + 0 * 0 + 0 0 0 1 0 0 0 0  
0 0 0 0 1 0 0 0 1 2 0 0 0 * 0 + 0 0  
0 0 0 1 2 * 0 2 1 0 0 0 0 2 1 2 0 0

上面三个图，+号是折点，\*号就是需要被替换的折点

假设A、B两点是同一个图形，来思考一下下面的路线

0 0 0 0 0 0  
0 0 1 0 B 0  
0 0 0 0 0 0  
0 A AA 0 1 0  
0 0 0 0 0 0  
0 0 0 0 0 0

如果我们的算法从向右开始寻找，顺时针方向旋转，那么A点先向右移动1格  
到达AA的位置，这时测试AA与B是否能连通（按情况二处理）,结果不能，因  
为折点出都有“障碍”（两个1），然后A点在移动，到达AAA处

0 0 0 0 0 0  
0 0 1 0 B 0  
0 0 0 0 0 0  
0 A AA AAA 1 0  
0 0 0 0 0 0  
0 0 0 0 0 0

在AAA处，再次与B点测试连通的时候（按情况二处理），结果是可以，所以  
A点可以与B点连通，路线为  
\+ *  
|  
\* －－－+

在增加一个障碍

0 0 0 0 0 0  
0 0 1 1 B 0  
0 0 0 0 0 0  
0 A AA AAA 1 0  
0 0 0 0 0 0  
0 0 0 0 0 0

这次，当寻找到AAA位置时，结果为不能连通。在向右，由于有障碍，所以向  
右这条路，宣告失败，递归返回到原点，换一个方向从A点向下在开始判断

0 0 0 0 0 0  
0 0 1 1 B 0  
0 0 0 0 0 0  
0 A 0 0 1 0  
0 AA 0 0 0 0  
0 AAA 0 0 0 0 (向下仍不能连通)

向左，一样。最后向上

0 0 0 0 0 0  
0 0 1 1 B 0  
0 AA 0 0 0 0  
0 A 0 0 1 0  
0 0 0 0 0 0  
0 0 0 0 0 0 (AA点与B点符合情况二，可以连通)

路线为  
\*  
|  
\-----------  
|  
\*

最坏的情况，以QQ 11\*19 的大小来计算， 共需移动28次，情况2共  
循环不超过500次  
0 0 0 0 0 0  
0 0 1 1 B 0  
0 0 0 1 1 1  
0 A 0 0 0 0  
0 0 0 0 0 0  
0 0 0 0 0 0

三、地图无解提示

因为连接对象的位置是固定的（用重列道具后位置也是固定的），我  
们以n个字符串（字符串1维数组） 来记录这些位置信息（n==游戏中出现  
的物体种类数），一个字符串记录一种，格式型如：

10208110507151218  
第一位1，表示物体的类别（是企鹅？是星星？）  
后面16位每4位一组，表示属于这个类别的一个对象的位置  
信息，0208 表示 数组中的坐标 Array\[2]\[8],即星星这个  
类别中，有一个星星在游戏中的坐标是\[2]\[8]。

这样，我们就在同一类别中，寻找该类别中现存的任意组合能否连通。  
即该类中的一个对象能否和该类别中其它对象连通。

只要找到一个，即有解。如果查找完所有的，那么就提示无解。

当我们消去一对连接对象时，在相应的字符串中删除掉这两个连接对  
象的位置信息（对应位置字符串变为－1），比如0208变为-1-1。

四、连接提示功能

根据上面的位置信息数组，按类别依次即时计算该连接对象能否和该  
类中其它连接对象相连。比如读取数组的第一个元素，在提取这个字符串  
中第一个连接对象的信息，比如1-1-11105-1-11218这个字符串， 提取出  
11，5这个位置信息，用它来连接12，18看能否连通。

五、道具问题

1，镜子  
依然根据位置信息字符串数组，提取每个对象的位置，然后用该连  
接对象的坐标x-（游戏宽度-1）取绝对值。  
0 0 0 0 0 0 0 0  
\* 0 0 0 0 0 0 * 0 - 3 ＝ -3  
0 * 0 0 0 0 * 0 1 - 3 ＝ -2  
0 0 0 0 0 0 0 0  
－－－－－ －－－－－  
0 1 2 3 0 1 2 3

2，重列  
假设我们在某局游戏中共出现了15种连接对象，每种4个，用1代表星星  
2代表企鹅...... ，那么我们仍定义一个字符串444444444444444 一共  
15个4，该字符串的每一位对应一个连接对象，比如第一位对应星星在  
游戏中还有多少个（4个），第二位代表企鹅在游戏中还有多少个......  
当我们销掉某个图片的时候，也对这个字符串对应的位置-2，而将这个  
字符串的每一位的数字相加，就是目前游戏剩下的图片数（QQ提示）。  
当其他游戏者对自己使用增加障碍道具时，相应位置+2即可。

现在游戏中连接对象的位置知道（位置信息数组），数量知道（定义的  
字符串），根据位置随机出现一个连接对象，如果该连接对象在前面定  
义的字符串中仍有数值（不为0），我们在以另一个字符串来记录这个变  
化（与前面功能结构完全相同），如果新字符串上的相应数值与原字符串  
上的相应数值相等了，则不在出现这种类型了（重列的类型数量和以前一  
样），扫描完所有的位置，从而实现了重列。（新旧字符串应相等，因为  
只是改变某个连接对象的位置，而数量没有改变）

3，什么时候出现道具？  
我感觉好像QQ的道具出现的比较公平（你出现，别人也有），这里就干脆  
这么定义吧：在某个时机（销了某个数量后，或者接连快速的销了多少对）  
那么就随机出现某种道具。

六、地图问题  
用这样一个数组代表我们想定制的排列形状

0 0 0 0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0 0 0 0  
0 0 1 1 1 1 1 1 1 1 0 0  
0 0 1 1 1 1 1 1 1 1 0 0  
0 0 1 1 1 1 1 1 1 1 0 0  
0 0 1 1 1 1 1 1 1 1 0 0  
0 0 0 0 0 0 0 0 0 0 0 0  
0 0 0 0 0 0 0 0 0 0 0 0

数组中为0的就是游戏中的空格，为1的代表某种连接对象，这样我们就可以订制任意的形状了。  
根据这个数组，如果某个点的值不为0，则随机生成一个连接对象，并在前面的种类详细数量  
字符串中的对应位置+1（QQ是每种4个），当这个位置（种类）的值为4时，就不再增加了。

喜欢玩QQ的连连看，很想自己也写一个，故有此文。