人人都能看懂的「跳一跳」平民演算法

01-25

跨年夜的時候，在家裡沒事幹，為了陪孩子玩，寫了個 python 腳本，自動玩微信「跳一跳」。後來又完善了一下，目前未發現會跳不中的情況，且大約90%的幾率跳到中心。

我今天在知乎上一搜，發現還挺多朋友寫這類程序的。相比之下，我覺得我用的演算法原理非常簡單，我稱之為平民演算法，不需要什麼計算機圖形學知識，所以在這裡寫一下供大家娛樂！

代碼發布在這兒：

liuben/weixinhopgithub.com

1 基本想法

電腦通過 adb 可以連上Android手機，然後截屏並拖回電腦以供電腦分析。然後電腦也可以通過 adb 控制觸摸 Android 手機的時間。從而為寫程序自動玩遊戲提供了可能。

要自動玩遊戲，無外乎3點：

算出目標點的坐標
算出起點的坐標
計算出跳躍距離，進而計算出觸摸時間

2 目標點分析

首先背景色是比較固定的（從上到下有微小變化），和物體有較大色差，所以定義一個兩點顏色差距的函數。這個在計算機圖形學上有專門的公式，但我覺得沒必要，直接寫了個最簡單的，就是將兩個像素的 RGB 分別相減的絕對值再加起來，就夠用了。如下所示：

r = start[0]-cur[0]g = start[1]-cur[1]b = start[2]-cur[2]distance = abs(r) + abs(g) + abs(b)

目標點自然是目標物體頂面的中心。

注意到目標正方體頂面最上方的點和最右側的點，分別對應目標點的x坐標和y坐標，所以如果能找出這兩個點的坐標就好了。

先找頂點坐標：跳過記分牌之後，從上往下搜索第一個跟背景色差別較大的點即可。

關於頂點坐標有兩個特殊情況：

第一，目標物體頂部為圓形。放大了看，會發現頂部有連續的若干個點。所以，實際演算法中在從上往下，從右往左搜到第一個色差很大的點之後，會繼續向左搜索連續的色差很大的點，最後取這一線段的中點，作為頂點。

第二，會有頂點低於棋子的情況，導致從上而下搜索時，先遇到了棋子的頭部。為了規避這種情況的干擾，我從棋子頭部取了一個特徵點，然後在頂點檢索時，在檢測到一個和背景色色差較大的點之後，和棋子的特徵點計算色差，如果色差很小，則認為進入了棋子頭部，然後跳過這個點及其周圍一定範圍的像素。

搞定頂點，再來搞右側點。

順著頂點向右下方檢索和背景色色差較大的點。什麼時候時候找到一個點，它下方那一行沒有比它更靠右的大色差點，就說明這個點是最右側點了。

右側點有一個特殊情況，也是圓形。在放大了看時，會發現圓形在邊緣會出現垂直的至多5個像素，然後繼續往外側走。

為了涵蓋這種情況，又避免和正方體這種右側點下面有很長的垂直線的情況相區分。實際演算法在從頂點搜索右側點時，每次循環都將y坐標加1，然後x坐標同上一行，開始向右搜索大色差點。如果這一行的最右側點，比上一行的最右側點，更靠右，則這一行成為候選；如果這一行的最右側點和上一行x坐標完全一樣，則上一行仍然是候選，開始計數並進入下一行，如果這種情況連續超過5行（即計數超過5），則候選行即是最右側點所在行。

有兩種特殊情況，目前的演算法會在計算最右側點時出現誤差：分別是杯子的情況，和最右側點被棋子遮擋的情況。

這兩種情況會跳不到中心，但也不至於掉下去。所以，我就沒有再進一步處理了。

3 起點分析

注意到棋子的顏色在遊戲中是唯一的，不過棋子在不同位置會有一點變化。所以，我先從棋子中根據其中心所在位置，截取了一幅特徵圖如下：

然後在畫面中，搜索和這個區域色差最小的區域，即可算出起點的坐標。

兩個區域的色差也很容易算，就是把源區域和特徵區域的點挨個算色差（按上面定義的簡單公式）再加起來就好了。

實際計算中為了減小計算量，會縮小檢索區域，比如起點肯定在目標點的下方。再把屏幕分成左右兩側，那麼起點肯定和目標點不在同一側屏幕中。另外如果一點和特徵圖的色差很大，就沒必要算整個區域的色差了。

目前看來，這種演算法準確率很高。

4 觸摸時間計算

首先要拿到一個標準距離下，能夠跳到中心的完美時間。這需要做一下實驗。

我的腳本開發了調試模式，可以從命令行控制進行截圖、分析、跳躍之一。可用於實驗獲得這個參數。

注意到，每次遊戲啟動時，第一步的跳遠距離是固定的。

所以，就在這一步反覆實驗跳躍時間就好了。

只要試出來一個就好，其他的距離程序都可以按照比例計算。

注意，一個距離要完美跳躍，觸摸時間在一個區間內都是可以的，建議選擇這個區間的中間值，以減少計算別的距離時的誤差。

5 總結

至此，演算法介紹完畢。不需要什麼多的知識，基本上會寫程序就能看懂吧，哈哈！整個演算法的時間複雜度如果以圖片的像素數量來衡量的話是 O(n)，應該是相當可以了。

這個腳本用Python開發，使用了 Pillow 庫。美中不足是計算時間較長，每一步需要計算6、7秒吧。我看 Pillow 庫的文檔裡面寫了按像素遍歷圖片的性能不佳，我程序也沒有在提高性能上做太多工作，所以目前也就這樣了。

以上純屬自娛自樂，做完後給小孩看了看，小孩表示很神奇，哈哈！