一造寝、絕地反擊
最近女票迷上了某平臺的連連看對戰(zhàn)小游戲家妆，于是免不了要找哥哥我 PK 一翻，雖然是被迫卷入戰(zhàn)爭簸呈，但是以朕驚世駭俗的智商榕订，那當然是勝券在握啦~~
沒曾想，幾個回合下來蜕便，竟被啪啪啪打臉劫恒，快把這個月的口糧都輸光了（每把5塊錢啊，肉疼Ｍ嫒埂＜婷场）
哎，完全拼手速是沒有希望的了吃溅，得想辦法讓連連看自動打
“連連看”都不會打的直男們溶诞，趕緊去懟一局
二、可行性
前段時間跳一跳火起來的時候决侈，有人就通過 adb 截屏并發(fā)送到電腦分析螺垢，再求得距離然后計算出按鍵時長，最后通過 adb shell 自動按鍵赖歌，從而獲得完美跳跳分枉圃，這一招用在連連看是否管用呢？
理論上庐冯，靠譜孽亲，分解如下：
- adb 截圖傳到電腦
- 將連連看的點擊區(qū)域識別為一個二維矩陣，每一種小動物用一個數(shù)字表示
- 對二維矩陣求解展父，計算出每個位置的點擊順序數(shù)組
- 通過 adb shell 一把梭返劲，一次性點掉所有
醬紫如果順利的話并且不被女票發(fā)現(xiàn)，贏回三個月的口糧都很有希望呀~~
三栖茉、實施步驟
技術(shù)選型
從上一節(jié)的分析來看篮绿，方案的實施涉及到很多圖片的分析處理，Python 可以方便的調(diào)用很多圖片庫吕漂，而且網(wǎng)上也有很多作業(yè)可以抄亲配，所以選擇基于 Python 來做
環(huán)境搭建
沒有很具體的安裝步驟，需要的咨詢谷歌哥
1） 安裝 adb 環(huán)境惶凝。安裝完成后吼虎，用數(shù)據(jù)線連接一臺 android 手機，執(zhí)行一些簡單的 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 和相關(guān)的圖片庫苍鲜，在安裝 openCv 的時候還踩了個大坑思灰，記錄了下，僅供參考
圖片處理
1）截屏保存
在終端坡贺，執(zhí)行如上的兩個 adb 命令就可以截屏保存了官辈，也就是說箱舞，這里需要一個可以調(diào)用終端命令，同時可以等待返回的 Python 方法：
// 執(zhí)行終端命令的方法
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）裁剪有效區(qū)域拳亿、再等比切出小動物頭像
如果不要求很通用只是對你的手機有效的話晴股，那么只需要將第一步截下來的屏幕用工具來量一量（如 Mark Man)，就可以用如下方式裁剪出有效區(qū)域
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")
# 有效點擊區(qū)域裁剪 (不通用的做法是肺魁，把這個矩形的坐標量出來)
gx = 43
gy = 401
gw = 993
gh = 1420
cut(Image.open("./screenshot/screenshot.png"), gx, gy, gw, gh, 'main')
如果要做得通用一些电湘，就需要計算圖片的比例了（只用于打敗女票的，完全沒必要嘛）
然后再按照10行7列切成小塊鹅经，并且根據(jù)二維數(shù)組的下標命名
# -*-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]
3）解析小動物頭像輸出數(shù)字二維矩陣（第一回合）
這一步著實需要下功夫寂呛，還踩了不少坑~~
首先想到的是通過求解圖片的 hash 值，利用 hash 值來比對圖片的相似度（例如感知 hash 算法）瘾晃。網(wǎng)上有各種求 hash 值的算法贷痪，實現(xiàn)起來倒也簡單，但是蹦误，比較的正確率只能達到百分之七劫拢、八十（這樣我們分析出的點擊路徑，肯定打不過啦Ｇ恳取舱沧！），主要是這些小動物頭像在 hash 算法下顯得都太相似了偶洋，拿感知哈希算法來說：
a) 縮小圖片尺寸
b) 轉(zhuǎn)為灰度圖片
c) 計算灰度平均值
d) 比較像素的灰度
e) 計算哈希值
f) 對比圖片指紋
想象一下熟吏，上面的小豬頭和小猴頭經(jīng)過如上的變換后，還有多少差異呢玄窝？
轉(zhuǎn)念一想牵寺，這個問題在機器學習領(lǐng)域，不過是那種最最簡單的分類問題哆料，so缸剪，完全可以先訓練一個模型出來
4）解析小動物頭像輸出數(shù)字二維矩陣（第一回合）
Turicreate 是蘋果開源的基于 python 機器學習框架吗铐，特點是輕量（只是分類相似的圖片而已东亦，當然是越簡單越好），先安裝之
然后將上面寫好的截屏裁剪代碼多執(zhí)行幾次唬渗，手工分類典阵，準備好訓練數(shù)據(jù)：
給每種小動物創(chuàng)建一個文件夾，再將所有該種類的動物裝進去
開始訓練镊逝，并保存模型：
#!/usr/bin/env python
#encoding=utf-8
import turicreate as tc
img_folder = 'data'
// 導入數(shù)據(jù)
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')
// 百分之八十的數(shù)據(jù)用于訓練壮啊，百分之二十用于測試
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)
// 輸出測試結(jié)果
print(metrics['accuracy'])
model.save('my_model_file')
執(zhí)行到倒數(shù)第二行的時候，順利輸出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) 兩種直接存在一條通路玄渗，它是一條只經(jīng)過沒有圖案的地方、且轉(zhuǎn)折點不超過2個的折線
具體代碼實現(xiàn)可以看看這篇博文的分析（雖然是 C 版）狸眼，這里我就不貼了藤树，繁瑣占篇幅
2） 搜索路徑，最簡單粗暴的一種做法
（1）從矩陣中挑出一個未被標記為刪除的元素拓萌，（2）再從矩陣中余下的不被標記刪除的元素尋找一個跟它一樣的元素岁钓，判斷是否可以相連，是則將兩個元素標記為刪除微王，并將點擊坐標壓入坐標數(shù)組屡限，否則重復（2），（3）重復（1）炕倘，知道找到所有的點擊坐標點
但是這種做法是 O(nXn)钧大，很遺憾，暫時也沒有想到更好的辦法罩旋，只是想到了一個小小的優(yōu)化策略拓型，開始先遍歷一輪，將所有挨著的相同圖標消掉（顯而易見的事情當然要先辦啦）瘸恼，減小 N劣挫，節(jié)省一下算法的時間
然后在“盲狙”的過程中，因為循環(huán)停止的條件是找到所有的坐標點东帅，假如游戲給了個無解的矩陣压固，或者咱們圖片識別錯了導致無解，就會陷入死循環(huán)（雖然這樣的概率極低靠闭，沒遇到過）帐我，所以要做一下循環(huá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 也即所有的坐標都找到即停止
// 否則也最多循環(huán)十次
count = 0
while (len(pos) < 70 and count < 10):
count = count + 1
commonBuild()
print(count)
很幸運，經(jīng)過優(yōu)化后的算法愧膀，基本上每次 count 都輸出為 1拦键，不需要遍歷太多次。假如真的出現(xiàn)了無解矩陣檩淋，循環(huán)了 10 次退出了芬为，那該如何是好呢？這個時候自己將機器沒有打完的點掉也應該沒有難度了
adb 一把梭
克服艱難險阻把坐標數(shù)組計算出來之后蟀悦，后面的事情就簡單了媚朦，執(zhí)行 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 命令的執(zhí)行間隔基本差不多要到 1 秒份氧，逐條執(zhí)行完之后黃花菜都涼了唯袄，要知道正常人打完一局也就 30、40 秒蜗帜，作為機器人越妈，這打完居然要 1 分多鐘，真是弱智機器人
嘗試將命令寫入一個 sh 文件钮糖，然后通過 adb shell 執(zhí)行批處理文件梅掠，稍微快了一點點，但是依然還需要幾十秒（在此之前還嘗試寫一個堡壘 app 來一次性接收坐標店归，然后再 android 系統(tǒng)中執(zhí)行命令阎抒，都木有用）。然后優(yōu)化分析算法的動力都木有了
不過話說回來消痛，跟女票打游戲且叁，還要用贏的么？
