武汉理工大学数据结构与算法综合实验连连看

1学生学号Xxx实验课成绩学生实验报告书实验课程名称数据结构与算法综合实验开课学院计算机科学与技术学院指导教师姓名xx学生姓名xx学生专业班级xxxx2015--2016学年第2学期2实验课程名称：数据结构与算法综合实验实验项目名称连连看游戏综合实践报告成绩实验者xxx专业班级xxxxx组别同组者完成日期年月日第一部分：实验分析与设计（可加页）一、实验目的和要求1.目的调研连连看游戏，了解连连看游戏的功能和规则等。掌握集成开发工具。掌握C++的基础编程。了解MFC框架，包括MFCDialog应用程序和GDI编程。了解线性结构，重点掌握数组和栈操作，掌握数组的遍历、消子和胜负判断等算法。了解企业软件开发过程，了解系统需求分析和设计，应用迭代开发思路进行项目开发。养成良好的编程习惯和培养软件工程化思维，综合应用“C++编程、MFCDialog、算法、线性结构”等知识，开发“连连看游戏”桌面应用程序，达到掌握和应用线性核心知识的目的。2.要求待开发的连连看游戏称为“欢乐连连看”，使用二维数组来保存游戏地图的数据，实现连连看的核心功能。欢乐连连看的功能有：主界面、开始游戏、消子、判断胜负、提示、重排、计时、游戏模式。主界面游戏主界面就是进行各项操作的入口。开始游戏玩家选择开始游戏模式，进入游戏后，选择开始游戏，系统根据设置的主题风格生成图片布局，以供玩家点击消除。游戏地图大小为640*400，是一个16行乘10列的矩形，分成160个小正方形，存放160张图片，每张图片大小为40*40。消子对玩家选中的两张图片进行判断，判断是否符合消除规则。只有符合以下规则的图片对才能被消除：一条直线连通两条直线连通三条直线连通如果可以消除，从游戏地图中提示连接路线，然后消除这两张图片，并计算相应的积分。如果不能消除，则保持原来的游戏地图。判断胜负当游戏完成后，需要判断游戏胜负。不同模式下判断胜负的规则不同。3基本模式时，如果在五分钟内将游戏地图的所有图片都消除，则提示玩家胜利。休闲模式时，如果游戏地图中所有图片都被消除，则提示玩家获胜。提示可以提示界面上能够消除的一对图片。计时设定一定时间来辅助游戏是否结束。重排根据随机数，重新排列地图上的图片。游戏模式游戏模式有:基本模式、休闲模式和关卡模式三种，可以根据是否定时等规则进行设置。二、分析与设计1.数据结构的设计1)顶点存储添加global.h文件，定义结构体tagVertex,用于保存游戏地图中一个点的行号、列号、值信息。typedefstructtagVertex{introw;//行intcol;//列intinfo;//信息类}Vertex;2)游戏地图存储结构使用二位数组来保存连连看游戏地图，在给没一种图片一个编号，并将这些编号保存在二位数组中。用户在屏幕上选择两张图片，对应为数组中的两组坐标。分别实现三个消子判断算法：一条直线连通、两条直线连通、三条直线连通，并使用者三个算法进项消子判断。若符合消子规则，就在屏幕上消除一对图片，并把数组对应元素清空。①游戏地图中图片种类和重复次数与游戏的级别汉难度有关。图片种类越多，重复次数越小，游戏难度越大，反之则越容易。②只有两张相同的图片才能消除。为保证游戏中的图片能够完全消掉，每种图片出现的次数一定是偶数，即2的倍数。③地图的大小与图片元素种类之间的关系地图的行数*地图的列数=图片种类数*每种图片重复的次数。④地图数据的存储a.用int类型的动态二位数组(int**m_pGameMap)存储地图中元素图片的编号。b.获得某行某列对应的元素编号。2.核心算法设计随机开局算法1)计算游戏中元素个数：行数*列数。2)计算每种花色重复数：行数*列数/花色数。4①判断（行数*列数%花色数）是否为0。如果不为0，则进行异常处理。②判断每一种花色的重复数能否被2整除，如果不能被二整除，则进行异常处理。3)按从左到右，从上到下，将花色数填入游戏地图。实现代码如下：intnRepeatNum=nRows*nCols/nPicNums;intcount=0;for(inti=0;inPicNums;i++){for(intj=0;jnRepeatNum;j++){m_Map[count/nCols][count%nCols]=i;count++;}}4)由于生成的地图是规则的，因此，需要将地图中的花色打乱。实现思路是：随机选择两个元素，将其值对调，重复若干次。消子判断的流程1)获得选中的两张图片的行号和列号。2)判断选中的图片是否同色，不同色，则不能相消。判断选中的图片是否为同一个图片，如果为不为同一个图片，则不能相消。3)判断连通性，如以下三种情况均不满足，则结束。①首先判断能否一条直线连通。②如果不能一条直线连通，则判断能否两条直线连通。③如果不能两条直线连通，则判断能否三条直线连通。4)获得连通路径，绘制连线。5)消除图片一条直线消子算法①判断两个顶点，行是否相同，若相同，则判断两个顶点在X方向是否连通。在CGameLogic类定义RowLink（）函数事项X方向的连通判断。依次判断在X方向两个顶点间每一个顶点，是否都为空，全为空表示可以连通，否则不能连通。实现代码如下：boolCGameLogic::RowLink(intm_Map[10][15],Vertexv1,Vertexv2){//将两个点的列进行调整，使nCol1的值小于nCol2的值introw=v1.row;intcol1=v1.col;intcol2=v2.col;if(col1col2){inttemp=col1;col1=col2;col2=temp;}//判断两个顶点间是否有不为空的图片5for(inti=col1+1;i=col2;i++){if(i==col2){returntrue;}if(m_Map[row][i]!=BLANK){break;}}returnfalse;②判断两个顶点，列是否相同，若相同，则判断两个顶点在Y方向是否连通。在CGameLogic类定义ColLink（）函数事项Y方向的连通判断。依次判断在Y方向两个顶点间每一个顶点，是否都为空，全为空表示可以连通，否则不能连通。实现代码如下：boolCGameLogic::ColLink(intm_Map[10][15],Vertexv1,Vertexv2){introw1=v1.row;introw2=v2.row;intcol=v1.col;if(row1row2){inttemp=row1;row1=row2;row2=temp;}for(inti=row1+1;i=row2;i++){if(i==row2){returntrue;}if(m_Map[i][col]!=BLANK){break;}}returnfalse;}两条直线消子算法若一条直线无法连通，则判断两条直线的情况。在CGameLogic类中定义OneCornerLink（）函数判断两点是否能两条直线连通。先判断两个顶点的X和Y方向的直线相交的两个顶点，是否为空。若能构成两条指向连通，那么相交的顶点必须为空才行。6若顶点有一个为空，则判断该顶点与两个顶点，横向与纵向一条直线是否连通，若都连通，则表示两条直线消子成功，否则不能相消。实现代码如下：boolCGameLogic::OneCornerLink(intm_Map[10][15],Vertexv1,Vertexv2){introw1=v1.row;intcol1=v1.col;introw2=v2.row;intcol2=v2.col;//判断相交的顶点是否为空if(m_Map[row1][col2]==BLANK){//判断两个同行的顶点是否一条直线连通if(LineY(m_Map,row1,row2,col2)&&LineX(m_Map,row1,col1,col2)){VertexV={row1,col2,BLANK};AddVertex(V);returntrue;}}if(m_Map[row2][col1]==BLANK){//判断两个同列顶点是否一条直线连通if(LineY(m_Map,row1,row2,col1)&&LineX(m_Map,row2,col1,col2)){VertexV={row2,col1,BLANK};AddVertex(V);returntrue;}}returnfalse;}三条直线消子算法若两条直线无法连通，则判断三条直线的情况。在CGameLogic类中定义TwoCornerLink()函数判断两点能否三条直线连通。三条直线消子时，假设选择的两张图片的位置为（nRow1，nCol1）和（nRow2，nCol2），则先寻找与Y轴平行的连通线段。如果Y轴没有找到可以连通的三条直线，则寻找以X轴平行的连通线段。1)搜索关键路径假设玩家选择的两个顶点为V0（row0,col0），V3（row3,col3），步骤如下：第一步：从地图的第一行开始扫描，当前扫描到nRow行。第二步：设置拐点：V1（nRow，col0）,V2(nRow,col3)。第三步：判断V1和V2是否水平方向向上连通，如果连通，则V1到V2的连线即为关键路径。如果不连通则接着扫描下一行，重复第二~四步。2)判断三条直线连通采用枚举法判断三条直线连通，假设玩家选择两个顶点为V0和V3，判断三条直7线连通的具体实现的具体步骤如下：①找到其中一条关键路径V1，V2。②判断V1和V0是否连通。③判断V2和V3是否连通。④如果同时满足V1和V0连通，V2和V3连通，则V0和V3满足三条直线连通。否则，在此关键路径下V0和V3不连通，找到下一条关键路径，重复2~4，直到判断出V0和V3是否连通。3)保存连通路径使用栈来保存连通路径中的关键点：起始点V0，拐点V1，拐点V2和终点V3。保存连通路径的步骤如下：①保存其实点V0。②判断是否存在能够满足三条直线消子的关键路径V1、V2。③如果存在，保存顶点V1、V2、V3，如果不存在，在删除起始点V0。实现代码如下：boolCGameLogic::TwoCornerLink(intm_Map[10][16],Vertexv1,Vertexv2){introw1=v1.row;intcol1=v1.col;introw2=v2.row;intcol2=v2.col;for(intcol=0;col16;col++){if(m_Map[row1][col]==BLANK&&m_Map[row2][col]==BLANK){if(LineY(m_Map,row1,row2,col)){if(LineX(m_Map,row1,col1,col)&&LineX(m_Map,row2,col2,col)){VertexV1={row1,col,BLANK};VertexV2={row2,col,BLANK};AddVertex(V1);AddVertex(V2);returntrue;}}}}for(introw=0;row10;row++){if(m_Map[row][col1]==BLANK&&m_Map[row][col2]==BLANK){if(LineX(m_Map,row,col1,col2)){if(LineY(m_Map,row,row1,col1)&&LineY(m_Map,row,row2,col2)){8VertexV1={row,col1,BLANK};VertexV2={row,col2,BLANK};AddVertex(V1);AddVertex(V2);returntrue;}}}}returnfalse;}4)胜负判断算法当所有元素被消掉，进行胜负判断，遍历地图中所有元素的值，当所有元素都为空时，表示获胜，游戏结束，否则继续游戏。实现代码如下：if(m_GameProgress.GetPos()=0&&!cgc.IsBlank(cgc.m_Map)){