首页 > 黑暗科技研究 > 自动扫雷机

自动扫雷机

2014年1月7日 发表评论 阅读评论
其实这篇东西是2012年8月写的。。

之前咧,我在写这篇"死兔"作弊器的时候,后面就提到要写一个自动扫雷机,然后花了两个下午研究了一下,嗯,基本完成了,至少可以称之为内核了。。

先说结果吧,初级和中级都可以在1s内完成游戏,高级经过多次测试,最快4秒,最慢6秒左右。

然后汇报一下功能,嘛,就自动扫雷呗,可以在游戏开始的时候自动识别总雷数,游戏的规模大小,然后没啥别的特点了。。【下面视频可以改画质。。


好吧,然后简单介绍一下原理,首先自动扫雷首先就要获得游戏的状态,就是什么位置上现在的示数是有还是无,有的话是多少,获取这个主要有两种方法,第一种是外挂法,就是读取扫雷这个进程的内存单元,扫描后可以通过多次试验知道内存状态的含义,然后就可以开始扫了,这种方法我看到有认识这么干的了(→传送门),这种方法只要会读取/扫描内存,知道内存的含义,额,之后就毫无技术含量了,因为那些还没开的雷的状态你都知道了。。不管规模多大都可以直接秒杀。。然后第二种是我这里用的方法,获取窗口的图像,通过图像来获取游戏的相关信息,进行推理,然后控制鼠标到相应位置完成左键或者右键的点击,在一个大循环中不断地获取图片的状态然后就可以不断的推理,点击了,就趣味性而言,我觉得这种方法比较好玩儿~

然后下面就是详细讲一下我实现的方法:

准备工作,作为图像处理,首先要准备一下基本图像,比如不同数字打开后的图片神马的,唉,你知道我试验出数字8那个图像花了多少时间么??在做模板匹配的时候一般不会有人把模板存为jpeg吧。。

首先是如何获取游戏的窗口的图像,额,我以前的API实现过这个功能,只不过是把图像存到OPENCV的IplImage这种数据类型下而已,API传送门~

好,接下来就是要获取雷数,我们知道游戏刚开始的时候左上角显示的就是这盘的总雷数,比如说下图中的40:

获取这个数字自然也是通过获取这一块的图像来获得啦,由于无论如何都是3位数,所以这个小窗口的大小是不会变的,实验获得这个窗口的位置,宽高什么的都不是难事儿(我这里是通过定位黑色边框找到的,就是下图中最外层的那一圈黑,不过我获取一次后就把位置当常量记下来了。。之后变成默认我知道这个位置。。)

看上图我们知道每个数字其实就是一个7SEG数码管,亮和暗很容易区分出来,所以我们只要扫描每一条的像素值,就可以知道这个位置是亮还是暗了,把数据存到一个3*7的矩阵中,之后直接译码即可。关于扫描,参见下图:

横着扫描时可以通过在1/4和3/4位置横扫两次就可以了,竖着也差不多,只要用上数学上的取模运算,可以把for的次数讲到最低。

然后获取游戏的规模,额,坑爹啊,我实现的方法很简单,就是用上面那个图像库中unknown.bmp去匹配,然后有多少个匹配的就可以知道游戏的规模了,然后写完发现,其实研究一下,就可以通过游戏窗口的大小直接获得游戏的规模了。。不过我那个方法可以在匹配的过程中记录下每个格子相对于游戏窗口的像素坐标,后面点击操作的时候可以直接用,(其实另外一个方法研究一下规律也可以。。)具体的这里就不详述了。。很简单的。。

接下来需要从图片中获取格子数字,我用了一个比较取巧的方法,我们可以看到每个数字都是由一种颜色写成的,而且每个数字颜色还不一样,所以我们可以在每个格子中间周围找一下背景颜色以外的颜色,如果有1-8中某个数字的颜色就可以知道那个格子是什么数字了。这个方法很快,也很好用,但是细细分析,会有一个不影响使用的缺点,就是数字7是黑色的,而一旦点中雷后,雷的显示也是黑色的,就会把雷判断为数字7,不过嘛,都点出雷了,说明game over了,判断也啥意义,而且我们只要判断游戏上部中间那张脸的样子就可以知道是否点雷了,如果不是,那这个确定就无所谓了。

如果真有代码的"洁癖"的话,可以用另一种方法来识别,每个格子是16*16 pix的,我们可以记录下每个数字中间那一行的16个点的颜色作为那个数字的"特征向量",然后在匹配这个就行了,这时候数字7和黑色雷中间一行其实是不一样的,所以不会有这个问题。

接下来就是扫雷策略上的问题了,把我在死兔里面提到的那个策略改一下,就可以得到扫雷的基本策略了,很简单,基本是个人都想得到的,就是:

1.如果一个格子周围的确定的雷的数目等于这个格子的示数,那么这个格子周围所有还未确定的格子都是安全的。

2.如果一个格子周围所有不确定的数目等于格子的示数减去已经确定的雷的数目,那么剩余的不确定的格子一定全都是雷!

然后如果这个策略不能确定任何未知格子的状态的话,就随机蒙一个。。

额,我一开始就是按照这个思路写的,但是实验结果就是,对于初级和中级的游戏,没啥压力,一下子就过关了,但是对于高级,99个雷,棋盘规模有较大,每次都会推无可推,然后随便蒙一个,然后就挂彩了。。我试了很多次,一次都没过关过。。然后我就开始研究一个复杂一点的推导,准本在上面那个初级策略无效的时候采用。

上面的初级策略的缺点就是只考虑每个格子自身周围的数字而不考虑周围的格子的周围,就是多个格子联立思考,比如说下图:

细细研究一下就知道这时候初级策略已经没有任何可以确定的未知格子了,但是看下图:

我们研究红框的那一部分,为了方便说明,对于红框内的部分我们建立新坐标,比如A就是(3,2)。我们看(2,3)那个点,数字2表明了在A,B,C三个点钟还有一个雷,我们再看看这个点上方(1,3)那个点,它表明B和C中有一个雷

A,B,C中共有一个雷,BC中也只有一个雷,那就是说明A一定不是雷!!

再比如说下图:

也是到了初级策略束手无策的时候,我们再看看红框中的部分,点(3,4)的那个数字3表明a,b,c中有两个是雷,而它旁边(3,5)那个点表明bc中只有一个是雷,那就是说,a一定是雷!!

为了把上面的推导一般化,我们先声明一下几个概念:

一是公共未知区域,表示(i,j)点周围未知区域中和(i',j')周围未知区域中重复的那一部分【(i,j)要和(i',j')相邻】,比如说上图中(3,4)和(3,5)公共未知区域就是b,c,因为b,c不仅是(3,4)的周围的未知区域,还是(3,5)周围的未知区域

二是点(i,j)关于点(i',j')的非公共未知区域【(i,j)要和(i',j')相邻】,就是说(i,j)周围的未知区域中不是(i',j')周围的未知区域的那一些。比如上图中(3,4)关于(3,5)的非公共未知区域就是a,因为a属于(3,4)的未知区域,但是不属于(3,5)

然后我们要使用上述高级策略的话,必须要确定地知道公共未知区域中雷的数目,这点要怎么保证呢,就是(i',j')的未知区域就是公共未知区域,这样我们就可以通过(i',j')的示数和周围已经开拓出来的雷的位置知道(i',j')周围还有几个雷,而这个雷的数目就是公共未知区域的雷的数目。有了上述概念,高级策略如下:

1.如果点(i,j)剩余的地雷数等于(i,j)关于(i',j')非公共区域位置的数目加上(i,j)和(i',j')的公共未知区域的的数目,那么(i,j)关于点(i',j')的非公共未知区域则全是雷!

2.如果点(i,j)剩余的地雷数等于(i,j)关于(i',j')非公共区域位置的数目,那么(i,j)关于点(i',j')的非公共未知区域则全部安全!

实验结果表明,用了高级策略后,高级模式下无压力,只要不是运气太衰,一般都可以过关。运气太衰有两种表现,分别在开头和结尾,开头就是说你一开始每次随机点的时候都只点出一格,没有出一片来,那这种情况下你只能继续随机点,点着点着雷就爆了。。

还有另外一种情况就是在结尾的时候,比如说下图。。

幸好我这是机器扫出来的,输了就输了,如果是人手一个一个扫,扫到最后出现这种情况,直接砸电脑!!(掀桌!!暴怒)不过还真别说,这种情况还挺常见的!!果然游戏生成布局的时候就很不科学。。


老规矩,上代码。。代码要用到opencv库,所以对大部分孩子而言不管用。。

Main:


MineGame.h:


MineGame.cpp


NumberTemplate.h


NumberTemplate.cpp


【完】

本文内容遵从CC版权协议,转载请注明出自http://www.kylen314.com

  • opencv,我只用过camshift。另外gnome自带的扫雷可以完全自定义,我之前设置过一次80*90,2000个雷的。然后玩了好几个小时

    • 本科专门搞图像处理,所以opencv用的比较多。。以至于写什么都想用opencv。。。现在。。基本不用了。。

      • 图形处理,是个高级的东东。我的极限就是这个了,是不是太挫?

        • 你过谦了。。我觉得很好啊,尤其是那个绘制博客关系图那个,很有意思也很有想法啊!最近想用python的PIL做图像相关的处理~用opencv一般都是贪用里面很多复杂的图像处理库,因为以前做的是人机交互,所以很多底层算法能不重写就不重写。。

          • 我感觉python的相关库也非常多,特别是科学计算相关的。而且底层库除了学习用,一般也用不到重写。

            • python最开始就是为了爬虫,然后用pythonxy开始做一些数值分析,然后最近也在看别人都在用py在做些什么,然后学习学习。。

              • pyxy,强大的包,可惜只有win下面的

                • 嗯,用来在某些场合代替Matlab的东西。。。linux反正把包下下来就行了嘛~虽然要自己收集包比较麻烦。。

                  • 我是直接vbox一个xp,里面装了pythonxy和Perl Dev Kit

                    • linux里面没有和pyxy差不多的东西么?我总感觉应该有人会去搞这个贡献社会的。。

                    • 用习惯了

                    • 这个的好快啊

                    • 我看了一下他的那个代码【脚本】,就是我文中一开始提到的那种直接读内存,马上就知道所有雷的位置了。。然后控制按键精灵去点。。。

                    • 恩。刚刚下载下来想要玩玩,打开菜单才想起来我的电脑没有扫雷……

                    • 。。。。。。。。。。23333333.。。。其实搞一个也很简单~

                    • 没有扫雷可以来玩这个。。http://mienfield.com/,刚刚被人推荐了。。

                    • 这个不错,做得很好。就是打开的慢了些

                    • 嗯。。。我每次都坚信我没点错,然后继续去开荒。。。直到我想收藏这个游戏进收藏夹。。。在一个不该点的地方。。。点了鼠标右键。。

                    • 我怎么点哪里都是地雷啊。连着好几次了

                    • 不是要在已有的“大陆”的边缘开始开荒么?

                    • var myDate = new Date();document.getElementsByClassName('dialog__input') .value='测试速度,javascript时间为:' + myDate.toLocaleTimeString();document.getElementsByClassName('dialog__button chat__enter') .click();刷屏了刷屏了

                    • 竟然把数组的下标给我替换成图片了

                    • 嗯,之前有人回我代码也是变成了一片表情的海洋,跟多说官方反映但是他们不鸟我。。。

                    • document.getElementsByClassName('dialog__input')返回来为空怎么破?

                    • 有干扰项,用第二个

                    • var myDate = new Date();document.getElementsByClassName('dialog__input')【1】 .value='测试速度,javascript时间为:' + myDate.toLocaleTimeString();document.getElementsByClassName('dialog__button chat__enter')【1】 .click();

                    • 确认一下。。你这个东西是在chrome的console里面用?我怎么调用返回都是[]。。。【还不是很懂前端的这种调试性质的东西。。其实不用刻意改符号,因为复制的时候变成文本的话会自动变回去的。。。【只是显示在评论里面不美观。。

                    • 复制的时候,虽然表情会变回alt的值,但会自动加一个空格。我这个是在chrome的console中执行的,昨天刷了屏,可以成功执行

          • 我感觉自己是纯粹的计算机编程外行。在校期间除了C语言基础课程是必修的,就没怎么学习其他的了。后来凭兴趣自学的似是而非,各个语言经常用混

            • 嘛~我修过的编程课也是就那一门,本来编程这种东西真要做得好,只能靠个人兴趣。。

  • 这都想得出来

    • 我觉得你应该不是指我用以前的文章滥竽充数这件事。。。

  • 博主坐好了,让我膜拜下!好了,可以站起来了,你牛啊!

    • 12年写的小玩意儿,现在没空更新博文。。就拿来凑数。。。

  • 有这时间 做个强大的吧

    • 强大是指哪方面呢?

  • 厉害。

  • 厉害,学习一下~

  • 表示没玩过....

    • 好吧。。现在没玩过扫雷的人不多了吧。。

  • 感觉好厉害啊,我不会

    • 不会扫雷?

      • 代码,扫雷也不会

        • 好吧。。

          • 真心的,没完过

            • 去玩一下吧!喜欢win的人不应该没玩过!

  • 靠,经典游戏就这样被外挂给糟蹋了

    • 怎么可以说是糟蹋呢?这是编程学习用的~

      • 我是扫雷游戏的粉丝,现在的手机都装了扫雷的游戏,鄙视外挂行为

        • 你可以认为是扫雷算法研究+图像处理学习,你人脑扫雷的思考过程要抽象成一般化的描述也是很有研究价值的!!

  • 这都能捣鼓出来。。太厉害了

    • 其实网上做过这个的人很多了,只是方法各不相同而已~

  • 好高端啊

  • 实在是上档次啊

  • 感觉这么小的功能实现起来好像很麻烦

    • 主要是因为这个方法是完全图像处理法,只根据游戏窗口图像这一信息来完成,而不是辅助加上一些程序内存信息这些东西。

  • 厉害!

    • 多谢夸奖【其实这个不难。。

  • 好强大,完了去了解下python的做法,应该更简洁吧

    • 这个是12年8月写的,那是我还没学python不过用python,肯定会更简洁,但是速度就不好保证了

  • 4s玩完有点悬,玩这游戏我都得深思熟虑!

    • 4S你指初等的?

      • 好吧,也就当初在学校玩,初等的,嘿嘿!

        • 4s很牛啦!!我当年为了刷个个位数秒都不知道刷了多少次。。

  • 太厉害了,对图像处理

    • 本科一直搞图像处理的。。。现在完全不碰了。。

  • 我做的是直接赢了,通过改写内存地址的信息。

    • 。。。。。改内存。。比读内存还狠。。。

  • 很久以前老研究这个 ,挺怀念

    • 孩子都有了,确实应该是很久以前的事了~嘻嘻

  • 你这分析得真透彻,我扫雷经常就在那些地方踩雷

    • 我也就在写这个程序的时候才专门去想一下这个问题,以前也没仔细研究过。。毕竟是要让计算机按人脑工作,所以必须把思考方式抽象出来。。

  • 来过留言。。

  • 这个好嗲!OAQ

  • 膜拜ノ(=゚ω゚)ノ

  • unnamed5719

    强力马克#2