【屠龙之技终有用】战棋辅助工具的实现
更新时间2019/10/165216 浏览综合
10.13 就一些问题作出必要说明：
Q1：这属于外挂吗？
A1：我认为不是，没有修改数据也没有自动操作，本质上是截图并分析图片，而已。
Q2：Over Power吗？
A2：并不，很多大佬的实力可能超乎你们的想象。如果程序本身没有太大问题，35波的平均消除就是稳定在38左右，@嫑逝 大佬的均消41可以说是到了匪夷所思的境地了。程序胜过人很多吗？这未免太低估人的智慧了。
Q3：会发布吗？
A3：暂时不会，程序本身存在许多问题，比如识别失败和错误的问题。其次，这个工具会造成不公平吗？我不清楚，尚需考量。
====================
实际上一步（一次交换或一次拖出）的消除过程是这样的：
交换：交换怪物位置 -> 消除于交换点处 -> ①下落 -> ②补充 -> ③一般消除 -> 如③进行则跳转至①
拖出：拖出怪物 -> ①下落 -> ②补充 -> ③一般消除 -> 如③进行则跳转至①
既然③的规则已经明确，只有②补充的规则尚待讨论。在没有石头和特殊边界干扰的情况下（如有，情况会变得较复杂，我不大清楚为什么这样设计，甚至认为这可能是一个不明显的bug），补充规则为从下到上从左到右依次补充，在消除王和解谜中具有一个确定的补充队列，而其它模式中，我们最常熟知的是秘境可以通过返回来刷掉落，因此推测一般的消除队列为随机生成无限队列的而非一个固定的循环队列。因此，我们并不能预知一个确切的结果，而可以获得一个统计结果。最有价值的统计参数当然是期望或者说平均值。
为什么选择战棋呢？因为战棋是单步的，我们只需使用暴力方法，穷举所有可消除的操作，并获得对应的形态经验/消除数的均值，取最大者，就能知道应该如何消除。那么，如何实现呢？
0.实现一个召唤与合成（核心部分）
没错，首先我们要做一个程序来模拟召唤与合成，能指定沙盘怪物，能够进行正常的交换、拖出过程并给出消除数。在已知消除规则的情况下，这一步并不难，只是一个体力活。
1.获取沙盘
手动录入当然是一个可选项，但是可能眼瞎……尤其是有野蛮人和886之后……（而且慢）
1.1 获取画面
因为我只会c++，这一过程需要在Windows上进行，操作目标是一个安卓模拟器或投屏软件，获得这一窗口的画面可以使用winapi，具体过程不赘述，总之是以窗口名搜索对应句柄，以句柄获得BITMAP，由于下一步仍需处理，以一个cv::Mat来存储数据。
这一图像是包含边框的，不过边框宽度一般恒定，裁掉即可。
1.2 图像分析
模板匹配可能太慢，而且需要预先有大量模板，故采用特征检测的方式——检测沙盘上的格子的位置，当然先提取边缘（canny），然后检测矩形吗？或许还是偏慢，个人实现起来需要1s左右，干脆先统计各行各列中边缘像素的数量从而得到可能的格子边缘所处的行、列，然后去匹配出格数和最左上角的格子的坐标，这样就能根据坐标截取每一格内部的图像。速度可以提高到100ms左右。
这里需要用到的数据是，画面高h，沙盘为n*n，则每格间距为精确的floor(0.9*h/n)，其中边框约为floor(0.9*h/n)/10。
1.3 获取沙盘怪物
从第一格起，将后续格子中的图像与其对比，使用L2范数作为衡量相似度的指标，相似则认为是同一种怪物，进行同种标记，直到棋盘中的怪物都被标记。
2.最优策略
获取沙盘后，当然穷举就行了，问题在于补充的不确定性，要随机多少次取均值呢？目前采用的方法是连续十次均值波动不超过0.1时，认为这一均值可以代表消除数的期望。
每隔一段时间（0.5s）获取一次画面并获取沙盘，如果检测成功且与上次不同则给出得到最大平均消除数的操作。
这一思路并不复杂，但是做起来还是挺麻烦的，目前的效果是这样：