作者：AchillesL
若转载文章，请标明文章出处

1.序

  上周实现了用程序自动填充数独（详情见《记数独X--Android openCV识别数独并自动求解填充APP开发过程》），这次想试试能不能用同样的方法玩“连连看”。实际上是可以的，解决连连看的真正难点在于：图片分类，即需要识别游戏中共有多少张不同种类的图片，并匹配相同的图片。对于求解连连看的算法并不非常难，本文有具体的介绍。

  本文重点涉及到的内容有：感知哈希算法、连连看求解算法、屏幕模拟点击。

  附LinkGameX运行的效果图，解一局连连看也就只需几秒：

效果图，可能加载有点慢

2.下载链接

  LinkGameX APP：点击下载 提取码：ez6v
  本文用到的连连看游戏APP：点击下载 提取码：clnh
  LinkGameX GitHub地址：https://github.com/AchillesLzg/jianshu-LinkGameX

3.本文内容

• 实现思路
• 项目介绍
• openCV配置与无Root截屏
• 图片相似度判断算法
• 连连看求解算法
• 后记
• 参考文章

4.实现思路

  步骤1：通过截屏，获取游戏的界面图像。为了避免遮挡游戏界面，本应用应该做成悬浮窗形式。

  步骤2：得到连连看游戏面板的矩形区域后，计算并截取每个小图片，通过感知哈希算法生成每个小图片的特征序列。

  步骤3：遍历每个小图片与其他图片的特征序列，计算两者的相识度，超过特定阈值可以认为是同一图片，否则是不同的图片，并最终将结果存入数组中。

  步骤4：使用连连看求解算法计算点击序列。

  步骤5：进行屏幕模拟点击。

5.项目介绍

  项目主要包含文件如下图：

6.openCV配置与无Root截屏

  我们需要截取其他APP的界面，因此需要用到截屏，得到截屏图片后，需要使用openCV的部分功能进行图像处理，因此也需要openCV的配置。此部分内容笔者有文章专门介绍，本文不再赘述。
  在Android Studio中配置openCV项目
  Android 5.0 无Root权限实现截屏

7.图片相似判断算法

  判断两张图片内容是否相同，有很多算法可以实现。本项目需要兼顾性能与精度，最终选用了感知哈希算法(Perceptual hash algorithm)。

感知哈希算法(perceptual hash algorithm)，它的作用是对每张图像生成一个“指纹”(fingerprint)字符串，然后比较不同图像指纹。结果越接近，就说明图像越相似。

  感知哈希算法实现步骤：

1. 缩小尺寸：将图像缩小到8*8的尺寸，总共64个像素。这一步的作用是去除图像的细节，只保留结构/明暗等基本信息，摒弃不同尺寸/比例带来的图像差异；

2. 简化色彩：将缩小的图像，转为64级灰度，即所有像素点总共只有64种颜色。

3. 计算平均值：计算所有64个像素的灰度平均值；

4. 比较像素的灰度：将每个像素的灰度，与平均值进行比较，大于或等于平均值记为1，小于平均值记为0；

5. 计算哈希值：将上一步的比较结果，组合在一起，就构成了一个64位的整数，这就是这张图像的指纹。组合的次序并不重要，只要保证所有图像都采用同样次序就行了；

6. 得到指纹以后，就可以对比不同的图像，看看64位中有多少位是不一样的。在理论上，这等同于”汉明距离”(Hamming distance,在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数)。如果不相同的数据位数不超过5，就说明两张图像很相似；如果大于10，就说明这是两张不同的图像。

  可以看到，该算法将图片归一化到8*8大小，并将彩色转灰度，因此很大程度去掉了不重要的细节，只保留了图像的轮廓、结构的信息，以此来判断两图像是否相同。

  事情真的这么简单？！ヾ(◍°∇°◍)ﾉﾞ

  经过笔者的试验，该算法的准确度可以达到98%左右，但这个精度满足本项目的要求吗？然而并没有！因为测试用的连连看APP共7行12列，84个格子，84×98%≈79，即每局游戏很可能会出现一两张图片时匹配错误的。如果连图片100%匹配也无法保证，更不用提求解算法了。

  o(▼皿▼メ;)o！！o(▼皿▼メ;)o！！o(▼皿▼メ;)o！！o(▼皿▼メ;)o！！o(▼皿▼メ;)o！！

  难道就这样做不下去了吗？也不是的，笔者思考后，至少还有两个地方可以继续优化：

1. 连连看中格子图片过小，而且可能会出现比较类似的图片，前面我们把图片归一化到8×8大小64灰度，可能会过多地省略了细节。笔者对感知哈希算法做了一些调整：图片归一化到16×16大小，保持255灰度。避免省去过多的细节。
2. 目前为止，我们是通过连连看面板的信息，通过计算得到的小格子区域，但可能计算误差，即使相同图案的格子，也可能存在位置的偏差。为了修正这个偏差，我们可以通过openCV的轮廓检测直接把图像的区域”扣“出来。这个也可以进一步提高感知哈希算法算法的精确度。

  笔者在完成这两步的优化后，基本可以做到每局游戏的图片匹配精度为100%。使用openCV进行轮廓检测，可以参考笔者另一篇文章《记数独X--Android openCV识别数独并自动求解填充APP开发过程》中的相关部分。

  【注】本部分代码主要在LinkGameXPicAnalyse类中实现，在这里不再贴代码。

8.连连看求解算法

  在编写连连看求解算法前，我们需要先知道连连看的游戏规则：若两点间的连接路径不超过两个拐点，则该两点可以被消除。所以，两点可消除，共有三种情况。

8.1 情况分类

8.1.1 情景一：两点间路径没有拐点

  如上图，若两点在同一行或者同一列上，两点是可直达的。这种情况很好判断，只需要判断两点的路径上是否满足所有的格子都被消除即可，即AB两点是否连通。

8.1.2 情景二：两点间路径有一个拐点

  若两点路径有一个拐点，此时的A、B点必然不在同一行或者同一列上，并且A→B存在两条路径，各有一个拐点。此时，我们只需判断两条路径的拐点是否有其中一个能满足能同时与AB点连通，若满足，A与B可消除。

8.1.3 情景三：两点间的路径有两个拐点

  如上图，A→B（实际情况AB不一定同行或同列）存在一条路径，路径上有两个拐点。这种情况看上去很复杂，其实不然，这个问题我们可以转换为刚才的情况：我们能不能找到一个拐点C，使得拐点C与拐点B能连通，并只存在一个拐点？明显地，这个拐点C与A必定同行或同列，我们只需遍历点A的同行与同列的格子，若找到一个这样的拐点C，则说明AB点可消。

8.2 代码实现

  我们稍加留心，就会发现：判断AB是否满足情景二（一个拐点），会调用到判断情景一（直连）的功能；判断AB是否满足情景三（两个拐点），会调用到情景二（一个拐点）的功能。可见，代码复用程度是很高的。

  实现代码时，我们用到布尔值二维数组，用于判断某个格子是否已消除。需要注意的是，判断两个拐点时可能会存在两拐点在矩形区域外的情况，因此我们的布尔值二维数组范围应该是bool[行+2][列+2]，而边界值全部置为true，表示已消除(可连通)。

  关键代码：

(LinkGameXAnalyse.java)
...
//没有拐点的情况
private boolean canLink1(LocInfo locInfo1, LocInfo locInfo2) {
    if (locInfo1.x != locInfo2.x && locInfo1.y != locInfo2.y) return false;
    if (locInfo1.x == locInfo2.x) {
        int min = Math.min(locInfo1.y, locInfo2.y);
        int max = Math.max(locInfo1.y, locInfo2.y);
        for (int i = min + 1; i < max; i++) {
            if (!isPointDismiss(new LocInfo(locInfo1.x, i))) {
                return false;
            }
        }
    } else {
        int min = Math.min(locInfo1.x, locInfo2.x);
        int max = Math.max(locInfo1.x, locInfo2.x);
        for (int i = min + 1; i < max; i++) {
            if (!isPointDismiss(new LocInfo(i, locInfo1.y))) {
                return false;
            }
        }
    }
    return true;
}
//只有一个拐点的情况
private boolean canLink2(LocInfo locInfo1, LocInfo locInfo2) {
    LocInfo crossPont1 = new LocInfo(locInfo1.x, locInfo2.y);
    if (isPointDismiss(crossPont1)) {
        return (canLink1(locInfo1, crossPont1) && canLink1(crossPont1, locInfo2));
    }
    LocInfo crossPont2 = new LocInfo(locInfo2.x, locInfo1.y);
    if (isPointDismiss(crossPont2)) {
        return (canLink1(locInfo1, crossPont2) && canLink1(crossPont2, locInfo2));
    }
    return false;
}
//有两个拐点的情况
private boolean canLink3(LocInfo locInfo1, LocInfo locInfo2) {
    for (int i = 0; i < flagRow; i++) {
        LocInfo locInfo = new LocInfo(i, locInfo1.y);
        if (!isPointDismiss(locInfo) || !canLink1(locInfo1, locInfo)) continue;
        if (canLink2(locInfo, locInfo2)) {
            return true;
        }
    }
    for (int i = 0; i < flagCol; i++) {
        LocInfo locInfo = new LocInfo(locInfo1.x, i);
        if (!isPointDismiss(locInfo) || !canLink1(locInfo1, locInfo)) continue;
        if (canLink2(locInfo, locInfo2)) {
            return true;
        }
    }
    return false;
}
...

9.屏幕模拟点击

  实现屏幕的模拟点击，一般比较可行有两个方法：一是申请root权限，调用adb指令执行屏幕点击。二是通过调用AccessibilityService新增了dispatchGesture方法，发送手势，当发送的手势Path是一个点时，表示点击操作。由于方法一需要root权限，且adb的指令执行速度慢，本项目采用第二个方法。注意首先这个方法是7.0之后加入的，所以最小版本改为24。

  【注】对于AccessibilityService的入门介绍，可见笔者的另一篇文章《记数独X--Android openCV识别数独并自动求解填充APP开发过程》的相关部分，在此不再赘述。

  在LinkGameXAccessibility的onCreate方法中，我们需要生产连连看小格子的屏幕坐标，以便后序点击时使用，关键代码：

(LinkGameXAccessibility.java)
...
public class LinkGameXAccessibility extends AccessibilityService {
    private static final String TAG = "LinkGameXAccessibility";
    private ArrayList<ArrayList<Point>> mPoints = new ArrayList<>();

    @Override
    public void onCreate() {
        super.onCreate();

        initPanelPointList();
    }

    private void initPanelPointList() {
        double width = LinkGameXUtils.RECT_WIDTH * 1.0 / LinkGameXUtils.COL;
        double high = LinkGameXUtils.RECT_HEIGH * 1.0 / LinkGameXUtils.ROW;

        for (int i = 0; i < LinkGameXUtils.ROW; i++) {
            ArrayList<Point> points = new ArrayList<>();
            for (int j = 0; j < LinkGameXUtils.COL; j++) {
                int x = (int) (LinkGameXUtils.RECT_Y + width * j + width / 2);
                int y = (int) (LinkGameXUtils.RECT_X + high * i + high / 2);

                points.add(new Point(x, y));
            }
            mPoints.add(points);
        }
    }

    @Override
    public void onAccessibilityEvent(AccessibilityEvent event) {
        Log.d(TAG, "onAccessibilityEvent: " + event.toString());
    }

    @Override
    public void onInterrupt() {

    }
}
...

  通过dispatchGesture完成模拟点击，关键代码：

(LinkGameXAccessibility.java)
...
public void dispatchGestureView(int startTime, int x, int y) {
    Point position = new Point(x, y);
    GestureDescription.Builder builder = new GestureDescription.Builder();
    Path p = new Path();
    p.moveTo(position.x, position.y);
    /**
     * StrokeDescription参数：
     * path：笔画路径
     * startTime：时间 (以毫秒为单位)，从手势开始到开始笔划的时间，非负数
     * duration：笔划经过路径的持续时间(以毫秒为单位)，非负数*/
    builder.addStroke(new GestureDescription.StrokeDescription(p, startTime, 1));
    dispatchGesture(builder.build(), null, null);
}
...

  【注】该部分主要在LinkGameXAccessibility类中实现。

10.后记

  该项目还是有很多地方可以继续优化的，如：

• 一局连连看有可能无法一次性完成，需要多次截屏，该功能在这里还没实现。
• 有些连连看的游戏界面不一定是方方正正的矩阵区域，对于异型连连看，还需要判断哪些区域是背景图片。
• 可尝试采用其他图像识别算法判断两图片是否内容相同。

11.参考文章

  图像相似度计算之哈希值方法OpenCV实现

  连连看所属算法分析与实现

  记数独X--Android openCV识别数独并自动求解填充APP开发过程