给小米商城的拼图游戏写了个外挂

最近小米商城 App 里推出了一个游戏,大概是酱紫的:

左图是游戏初始状态,右图是游戏完成的样子,点左下角的图就能看到。规则是,利用唯一的那个空格移动所有的小块,直到恢复原图。不用担心,缺的一块一定是最后那一块儿,所以你也要保证最后缺口还在右下角的地方。

Puzzle Game

为了方便处理,把每一块(按照在完成图上的位置)编上号,如此以后,问题就变成了:

1
2
3
4
11 8 5 6
10 9 0 4
13 1 2 7
14 12 3 [15]

这样的一个矩阵,只有 [15] 可以和四领域的元素交换。求一个方案,使得若干次交换之后,变成:

1
2
3
4
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 [15]

以上问题用 A 算法解决。其中启发函数 $h(x)$ 设为当前状态中 *除[15]之外的所有块,离它正确位置的曼哈顿距离,可以证明这个值总是不大于真实的剩余步数,所以一定能找到最优解。

实际上,为了加快计算速度,把 $h(x)$ 乘个 2,效果很好。

剩下的细节就比较容易了:

(因为我的 Windows 下有现成的 Android SDK,所以就在windows 下搞了)

  • 用 ADB 命令截图(2张图:拼好前 before.png,拼好后 after.png
1
2
adb shell screencap -p /sdcard/before.png
adb pull /sdcard/before.png before.png
  • 用 Python + PIL 对拼图的每一块做匹配,输出上面的那个矩阵

  • 用 C++ 写个 A 算法(A 算法计算量还挺大的,内存也要省着用)

  • 把输出的 Solution 转化成指令序列(TouchScreen),用 ADB 发给手机

爽!!Awesome!!排行榜上第一名就是我,没错就是哈士奇头像的那个。

附程序:Gist

运行它你需要在当前目录中创建一个名为 adb ,指向 <SDK安装目录>\android-sdk\platform-tools 的符号链接。

P.S.

Well, 我真是太无聊了……