第5讲 综合应用-自动扫雷器

《算法分析与设计》第5讲综合应用－自动扫雷器2知识点一、Windows扫雷游戏程序二、两个参考程序三、自动扫雷器的原理四、程序界面采用的技术和方法4.1获取并显示操作系统的版本号4.2启动扫雷游戏4.3并排居中显示两个窗口、计算扫雷游戏地图行数和列数4.4开启新局五、决策前的准备5.1扫描地图5.2方格16种状态的表示5.3获取每个方格第8行16个像素的颜色并与预存的16种状态比对六、决策6.1普通决策6.2高级决策3一、Windows扫雷游戏程序鼠标左右键的作用：鼠标左键单击：点开某个位置；鼠标右键单击：将某个位置标记为地雷；鼠标左右键同时单击：见下一页。在自动扫雷程序中，需要人为地向扫雷程序发送这些鼠标消息，达到自动标记地雷或点开位置的功能。4鼠标左右键同时单击：如果单击的位置周围8个相邻位置中已标记为地雷的个数=该位置显示的数字，则将其他未点开的位置全部点开(如果标记的位置是正确的，则其他位置中不可能有地雷)。思考：鼠标左右键同时单击下图中标注的位置，会有什么效果？5思考人在玩扫雷游戏时，会采用哪些推理规则。6期末作品参考模仿Windows扫雷游戏，用VC/MFC设计一个扫雷游戏，其界面和功能可参考Windows扫雷游戏。7二、两个参考程序软件名称：自动扫雷器：作者：任全。开发工具：VC/MFC。特点：需要人工点开，当算法不能继续时，需要人工介入。说明：该程序为本课件的参考程序，本课件做了简化、并补充了大量的注释。8软件名称：自动扫雷。作者：葛永。开发工具：未知。特点：以猜测替代人工操作。功能更全面，提供了多个选项的设置，甚至可以自定义推理规则。9三、自动扫雷器的原理启动扫雷游戏后，当用户点击“扫雷”按钮时，扫描扫雷游戏地图，通过提取每个方格(16×16)中间第8行16个像素的颜色，跟预存的16种状态的颜色进行比对，从而判断每个方格的状态。10根据每个方格状态的信息进行决策(包括普通决策和高级决策)，从而点开某个(或某些)位置，或者将某个(或某些)位置标记为地雷。某次决策后：如果判定出现了踩到地雷的状态，则提示“扫雷失败”。如果所有地雷位置都正确标记出来、其他位置都点开了，则提示“扫雷成功”。如果某次决策无法点开位置或标记地雷，则提示“算法不能继续了”，请求用户手动点开一些位置。11决策例子：请试着根据下图所显示的各方格的状态判断哪些位置可以标记为地雷，哪些位置可以点开。12补充：Windows画图应用程序妙用将一个bmp位图文件用画图软件打开，然后放大8倍，可以清晰地观察到每个像素。可以显示网格，可以显示缩略图。在状态栏中可以显示当前鼠标光标的位置，所选矩形区域的大小等。13画图程序在分析自动扫雷器代码中的作用：扫雷游戏程序和自动扫雷器窗口大小分别是多少个像素，标题栏和菜单栏高度是多少个像素，边框高度或宽度是多少个像素，等等。每个方格16×16区域具体包含了哪些像素。提取每个方格第8行16个像素的颜色，第8行具体是哪一行。等等。14补充：其他工具软件的应用01取屏幕上任一点的RGB颜色值（绿色）：色值传递员(plsread)。02中英文颜色RGB代码对照表（绿色）。03YUV、RGB转换并带颜色显示（绿色）。04RGB颜色分析器V4·0（绿色）。以上软件均已上传到网络课堂(或服务器)中。15补充：像素位图文件是由像素组成。行和列上的像素序号从0开始计起。在Windows绘图应用程序中打开一幅位图文件(*.bmp)，然后放大8倍，并显示网格，可以清晰地观察到位图的每个像素。显示器屏幕分辨率为1280×800，则意味着水平方向上为1280个像素，竖直方向上为800个像素。许多GDI绘图函数的绘图单位也是像素。16补充：坐标系屏幕坐标系：坐标系原点在屏幕左上角。客户区坐标系：坐标系原点在客户区左上角。坐标系转换函数：API函数：ClientToScreen。xxyy扫雷游戏窗口中某一个点的客户区坐标为(20,20)，其屏幕坐标可能为(277,282)。17补充：屏幕坐标和区域屏幕坐标：CPoint类(MFC中的类)表示屏幕上一个点的坐标。与Windows中的结构体POINT(即API中的结构体)类似，增加了很多成员函数。区域：CRect(MFC中的类)表示屏幕上一个矩形区域。与Windows中的结构体RECT(即API中的结构体)类似，增加了很多成员函数。typedefstructtagPOINT{LONGx;LONGy;}POINT;typedefstructtagRECT{LONGleft;LONGtop;LONGright;LONGbottom;}RECT;18补充：MFC/SDK的数据类型与C/C++的数据类型MFC，MicrosoftFoundationClassLibrary。SDK，WindowsSoftwareDevelopmentKit。在SDK应用程序中，采用API函数来实现程序功能。所以SDK应用程序也就是基于API函数的应用程序。在MFC/SDK中定义了很多数据类型，为了跟其他计算机语言中的数据类型相区别，特意采用大写字母。BOOL、BSTR、BYTE、COLORREF、DWORD、LONG、LPARAM、LPCSTR、LPSTR、LPCTSTR、LPTSTR、LPVOID、LRESULT、UINT、WNDPROC、WORD、WPARAM、POSITION、LPCRECT等等。每种数据类型的含义及所占字节数请查阅MSDN。在MFC/SDK中仍然支持C/C++的数据类型。19补充：颜色在计算机中的表示在计算机中，颜色是用R(红)、G(绿)、B(蓝)3个分量来表示的，每个分量取值为0~255，可以用一个字节来存储。因此，RGB一共可以表示255×255×255种颜色。在Windows操作系统中，使用COLORREF数据类型来表示RGB颜色。COLORREF占4个字节、32位，用16进制来表示是0x00bbggrr，即最高字节不用，次高字节表示B分量、次低字节表示G分量，最低字节表示R分量。在有的时候(比如在调试状态下)，COLORREF是以十进制形式显示的，比如白色(0x00FFFFFF)的值为16777215。API函数GetPixel可以获得屏幕上指定位置的颜色值，返回的是COLORREF类型的值。20常用颜色列表：RGB值COLORREF颜色中文名称RGB(0,0,0)0x00000000黑色RGB(128,0,0)0x00000080栗色RGB(0,128,0)0x00008000深绿色RGB(128,128,0)0x00008080橄榄色RGB(0,0,128)0x00800000海军蓝色RGB(128,0,128)0x00800080紫色RGB(0,128,128)0x00808000水鸭色RGB(128,128,128)0x00808080灰色RGB(192,192,192)0x00C0C0C0银白色RGB(255,0,0)0x000000FF红色RGB(0,255,0)0x0000FF00绿色RGB(255,255,0)0x0000FFFF黄色RGB(0,0,255)0x00FF0000蓝色RGB(255,0,255)0x00FF00FF洋红色RGB(0,255,255)0x00FFFF00青色RGB(255,255,255)0x00FFFFFF白色注意，在COLORREF数据中，是按BGR的顺序从高位到低位存放的。这16种颜色也是扫雷程序各方格中可能出现的16种颜色。21四、程序界面采用的技术和方法自动扫雷器界面：基于对话框的应用程序。界面很简单。22CMineCrackDlg类自定义数据成员和函数成员含义及功能。数据成员：BOOLm_bWin98;//操作系统是否为Win98、Win2003的标志变量CStringwinMineClassName;//扫雷游戏程序窗口类名HWNDhWinMineWnd;//扫雷游戏窗口句柄CRectrectWinMine;//扫雷游戏窗口区域CRectrectMe;//本程序窗口区域BOOLm_bStart;//扫雷游戏是否启动的标志intm_nWidth;//扫雷游戏水平方向上方格的数目(即列数)，高级是16行×30列intm_nHeight;//扫雷游戏竖直方向上方格的数目(即行数)intm_nMineNum;//地雷的个数intm_nMineCurNum;//当前已标记出的地雷数目//申请m_nWidth×m_nHeight大小的存储空间//每个元素代表一个位置，取值为0～FF，分别代表一种状态BYTE*m_map;BYTEm_ColorSample[16][8];//预先存储的扫雷游戏方格16种状态的颜色4.0数据成员和函数成员说明23数据成员m_bWin98说明：Win98、Win2003和Win2000、WinXP中的扫雷应用窗口有一些细微差别：Win98、Win2003中的扫雷程序窗口宽度多4个像素、高度多4个像素。在通过窗口大小来计算扫雷游戏的行数和列数时要区分Win98、Win2003系统和其他系统。BOOLm_bWin98;CStringwinMineClassName;HWNDhWinMineWnd;CRectrectWinMine;CRectrectMe;BOOLm_bStart;intm_nWidth;intm_nHeight;intm_nMineNum;intm_nMineCurNum;BYTE*m_map;BYTEm_ColorSample[16][8];24数据成员m_nWidth、m_nHeight说明：m_nWidth：扫雷游戏水平方向上有多少个方格。m_nHeight：扫雷游戏竖直方向上有多少个方格。数数高级模式水平和竖直方向上分别有多少个方格。BOOLm_bWin98;CStringwinMineClassName;HWNDhWinMineWnd;CRectrectWinMine;CRectrectMe;BOOLm_bStart;intm_nWidth;intm_nHeight;intm_nMineNum;intm_nMineCurNum;BYTE*m_map;BYTEm_ColorSample[16][8];25BOOLm_bWin98;CStringwinMineClassName;HWNDhWinMineWnd;CRectrectWinMine;CRectrectMe;BOOLm_bStart;intm_nWidth;intm_nHeight;intm_nMineNum;intm_nMineCurNum;BYTE*m_map;BYTEm_ColorSample[16][8];数据成员m_map数组说明：在启动(含重新开具)扫雷游戏时，申请一维数组存储空间，并用m_map指向这段存储空间。一维数组存储空间当作二维数组存储空间使用。m_map数组元素取值含义：#defineUNKNOW0x00//未知#defineNOMINE0xFF//确定没有地雷#defineISMINE0x0F//确定为地雷#defineNEIGHBOR_10x01//数字1//即该位置没有地雷，但周围8个方向上有1颗地雷(以下同)#defineNEIGHBOR_20x02//数字2#defineNEIGHBOR_30x03//数字3#defineNEIGHBOR_40x04//数字4#defineNEIGHBOR_50x05//数字5#defineNEIGHBOR_60x06//数字6#defineNEIGHBOR_70x07//数字7#defineNEIGHBOR_80x08//数字8m_map=newBYTE[m_nWidth*m_nHeight];ZeroMemory(m_map,m_nWidth*m_nHeight);//系统函数，清零内存空间26BOOLm_bWi