如何叉着腰喝着茶穿越福城？

概述

春节快到了，于是新版QQ多了福袋这么个玩意儿，获取福袋的方法很简单就是玩小游戏。当然这篇文章不是记录如何刷福袋的(雾)，而是穿越福城这个小游戏和微信跳一跳很相似，但又有不同之处，所以身为爱折腾人士怎么可能放过此游戏？像这种游戏看着它玩远比你自己玩有意思多了。

Title

一、游戏分析

1.游戏玩法

游戏玩法很简单，和微信跳一跳完全没区别，只要按住屏幕，小企鹅前面就会伸出一根梯子，按的时间越长梯子也越长，放开之后梯子就会向下一个格子下落，落到越靠近方块中心得分越高。如果梯子的长度没有达到下一层，或者是超过了下一层，那么不得分，并且游戏判定结束。

2.得分机制

按住屏幕一定时间后放开，使得梯子落下后边缘尽可能靠近中心，最外层得一分，中间层得两分，中心块得三分，各层之间用颜色来区分。

Title

特别的，如果连续拿到中心块的话，所得分数将是上一次得分累计加三分，即用$k$代表连续拿到中心块的次数，那么第$k$次所获得的分数$C_k$可以表示为：

$\begin{equation} C_k=3k (k=1,2,...) \end{equation}$

这一机制也就使得，短时间内获得高分的需求将不是尽可能多的击中中心块，而是尽可能多的连击中心块。

二、机机交互

我们的目的是叉着腰喝着茶穿越福城，所以就需要电脑自动帮我们玩，然而手机肯定是不会自己玩的，我们需要在电脑上编写程序，进而通过程序来获取手机数据并控制手机，这是机器与机器之间的交互，简称机机交互。

机机交互我选择adb大法，可是要求手机是安卓系统，这就苦逼了，家里翻来翻去都没有安卓系统的设备，这可咋办呢？

没关系我们还有模拟器啊，不慌不慌，打开MUMU，开启模拟器的USB调试后

1	adb connect 127.0.0.1:7555

正常连接，这可又苦逼了，使用模拟器竟然进不去这个游戏？？这只企鹅是魔鬼吧，这可咋办呢？好在我又翻来翻去，终于，还是找到了一台CentOS系统的手机，看上去颇具年代感，不过也够用了。

首先进入手机设置，将开发者模式打开，并且打开USB调试功能，随后用数据线将手机与电脑连接起来，在手机上授权所连接的电脑进行调试就可以了。在控制台中可以看到我们的手机设备已经Attached，并且状态正常。

ADB连接

如果显示设备offline，那么请检查：

是不是线松了/…（紧一紧插口或者重连）
手机端是否打开了USB调试（若没有则打开重连）
手机端是否对所连接的电脑授权同意了（若没有则重连确认授权）

如果以上两条都没问题，那么请尝试：

重启ADB服务

1
2
3

adb kill-server
adb start-server
adb devices

断开连接，重启手机、电脑，重新连接
换用更高版本的ADB

连接成功后，我们就可以写点代码测试一下效果了：

#include <iostream>
int main()
{
	system("adb shell input tap 100 100");
	return 0;
}

也可以直接在控制台进行测试，下面是一些基本操作的adb指令：

点击屏幕$(x,y)$

1	adb shell input tap x y

滑动屏幕$(x_1,y_1) \rightarrow (x_2,y_2)$，总时长$t$毫秒

1	adb shell input swipe x1 y1 x2 y2 t

长按屏幕$(x,y)$处$t$毫秒

1	adb shell input swipe x y x y t

三、原理分析

1.基本原理

游戏本身只有一个输入操作，就是长按屏幕，对应的也就只有一个输入变量，即长按时间。而玩家控制按压时间的长短则是依靠小企鹅和目标块之间的距离来判断的，距离越长所需的按压时间也越长，距离越短所需的按压时间也越短。正如$3Blue1Brown$所说，在解决问题的过程中取名字总是喜闻乐见的，我们就将长按时间取名叫做$HoldTime$，小企鹅与中心块之间的距离叫做$Distance$，按压得到的梯子长度叫做$Length$，直观上看很容易得出结论：

$\begin{equation} HoldTime \propto Length \end{equation}$ $\begin{equation} HoldTime \propto Distance \end{equation}$

但事实真的如此吗？我记录了一些三分情况下的$Distance$与$HoldTime$数据，并做出散点图

Title

发现两者之间并不存在明确的线性关系，甚至好像毫无关系，但无论如何，$Distance$在直观上与$HoldTime$是必然存在线性或近似线性的关系的，因此我选择认为他们是线性关系，只是还有其他量影响着我们的长按时间，将本身的线性扭曲了，因此下面关于$Distance$的内容均以线性讨论，校正的内容在$3.2$中进行探讨。

其实说白了，我们需要做的就是找出$Distance$与$HoldTime$之间的函数关系$H(d)$，使得按照$Distance$计算出的按压时长$H(d)$得到的梯长$Length$与$Distance$自身的差值$\delta$尽可能小，即

$\begin{equation} min \delta = min\{|L(H(d))-d|\} \end{equation}$

但是$Distance$本身并没有绝对标准的数据来源，这个指标$\delta$我们大可直接以可视的得分情况来代替，得三分说明$\delta$足够小，得两分说明$\delta$大小一般，得一分或不得分就说明$\delta$偏大了，我们进而可以引入更高一层的判别指标来对$H(d)$做出更具整体性的评价：

定义计算$n$次$H(d)$，得$m$分的次数为$C_m$，则有$n$轮中心命中概率

$\begin{equation} P(n)=\frac{1}{n}\Sigma_{m=3}^{+\infty}C_m \end{equation}$

此时问题转化为了：寻找一个函数$H(d)$，使得依照此函数进行游戏满足

$\begin{equation} lim_{n \rightarrow + \infty}\frac{1}{n}\Sigma_{m=3}^{+\infty}C_m=1 \end{equation}$

2.计算原理

在实际操作的过程中，你会发现需要考虑的量并不仅仅只有$Distance$而已，由于缩放特性的存在，像素世界里距离的定义永远是相对的，同样是$200px$在不同的缩放参数下所表示的距离可能相差很大，例如在本文的封面图中，我们可以测量出小企鹅底部到目标中心点的最小包围矩形宽度$300px$，高度$173px$，距离大致是$245px$，而在下图中，小企鹅到中心点的距离大致是$167px$，可是下图的距离显然比封面图的距离要远，但像素层面的距离却更短，这就是全局缩放所导致的。

Title

为了知晓缩放程度，我们可以选择常量——企鹅自身高度作为参照依据，企鹅在屏幕上显示的高度记作$HeightPlayer$，$HeightPlayer$越小，说明全局缩放程度越大，更准确的说是全局缩小的程度越大。
可以选择找出$HeightPlayer$与缩放比例之间的关系，进而矫正$Distance$为$d’$并继续使用原来的函数$H(d’)$计算长按时间，也可以选择直接将$HeightPlayer$也纳为影响按压时间的客观变量，修改得到新的二元函数$H(d,h)$，这里我选择了第二种方式。

如果你想要采用第一种方式的话，即寻找校正函数来修正被缩放的$Distance$，你可能需要记录一些数据来检视$Height$与$HoldTime$之间的数学关系以避免盲目的尝试，虽然我选的第二种方式，但依旧做了一下这方面的测试，下面的内容可供参考。

Title

做出$Height$与$HoldTime$的散点图，可以看到两者之间呈现出二次函数的关系，通过二次函数拟合，得到了可观的$R-squre$与$SSE$，所以如果你想尝试矫正$Distance$，那么你可能需要从形如下式的函数入手

$\begin{equation} D'(d,h)=(h-c_1)^2d+c_2 \end{equation}$

这里不给出所求得的$c_1$与$c_2$的具体数值，因为不同的设备有不同的分辨率，参数的具体值是没有意义的，后文有给出部分计算数据，如果你尝试直接套用的话，可能不会得到理想的效果。

3.数据获取原理

由上面的原理不难知道，为了计算长按时间，我们需要的数据无非就是企鹅高度和距中心点的距离，这两个数据通过简单的图像分析和简单的计算不难得到。
首先中心块的颜色集合与企鹅的颜色集合是固定的，通过

1 2	adb shell screencap -p /sdcard/screen.png adb pull /sdcard/screen.png

得到屏幕图像后，逐像素点扫描，检查是否满足中心块/企鹅颜色即可。

这个过程可以用数学模型更清晰的表述出来，下面给出寻找中心块与企鹅，以及企鹅高度计算的数学描述。

假设中心块的颜色集合为三元组

$\begin{equation} RGB_t=\{(r_1,g_1,b_1),(r_2,g_2,b_2),...,(r_m,g_m,b_m)\} \end{equation}$

企鹅身体的颜色集合为三元组

$\begin{equation} RGB_b=\{(r_1,g_1,b_1),(r_2,g_2,b_2),...,(r_n,g_n,b_n)\} \end{equation}$

指定扫描区域的红黄蓝三原色数据被分别存放在二维数组$R[i][j]$、$G[i][j]$、$B[i][j]$中，定义函数

$\begin{equation} Exist(r,g,b,A)=\left\{ \begin{array}{rcl} 1 & & {(r,g,b) \in A}\\ 0 & & {(r,g,b) \notin A} \end{array} \right. \end{equation}$

当某点$(x,y)$满足

$\begin{equation} Exist(R[x][y],G[x][y],B[x][y],RGB_t) = 1 \end{equation}$

认为该点落在目标中心块中，在所有满足该式的点集中取$y$最小的那对坐标$(x1,y{min})$即是中心块的顶点，取$y$最大的那对坐标$(x2,y{max})$即是中心块的底点，$(\frac{x1+x_2}{2},\frac{y{min}+y_{max}}{2})$即是中心点坐标；

当某点$(x,y)$满足

$\begin{equation} Exist(R[x][y],G[x][y],B[x][y],RGB_b) = 1 \end{equation}$

认为该点落在企鹅身体中，在所有满足该式的点集中取$y$最小的那对坐标$(x1,y{min})$即是企鹅的顶点，取$y$最大的那对坐标$(x2,y{max})$即是企鹅的底点，易得企鹅的高度

$\begin{equation} HeightPlayer=y_{max}-y_{min} \end{equation}$

Title

最后提一点，全屏扫描肯定是低效的，为了提高检测效率，在实际编码时最好截取屏幕固定的矩形区域，例如上图这样的区域，再进行扫描以节省时间。

四、算算看吧

其实很显然$H(d,h)$应该就是简单的线性组合$k_1d+k_2h$，可以直接通过一定一动结合二分法将$k_1$与$k_2$的值手动调出个八九不离十，但我实在是懒…所以直接无脑记录$60$次命中中心情况下的$d$、$h$数据进行多元函数拟合了。但是注意，这样做是有弊端的，为了得到尽可能好的拟合效果，得到较高的均方根方与低$SSE$，往往忍不住用高次拟合，而最终损失的是算法的鲁棒性。
最后得到的拟合函数：

$\begin{equation} H(d,h) = p_{00} + p_{10}d + p_{01}h + p_{20}d^2 + p_{11}dh + p_{02}h^2 \end{equation}$

下列系数均略写了$95\%$的置信区间：

$\begin {array}{r|r|r|r|r|r} \hline p_{00} & p_{10} & p_{01} & p_{20} & p_{11} & p_{02} \\ \hline 1311 & 8.71 & -63.91 & -0.0101 & -0.02503 & 0.5314 \\ \hline \end {array}$

拟合图像你要是这样看的话没啥用：

Title