本帖最后由 踢馆帝 于 2013-8-8 19:18 编辑
序言 本人平时无聊时总会玩玩扫雷游戏，某天一如既往的被炸死后，突然想写一个自动扫雷的程序来玩玩，经过几天的思考和CODING，算是完成了一个初版，下面就来简单介绍一下扫雷的基础和程序的流程。 命名 先规定一下本文中使用的基本名词 （1）扫雷中的方格称为<块> （2）有数字的块称为<数字块> （3）没有点击也没有做标记的块称为<未知块> （4）已经确定是雷的称为<雷> （5）<块>周围相邻的所有块的集合称为<8-邻域> （6）将<8-邻域>扩大一个单位，并去除四个角落，称为<20-邻域>
file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\ksohtml\wps_clip_image-8386.png <8-邻域>和<20-邻域>示意图 <8-邻域>：红色区域除去a <20-邻域>：黄色区域除去a 扫雷基础 在扫雷游戏刚开始，第一步貌似点哪里被炸的几率都一样，但其实并非如此，我们以WINDOWS-XP的扫雷（简称<XP扫雷>）为例，<XP扫雷>的第一步一定不会是雷，有兴趣的童鞋可以用DEBUG工具分析或者查看源代码。<XP扫雷>的运行机制是当用户第一次点击时，生成雷区，如果用户点击的<块>正好是雷，则重新生成雷区。因此第一步不用担心。 既然第一步不会被炸，那么随便点哪里都一样吗？其实也不是，因为我们希望第一步能点开一片区域（也就是被点击的<块>的<8-邻域>没有雷），这样我们就可以从区域的边界来推算下一步该如何选择。 好了，那么问题就变成这样了：<XP扫雷>刚开始时，哪些<块>在点击后，<8-邻域>一个雷都没有的几率最大？相信大家凭直觉就能知道是雷区的角落和边界，实际上也正是如此，通过计算也能得出角落是最优选择，其次是边界。 判断方法1 假如第一步已经点开了一片区域，那么下面我们就要推算哪些是雷，哪些不是雷了。 先说最简单的判断方法，也就是<数字块>的<8-邻域>中的<未知块>的数量等于<数字块>的数字，此时，所有的<未知块>都是<雷>。下面的图就是一个典型例子。
file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\ksohtml\wps_clip_image-9538.png 判断方法2 这是一个稍微复杂一点的方法，涉及到的区域是<20-邻域>。看到下图中，黄色方框中的<3>的<8-邻域>中有2个<未知块>，但是只有1个<雷>，因此无法判断。再看红色方框中的<1>，它的<8-邻域>中有3个<未知块>，1个<雷>，也无法判断。但是将这两个区域结合起来，我们将<1>的<8-邻域>的所有<未知块>称为<未知集合1>，将<3>的<8-邻域><未知块>称为<未知集合2>，我们发现<未知集合1>包含了<未知集合2>，因此可以果断得出结论，<未知集合1>和<未知集合2>的未重叠部分，一定没有<雷>。 将这个方法归纳一下： 设<未知集合1>有n1个<未知块>，b1个<雷> <未知集合2>有n2个<未知块>，b2个<雷> 且<未知集合1>包含<未知集合2>，可以得出n1>n2 那么<未知集合1>除去<未知集合2>的剩余部分有n1-n2个<未知块>，有b1-b2个<雷> 此时可以考察b1-b2，如果b1-b2 = 0，则说明n1-n2个<未知块>全都不是<雷>，如果 b1-b2 = n1-n2，则说明n1-n2个<未知块>全都是<雷>。 其实这个方法还可以继续推广，<未知集合1>包含<未知集合2>~<未知集合n>，并且<未知集合2>~<未知集合n>互相不想交，则也可以适用上面的判断。
file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\ksohtml\wps_clip_image-31801.png 更高级的判断方法 本人比较愚笨，只会用这两种方法，穷途末路以后就全拼RP.......... 如果各位有什么其它更高级的方法，希望能告诉我。程序实现 程序分为几个部分 （1）雷区的获取 本程序是直接通过分析图像来获得雷区信息的，步骤如下： l 通过win32函数找到扫雷游戏的窗口坐标和窗口大小 l 对扫雷窗口截图，转换为彩色图和灰度图两个版本 l 通过灰度图分析雷区的方格信息，方法是找到每行每列像素的灰度边界，找出边界之间的距离，并列出距离的直方图，通过直方图找到方格的大小和数量，并可以找到雷区相对于窗口的相对坐标 l 获取每个方格的状态则是采用彩色图，简单的将方格像素直接和预存的常量对比，状态包含<未知>，<0>，<1>，<2>，<3>，<4>，<5>，<6>，<7>，<8>，<旗帜>，<？><雷> （2）雷区判断 l 使用上文提到的两种方法遍历雷区，获取整个雷区的<概率图>，概率是从0~1，0代表一定不是雷，1代表一定是雷，除了0和1以外的概率并不是非常准确，因为只是采用了上文提到的两种方法来计算。 l 调用win32函数控制鼠标，将所有概率是0的方格点开，概率是1的标记旗帜（也可以不标记，因为标记旗帜对程序来说没有任何作用） l 重复上述步骤，直到完成扫雷或者无法继续 下图是一次自动解<扫雷高级>的结果，可以看到并没有扫完，程序无法继续了，实际上只通过上面说到的两种方法，只能完成<扫雷初级>和大部分<扫雷中级>，<扫雷高级>的完成率是很低的，最后只能使用概率来拼RP。
file:///C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\ksohtml\wps_clip_image-26082.png 屏幕最上面的图表是概率图，概率0是白色，概率1是红色，概率越大颜色越深 | 
发新帖
发表于 2013-8-8 14:52:11
提升卡
置顶卡
变色卡
楼主
