扫雷课程设计报告.doc

Harbin Institute of Technology课程设计报告课程名称： 数据结构与算法课程设计设计题目： 扫雷 院 系： 计算机科学与技术学院 班 级： 10503104 设 计 者： 陆亮 学 号： 1050310404 指导教师： 刘晓燕 设计时间： 2007-8-27到2007-9-8哈尔滨工业大学哈尔滨工业大学课程设计任务书 姓 名：陆亮 院 （系）：计算机科学与技术学院 专 业：计算机科学与技术 班 号：1050310404 任务起至日期：2007年8月27日至2007年9月9日 课程设计题目： 扫雷游戏 课程设计要求： 能够给出游戏结果（输、赢、剩余的雷数、用掉 的时间按妙计）。游戏界面最好图形化，否则一定要清楚的字符界面。设计任务总述：本题目做一个N x M的扫雷游戏，每个方格包含两种状态：关闭（closed）和打开（opened），初始化时每个方格都是关闭的，一个打开的方格也会包含两种状态：一个数字（clue）和一个雷（bomb）。你可以打开（open）一个方格，如果你打开的是 一个bomb，那么就失败；否则就会打开一个数字，该数字是位于0，8的一个整数，该数字表示其所有邻居方格（neighboring squares）所包含的雷数，应用该信息可以帮助你扫雷。工作计划及安排：8月27日-8月30日：学习vc+6.0的MFC编程，以及扫雷所需设计的算法；8月31日-9月5日：实现扫雷的基本框架；9月6日-9月9日：优化功能；指导教师签字_ 年 月 日 数据结构与算法课程设计中期检查结果学号：1050310404姓名：陆亮指导老师：刘晓燕课程设计题目：扫雷系统总任务描述：本题目做一个N x M的扫雷游戏，每个方格包含两种状态：关闭（closed）和打开（opened），初始化时每个方格都是关闭的，一个打开的方格也会包含两种状态：一个数字（clue）和一个雷（bomb）。你可以打开（open）一个方格，如果你打开的是 一个bomb，那么就失败；否则就会打开一个数字，该数字是位于0，8的一个整数，该数字表示其所有邻居方格（neighboring squares）所包含的雷数，应用该信息可以帮助你扫雷。已完成工作描述：1.所需的算法都已经设计完毕，包括展拓空白区域，判胜，获得周围雷数，以及随机布雷2.翻阅了大量有关的书籍，初步学习了VC+6下一步工作计划及安排：1 星期一星期二：鼠标左右键的处理流程；2 星期三：计时器功能，计数功能；3 星期四：调试，完善；4. 星期五：准备PPT答辩填表时间：2007-9-3指导教师签字：一、 题目分析(1) 问题描述本题目做一个N x M的扫雷游戏，每个方格包 含两种状态：关闭（closed）和打开（opened），初始化时每个方格都是关闭的，一个打开的方格也会 包含两种状态：一个数字（clue）和一个雷（bomb）。你可以打开（open）一个方格，如果你打开的是 一个bomb，那么就失败；否则就会打开一个数字，该数字是位于0，8的一个整数，该数字表示其所有 邻居方格（neighboring squares）所包含的雷数，应用该信息可以帮助你扫雷。图4-20 扫雷游戏的图例具体实现要求的细节:a.能够打开一个方格，一个已打开的方格不能再关闭。b.能够标记一个方格，标记方格的含义是对该方格有雷的预测（并不表示真的一定有雷），当一个方格标记后该方格不能被打开，只能执行取消 标记的操作，只能在取消后才能打开一个方格。c.合理分配各个操作的按键，以及各方格各种状态如何合理显示。(2) 基本要求a.能够给出游戏结果（输、赢、剩余的雷数、用掉的时间按妙计）。b.游戏界面最好图形化。(3)所需解决的问题a.运行的结果必须采用可视化的界面，因此开发工具我选择了VC+6.0，用MFC工程解决此题目；b.题目要求M*N的雷区，因此学要与用户对话，以获得区域大小和雷数目，可以使用MFC中的对话框来实现；c.雷的位置应该是随机的，因此必须采用生成随机数的办法布雷，同时还应该注意避免用户第一次就点击到了雷，这是没有意义的；d.方格会处于各种不同的状态，设计其结构并定义相应的状态宏是必要的；e.因游戏的状态不同，消息机制是会对鼠标信息进行不同处理，因此要定义游戏状态宏，并时时记录游戏的状态；f.点击到了某区域发现其周围没有雷，那么显而易见应该点开周围的区域，如果这样的操作由用户一一完成，将增加用户很多的操作负担，大大减少了游戏的趣味性，因此周围的空白区域应该自动打开，这就需要一个函数来递归的完成此任务；g.为了获得所点击的方格周围雷数，要设计一个函数，其中要注意处理边界方格；h.当鼠标左或右键点击后，都应该判断是否胜利，胜利条件应当选择准确；i.左右键点击后，响应其消息的函数是相当复杂的，应当根据点击的位置，游戏的状态以及点击的方格状态，来进行不同的处理；j.确定点击的是哪一个方格，可以用点击的位置坐标来计算；k.设计一个计时器，显示游戏进行的时间；l.设计一个计数器，显示剩余的雷数，考虑标记的雷数比实际的雷数多时的情况二、 总体设计1.要实现点击后出现不同的图像，如空白或标记为雷或标记为有2两颗雷等，就需要利用MFC的重绘机制。重绘的依据是方块的属性，重绘的时间是在以下三个动作结束之后：左键点击，右键点击，以及重置游戏。下面就分别介绍这三个动作要进行什么样的处理，为重绘做好准备。(1).左键点击重置游戏等待状态进行状态结束状态雷区笑脸区左键点击后判断位置点击位置下面重点分析点击在雷区后的处理m_poldmine = GetMine(point.x, point.y) /通过坐标获取方块位置/如果游戏处于等待状态if(GameState =GS_WAIT)/启动计时器；SetTimer();/布雷；LayMine();/改变游戏状态为运行；GameState = GS_RUN;/如果游戏处于进行状态if(GameState = GS_RUN)/方块状态为正常时进行处理，对于已经点开的区域不再处理If(方块属性为正常) If( IsMine()/所点击的方格是雷则要进行失败处理Dead();else/不是雷的处理around = GetAroundnum();/获取其周围雷的数目if(around = 0)/如果周围没雷ExpandMines();/展拓空白区域else/如果周围有雷DrawDownNum();/改变此方块属性if(victory() /判断是否胜利胜利处理；Invalidate();/发出重绘消息；(2).右键点击void CLuliangView:OnRButtonDown(UINT nFlags, CPoint point) /游戏处于进行状态是响应右键的条件，右键只能在雷区起作用if(GameState = GS_RUN & point.y 80)NewMine = GetMine(point.x, point.y);/获得点击方块switch(NewMine-uState)/根据方块的属性做不同标记/正常状态的标记为雷，剩余雷数减1case STATE_NORMAL:NewMine-uState = STATE_FLAG;m_LeftMineNum-;break; /被标记为雷的改为未知状态，剩余雷数加1case STATE_FLAG: NewMine-uState = STATE_DICEY; m_LeftMineNum+;break;/被标记为未知状态的改为正常状态case STATE_DICEY: NewMine-uState = STATE_NORMAL;break;default: break;/其他状态的方格，右键均不处理if(Victory()/判断是否胜利胜利处理Invalidate();/发出重绘消息；(3).重新设置游戏，即改变雷数和雷区大小SetMineArea sizedlg;/建立对话框对象sizedlg.DoModal();/弹出对话框XMineNum = sizedlg.m_x_mine_num;/获得雷区宽YMineNum = sizedlg.m_y_mine_num;/获得雷区高MineNum = sizedlg.m_MineNum/获得雷的个数;SizeWindow();/改变窗口大小InitialGame();/初始化方格，计时器，计数器等Invalidate();/发出重绘消息；2.还有一个十分重要的函数就是绘制函数OnDraw（），每次重绘时都会自动调用此函数。它绘制了雷区，计数器区，计时器区以及笑脸区。下面是它所绘制的大体框架：三、 数据结构设计 雷区方格的数据结构（1）为了唯一标识一个方格，设计两个UINT(无符号整数)变量来记录它的行和列；（2）每一个方格有两种属性，雷与非雷，因此需要一个BOOL变量记录其属性；（3）每个方格都有一个状态，比如未被点击过的状态，被标记为雷的状态，打开后周围有一颗雷的状态等等。标志状态有两个作用：a.其状态的不同决定了将其绘制为什么样的图形，比如某方格其状态为“未 被点击过”，那么它会被绘制为；某方格状态为“被标记为雷”，那么它被绘制为；又如某方格状态为“打开后显示1”，被绘制为。b.其状态的不同决定了它被点击后受到不同的处理。比如方格1的状态为“未被点击过”，方格2的状态为“打开后显示1”，当鼠标左键点击方格1的时候，它将会被打开判断是否是雷等操作，而当鼠标点击方格2的时候，它不会被做任何处理；四、 算法设计（1）布雷函数：利用srand(),rand()随机机制产生随机数，分别对列和行取模，便产生了雷的随机位置。但是布雷前，先要判断此随机位置是否已经布上了雷。（2）获得周围雷的数目扫描其周围的所有相邻方格，记录雷数，扫描前要选择合理的起始点，以处理边框上的特殊位置。处理方法是：如果方块处在第0行，扫描起始行为0，否则不变；如果方块处在第0列，扫描起始列为0，否则不变；（3）展拓空白区域展拓原因：当玩家点击的方块周围无雷时，此方块会被重绘为空白，此时没有必要让玩家将其周围一一点开，应直接打开展拓条件：周围雷数为零函数void ExpandMines(UINT row, UINT col)参数：row, col所点击的方块位置算法:递归递归结束条件：某一个方块不需要拓展就是因为其周围的雷数不是零（4）判断胜利 两个条件：1.属性不为雷（ ATTRIB_EMPTY）的方块当前状态在STATE_NUM1和STATE_EMPTY之间（19）2.属性为雷（ATTRIB_MINE)的方块当前状态为STATE_MINE五、 物理实现及结果1. 主要数据结构的物理设计（1）雷区方格的数据结构方块的的结构体typedef struct UINT uRow; /所在雷区二维数组的行UINT uCol; /所在雷区二位数组的列UINT uState; /当前状态UINT uAttrib; / 方块属性（雷或非雷） MINEWND;当前状态宏：#define STATE_NORMAL 0 /正常#define STATE_NUM1 1 /周围有1雷#define STATE_NUM2 2 #define STATE_NUM3 3#define STATE_NUM4 4#define STATE_NUM5 5#define STATE_NUM6 6#define STATE_NUM7 7#define STATE_NUM8 8#define STATE_EMPTY 9#define STATE_FLAG 10 /被右键标记为雷#define STATE_MINE 11 /当失败时把所有的雷标记出#define STATE_ERROR 12 /被右键误标记为雷#define STATE_ERRORCLICK 13/被左键点击为雷#define STATE_DICEY 14 /未知状态 （2）游戏状态#define GS_WAIT1/#defineGS_RUN2/#define GS_FAIL3/#define GS_WIN4/用GameState变量记录游戏的状态，初始化为GS_WAIT2. 核心算法的物理实现 （1）布雷函数：当鼠标第一次点击雷区时布雷void CMineWnd:LayMines(UINT row, UINT col)srand( (unsigned)time( NULL ) ); /埋下随机种子UINT i, j;for(UINT index = 0; index m_uMineNum;) i = rand() % m_uYNum; /取随即数j = rand() % m_uXNum; /保证第一次点击的不是雷if (i = row & j = col) continue;if(m_pMinesij.uAttrib != ATTRIB_MINE) m_pMinesij.uAttrib = ATTRIB_MINE;/雷index+;（2）获得周围雷的数目函数：难点是四个顶点和四边上特殊的方块UINT GetAroundNum(UINT row, UINT col)/寻找合适的起始位置UINT i, j;UINT minRow = (row = 0) ? 0 : row - 1;UINT maxRow = row + 2;UINT minCol = (col = 0) ? 0 : col - 1;UINT maxCol = col + 2; /通过方块的属性（ uAttrib ）来判断是否是雷UINT around;for (i = 10; i 10; i+) for (j = minCol; j maxCol; j+)if (!IsInMineArea(i, j)continue;if (m_pMinesij.uAttrib = ATTRIB_MINE) around+;return around;（3）展拓空白区域void ExpandMines(UINT row, UINT col)判断起始点minRow,maxRow,minCol,maxCol；around = GetAroundNum(row,col)；/获得雷的数目if(around != 0) /递归结束条件其属性标记为相应数字；elsefor（其周围所有的