java吧 关注:1,234,931贴子:12,703,981

自动扫雷机完成过程详解

只看楼主收藏回复

最近闲来无事,又一直喜欢写点小游戏,于是就瞄上了扫雷。原本只是想写个控制台版的自己玩玩,但想想貌似自动解扫雷也不算太难,至少我自己玩的逻辑是可以用算法描述的,所以就开始着手写一个可以解扫雷的代码。刚开始的时候还没有打算真实的玩windows的扫雷,因为数字识别的部分的确有点难度,于是先花了一天左右的时间学怎么控制鼠标和处理图像。


IP属地:江苏1楼2016-04-29 10:11回复
    下面我给大家讲一下这个扫雷机完成的过程。第一步,写一个控制台版模拟扫雷小游戏。第二步,将自己玩扫雷的逻辑用代码表述出来,并检验是否能够成功。第三步,玩扫雷的逻辑已经有了,只需要将第一步中小游戏模拟鼠标单击并返回桌面数字的代码,替换为真实的鼠标点击和读取图片识别数字,那基本就完成了。


    IP属地:江苏2楼2016-04-29 10:11
    收起回复
      用于我本人用的是python写的,所以在这里不打算将源码全部贴出。改为使用伪代码描述算法逻辑,只要理解了算法,自己实现比照抄代码更有成就感,而且我自己的代码因为任务简单且当时考虑不够周全,有一些需要重构的地方,我也不好意思发出来让大家见笑。很多人问我python和java的区别,其实扫雷里面用到的逻辑,java都是可以实现的。我使用python只因为python的列表表达式对list的各种操作较java方便一点。


      IP属地:江苏3楼2016-04-29 10:11
      回复(2)
        下面开始讲第一步:写一个模拟扫雷小游戏由于模拟扫雷不需要真实的GUI,所以可以省去很多工作量。大部分可以由文字表述的游戏,我都只用控制台实现。这一步应该很多人都接触过,我昨天还看见有人发帖问扫雷怎么写。这里需要一个Game类的对象以及以下的方法:
        void createNewGame( row ,column,mines){
        //创建一个新的游戏
        this.field=new int[row][column] //真实的雷分布数据,0-8表示周围的区域雷的个数,9可以用来表示雷,因为平面扫雷中不会出现9
        this.mask=new int[row][column] //玩家可见的层,初始化可用0-9以外的内容填充,python中我用'-'表示未点击格
        //布置所有的雷
        setMines(mines)}
        void setMines(mines){
        //设置一定数量的雷,如果想保证玩家第一步不至于点到雷,可将第一步的位置传入,将此位置从可布雷的区域排除
        for 0-mines{
        //生成一个随机位置,此算法参考扑克牌发牌算法,使用一维数组来表示所有的可用位置,每次随机取一位,并将该值从数组中移除
        //将布置雷的位置周围的数字加1,注意边界检查以及避免修改原本是雷(9)的格子
        }
        }
        int[][] getMask(){
        //返回游戏的当前分布
        return xxx}
        至以上,一个模拟的扫雷游戏就已经初始化好了


        IP属地:江苏5楼2016-04-29 10:13
        收起回复
          再写一个单击和双击的方法:
          单击和双击模拟就写好了,如果有兴趣,可以直接使用控制台开始玩模拟扫雷了,当然,最好加上一个显示mask的方法,方便自己看游戏进度


          IP属地:江苏6楼2016-04-29 10:15
          收起回复
            下面开始第二步:根据上面的mask解一个扫雷游戏,即计算出下一步点击哪里玩过扫雷的人都了解,当游戏上的信息完全无法推理出新的信息时,随机是唯一的选择。所以这里必然会使用到随机,这也是唯一可能导致游戏失败的地方。当扫雷的雷分布越密集,可获得的数字信息就越少,且随机失败的概率就越大。比如同时出现两处二选一的情况,胜率立马变成1/4.这也是为什么高级非常难的原因。目前我的解法在解初级9*9(10雷),中级16*16(40雷)的胜率在80-85左右。但高级16*30(99雷)的胜率不足15%。如果再加上图像识别误差导致的失败,这个胜率会更低一点。如果有哪位能在不影响算法效率的情况下明显的提高高级的胜率,欢迎大家分享


            IP属地:江苏7楼2016-04-29 10:15
            回复


              IP属地:江苏9楼2016-04-29 10:17
              回复
                各位稍等。。讲起来东西有点多,请耐心等待


                IP属地:江苏10楼2016-04-29 10:18
                回复


                  IP属地:江苏11楼2016-04-29 10:24
                  回复
                    我怀疑你不是老司机


                    IP属地:上海来自Android客户端12楼2016-04-29 10:40
                    收起回复
                      现在来讲解较为复杂的strategy3中的逻辑:当两个数字周围存在共有空白区域的时候,可以通过两个数字的大小等信息推断出新的信息(这两个数字可以不是紧邻着彼此,比如隔着一个格子也可以满足条件)
                      这里有两种情况,分别对应确定雷和排除雷的逻辑。情况1:排除雷,如果出现如下图所示,“-”代表为点击
                      0 1 -
                      0 1 -
                      0 3 -
                      图中的两个1,我用1(0,1),1(1,1)表示,这两个数字的共有区域为same=[(0,2),(1,2)].且 len(same)>0 and len(same)==len(empty((0,1)))用文字描述,即(0,1)周围的雷只能分布在两个数的共有区域。即共有区域的雷个数为1。由此可推断出,当 mines((1,1))-mines((0,1))==0 and len(same)>0 and len(same)==len(empty((0,1)))时,所有的(1,1)周围非共有区域都可以排除
                      情况2:
                      0 1 -
                      0 2 -
                      0 3 -
                      与上一种情况略有不同,1(1,1)变成了2(1,1).这时,mines((1,1))-mines((0,1))==x and len(empty((1,1)))-len(same)==x (x可为任意数字,即表示这两个等式的左边计算结果相等,此例中,x=1),可推断出2(1,1)周围的非共有区域都是雷用文字描述为:same中最多只可容纳一颗雷,所以2(1,1)的剩余1格区域必然是一颗雷,此情况可推广至剩余x颗雷


                      IP属地:江苏13楼2016-04-29 10:41
                      收起回复
                        以上,根据扫雷的局面来推理和解题的逻辑已经实现,如我之前所说,此解法的胜率依赖于游戏的雷分布密度,雷数量越多,分布越密集,解题效果越弱。
                        最后进行最后一步,将game.click替换为真实的点击方法在java中,可使用继承,直接重写click方法,rightclick可以不用重写,因为在mask上标记为雷就可以获得相应信息,避免在桌面上的右击,且不影响游戏结果其他语言中,可将方法作为参数传入solve方法,不过推荐使用面向对象的方式,将一些彼此不公用的参数分开设置


                        IP属地:江苏14楼2016-04-29 10:47
                        回复
                          好厉害的样子


                          来自Android客户端15楼2016-04-29 10:48
                          回复
                            现在即将讲到最难的部分,涉及的内容也最多,就是数字图像的识别。首先,我们需要获取游戏上可点击位置的参数,比如扫雷的可点击区域左上右下角的坐标。这里由于游戏窗口的大小以及游戏的行列数据是可以人为控制的 。所以只要将这些需要事先获取,并写入代码中即可。我并不想在图片边界识别上花太多功夫,毕竟我们的目标是扫雷。其次,扫雷可能出现的图片单元较为单一,1-8的数字,代表0的白色空格,代表未点击区域的蓝色空格和两种颜色的雷。所以我们的目标就是写一个方法能够区分以上的12类图片。这里称之为12类是因为如果你仔细观察,就会发现扫雷上的图片之间并不是完全相同,加上我们的人工裁剪误差,即使人类可以一眼分辨的两个同类图片,他们的数据上的差异也会非常的明显。例如蓝色的空格中左上角的颜色最浅,右下角颜色最深,这会导致很多不必要的麻烦。


                            IP属地:江苏16楼2016-04-29 11:29
                            回复
                              对于图片的识别,直观的角度上来讲,将获得的图片与已有的训练集图片进行比较是最容易理解的。所以第一版我也是这么做的。当然裁剪图片二值化以后的数据与训练集图片的数据不可能完全一样,这里我们就需要知道怎么计算两个图片之间的差距。当一个图片出现,我们计算出它离哪个训练集的图片越接近,那它越可能是对应的数字。这里需要先介绍一下汉明距离。这个一般是用来计算两个字符串之间的距离,即通过越少的改动将一个字符变成另一个字符,那这两个字符就越接近。(具体算法请百度)


                              IP属地:江苏17楼2016-04-29 11:30
                              收起回复