迷宫课程设计

课程设计说明书【此页单独打印】课程名称:数据结构与算法B综合课程设计课程代码： 6013799题 目：DFS生成迷宫与迷宫的BFS、DFS搜索年级/专业/班:2012/计算机科学与技术/04班学生姓名学号312012080605426开始时间2012年12月20日完成时间2012年12月24日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总分（100）指导教师签名： 年_月_日

目录摘要TOC\o"1-5"\h\z1前言 41.1问题的提出 41.2任务与分析 4\o"CurrentDocument"2.软件总体设计 5\o"CurrentDocument"2.1开发工具 5\o"CurrentDocument"2.2系统框图 5\o"CurrentDocument"2.3模块功能 62.3.1绘图模块 错误！未定义书签。2.3.2DFS模块 错误！未定义书签。2.3.3BFS模块…… •错误！未定义书签。3.人机界面设计 43.1客户区原始界面 43.2迷宫拆墙界面 43.3DFS走迷宫界面 43.4BFS走迷宫界面 44.功能详细设计 7绘墙 拆墙 迷宫信息文本存储4.4走迷宫(DFS) 4.5走迷宫(BFS) 错误！未定义书签。错误！未定义书签错误！未定义书签错误！未定义书签错误！未定义书签错误！未定义书签结论 205软件测试 错误！未定义书签。错误！未定义书签错误！未定义书签错误！未定义书签错误！未定义书签错误！未定义书签结论 20致谢 20参考文献 错误！未定义书签。摘要迷宫是一种充满复杂通道的建筑物，很难找到从其内部到达入口或从入口到达中心的道路。比喻复杂艰深的问题或难以捉摸的局面。迷宫从古代就有人在研究并加以运用，它拥有千百年的历史，迷宫问题向来经典，有很多人都在研究它，以至于有很多迷宫相关的算法，要走迷宫首先要形成迷宫，这里采用常见的DFS深度优先搜索算法生成迷宫这样生成的迷宫是迷宫各个点所组成图的一个生成树，所以可以保证迷宫中任意两点都有路径到达，并且迷宫中没有环路(完美迷宫)，迷宫拆完墙以后就构成了一条通道，当然为了下一次生成同样的迷宫，迷宫的拆墙信息以及各个单元格的四面墙的信息都应该以文件的形式进行保存，以便下一次读取恢复原来迷宫的形态，走迷宫采用DFS、BFS两种搜索方法，DFS的特点：纵深进行到底，采用STL的stack存储数据。BFS的特点：宽度进行到底，采用STL的queue储存数据。调用gui函数并且采用Sleep()的方式将程序挂起，计算机一边运算一边动态展现，最终到达出口。关键词：DFSBFSGUIstackqueue1前言1.1问题的提出为了更深刻地理解DFS、BFS搜索算法的搜索原理，为了了解gui相关函数的调用，为了将所学算法运用于生活中实际中我们编写了这个走迷宫程序。1.2任务与分析基于图形用户界面GUI的标准“Windows”应用程序。贴图表现：迷宫(二维平面图案，包括墙壁和通道)。动画表现：动态表现迷宫生成和求解的每一步变化过程。迷宫大小：N和M(用户输入)，允许范围：10〜30,缺省值：15和15。迷宫格子：N*M大小的迷宫由N*M个格子构成，每个格子有东、南、西、北四堵墙，迷宫生成过程就是对所有格子进行一次遍历——拆墙过程，遍历完成后迷宫就生成了。迷宫入口和出口：分别在第0行和第N-1行上随机选择。算法要求：(1)生成的迷宫有解；(2)禁用递归程序；(3)保证每次生成的迷宫不同，这要求生成时用随机函数(时间种子)。迷宫类型：生成的是完美迷宫即单连通迷宫，迷宫中不存在环，且不存在不可访问区域，迷宫中任意两点之间有且仅有唯一的路径(参考：图的生成树)。文件存储：将生成的迷宫保存在文件中(用文本文件，迷宫数据的存储格式自定)；迷宫求解时，从相应的迷宫文件中读取迷宫数据，然后求解。界面设计要求操作流程简便合理，操作界面美观自然，符合用户一般操作习惯。界面简洁美观，配色和谐，比例合适，符合大多数人的审美趣向。菜单设置“使用说明”，介绍本软件的开发者、特色、各项功能及使用。2.软件总体设计2.1开发工具开发工具：visualC++6.0（企业版）优点：模块加载速度快，界面简单易操作开发环境：windows7（旗舰版x64系统）运行环境windows95以上2.2系统框图（1）系统组成框图WinMain（函数入口）DFSWinMain（函数入口）DFS走迷宫BFS走迷宫DFS（拆墙）图2-12）系统流程图：

2.3模块功能软件开发方式：SDKGUI函数模块：DrawWhiteGround(HDChdc);//将整个客户区绘制为白色DrawRedBlock(HDChdc,intl,intt,intr,intb);//绘制迷宫起始点与终止点八、、DrawRect (HDChdc, intl, intt, intr, intb);//绘制单元方格DrawCell (HDChdc, intl, intt, intr, intb);//绘制移动方块DrawGamePlace(HDChdc,intcol,introw);//在客户区绘满单元格Adj(intx,inty,bool*visited,intcol);//判断该单元格是否有没有被访问的相邻单元格Adj_NoWall(intx,inty,bool*visited,Wall*wall,intcol);//判断该单元格是否有没有被访问的相邻单元格并且周围没有墙可以访问Replace(HDChdc,intx,inty,intz,intk);//拆墙(用白色划线替换红色划线)文件操作模块：WriteDocument(MazeEdge*mazeedge,Wall*wall,inti);//将迷宫拆墙数据写入txt文件中ReadDocument(HDChdc);//从txt文件中读取迷宫拆墙数据核心算法模块：DrawPath(HDChdc,intw,inth);//迷宫拆墙DFS(HDChdc);//深度优先搜索寻找迷宫路径BFS(HDChdc);//广度优先搜索寻找迷宫路径动态效果关键函数：Sleep()3人机界面设计

图3-1客户区原始界面图3-2迷宫拆墙界面图3-3DFS走迷宫界面图3-4BFS走迷宫界面4功能详细设计GUI函数模块：1)//将整个客户区绘制为白色voidDrawWhiteGround(HDChdc){intcol,row;std::ifstreamf("C:\\迷宫拆墙数据.txt");f>>col>>row;f.close();HBRUSHhbrush=CreateSolidBrush(RGB(255,255,255));SelectObject(hdc,hbrush);Rectangle(hdc,0,0,col*CELL,row*CELL);DeleteObject(hbrush);}2)//绘制迷宫起始点与终止点voidDrawRedBlock(HDChdc,intl,intt,intr,intb){HBRUSHhbrush=CreateSolidBrush(RGB(255,0,0));SelectObject(hdc,hbrush);Rectangle(hdc,l,t,r,b);DeleteObject(hbrush);}//画单元格，后面四个参数依次为左上坐标和右下坐标voidDrawRect(HDChdc,intl,intt,intr,intb){MoveToEx(hdc,l,t,NULL);//将起始点移动到(l,t)LineTo(hdc,r,t);LineTo(hdc,r,b);LineTo(hdc,l,b);LineTo(hdc,l,t);}//用绿色画刷画移动目标voidDrawCell(HDChdc,intl,intt,intr,intb){HBRUSHhbrush;hbrush=CreateSolidBrush(RGB(0,255,0));//绿色画刷SelectObject(hdc,hbrush);Rectangle(hdc,l,t,r,b);DeleteObject(hbrush);}//在客户区绘满单元格voidDrawGamePlace(HDChdc,intcol,introw){inti,j;HPENhpen1;hpen1=CreatePen(PS_SOLID,1,RGB(255,0,0));//绘制游戏区域方格线(红色)SelectObject(hdc,hpen1);for(i=0;i<row;i++)for(j=0;j<col;j++)DrawRect(hdc,j*CELL,i*CELL,(j+1)*CELL,(i+1)*CELL);DeleteObject(hpen1);}//判断该单元格是否有没有被访问的相邻单元格boolAdj(intx,inty,bool*visited,intcol){if((x-1>-1)&&!visited[y*col+x-1]||(x+1<W)&&!visited[y*col+x+1]||\y-1>-1&&!visited[(y-1)*col+x]||y+1<H&&!visited[(y+1)*col+x])returntrue;returnfalse;}//判断该单元格是否有没有被访问的相邻单元格并且周围没有墙可以访问boolAdj_NoWall(intx,inty,bool*visited,Wall*wall,intcol){if((x-1>-1)&&!visited[y*col+x-1]&&wall[y*col+x].wall_l==0||(x+1<W)&&!visited[y*col+x+1]&&wall[y*col+x].wall_r==0||\y-1>-1&&!visited[(y-1)*col+x]&&wall[y*col+x].wall_t==0||y+1<H&&!visited[(y+1)*col+x]&&wall[y*col+x].wall_b==0)returntrue;returnfalse;}//拆墙(用白色划线替换红色划线)voidReplace(HDChdc,intx,inty,intz,intk){HPENhpen;hpen=CreatePen(PS_SOLID,1,RGB(255,255,255));SelectObject(hdc,hpen);MoveToEx(hdc,x,y,NULL);LineTo(hdc,z,k);DeleteObject(hpen);}文件操作模块：//将迷宫拆墙数据写入txt文件中voidWriteDocument(MazeEdge*mazeedge,Wall*wall,inti){intj;std::ofstreamf("C:\\迷宫拆墙数据.txt");f<<W<<""<<H<<std::endl;//写入拆墙数据for(j=0;j<i+1;j++)f<<mazeedge[j].x<<""<<mazeedge[j].y<<""\<<mazeedge[j].z<<""<<mazeedge[j].w<<std::endl;f.close();std::ofstreamf1("C:\\每个单元格四面墙的数据.txt");//写入每个单元格四面墙的数据for(j=0;j<i+2;j++)f1<<wall[j].wall_l<<""<<wall[j].wall_t<<""\<<wall[j].wall_r<<""<<wall[j].wall_b<<std::endl;f1.close();}2)//从txt文件中读取迷宫拆墙数据boolReadDocument(HDChdc){intcol,row,i;MazeEdge*mazeedge;std::ifstreamf("C:\\迷宫拆墙数据.txt");if(f.fail())//打开文件失败returnfalse;else{f>>col>>row;f.close();}DrawGamePlace(hdc,col,row);//在客户区绘满红色单元格mazeedge=newMazeEdge[col*row-1];f.open("C:\\迷宫拆墙数据.txt");f>>col>>row;for(i=0;i<col*row-l;i++)//从txt文档中读入数据f>>mazeedge[i].x>>mazeedge[i].y>>\mazeedge[i].z>>mazeedge[i].w;f.close();for(i=0;i<col*row-l;i++)//拆墙Replace(hdc,mazeedge[i].x,mazeedge[i].y,mazeedge[i].z,mazeedge[i].w);returntrue;}核心算法模块：1)//迷宫拆墙voidDrawPath(HDChdc,intcol,introw){intx,y,temp,i(-1);bool*visited; //访问标记POSITION*position;//储存每个单元格的坐标POSITIONw;std::stack<POSITION>Stack;MazeEdge*mazeedge;Wall*wall;//储存每个单元格的墙的情况wall=newWall[col*row];//申请col*row个单元格for(x=0;x<row;x++)//请所有单元格的四面墙初始化为都有状态for(y=0;y<col;y++){wall[x*col+y].wall_l=1;wall[x*col+y].wall_t=1;wall[x*col+y].wall_r=1;wall[x*col+y].wall_b=1;}visited=newbool[col*row];//访问标记for(x=0;x<row;x++)for(y=0;y<col;y++)visited[x*col+y]=false;//初始为未访问状态position=newPOSITION[col*row];for(x=0;x<row;x++)//给每个点定位for(y=0;y<col;y++){position[x*col+y].x=y*CELL;position[x*col+y].y=x*CELL;position[x*col+y].index_x=y;position[x*col+y].index_y=x;}mazeedge=newMazeEdge[col*rowT];//—棵树有顶点数-1条边MessageBox(NULL,TEXT(〃现在开始拆墙〃)，TEXT(〃消息〃)，NULL);srand(time(NULL));//系统时间作随机种子x=rand()%col;//随机产生起始点y=rand()%row;Stack.push(position[y*col+x]);//迷宫入口进栈visited[y*col+x]=true;//标记已经访问过while(!Stack.empty()){w=Stack.top();while(Adj(w.index_x,w.index_y,visited,col))//如果该单元格有没有被访问{temp=rand()%4;if(temp==0&&(w.index_x+1<col)&&!visited[w.index_y*col+w.index_x+1])//右{Sleep(50);i++;mazeedge[i].x=w.x+CELL;/*记录迷宫的拆墙数据*/mazeedge[i].y=w.y;mazeedge[i].z=w.x+CELL;mazeedge[i].w=w.y+CELL;wall[w.index_y*col+w.index_x].wall_r=0;//单元格(w.index_x,w.index_y)wall[w.index_y*col+w.index_x+1].wall_l=0;(w.index_x+1,w.index_y)的左墙被拆除Replace(hdc,w.x+CELL,w.y,w.x+CELL,w.y+CELL);//拆右竖墙visited[w.index_y*col+w.index_x+l]=true;//标记已经访问过的单元格Stack.push(position[w.index_y*col+w.index_x+1]);//符合条件的相邻单元w=Stack.top();}if(temp==1&&(w.index_x—l>—l)&&!visited[w.index_y*col+w.index_x—l])//左移{Sleep(50);i++;mazeedge[i].x=w.x;/*记录迷宫的拆墙数据*/mazeedge[i].y=w.y;mazeedge[i].z=w.x;mazeedge[i].w=w.y+CELL;wall[w.index_y*col+w.index_x].wall_l=0;wall[w.index_y*col+w.index_x—1].wall_r=0;Replace(hdc,w.x,w.y,w.x,w.y+CELL);//拆左竖墙，左拆与右拆不一样visited[w.index_y*col+w.index_xT]=true;//标记已经访问过的单元格Stack.push(position[w.index_y*col+w.index_x—1]);w=Stack.top();}if(temp==2&&(w.index_y—1>—1)&&!visited[(w.index_y—1)*col+w.index_x]){Sleep(50);i++;mazeedge[i].x=w.x;/*记录迷宫的拆墙数据*/mazeedge[i].y=w.y;mazeedge[i].z=w.x+CELL;mazeedge[i].w=w.y;wall[w.index_y*col+w.index_x].wall_t=0;wall[(w.index_y—1)*col+w.index_x].wall_b=0;Replace(hdc,w.x,w.y,w.x+CELL,w.y);//拆横墙visited[(w.index_yT)*col+w.index_x]=true;//标记已经访问过的单元格Stack.push(position[(w.index_y—1)*col+w.index_x]);w=Stack.top();}if(temp==3&&(w.index_y+1<row)&&!visited[(w.index_y+1)*col+w.index_x]){Sleep(50);i++;mazeedge[i].x=w.x;/*记录迷宫的拆墙数据*/mazeedge[i].y=w.y+CELL;mazeedge[i].z=w.x+CELL;mazeedge[i].w=w.y+CELL;wall[w.index_y*col+w.index_x].wall_b=0;wall[(w.index_y+1)*col+w.index_x].wall_t=0;Replace(hdc,w.x,w.y+CELL,w.x+CELL,w.y+CELL);//拆横墙visited[(w.index_y+1)*col+w.index_x]=true;//标记已经访问过的单元格Stack.push(position[(w.index_y+1)*col+w.index_x]);w=Stack.top();}}Stack.pop();//回溯}WriteDocument(mazeedge,wall,i);//将迷宫拆墙数据写入txt文件}//深度优先搜索寻找迷宫路径voidDFS(HDChdc){intcol,row,entrance,exit,i,j;bool*visited=NULL;//访问标示boolstatus(false);//走迷宫状态POSITION*position二NULL;//记录各个单元的坐标POSITIONw;//临时中间变量Wall*wall=NULL;//储存单元格四面墙的信息std::stack<POSITION>Stack;std::ifstreamf("C:\\迷宫拆墙数据.txt"); /*读迷宫规模数据*/f>>col>>row;//从txt文件中获取原来迷宫的规模f.close();wall=newWall[col*row];std::ifstreamf1("C:\\每个单元格四面墙的数据.txt");/*读迷宫墙的信息*/for(i=0;i<col*row;i++)//从txt文档中读入每个单元格四面墙数据f1>>wall[i].wall_l>>wall[i].wall_t>>wall[i].wall_r>>wall[i].wall_b;f1.close();srand(time(NULL));//系统时间作随机种子entrance=rand()%col;//随机在迷宫第一行和最后一行分别产生入口与出口exit=rand()%col;visited=newbool[col*row];//访问标记for(i=0;i<row;i++)for(j=0;j<col;j++)visited[i*col+j]=false;//初始为未访问状态position=newPOSITION[col*row];for(i=0;i<row;i++)//给每个点定位for(j=0;j<col;j++){position[i*col+j].x=j*CELL;position[i*col+j].y=i*CELL;position[i*col+j].index_x=j;position[i*col+j].index_y=i;}Stack.push(position[entrance]);//迷宫入口进栈visited[entrance]=true;DrawRedBlock(hdc,entrance*CELL+6,6,(entrance+1)*CELL-6,CELL-6);DrawRedBlock(hdc,exit*CELL+6,(row-1)*CELL+6,(exit+1)*CELL-6,row*CELL-6);//绘制迷宫出口while(!Stack.empty()&&!status){w=Stack.top();while(Adj_NoWall(w.index_x,w.index_y,visited,wall,col))//女口果有还{if(wall[w.index_y*col+w.index_x].wall_b==0&&!visited[(w.index_y+1)*col+w.index_x]){Sleep(200);DrawCell(hdc,w.x+6,w.y+CELL+6,w.x+CELL-6,w.y+2*CELL-6);visited[(w.index_y+1)*col+w.index_x]=true;Stack.push(position[(w.index_y+l)*col+w.index_x]);//入栈w=Stack.top();}elseif(wall[w.index_y*col+w.index_x].wall_r==0&&!visited[(w.index_y)*col+w.index_x+1]){Sleep(200);DrawCell(hdc,w.x+CELL+6,w.y+6,w.x+2*CELL-6,w.y+CELL-6);//使移动目visited[w.index_y*col+w.index_x+1]=true;Stack.push(position[w.index_y*col+w.index_x+l]);//入栈w=Stack.top();elseif(wall[w.index_y*col+w.index_x].wall_l==0&&!visited[w.index_y*col+w.index_x-1])Sleep(200);DrawCell(hdc,w.x-CELL+6,w.y+6,w.x-6,w.y+CELL-6);visited[w.index_y*col+w.index_x-1]=true;Stack.push(position[w.index_y*col+w.index_x-1]);//入栈w=Stack.top();}elseif(wall[w.index_y*col+w.index_x].wall_t==0&&!visited[(w.index_y-1)*col+w.index_x]){Sleep(200);DrawCell(hdc,w.x+6,w.y-CELL+6,w.x+CELL-6,w.y-6);visited[(w.index_y-1)*col+w.index_x]=true;Stack.push(position[(w.index_y-1)*col+w.index_x]);//入栈w=Stack.top();if(w.index_y==row-1&&w.index_x==exit)//如果到达迷宫出口则停止搜索{DrawRedBlock(hdc,exit*CELL+6,(row-1)*CELL+6,(exit+1)*CELL-6,row*CELL-6);MessageBox(NULL,TEXT("成功走出迷宫!"),TEXT("Congratunations"),MB_ICONINFORMATION);status=true;break;}}Stack.popO;//回溯}}//广度优先搜索寻找迷宫路径voidBFS(HDChdc){intcol,row,entrance,exit,i,j;bool*visited=NULL;//访问标示boolstatus(false);//走迷宫状态POSITION*position二NULL;//记录各个单元的坐标POSITIONu;//临时中间变量Wall*wall=NULL;//储存单元格四面墙的信息std::queue<POSITION>Queue;charBuffer[20];std::ifstreamf("C:\\迷宫拆墙数据.txt"); /*读迷宫规模数据*/f>>col>>row;//从txt文件中获取原来迷宫的规模f.close();wall=newWall[col*row];std::ifstreamf1("C:\\每个单元格四面墙的数据.txt");/*读迷宫墙的信息*/for(i=0;i<col*row;i++)//从txt文档中读入每个单元格四面墙数据f1>>wall[i].wall_l>>wall[i].wall_t>>wall[i].wall_r>>wall[i].wall_b;f1.close();srand(time(NULL));//系统时间作随机种子entrance=rand()%col;//随机在迷宫第一行和最后一行分别产生入口与出口exit=rand()%col;visited=newbool[col*row];//访问标记for(i=0;i<row;i++)for(j=0;j<col;j++)visited[i*col+j]=false;//初始为未访问状态position=newPOSITION[col*row];for(i=0;i<row;i++)//给每个点定位for(j=0;j<col;j++){position[i*col+j].x=j*CELL;position[i*col+j].y=i*CELL;position[i*col+j].index_x=j;position[i*col+j].index_y=i;}Queue.push(position[entrance]);//迷宫入口进队列visited[entrance]=true;DrawRedBlock(hdc,entrance*CELL+6,6,(entrance+1)*CELL-6,CELL-6);DrawRedBlock(hdc,exit*CELL+6,(row-1)*CELL+6,(exit+1)*CELL-6,row*CELL-6);//绘制迷宫出口while(!Queue.empty()){u=Queue.front();Queue.pop();if(Adj_NoWall(u.index_x,u.index_y,visited,wall,col)){if((u.index_y+1<row)&&!visited[(u.index_y+1)*col+u.index_x]&&wall[u.index_y*col+u.index_x].wall_b==O)//如果作相邻单元格没有被访问过，并且可以被访问{Sleep(100);DrawCell(hdc,u.x+6,u.y+CELL+6,u.x+CELL-6,u.y+2*CELL-6);visited[(u.index_y+1)*col+u.index_x]=true;Queue.push(position[(u.index_y+1)*col+u.index_x]);//下单元格进队列}if((u.index_x-1>-1)&&!visited[u.index_y*col+u.index_x-1]&&wall[u.index_y*col+u.index_x].wall_l==O)//如果作相邻单元格没有被访问过，并且可以被访问{Sleep(100);DrawCell(hdc,u.x-CELL+6,u.y+6,u.x-6,u.y+CELL-6);//画左单元格visited[u.index_y*col+u.index_x-1]=true;Queue.push(position[u.index_y*col+u.index_x-l]);//左单元格进队列}if((u.index_x+1<col)&&!visited[