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

发表于 更新于 Disqus：

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

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

为了方便处理，把每一块（按照在完成图上的位置）编上号，如此以后，问题就变成了：

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* 算法解决。其中启发函数 设为当前状态中 除[15]之外的所有块，离它正确位置的曼哈顿距离，可以证明这个值总是不大于真实的剩余步数，所以一定能找到最优解。

实际上，为了加快计算速度，把 乘个 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, 我真是太无聊了……