先说下效果，杂色情况下3秒之内消除20个以上圆珠。
1，首先是用安卓模拟器下载安装智龙迷城游戏。
2，固定模拟器的大小和位置，这样游戏启动的时候在屏幕上的位置就是固定的了。方便后续操作。
3，用python的autogui库获取当前鼠标的位置，然后鼠标放到左上角和右下角，查看坐标，并记录下来。（现在已经改成了利用adb截图，截图时间稍长，但是不需要位置固定了）
4，根据上面的位置，就可以判断每一个珠子的算是精确的位置。用autogui模块获取左上角和右下角的确定的矩形区域。
5，接下来是确定每个圆珠的类别。方法有很多，我采用的一个如下：
现在是用的opencv的判断相似度的一个函数，准确度和稳定性较高，但是速度稍慢。
6，类别信息存到一个矩阵种，接下来就是主要的算法。没有太好的思路，所以采用了暴力枚举，因为地图就这么大（当然也有大的，不过速度并不会满多少）。
遍历所有的位置。其中一个位置是A，然后A往四周四个方向走会产生交换当前珠子和下一个珠子，往几个方向走就会产生几个局面，对所有的局面都继续进行同样的操作。最终的目的是为了枚举出所有的路线和结果。用递归的话不好控制流程，可以选择使用手工栈。当然一个圆珠理论上是可以走无限步骤的。这样时间就是无限的了，所以可以有这样的策略，走1步可能性是4种，第二步也是4种，n步的话，总的可能性就是4^n，这样可以走个7，8步，电脑还是承受的住。用一个属性记录当前局面是多少步走过来的，如果超过的话这个局面就不会产生新的局面，算法也会这样终止。
原始的算法是很慢的，遍历每个位置，7，8步能几十秒。这里剔除了一些不必要的走法之后，速度快了很多倍。
比如：
（1）A-B-A走了一步再回来是没有必要的，因为回来之后的情况是处理过的。
（2）相邻的位置是一样的，也就是AB相邻并且AB类型一样，就没必要从A再走到B了，这样走一步产生的局面是会处理的。
（3）*还可以判断产生的局面（包括圆珠和当前圆珠）是否出现过，如果出现过就不进行递归处理了。这个对比比较麻烦没有做。
（4）使用numba或者多线程加速，我用的前者，速度没有 上说的那么夸张，只快了四五倍（用在了判断局势界面）。
产生了所有局面之后，需要写个函数来判断每个局面的得分：算法如下
基本上也是枚举，遍历所有可能能产生三连的位置，判断整个局面有几个三连，进一步可以判断有多少个五连，交叉等等。遇到每种类型就会得相应得分数，可以根据圆珠类型和连接方式确定得分。最终从所有得局面种找一个得分最高的作为最终得最终选择。还可以把能看到的落下的圆珠会得的分也算上（已经加上），这样得到的结果会更真实一些。
另外天上掉下来的圆珠可能也会产生combo，所以总的combo会更多。
7，平均六七个combo，还没有，每次转都认真玩的话还是基本可以达到的。而且人用心玩可以做的更好，关键的原因是人可以走的更远，10+甚至20步+，但是很难一直转注规划等等。机器要走这么多步骤的话，计算量就是天文数字了。
8，产生的最优局面如果是走了10步得到的，程序种每一步的历史记录都记录下来了，并且记录了出发点。这样从出发点，一步步按照历史记录走就可以完成了，矩阵位置和屏幕位置也是很好对应的。还是用autogui进行鼠标的一些点击移动释放等等操作。
9，实验效果：
自动检测屏幕的pad区域，如果每个圆珠都识别成功，代表当前圆珠就位了，然后就执行自动转珠。这样基本不用宠物的主动技能就可以打通一关。解放双手。
Todo list:
识别加强版本圆珠
自动选关
其他类似游戏，比如tos神魔之塔，也可以类似的方法解决。
程序估计还有优化的余地，代码先不放出来了，有需要代码的或者有更好的想法可以加我qq：603997262。
ps：经过了numpy和numba加速，把判断最优步长操作转化成Numpy数组操作，把可能的步骤存入H5文件（读取都很快），
再用numba加速。三秒钟已经可以处理从任意一个棋盘位置走11步的所有情况，这些情况中包括了下落会产生的效果，从中找到消除个数最多的情况。
ps：分阶段优化。比如9步之内最优消除18个，那么以这个状态为开始，这个状态的最后一步为起点，继续迭代运行，把总的步骤加起来，最终大概能消除23个左右。因为第二次迭代的时候，起点是从棋盘的一个位置开始得，所以总的时间很少。只有前一步骤的几十分之一。所以总时间没有增加多少，只是移动时间变多了。
终极目标：（首先把所有的颜色排序，摆好（如图），然后计算什么样的操作可以达到这个排序呢样的算法吗！）
文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览35245 人正在系统学习中
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！