簡要概述

網(wǎng)上已經(jīng)有很多Python實現(xiàn)的跳一跳輔助程序，有基于模版匹配的呛伴，還有基于深度學習端到端的方法勃痴，都很厲害。但是沒有一種算法和我自己想的一樣：尋找一行上與背景不一樣的像素热康，找出其最值沛申，當最值連續(xù)不變化三次時，即認為找到了中心點的y坐標姐军，而x坐標選擇第一行存在于背景色不一致的像素x值得平均值铁材。 所以自己寫代碼把想法實現(xiàn)了出來尖淘。
主要的算法如下：
1 使用模版匹配尋找棋子的位置
2 根據(jù)棋子坐標截取籃框部分用以識別嚇一跳的中心坐標
3 用Cython實現(xiàn)的子程序識別籃筐部分的中心：x坐標為第一行存在于背景色不一致的像素x值得平均值， y坐標為連續(xù)三次與背景色顏色不一致像素x坐標的最值不產(chǎn)生變化時的y值著觉；在尋找中心時村生，兼顧尋找RGB=(245, 245, 245)的像素區(qū)域中心，用以糾正識別誤差固惯；如圖中Out所示梆造。
4 最后根據(jù)識別的棋子和塊中心計算出像素距離，計算跳躍時間葬毫；跳躍時間先是使用簡單的線性模型镇辉，然后不斷地記錄調到正中心的距離和時間，最后使用KNN算法給出下一跳的時間贴捡。

識別過程示意

Code

首先是Cython寫的像素級訪問函數(shù)忽肛，文件名為fastLocation.pyx，注意后綴是.pyx而非py烂斋。

import numpy as np
cimport numpy as np
cimport cython

DTYPE = np.uint8
ctypedef np.uint8_t DTYPE_t


cdef unsigned char absSub(unsigned char v1, unsigned char v2):
    return v1-v2 if v1>v2 else v2-v1

@cython.boundscheck(False)
@cython.wraparound(False)
def chessDetect(np.ndarray[DTYPE_t, ndim=3] image):
    cdef int height, width, i, j, xmin, xmax, prexmin=0, prexmax=0, x, y, rcount=0, lcount=0, xcount = 0, xsum=0,whitex=0, whitey = 0, whitecount=0, ai, aj
    cdef bint Foundx=False, Foundxmin
    cdef unsigned int diff
    height = image.shape[0]
    width = image.shape[1]
    cdef np.ndarray[DTYPE_t, ndim=2] out = np.zeros([height, width], dtype=DTYPE)
    cdef np.ndarray[DTYPE_t, ndim=1] backgroundColor, t
    backgroundColor = image[0, 0]
    for i in range(height):
        xmin = 0
        xmax = 0
        Foundxmin = False
        for j in range(1, width):
            t = image[i, j]
            if t[0] == 245 and t[1] == 245 and t[2] == 245:
                whitex += j
                whitey += i
                whitecount += 1
            diff = absSub(t[0], backgroundColor[0]) + absSub(t[1], backgroundColor[1]) + absSub(t[2], backgroundColor[2])
            if diff > 30:
                out[i, j] = 255
                if not Foundx:
                    xsum += j
                    xcount += 1
                if not Foundxmin:
                    xmin = j
                    Foundxmin = True
                xmax = j
        if xcount != 0:
            x = xsum // xcount
            Foundx = True
        if (xmin == prexmin or xmax == prexmax) and Foundx and (xmax-x>50 or x-xmin>50):
            # print(xmax, xmin, xmax-xmin) 
            if xmin == prexmin and xmax == prexmax:
                lcount += 1
            if xmax == prexmax:
                rcount += 1
        if lcount >= 2 or rcount >= 6: 
            y = i
            break
        prexmin = xmin
        prexmax = xmax
    for ai in range(i, min(height, i+20)):
        for aj in range(1, width):
            t = image[ai, aj]
            if t[0] == 245 and t[1] == 245 and t[2] == 245:
                whitex += aj
                whitey += ai
                whitecount += 1
            diff = absSub(t[0], backgroundColor[0]) + absSub(t[1], backgroundColor[1]) + absSub(t[2], backgroundColor[2])
            if diff > 30:
                out[ai, aj] = 255
    if whitecount != 0:
        # print("Here", whitex, whitey, whitecount)
        whitex = int(whitex/whitecount)
        whitey = int(whitey/whitecount)
    return out, x, y, whitex, whitey

關于如何使用Python與numpy交互屹逛，請參閱Cython文檔。然后再同目錄下建立setup.py

from distutils.core import setup, Extension
from Cython.Build import cythonize
import numpy

setup(ext_modules=cythonize("fastGetLocation.pyx"),  include_dirs=[numpy.get_include()])

然后汛骂，在命令行使用

python setup.py build_ext --inplace

編譯Cython生成對應的C代碼和可以被Python調用的庫罕模，這樣Cython的像素級訪問就完成啦。簡單對比一下性能(基于Intel core i7 3630QM)帘瞭，直接使用Python訪問numpy進行處理需要8秒淑掌；使用Cython之后只需要400ms，提速約20倍蝶念；使用C++版本的OpenCV實現(xiàn)抛腕，處理一張圖像僅需20ms。由此可見媒殉，還是C++的速度更快更好担敌。
下面進入主題部分：

# encoding=utf-8
import cv2
import numpy as np
import pandas as pd
from sklearn.neighbors import KNeighborsRegressor
from fastGetLocation import chessDetect
import time
import os
import glob

class AutoJumper():

    def __init__(self):
        self.player = cv2.imread("player.jpg")
        if self.player is None:
            print("player.jpg lost, exiting...")
            exit(0)
        self.player_height, self.player_width, _ = self.player.shape
        self.screen_width, self.screen_height = 1080, 1920
        self.player_bias = 40 # 減去棋子寬度，縮小檢測范圍
        self.BEGIN_Y = 540 # 檢索開始行
        self.delayTime = 1000
        self.debug = False
        self.paths = glob.glob(".\\backup\*.png")

        cv2.namedWindow("Auto_Jump^_^", 0)

        self.count, self.predistance, self.pretime = 0, 0, 0

        data = pd.read_csv("data.csv")
        print("%d pre data loaded!" % len(data))
        if len(data) > 500:
            data = data[len(data)-500:len(data)]
        reg_X = data['distance'].values.reshape(-1, 1)
        reg_y = data['time']
        self.knnreg = KNeighborsRegressor(n_neighbors=2).fit(reg_X, reg_y)

        # Running Parameter
        self.player_x, self.player_y = 0, 0
        self.chess_x, self.chess_y = 0, 0
        self.count = 0
        self.predistance, self.pretime = 0, 0
        self.currdistance, self.currtime = 0, 0
        self.jumpRight = False #恰好調到中央Flag

    def get_screenshot(self, id):
        os.system('adb shell screencap -p /sdcard/%s.png' % str(id))
        os.system('adb pull /sdcard/%s.png .' % str(id))


    def makeJump(self):
        press_x = int(320 + np.random.randint(20))    
        press_y = int(410 + np.random.randint(20))
        cmd = 'adb shell input swipe %d %d %d %d ' % (press_x, press_y, press_x, press_y) + str(self.currtime)
        os.system(cmd)

    def detectPlayer(self):
        res1 = cv2.matchTemplate(self.image, self.player, cv2.TM_CCOEFF_NORMED)
        min_val1, max_val1, min_loc1, max_loc1 = cv2.minMaxLoc(res1)
        top_left = max_loc1
        bottom_right = (top_left[0] + self.player_width//2, top_left[1] + self.player_height) 
        cv2.circle(self.image, bottom_right, 10, 255, 10)
        self.player_x, self.player_y = bottom_right

    def detectChess(self):
        if self.player_x >= self.screen_width/2:
            startx, endx, starty, endy = 0, max(self.player_x-self.player_bias, 10), self.BEGIN_Y, self.player_y
        else:
            startx, endx, starty, endy = self.player_x+self.player_bias, self.screen_width, self.BEGIN_Y, self.player_y
        out, x, y, whitex, whitey = chessDetect(self.image[starty:endy, startx:endx])
        cv2.rectangle(self.image, (startx, starty), (endx, endy), 255, 10)
        cv2.circle(self.image, (whitex+startx, whitey+starty), 20, (0, 255, 0), 10)
        cv2.circle(self.image, (x+startx, y+starty), 10, (0, 0, 255), 10)
        # if self.count % 5 != 0:
        #     y = self.player_y - abs(x-self.player_x)*1.732/3
        if abs(x-whitex) + abs(y-whitey) < 30:
            x = whitex
            y = whitey
            self.jumpRight = True
        self.chess_x, self.chess_y = x+startx, y+starty

    def calDistanceAndTime(self):
        self.currdistance = np.sqrt((self.chess_x-self.player_x)**2+(self.chess_y-self.player_y)**2)
        self.currtime = int(self.knnreg.predict(self.currdistance))

    def showImage(self):
        cv2.imshow("Auto_Jump^_^", self.image)
        if cv2.waitKey(self.delayTime) & 0xFF == 27:
            print("Ese key pressed, exiting")
            exit(0)
    def parameterUpdate(self):
        self.count += 1
        self.predistance, self.pretime = self.currdistance, self.currtime
        if self.jumpRight:
            f = open("data.csv", 'a')
            print("Writing log: (%f, %d)" % (self.predistance, self.pretime))
            f.write("%f,%d\n" % (self.predistance, self.pretime))
            f.close()
        self.jumpRight = False

    def jump(self):
        t = time.time()
        self.get_screenshot(0)
        if self.debug:
            self.image = cv2.imread(self.paths[self.count])
            self.delayTime = 0
        else:
            self.image = cv2.imread("0.png")
        self.detectPlayer()
        self.detectChess()
        self.calDistanceAndTime()
        self.makeJump()
        self.showImage()
        self.parameterUpdate()
        print("\nStep %d:" % self.count, time.time()-t)

if __name__ == '__main__':
    jumper = AutoJumper()
    while True:
        jumper.jump()

主體部分的代碼和其他作者的代碼大同小異廷蓉，所以沒怎么寫注釋全封。這里使用了KNN算法去計算距離，并且在收集數(shù)據(jù)較多時苦酱，只取后500項數(shù)據(jù)進行訓練，理論上具有一定的自學習能力疫萤。

距離時間模型

根據(jù)我自己手機的數(shù)據(jù)（小米Note標準版）敢伸，繪制成一下時間距離圖像，橫軸為像素距離，縱軸為跳躍時間钓丰。

距離-時間圖像

從圖中可以看出，距離時間大體上呈線性關系携丁，但是在兩端具有截面效應，而且由于高距離的樣本偏少梦鉴，會導致距離較遠時跳躍時間樣本不足，從而導致并不能一直跳在中心肥橙。

不足

其實我一直想實現(xiàn)能夠一直調到正中心的算法，但是后來發(fā)現(xiàn)這個目標比較難秸侣。此算法目前達到的最高分是1538分。

最高分