迷宫的路由与生成课程设计说明书数据结构与算法设计综合设计.doc

迷宫的生成与路由课程设计说明书课 程 名 称: 数据结构与算法设计综合设计课 程 代 码: 题 目: 迷宫的生成与路由 年级/专业/班: 学 生 姓 名: 学 号: 开 始 时 间: 年 月 日完 成 时 间: 年 月 日课程设计成绩：平时学习态度与效果（30）技术水平与实际能力（30）团队协作与技术创新（10分）设计说明书撰写质量（30）总 分（100）指导教师签名： 年 月 日目 录 1 需求分析12 概要设计33详细设计94调试分析205用户使用说明226测试结果247结论26致谢29参考文献3065摘 要 用c+语言编写的生成一个nm(n行m列)的迷宫，完成迷宫的组织和存储，并实现迷宫路由算法。（1）使用二维数组matrixmn表示迷宫，其中m,n为迷宫的行、列数，当元素值为0时表示该点是通路，当元素值为1时表示该点是墙。在每一点都有4种方向可以走，可以用数组wall4来表示每一个方向上的墙，用另一个二维数组graphmn记录墙和节点的情况。（2）选用深度优先算法和广度优先算法寻找路径，迷宫由程序自动创建。关键词：迷宫生成、广度优先、深度优先 引 言 1 需求分析 设计算法生成一个n*m（n 行m 列）的迷宫，并完成迷宫的组织和储存。实现两种不同的迷宫算法：广度优先，深度优先算法。 要求： 1n 和m 是用户可配置的，缺省值为50 和50。 2迷宫的入口和出口分别在第0行和第n-1行上，随机选择。 3生成迷宫要求是随机，且连通的。4. 迷宫具有多条分支路线 。5. 进行深度优先探索迷宫路径并进行输出。6. 进行广度优先探索迷宫路径并进行输出。7实现图形化界面显示。8. 在图形界面输出寻路过程坐标。8. 实现按钮事件处理的图形用户界面交互。1.1任务与分析随机生成一个迷宫（由用户规定其大小）并使用。算法分析迷宫是连通的。使用图形表示，并分别在迷宫的第一行和最后一行随机选择出口和入口，输出可通迷宫的最佳路径。任务一：迷宫随机生成算法的实现。任务二：迷宫深度.优先搜索算法实现。任务三：迷宫广度优先搜索算法实现。任务三：进行图形界面的表示。分析：对三大主要功能模块进行三大主类设计，分别为maze类，dfs类，bfs类，最后使用mfc应用程序进行图形界面的表示。1.2测试数据m, n 取默认值50，50m, n 取默认值20，20m, n 取默认值60, 602 概要设计（此处说明本课程设计题目的模块划分及各模块的功能介绍和对应的函数名（原型）以及各模块间的层次（调用）关系以框图描述）1 本系统所设计的函数见表2.1mazecell类函数名称函数原型功能描述mazecellmazecell();迷宫格对象初始化。maze类函数名称函数原型功能描述mazemaze(int m = 49, int n = 49)初始化迷宫行数和列数，构造节点矩阵createmazevoid createmaze()随机创建课连通迷宫printmazevoid printmaze()在dos界面打印迷宫hasunaccessadjnodebool hasunaccessadjnode(int,int)判断下一节点是否可以访问breakwallvoid breakwall(mazecell*)拆掉墙，使两节点连通tonextnodevoid tonextnode()移动当前节点到下一节点makeromdanstartandendvoid makeromdanstartandend()随机生成入口和出口getgraphrowint getgraphrow()返回迷宫矩阵的行数getgraphcolumnint getgraphcolumn()返回迷宫矩阵的列数mazemaze()销毁迷宫，释放内存getgraphint* getgraph()返回迷宫的矩阵数组coordinate类函数名称函数原型功能描述coordinatecoordinate(int, int)coordinate()对象手动初始化以及默认初始化getxint getx();获得坐标x值getyint gety();获得坐标y值dfs类函数名称函数原型功能描述dfsdfs(int *graph, int, int );dfs对象初始化mazepathvoid mazepath();dfs算法寻找生成迷宫路径haspathbool haspath(int x, int y);有可访问迷宫格判断printpathvoid printpath();dos界面打印路径getvalueint getvalue(int, int);获得dfs对象某个迷宫格的value值bfs类函数名称函数原型功能描述bfsbfs(int *graph, int, int );bfs对象初始化mazepathvoid mazepath();bfs算法寻找生成迷宫路径haspathbool haspath(int x, int y);有可访问迷宫格判断printpathvoid printpath();dos界面打印路径getvalueint getvalue(int, int);获得bfs对象某个迷宫格的value值mfc应用程序函数名称函数原型功能描述onbnclickedcreatemazeonbnclickedcreatemaze()点击“生成迷宫”按钮随机生成迷宫，并且在窗口进行显示onbnclickeddfsonbnclickeddfs()点击“dfs寻路”按钮在生成迷宫上进行dfs寻路，在窗口显示onbnclickedbfsonbnclickedbfs()点击“bfs寻路”按钮在生成迷宫上进行bfs寻路，在窗口显示onbnclickedexitonbnclickedexit()点击“退出按钮”,程序关闭退出onbnclickedaboutonbnclickedabout()点击“关于”按钮，显示程序使用说明及其他2 本系统函数的调用关系见图2.1omfc程序初始化按钮：生成迷宫按钮：dfs寻路按钮：bfs寻路按钮：退出按钮：关于使用maze类创建一个对象，随机生成迷宫使用dfs类创建一个对象，进行dfs路径寻找使用bfs类创建一个对象，今夏bfs路径寻找进行bfs路径寻找退出并关闭应用程序弹出窗口，显示使用说明等内容maze类对象创建构造函数进行初始化，构建节点矩阵和迷宫矩阵createmaze函数根据节点矩阵进行迷宫的随机创建，并将生成迷宫保存在迷宫矩阵中迷宫随机生成完成算法阐述：迷宫节点以及相关功能函数定义规定墙占用格子规定每个节点代表一个可通过格子，节点有四面墙边框为墙采用深度优先算法生成迷宫if 存在可访问节点if 存在当前节点可访问的邻节点随机获得邻节点清空当前结点和邻节点中间的墙当前结点入栈设置邻节点属性为已访问邻节点置为当前结点else if 若栈不为空令栈顶节点为当前结点else随机取节点置为当前结点dfs对象创建dfs对象初始化mazepath()进行dfs寻路，并将结果保存在矩阵中dfs寻路完成算法阐述：.使用graph进行dfs搜索，graph为二维数组，其中1为墙，0为路while 存在未访问迷宫格if 存在当前迷宫格可访问的邻格子当前迷宫格周围（上下左右）存在格子为0if 存在向下的格子当前格子入栈向下邻格子设为当前格子访问数+else当前格子入栈邻格子设为当前格子访问数+else if 若栈不为空令栈顶格子为当前格子else随机取格子置为当前格子bfs对象创建bfs对象初始化mazepath()进行bfs寻路，并将结果保存在矩阵中bfs寻路完成算法阐述：.cur = startcur入队while（队不空）if(到达出口)breakif(有可访问邻点)该邻点入队设置该邻点已访问cur = frontfront 出队3详细设计（对概要设计部分所介绍的功能模块进行详细介绍及实现。并给出相应函数的定义即实现函数。）1. 节点类型和指针类型 mazecell* matrix 存储迷宫节点的数组 stackmazestack 存放节点的堆栈 迷宫中节点类型的定义： typedef class mazecell private: bool isaccessed; /可访问性 int x, y; /坐标 int wall4; /四面墙 bool flags; /标记一个节点是否已被访问mazenode;2. 迷宫的操作（1） 创建迷宫void maze:createmaze()currentcell = &matrix00; /从0,0开始访问currentcell-isaccessed = true;/初始点为0,0 标记为真 accessed += 1; /访问节点加1tonextnode(); /寻找下一节点for (int i = 0; irow; i+)/将每一行节点的上下墙（也有是可能已经被拆掉成为可走的格子）弄为迷宫里的该节点格子上下格子for (int j = 0; jcolumn; j+)graph2 * i2 * j + 1 = *matrixij.wall;if (i = row - 1)graph2 * i + 22 * j + 1 = *(matrixij.wall + 1);for (int j = 0; jcolumn; j+)/将每一列节点的左右墙（也有可能是可走）弄为迷宫里的该节点格子左右格子 for (int i = 0; irow; i+)graph2 * i + 12 * j = *(matrixij.wall + 2);if (j = column - 1)graph2 * i + 12 * j + 2 = *(matrixij.wall + 3); makerandomstartandend(); /随机定义迷宫出入口 cout n现在生成迷宫！： x;int currenty = currentcoordinate-y;mazepointercurrentxcurrenty.accessed = true;mazepointercurrentxcurrenty.value = 2;int i;while (currentx != (m-1) currentx = currentcoordinate-x;currenty = currentcoordinate-y;i = -1;/记录有效相邻格子数 cout x: currentx y: currenty accessed = true;pathstack.push(*currentcoordinate);/将上一个格子坐标进栈currentcoordinate = tempi;currentcoordinate-value = 2;currentcoordinate-accessed = true;accessecount+;currentx = currentcoordinate-x;currenty = currentcoordinate-y;elseif (!pathstack.empty()/当前格子无可走的相邻格子，返回到上一个格子 mazepointercurrentxcurrenty.value = -1;currentcoordinate = &pathstack.top();pathstack.pop();4. bfs算法实现void bfs:mazepath()currentcoordinate = new coordinatebfs(0, start);int count1 = 0, count2 = 0;/count1为记录前一个被访问格子（栈顶部格子）可走相邻格子数，count2为当前访问格子的可走相邻格子数 int currentx = currentcoordinate-x;int currenty = currentcoordinate-y;mazepointercurrentxcurrenty.accessed = true;mazepointercurrentxcurrenty.value = 2;/int entry = startpoint; /入口id/int exit = endpoint; /出口id/记录所有房间的访问路径,trapathi表示访问到房间i的路径上的前一节点/vector trapath(endpoint,-1);/depathquery pathquery;s_i = 0;s = new cstringm*n;pathquery.push_back(mazepointer0start);while (!pathquery.empty()if (currentx = (m - 1)break;int i = 0;/if (mazepointercurrentxcurrenty.value = 2) /如果已经该房间已经访问过了，则跳过/continue;if (haspath(currentx, currenty - 1)pathquery.push_back(mazepointercurrentxcurrenty - 1);/mazepointercurrentxcurrenty - 1.value = 2;currentcoordinate-accessed = true;i+;if (haspath(currentx, currenty + 1)pathquery.push_back(mazepointercurrentxcurrenty + 1);/mazepointercurrentxcurrenty + 1.value = 2;currentcoordinate-accessed = true;i+;if (haspath(currentx - 1, currenty)pathquery.push_back(mazepointercurrentx - 1currenty);/mazepointercurrentx - 1currenty.value = 2;currentcoordinate-accessed = true;i+;if (haspath(currentx + 1, currenty)pathquery.push_back(mazepointercurrentx + 1currenty);/mazepointercurrentx + 1currenty.value = 2;currentcoordinate-accessed = true;i+;if (i = 0)mazepointercurrentxcurrenty.value = -1;elsemazepointercurrentxcurrenty.value = 2;pathquery.pop_front();currentcoordinate = &pathquery.front();currentx = currentcoordinate-x;currenty = currentcoordinate-y;ss_i+.format(_t(%d,%d)n), currentx, currenty);/cout x: currentx y: currenty endl;5. mfc按钮功能实现void cmaze_mfcdlg:onbnclickedcreatemaze()/ todo: 在此添加控件通知处理程序代码int m, n;updatedata(true);if (m_mazex = 0 | m_mazey = 0)m = 50;n = 50;elsem = (int)m_mazex;n = (int)m_mazey;maze maze(m,n);/创建迷宫对象maze.createmaze();r = maze.getgraphrow();c = maze.getgraphcolumn();arr = maze.getgraph();arr = new int*maze.getgraphrow();for (int i = 0; imaze.getgraphrow(); i+)arri = new intmaze.getgraphcolumn();for (int i = 0; ir; i+)for (int j = 0; jc; j+)arrij =maze.getgraph()ij;/double length = 50;/double wide = 50;/*int x = 5; int y = 5;*/hdc hdc = :getdc(m_hwnd);hbrush hbrush_bk, hbrushold_bk;hbrush_bk = createsolidbrush(rgb(255, 255, 255);hbrushold_bk = (hbrush)selectobject(hdc, hbrush_bk);:rectangle(hdc, 0, 0, 700 , 700);selectobject(hdc, hbrushold_bk);deleteobject(hbrush_bk);for (int i = 0; i r; i+)for (int j = 0; j c; j+)if (arrij = 1)/墙 hbrush hbrush, hbrushold;hbrush = createsolidbrush(rgb(138, 54, 15);hbrushold = (hbrush)selectobject(hdc, hbrush);:rectangle(hdc, i*10, j*10, i*10+10, j * 10 + 10);selectobject(hdc, hbrushold);deleteobject(hbrush);:releasedc(m_hwnd, hdc);void cmaze_mfcdlg:onbnclickeddfs()/ todo: 在此添加控件通知处理程序代码dfs dfs(arr, r, c);dfs.mazepath();/*dfs.printpath();*/hdc hdc = :getdc(m_hwnd);for (int i = 0; i r; i+)for (int j = 0; j c; j+)if (dfs.getvalue(i , j) = 2)hbrush hbrush, hbrushold;hbrush = createsolidbrush(rgb(0, 0, 255);hbrushold = (hbrush)selectobject(hdc, hbrush);:rectangle(hdc, i * 10, j * 10, i * 10 + 10, j * 10 + 10);selectobject(hdc, hbrushold);deleteobject(hbrush);else if (dfs.getvalue(i, j) = -1)hbrush hbrush_2, hbrushold_2;hbrush_2 = createsolidbrush(rgb(125, 125, 255);hbrushold_2 = (hbrush)selectobject(hdc, hbrush_2);:rectangle(hdc, i * 10, j * 10, i * 10 + 10, j * 10 + 10);selectobject(hdc, hbrushold_2);deleteobject(hbrush_2);:releasedc(m_hwnd, hdc);m_pathcoordinate.resetcontent();for (int i = 0; i dfs.s_i;i+)m_pathcoordinate.insertstring(0, dfs.si);void cmaze_mfcdlg:onbnclickedbfs()/ todo: 在此添加控件通知处理程序代码bfs bfs(arr, r, c);bfs.mazepath();/*dfs.printpath();*/hdc hdc = :getdc(m_hwnd);for (int i = 0; i r; i+)for (int j = 0; j c; j+)if (bfs.getvalue(i, j) = 2)hbrush hbrush, hbrushold;hbrush = createsolidbrush(rgb(0, 0, 255);hbrushold = (hbrush)selectobject(hdc, hbrush);:rectangle(hdc, i * 10, j * 10, i * 10 + 10, j * 10 + 10);selectobject(hdc, hbrushold);deleteobject(hbrush);else if (bfs.getvalue(i, j) = -1)hbrush hbrush_2, hbrushold_2;hbrush_2 = createsolidbrush(rgb(125, 125, 255);hbrushold_2 = (hbrush)selectobject(hdc, hbrush_2);:rectangle(hdc, i * 10, j * 10, i * 10 + 10, j * 10 + 10);selectobject(hdc, hbrushold_2);deleteobject(hbrush_2);:releasedc(m_hwnd, hdc);m_pathcoordinate.resetcontent();for (int i = 0; i loadicon(idr_mainframe);void cmaze_mfcdlg:dodataexchange(cdataexchange* pdx)cdialogex:dodataexchange(pdx);ddx_text(pdx, idc_row, m_mazex);ddx_text(pdx, idc_column, m_mazey);ddx_control(pdx, idc_list, m_pathcoordinate);begin_message_map(cmaze_mfcdlg, cdialogex)on_wm_syscommand()on_wm_paint()on_wm_querydragicon()on_bn_clicked(idc_createmaze, &cmaze_mfcdlg:onbnclickedcreatemaze)on_bn_clicked(idc_dfs, &cmaze_mfcdlg:onbnclickeddfs)on_bn_clicked(idc_bfs, &cmaze_mfcdlg:onbnclickedbfs)on_bn_clicked(idc_exit, &cmaze_mfcdlg:onbnclickedexit)on_bn_clicked(idc_about, &cmaze_mfcdlg:onbnclickedabout)end_message_map()/ cmaze_mfcdlg 消息处理程序bool cmaze_mfcdlg:oninitdialog()cdialogex:oninitdialog();/ 将“关于.”菜单项添加到系统菜单中。/ idm_aboutbox 必须在系统命令范围内。assert(idm_aboutbox & 0xfff0) = idm_aboutbox);assert(idm_aboutbox appendmenu(mf_separator);psysmenu-appendmenu(mf_string, idm_aboutbox, straboutmenu);/ 设置此对话框的图标。 当应用程序主窗口不是对话框时，框架将自动/ 执行此操作seticon(m_hicon, true);/ 设置大图标seticon(m_hicon, false);/ 设置小图标/ todo: 在此添加额外的初始化代码return true; / 除非将焦点设置到控件，否则返回 truevoid cmaze_mfcdlg:onsyscommand(uint nid, lparam lparam)if (nid & 0xfff0) = idm_aboutbox)caboutdlg dlgabout;dlgabout.domodal();elsecdialogex:onsyscommand(nid, lparam);/ 如果向对话框添加最小化按钮，则需要下面的代码/ 来绘制该图标。 对于使用文档/视图模型的 mfc 应用程序，/ 这将由框架自动完成。void cmaze_mfcdlg:onpaint()if (isiconic()cpaintdc dc(this); / 用于绘制的设备上下文sendmessage(wm_iconerasebkgnd, reinterpret_cast(dc.getsafehdc(), 0);/ 使图标在工作区矩形中居中int cxicon = getsystemmetrics(sm_cxicon);int cyicon = getsystemmetrics(sm_cyicon);crect rect;getclientrect(&rect);int x = (rect.width() - cxicon + 1) / 2;int y = (rect.height() - cyicon + 1) / 2;/ 绘制图标dc.drawicon(x, y, m_hicon);elsecdialogex:onpaint();/当用户拖动最小化窗口时系统调用此函数取得光标/显示。hcursor cmaze_mfcdlg:onquerydragicon()return static_cast(m_hicon);3.2 数据录入实现m, n 取默认值50，50m, n 取默认值20，20m, n 取默认值60, 604 调试分析（该部分内容包括：对准备进行测试的数据进行测试，并对在调试过程中遇到的问题是如何分析和解决的进行描述。）1. 问题1：数组越界问题描述：寻路过程，发生越界的情况问题解决：搜寻路径是添加越界检查函数2. 问题2：死循环问题描述：迷宫创建过程，发生死循环情况问题解决： 添加判断语句判断当前节点是否已到达终点3. 问题3：坐标问题问题描述：只能输出一个坐标问题解决： 使用cstring数组存储所有节点的坐标，最后输出5用户使用说明此处说明如何使用你所设计的软件1. 输入x和y的值，点击生成迷宫进行随机生成，可重复点击，随机生成。2. 如未输入x和y的值，则默认值为50，点击生成迷宫按钮，随机生成迷宫，可重复生成。3. 生成迷宫之后，点击dfs寻路，会生成dfs路径，寻路坐标表示在右边空栏。4. 生成迷宫之后，点击bfs寻路，会生成bfs路径，寻路坐标表示在右边空栏。5. 点击退出按钮，程序会关闭退出6. 点击相关按钮，会提示应用程序使用说明。6测试结果（此处应对你所设计的软件和经过测试，下个结论。.分别使用默认值(50，50) 输入值（20，20）（60，60）进行迷宫生成，dfs寻路，bfs寻路测试，测试结果如下： 结 论 通过本次课程设计可以得出结论如下：1. 迷宫深度优先算法可以迅速生成一个矩形迷宫，但是生成迷宫具有一条明显的通路。2. 迷宫dfs路径探索，可以明显在使用较少计算量的情况下的寻求一条迷宫通路。3. 迷宫bfs路径探索，需要进行大量的计算，其速度不如dfs路径探索但可以找到具有最优解的路径。4. 通过本次课程设计，深入探索了栈，队列等数据结构的应用，以及深刻学习了dfs算法和bfs算法在实际中的应用，并且对于程序编写能力进行了显著锻炼。 致 谢 本次课程设计能够得到这样的成果，感谢指导老师的倾力执导，以及各位组员的辛勤努力。7 附录程序源代码：bfs.h#pragma once#include #includemaze.h#includeusing namespace std;class coordinatebfsfriend class bfs;public:coordinatebfs()x = y = value = 0;accessed = false;coordinatebfs(int a, int b)x = a;y = b;value = 0;accessed = false;int getx();int gety();int x;int y;int value;bool accessed;class bfs/todopublic:cstring *s;int s_i;bfs(int *graph, int graphrow, int graphcolumn);bfs();/void getmaze(int*,int,int);void mazepath();bool haspath(int x, int y);void printpath();int getvalue(int, int);private