一、绝地反击
最近女票迷上了某平台的连连看对战小游戏，于是免不了要找哥哥我 PK 一翻，虽然是被迫卷入战争，但是以朕惊世骇俗的智商，那当然是胜券在握啦~~ 没曾想，几个回合下来，竟被啪啪啪打脸，快把这个月的口粮都输光了（每把5块钱啊，肉疼！！） 哎，完全拼手速是没有希望的了，得想办法让连连看自动打
“连连看”都不会打的直男们，赶紧去怼一局
二、可行性
前段时间跳一跳火起来的时候，有人就通过 adb 截屏并发送到电脑分析，再求得距离然后计算出按键时长，最后通过 adb shell 自动按键，从而获得完美跳跳分，这一招用在连连看是否管用呢？ 理论上，靠谱，分解如下：
- adb 截图传到电脑
- 将连连看的点击区域识别为一个二维矩阵，每一种小动物用一个数字表示
- 对二维矩阵求解，计算出每个位置的点击顺序数组
- 通过 adb shell 一把梭，一次性点掉所有
酱紫如果顺利的话并且不被女票发现，赢回三个月的口粮都很有希望呀~~
三、实施步骤
技术选型
从上一节的分析来看，方案的实施涉及到很多图片的分析处理，Python 可以方便的调用很多图片库，而且网上也有很多作业可以抄，所以选择基于 Python 来做
环境搭建
没有很具体的安装步骤，需要的咨询谷歌哥
1） 安装 adb 环境。安装完成后，用数据线连接一台 android 手机，执行一些简单的 adb 命令预热下
// 是否连接上
adb devices
// 可否截屏保存
adb shell /system/bin/screencap -p /sdcard/screenshot.png
adb pull /sdcard/screenshot.png /yourDocuments/screenshot.png
// 可否点击屏幕
adb shell input tap 100 100
2）安装 python 和相关的图片库，在安装 openCv 的时候还踩了个大坑，记录了下，仅供参考
图片处理
1）截屏保存 在终端，执行如上的两个 adb 命令就可以截屏保存了，也就是说，这里需要一个可以调用终端命令，同时可以等待返回的 Python 方法：
// 执行终端命令的方法
def sh(command):
p = subprocess.Popen(command, shell=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT)
print p.stdout.read()
// 截屏保存
sh('adb shell /system/bin/screencap -p /sdcard/screenshot.png')
sh('adb pull /sdcard/screenshot.png /yourDocuments/screenshot.png')
2）裁剪有效区域、再等比切出小动物头像 如果不要求很通用只是对你的手机有效的话，那么只需要将第一步截下来的屏幕用工具来量一量（如 Mark Man)，就可以用如下方式裁剪出有效区域
from PIL import Image
def cut (im, x, y, w, h, name):
region = im.crop((x, y, x+w, y+h))
region.save("./screenshot/" + name + ".png")
# 有效点击区域裁剪 (不通用的做法是，把这个矩形的坐标量出来)
gx = 43
gy = 401
gw = 993
gh = 1420
cut(Image.open("./screenshot/screenshot.png"), gx, gy, gw, gh, 'main')
如果要做得通用一些，就需要计算图片的比例了（只用于打败女票的，完全没必要嘛）
然后再按照10行7列切成小块，并且根据二维数组的下标命名
# -*-coding:utf-8-*-
from PIL import Image
import cutImg
def cut ():
im = Image.open("./screenshot/main.png")
# 图片的宽度和高度
img_size = im.size
width = img_size[0]
height = img_size[1]
distanceW = width / 7
distanceH = height / 10
print(distanceW, distanceH)
x = 0
y = 0
for num in range(0, 10):
for i in range(0, 7):
x = distanceW * i
y = distanceH * num
name = str(num) + str(i)
cutImg.cut(im, x + 15, y + 15, distanceW - 20, distanceH - 20, name)
return [distanceW, distanceH]
这一步着实需要下功夫，还踩了不少坑~~
首先想到的是通过求解图片的 hash 值，利用 hash 值来比对图片的相似度（例如感知 hash 算法）。网上有各种求 hash 值的算法，实现起来倒也简单，但是，比较的正确率只能达到百分之七、八十（这样我们分析出的点击路径，肯定打不过啦！！），主要是这些小动物头像在 hash 算法下显得都太相似了，拿感知哈希算法来说： a) 缩小图片尺寸 b) 转为灰度图片 c) 计算灰度平均值 d) 比较像素的灰度 e) 计算哈希值 f) 对比图片指纹
转念一想，这个问题在机器学习领域，不过是那种最最简单的分类问题，so，完全可以先训练一个模型出来
4）解析小动物头像输出数字二维矩阵（第一回合） Turicreate 是苹果开源的基于 python 机器学习框架，特点是轻量（只是分类相似的图片而已，当然是越简单越好），先安装之
然后将上面写好的截屏裁剪代码多执行几次，手工分类，准备好训练数据：
开始训练，并保存模型：
#!/usr/bin/env python
#encoding=utf-8
import turicreate as tc
img_folder = 'data'
// 导入数据
data = tc.image_analysis.load_images(img_folder, with_path=True)
// 使用文件名来做标签
data['label'] = data['path'].apply(lambda path: path.split('/')[len(path.split('/')) - 2])
data.save('doraemon-walle.sframe')
// 百分之八十的数据用于训练，百分之二十用于测试
train_data, test_data = data.random_split(0.8, seed=2)
// 开始训练模型
model = tc.image_classifier.create(train_data, target='label')
// 测试模型
predictions = model.predict(test_data)
metrics = model.evaluate(test_data)
// 输出测试结果
print(metrics['accuracy'])
model.save('my_model_file')
执行到倒数第二行的时候，顺利输出1.0（百分百的正确率有木有）：
使用训练好的模型，输出二维矩阵：
import turicreate as tc
loaded_model = tc.load_model('my_model_file')
def getDataset():
data = tc.image_analysis.load_images('screenshot', with_path=True)
arr = loaded_model.predict(data)
result = []
temp = []
for index in range(len(arr)):
if (index % 7 == 0):
temp = []
if ((index + 1) % 7 == 0):
result.append(temp)
// f 为 0，标记为未删除
temp.append({'v': int(arr[index]), 'f': 0})
return result
路径求解
1）判断两个动物图标可连 需要满足如下条件： a) 相同的图标 b) 两种直接存在一条通路，它是一条只经过没有图案的地方、且转折点不超过2个的折线 具体代码实现可以看看这篇博文的分析（虽然是 C 版），这里我就不贴了，繁琐占篇幅
2） 搜索路径，最简单粗暴的一种做法 （1）从矩阵中挑出一个未被标记为删除的元素，（2）再从矩阵中余下的不被标记删除的元素寻找一个跟它一样的元素，判断是否可以相连，是则将两个元素标记为删除，并将点击坐标压入坐标数组，否则重复（2），（3）重复（1），知道找到所有的点击坐标点 但是这种做法是 O(nXn)，很遗憾，暂时也没有想到更好的办法，只是想到了一个小小的优化策略，开始先遍历一轮，将所有挨着的相同图标消掉（显而易见的事情当然要先办啦），减小 N，节省一下算法的时间
然后在“盲狙”的过程中，因为循环停止的条件是找到所有的坐标点，假如游戏给了个无解的矩阵，或者咱们图片识别错了导致无解，就会陷入死循环（虽然这样的概率极低，没遇到过），所以要做一下循环保护
# 遍历消除(盲狙)
def commonBuild():
global data
global pos
for num in range(0, 10):
for i in range(0, 7):
item = data[num][i]
if (item['f'] == 1):
continue
for ix in range(0, 10):
if (item['f'] == 1):
break
for iy in range(0, 7):
item1 = data[ix][iy]
if (item1['f'] == 1 or item1['v'] != item['v'] or (ix == num and iy == i)):
continue
if (remove.canRemove(num, i, ix, iy, data) == 1):
item['f'] = 1
item1['f'] = 1
pos.append(getPos(i, num))
pos.append(getPos(iy, ix))
break
// 达到 70 也即所有的坐标都找到即停止
// 否则也最多循环十次
count = 0
while (len(pos) < 70 and count < 10):
count = count + 1
commonBuild()
print(count)
很幸运，经过优化后的算法，基本上每次 count 都输出为 1，不需要遍历太多次。假如真的出现了无解矩阵，循环了 10 次退出了，那该如何是好呢？这个时候自己将机器没有打完的点掉也应该没有难度了
adb 一把梭
克服艰难险阻把坐标数组计算出来之后，后面的事情就简单了，执行 adb 命令一把梭
for index in range(len(pos)):
command = 'adb shell input tap ' + str(pos[index][0]) + ' ' + str(pos[index][1])
print(command)
os.system(command)
四、后来，我赢了么?
然而并没有！！！ 因为每条 adb 命令的执行间隔基本差不多要到 1 秒，逐条执行完之后黄花菜都凉了，要知道正常人打完一局也就 30、40 秒，作为机器人，这打完居然要 1 分多钟，真是弱智机器人
尝试将命令写入一个 sh 文件，然后通过 adb shell 执行批处理文件，稍微快了一点点，但是依然还需要几十秒（在此之前还尝试写一个堡垒 app 来一次性接收坐标，然后再 android 系统中执行命令，都木有用）。然后优化分析算法的动力都木有了
不过话说回来，跟女票打游戏，还要用赢的么？
感兴趣加微勾搭：facemagic2014
