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

文档介绍：该【最新武汉理工大学数据结构与算法综合实验连连看 】是由【guoxiachuanyue007】上传分享，文档一共【22】页，该文档可以免费在线阅读，需要了解更多关于【最新武汉理工大学数据结构与算法综合实验连连看 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。精品文档
精品文档
精品文档
学生学号
Xxx
实验课成绩
口
实验课程名称
数据结构与算法综合实验
开课学院
计算机科学与技术学院
指导教师姓名
XX
学生姓名
XX
学生专业班级
XXXX
2015—2016学年第2学期
精品文档
精品文档
精品文档
实验课程名称:数据结构与算法综合实验
实验项目名称
连连看游戏综合实践
报告成绩
实验者
XXX
专业班级
XXXXX
组别
同组者
完成日期
年月日
第一部分:实验分析与设计(可加页)
一、实验目的和要求

•调研连连看游戏,了解连连看游戏的功能和规则等。
•掌握集成开发工具。
•掌握C++的基础编程。
了解MFC框架,包括MFCDialog应用程序和GDI编程。
了解线性结构,重点掌握数组和栈操作,掌握数组的遍历、消子和胜负判断等算法。
了解企业软件开发过程,了解系统需求分析和设计,应用迭代开发思路进行项目开发。
养成良好的编程****惯和培养软件工程化思维,综合应用“C++编程>MFCDialog、算法、线性结构”等知识,开发“连连看游戏”桌面应用程序,达到掌握和应用线性核心知识的目的。
2•要求
待开发的连连看游戏称为“欢乐连连看”,使用二维数组来保存游戏地图的数据,实现连连看的核心功能。欢乐连连看的功能有:主界面、开始游戏、消子、判断胜负、提示、重排、计时、游戏模式。
•主界面游戏主界面就是进行各项操作的入口。
•开始游戏
玩家选择开始游戏模式,进入游戏后,选择开始游戏,系统根据设置的主题风格生成图片布局,以供玩家点击消除。
游戏地图大小为640*400,是一个16行乘10列的矩形,分成160个小正方形,存放160张图片,每张图片大小为40*40。
•消子
对玩家选中的两张图片进行判断,判断是否符合消除规则。只有符合以下规则的图片对才能被消除:
一条直线连通
❖两条直线连通
❖三条直线连通
如果可以消除,从游戏地图中提示连接路线,然后消除这两张图片,并计算相应的积分。如果不能消除,则保持原来的游戏地图。
•判断胜负
精品文档
精品文档
当游戏完成后,需要判断游戏胜负。不同模式下判断胜负的规则不同。
精品文档
❖基本模式时,如果在五分钟内将游戏地图的所有图片都消除,则提示玩家胜利。
❖休闲模式时,如果游戏地图中所有图片都被消除,则提示玩家获胜。
•提示
可以提示界面上能够消除的一对图片。
•计时
设定一定时间来辅助游戏是否结束。
•重排
根据随机数,重新排列地图上的图片。
•游戏模式
游戏模式有:基本模式、休闲模式和关卡模式三种,可以根据是否定时等规则进行设置。
二、分析与设计
数据结构的设计
1)顶点存储
,定义结构体tagVertex,用于保存游戏地图中一个点的行号、列号、值信息。
typedefstruettagVertex
{
introw;//行
intcol;//列
intinfo;//信息类
}Vertex;
2)游戏地图存储结构
使用二位数组来保存连连看游戏地图,在给没一种图片一个编号,并将这些编号保存在二位数组中。
用户在屏幕上选择两张图片,对应为数组中的两组坐标。分别实现三个消子判断算法:一条直线连通、两条直线连通、三条直线连通,并使用者三个算法进项消子判断。若符合消子规则,就在屏幕上消除一对图片,并把数组对应元素清空。
游戏地图中图片种类和重复次数与游戏的级别汉难度有关。图片种类越多,重复次数越小,游戏难度越大,反之则越容易。
只有两张相同的图片才能消除。为保证游戏中的图片能够完全消掉,每种图片出现的次数一定是偶数,即2的倍数。
地图的大小与图片元素种类之间的关系
地图的行数*地图的列数二图片种类数*每种图片重复的次数。
地图数据的存储
用int类型的动态二位数组(int**m_pGameMap)存储地图中元素图片的编号。
获得某行某列对应的元素编号。
核心算法设计
•随机开局算法
精品文档
精品文档
1)计算游戏中元素个数:行数*列数。
2)计算每种花色重复数:行数*列数/花色数。
判断(行数*列数%花色数)是否为0。如果不为0,则进行异常处理。
精品文档
判断每一种花色的重复数能否被2整除,如果不能被二整除,则进行异常处理。
3)按从左到右,从上到下,将花色数填入游戏地图。
实现代码如下:
intnRepeatNum=nRows*nCols/nPicNums;
intcount二0;
for(inti二0;i<nPicNums;i++)
{
for(intj=0;j〈nRepeatNum;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)
{
//将两个点的列进行调整,使nColl的值小于nCol2的值
;
;
intcol2=;
if(col1>col2)
{
inttemp=col1;
col1=col2;
精品文档
精品文档
col2二temp;
}
//判断两个顶点间是否有不为空的图片
for(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){
;
introw2=;
intcol=;
if(row1>row2)
{
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方向的直线相交的两个顶点,是否为空。若能构成两条指向连通,那么相交的顶点必须为空才行。
若顶点有一个为空,则判断该顶点与两个顶点,横向与纵向一条直线是否连通,若都连通,则表示两条直线消子成功,否则不能相消。
实现代码如下:
精品文档
精品文档
精品文档
boolCGameLogic::OneCornerLink(intm_Map[10][15],Vertexv1,Vertexv2){
;
intcol1=;
introw2=;
intcol2=;
//判断相交的顶点是否为空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()函数判断两点能否三条直线连通。
三条直线消子时,假设选择的两张图片的位置为(nRowl,nColl)和(nRow2,nCol2),则先寻找与Y轴平行的连通线段。
如果Y轴没有找到可以连通的三条直线,则寻找以X轴平行的连通线段。
搜索关键路径
假设玩家选择的两个顶点为VO(rowO,colO),V3(row3,col3),步骤如下:第一步:从地图的第一行开始扫描,当前扫描到nRow行。
第二步:设置拐点:VI(nRow,col0),V2(nRow,col3)。
第三步:判断VI和V2是否水平方向向上连通,如果连通,则VI到V2的连线即为关键路径。如果不连通则接着扫描下一行,重复第二~四步。
判断三条直线连通
采用枚举法判断三条直线连通,假设玩家选择两个顶点为V0和V3,判断三条直线连通的具体实现的具体步骤如下:
找到其中一条关键路径VI,V2。
判断VI和V0是否连通。
判断V2和V3是否连通。
精品文档
如果同时满足VI和V0连通,V2和V3连通,则V0和V3满足三条直线连通。否则,在此关键路径下V0和V3不连通,找到下一条关键路径,重复2~4,直到判断出V0和V3是否连通。
保存连通路径
使用栈来保存连通路径中的关键点:起始点V0,拐点VI,拐点V2和终点V3。保存连通路径的步骤如下:
保存其实点V0。
判断是否存在能够满足三条直线消子的关键路径VI、V2。
如果存在,保存顶点VI、V2、V3,如果不存在,在删除起始点V0。
实现代码如下:
boolCGameLogic::TwoCornerLink(intm_Map[10][16],Vertexv1,Vertexv2){
introw1=f..row;
;
introw2=;
intcol2=;
for(intcol=0;col<16;col++)
{
if(m_Map[row1][col]==BLANK&&i_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(Vl);
AddVertex(V2);
returntrue;
}
}
}
}
for(introw=0;row<10;row++)
{
if(m_Map[row][col1]==BLANK&&i_Map[row][col2]==BLANK)
{
if(LineX(m_Map,row,col1,col2))
{
if(LineY(m_Map,row,row1,col1)&&LineY(m_Map,row,row2,col2))
{
VertexV1={row,col1,BLANK};
VertexV2={row,col2,BLANK};
AddVertex(Vl);
精品文档
精品文档
精品文档
AddVertex(V2);
returntrue;
精品文档
精品文档
精品文档
}
}
}
}
returnfalse;
}
胜负判断算法
当所有元素被消掉,进行胜负判断,遍历地图中所有元素的值,当所有元素都为空时,表示获胜,游戏结束,否则继续游戏。
实现代码如下:
if(()<=0&&!()){
KillTimer(PLAY_TIMER_ID);
intresult=MessageBox(_T("很遗憾,时间到了!,是否重新开始游戏?〃),_T("提示〃));
if(result二IDOK){
GetDlgItem(IDC_BUTTON_START)->EnableWindow(TRUE);
}
else{
exit(0);
}
IsPlaying=false;
}
elseif(()>0&&()){
KillTimer(PLAY_TIMER_ID);
intresult;
result二MessageBox(_T(〃获胜!是否重新开始游戏?〃),_T("提示"));
if(result二IDOK){
GetDlgItem(IDC_BUTTON_START)->EnableWindow(TRUE);
}
else{
exit(0);
}
}
重排
当进行游戏的过程中会出现无法再进行消子的情况,点击重排按钮就可以将剩下子进行随机重排以便客户能够正常进行消子操作。首先在CGameLogic类中定义一个DisOrderMap()函数来对剩下的元素进行重排,实现代码如下:voidCGameLogic::DisOrderMap(intm_Map[10][16])
{—
intnRows=10;
intnCols=16;
srand((int)time(NULL));
精品文档
精品文档
精品文档