基于图形迷宫算法 原创作品,谢谢支持《数据结构》课程设计报告----基于图形界面的迷宫算法实现班 级: 电信0601班 学 号: 3号 1号 姓 名: 彭俊彬 张洋 时 间: 2008 1月 3 日 目录 一.设计目的 3 二.设计内容 3 1.分工情况: 3 2.需求分析: 3 (1)界面设计 3 (2)系统操作函数 4 (3)迷宫算法实现: 5 三.概要设计 6 (1)数据结构定义 6 1).界面设计 6 2).迷宫算法类 7 (2)程序流程图 8 (3)算法详细解释 8 四. 使用说明及测试结果: 13 五.源程序及系统文件使用说明 16 (1)框架类OnPaint重绘函数 17 (2)探索迷宫SearchMaze函数 17 六.心得体会 19 (1)组员的心得 19 (2)对课程感想: 20 (3)问题及解决方法 21 1)界面设计: 21 2)迷宫算法方面 21 (4)仍未解决问题 22 七.参考文献 22一.设计目的我们这次课程设计选的题目是迷宫算法的实现,选这个题目的原因是在我们数据结构课程上老师曾经讲过这个迷宫求解的算法,但是书上讲的过于简单而且没有详细的程序.而我们又对这个课题比较感兴趣,因为以前我们曾经在电子设计大赛上看到过类似的迷宫机器人的算法(当然那个算法要比我们这个复杂很多,但基本思想我们的程序还是有的),我们就想通过vc++编写出一个基于图形界面的迷宫程序来大概模拟机器人走迷宫的大概过程.二.设计内容1.分工情况: 在此我们可以自信的说句:“我们的程序是100%原创的,没有一句从网上粘贴复制而来,全部程序1500多行都是我们自己一行一行写的!”。我们组只有两个人,所以分工比较明确。彭俊彬主要负责程序的编写及调试,张洋主要负责资料收集及测试。2.需求分析:因为我们是用VC++编写基于MFC的图形界面迷宫算法,所以程序不紧包括算法,图形界面的设计也是我们程序的主要内容.所以完成系统主要任务就包括了界面的设计及算法的实现.(1)界面设计利用MFC提供的基本类库,编写框架类及应用程序类,实现程序界面设计,主要完成包括窗口,菜单及工具条的设计.利用设备描述表DC完成对迷宫元素的贴图,能够响应用户消息. 大概完成如下图所示基本界面:(2)系统操作函数1)新建:新建迷宫地图,地图大小由用户自己设定,系统根据用户设定自动改变窗体大小,适应用户的输入。2)保存:保存用户编写的地图,方便下次运行时读取地图信息,地图信息保存在“maze.data”文件中。3)读取:读取“maze.data”文件中地图信息,方便用户运行程序。4)退出:退出本迷宫系统。5)绘图:用户编写自己的迷宫地图,其中包括地面,墙壁,入口,出口的设置6)探索迷宫:通过编写的迷宫算法类,逐步探索迷宫,并显示用户具体探索方案,用户可通过速度调节滑块,调节迷宫的探索速度。7)最短路径:显示出经计算机探索后的最短路径,如下所示:(3)迷宫算法实现: 算法实现是整个系统的灵魂所在,前面写的界面程序如果没有这个部分则形同虚设。编写出一个迷宫算法类主要完成迷宫地图信息保存,探索迷宫及显示最短路径的操作. 1)保存迷宫信息:根据用户绘制的迷宫将迷宫信息保存在类成员maze中,并以特殊标记区分地面、墙壁、入口及出口。2)改变迷宫信息:根据用户修改的迷宫改变类成员maze中保存的迷宫元素信息。3)探索迷宫操作:以“穷举求解”的方法逐步探索出走到出口的所有可能的路径,并通过双向链表保存最佳路径信息,方便对路径操作。4)最短路径:以双向链表保存的信息,绘制出从入口到出口的最短路径。当然实现这个类的功能不止这些操作,这里只是给出概述,具体的内容将在后面介绍。三.概要设计(1)数据结构定义1).界面设计class CMainFrame : public CFrameWnd //继承于CFrameWnd的框架类{DECLARE_DYNCREATE(CMainFrame)public: CMainFrame(); public: //类成员 BOOL IsSearch; CMapEdit *m_pMapEdit;…… //省略部分成员 char m_MazeWidth,m_MazeHigh,m_CurrentSel; CToolBar m_wndToolBar;protected: virtual ~CMainFrame(); // Generated message map functions //窗口的主要消息 //{{AFX_MSG(CMainFrame) afx_msg int OnCreate(LPCREATESTRUCT lpCreateStruct);…… //限于篇幅省略一些操作,重要操作将在后面详细介绍 afx_msg void OnTimer(UINT nIDEvent); //}}AFX_MSG DECLARE_MESSAGE_MAP()};2).迷宫算法类struct StepPoint //走迷宫时运用双向链表保存迷宫信息{ CPoint m_StepPoint; int direct; struct StepPoint *next; struct StepPoint *pre;};class CMapEdit //迷宫算法类,系统的灵魂所在{public: //迷宫算法类的成员 char *maze; BOOL *IsPass; CBitmap *m_pbmp; ……//省略部分成员public: //迷宫算法类的基本操作 void Init(); ……//省略部分操作 virtual ~CMapEdit(); BOOL DrawMap(CDC *pDC); void ClearMap(); void DrawMouseCursor(CPoint point,char CurrSel,CDC *pDC); void CMapEdit::ChangMap(CPoint point, char CurSel);};应用程序类程序进程程序框架类主界面迷宫算法类算法实现消息处理对话框类各种对话框各类消息处理函数Splash类欢迎界面(2)程序流程图系统中主要运用了五个中S(3)算法详细解释系统中Slash类、应用程序类、框架类及对话框类均从MFC的基础类CSplash、CWinApp、CFrameWnd及CDialog继承,我们仅是编写响应的消息处理函数,不涉及到算法范畴。下面将对系统的“灵魂所在”即迷宫算法类做出具体解释及说明。系统通过双向链表保存迷宫信息,运用了如下数据结构:struct StepPoint{ CPoint m_StepPoint; //通过CPoint类对象保存迷宫坐标点 int direct; //保存下一步的方向信息 struct StepPoint *next; //指向下一个迷宫节点信息 struct StepPoint *pre; //指向前一个迷宫节点信息};这个类的成员保存了具体探索过程中的各种信息,有如下成员:public: char *maze; //保存动态生成迷宫元素的具体信息 BOOL *IsPass; //判当前迷宫块是否走过 CBitmap *m_pbmp; //贴图用m_pbmp CDC *m_tmpDC; //内存DC char m_MazeWidth,m_MazeHigh; //保存迷宫大小 StepPoint *m_pCurStep,*m_pPreStep,*m_pFirstStep; //保存当前,前一个及第一个迷宫块信息 int m_CurPos,m_NextPos; //当前位置 CPoint m_MazeStart,m_MazeExit; //出口入口坐标信息 char m_BallNum,m_ExitNum; //出口入口个数 BOOL IsEnableOut; //迷宫是否能走出 在保存迷宫信息时我遇到一个问题:刚开始我是想用一个比较大二维数组maze[][]来保存迷宫元素信息的,但后来发现用二维数组保存动态迷宫信息时不仅造成浪费,而且会出错,后来我就运用一个指针来指向根据用户输入大小而定的动态空间,但这样做就又有另一个问题了。我们的迷宫是二维坐标,用二维数组保存迷宫信息直观而方便,现在用指针来操作,就必须找到二维坐标与线性变量的关系。几经探索我终于发现当前迷宫序列号(第一块为0,第二块为1……以此类推)除以当前迷宫宽度m_MazeWidth所得的商恰为X坐标,它的余数位Y坐标,这就解决了坐标映射的问题。下面将对系统的主要算法做出解释说明:BOOL CMapEdit::SearchMaze(){……//删除部分代码将在后面贴出 if (Pass(m_CurPos)) { IsPass[m_CurPos]=true; NextPos(m_pCurStep->direct); if (GoMaze(m_pCurStep->direct+37)) { StepPoint *nextStep; //周围能够通过 …… nextStep->next=NULL; //双向链表插入新节点 …… m_CurPos=m_MazeStart.y*m_MazeWidth+m_MazeStart.x; } } else //当前位置不能通过 { ………… delete tmpStep; //删除节点 UpdateMap(m_pCurStep->m_StepPoint,MAZEBALL); } } return false;} 系统算法主要采用“穷举求解”的方法,即从入口出发,顺着某一方向向前探索,若能走通,则继续向前走;否则顺着原路退回,换一个方向再继续探索,直至所有可能的通路都探索到为止。具体来说,假设当前位置可通即IsPass函数返回置为真(当前位置走过且每个方向均走过则返回假),程序将以当前位置方向向前探索执行GoMaze(m_pCurStep->direct+37)函数,加上37是为了响应键盘输入方向即用户可以通过键盘自己走迷宫,这样就不用重写函数了,大概的GoMaze函数如下:BOOL CMapEdit::GoMaze(UINT keyNum){ if (CheckMaze()) { char x,y; ……//删除代码将在后面贴出 if (keyNum == 38 && maze[(y-1)*m_MazeWidth+x]!=MAZEWALL &&(y-1>=0) && !IsPass[m_NextPos]) //按下键盘“上”或当前方向为上,执行 { m_MazeStart.y--; maze[y*m_MazeWidth+x]=MAZEGROUND; maze[(y-1)*m_MazeWidth+x]=MAZEBALL; }…… //省略下、左、右的操作过程 m_pCurStep->direct++; } return false;}GoMaze函数当下一个位置可以走通(不是墙且没有越界)则会改变系统迷宫信息,返回为真否则为假。如果GoMaze返回为真,程序将要把当前位置插入到双向链表中,操作如下:(2,0)1pre next(2,1)0pre next坐标方向指针域下一方向可通指向前一节点 NULL新迷宫节点如果GoMaze返回为假,否则返回当前位置,并以另一方向探索迷宫。假设此时当前位置每个方向均已通过,则会执行删除节点,回退过程,如下:(2,0)1pre next(2,1)0pre next坐标方向指针域回退指向前一节点 NULL NULL删除节点 这里操作其实就是入栈及出栈的过程,但我用双向链表是为了在显示最短路径时方便操作。至此迷宫算法类介绍完毕,现在看起来这个过程是多么简单,可我在写这个算法时也算是费了挺大的劲,看了数据结构书老半天才有些明白(书上只是简单的描述性语言相当让人费解,但基本思想还是一样的)。四. 使用说明及测试结果:系统启动后显示欢迎界面:随后系统自动加载用户保存地图信息,如果地图文件maze.data丢失或错误,系统将显示 并创建系统默认大小地图,用户也可通过“新建”命令新建指定大小迷宫:创建空白地图如下:此后用户可通过菜单或工具条,绘制自己的地图,为了方便用户绘制特做出如下工具条:用户在点击迷宫元素后即可通过单击或拖拉鼠标,绘制迷宫: 用户如果对绘制迷宫不满意,还可通过点击“地面”按钮擦除指定位置的迷宫元素。绘制迷宫完成后,用户即可点击“迷宫”菜单中“探索迷宫”命令,系统弹出调节速度对话框,用户通过调节滑块改变探索迷宫速度:点击确定键后,系统将以指定速度向前探索迷宫:探索迷宫中。。。如果找到出口系统将提示:(如果没有出口系统将提示:)如果找到了出路系统将进一步提示:用户此时选择是,系统将打印出探索迷宫的最短路径:用户也可通过选择菜单中“最短路径”来显示路径,显示效果同上。值得一提的是,用户也可以通过键盘的方向键,控制人物在迷宫中探索地图,然后我们可以通过AI走迷宫,看看我们自己走的路径是否最短。五.源程序及系统文件使用说明由于篇幅原因此处只贴出重要的代码及算法(关键数据结构已在概要设计中做出解释说明,这里不再赘述):(1)框架类OnPaint重绘函数void CMainFrame::OnPaint() { CPaintDC dc(this); // device context for painting CDC mdc; CBitmap bitmap; CRect m_rcClient; // TODO: Add your message handler code here GetClientRect(&m_rcClient);mdc.CreateCompatibleDC(&dc); bitmap.CreateCompatibleBitmap(&dc,m_rcClient.Width(),m_rcClient.Height()); //创建兼容DC mdc.SelectObject(&bitmap); m_pMapEdit->DrawMap(&mdc); //绘制地图 m_pMapEdit->DrawMouseCursor(m_CurPoint,m_CurrentSel,&mdc); //鼠标跟随 dc.BitBlt(0,0,m_rcClient.Width(),m_rcClient.Height(),&mdc,0,0,SRCCOPY); //把内存DC贴入当前设备描述表 bitmap.DeleteObject();}(2)探索迷宫SearchMaze函数BOOL CMapEdit::SearchMaze(){m_CurPos=m_MazeStart.y*m_MazeWidth+m_MazeStart.x; m_pCurStep->m_StepPoint=m_MazeStart; if(m_MazeStart==m_MazeExit) { IsEnableOut=true; return true;//true 结束探索} if (Pass(m_CurPos)) { IsPass[m_CurPos]=true; NextPos(m_pCurStep->direct); if (GoMaze(m_pCurStep->direct+37)) { StepPoint *nextStep; //周围能够通过 nextStep=new StepPoint; nextStep->m_StepPoint=m_MazeStart; nextStep->direct=0; //下面添加新的迷宫节点 nextStep->next=NULL; nextStep->pre=m_pCurStep; m_pCurStep->next=nextStep; m_pCurStep=nextStep; m_pPreStep=m_pCurStep->pre; m_CurPos=m_MazeStart.y*m_MazeWidth+m_MazeStart.x; } } else { if (m_pCurStep!=m_pFirstStep->next) { //当前位置不能通过 if (m_pCurStep->direct==4 && m_pCurStep!=NULL) { //删除节点,实现回退 UpdateMap(m_pCurStep->m_StepPoint,MAZEGROUND);//贴回地板 StepPoint *tmpStep; tmpStep=m_pCurStep; ASSERT(m_pPreStep->next); m_pPreStep=m_pPreStep->pre; m_pCurStep=m_pCurStep->pre; m_MazeStart=m_pCurStep->m_StepPoint; delete tmpStep; UpdateMap(m_pCurStep->m_StepPoint,MAZEBALL); }} else return true; } return false;}六.心得体会(1)组员的心得1)彭俊彬: 编程是件很美妙的事情,程序员通过各种函数实现心中既定的功能,看着自己的程序成功通过编译并运行起来,是相当有成就感的,这时编程过程遇到的各种失落感都会抛之脑后。这次是我自学C++及VC++一来写的第一个图形界面程序,虽然功能还不是很强大,但这次课程设计给了我机会同时也给我相当的鼓励,让我知道只要肯付出就一定会有收获的。这次课程设计更让我感受到,要提高自己的编程能力,必须亲自去体验、去设计、编辑、编译、调试、运行。看程序和改程序跟自己亲自去写程序,在难度系数上就不是一个等级的。虽然我不是软件专业学生,以后也不一定从事软件开发,这次课程设计不仅锻炼了我设计、编程及调试的能你。更关键是使我认识到,凭借我对新事物的兴趣及融入程度,对于以后无论学习还是工作上遇到的问题,我都能继续抱着不轻言放弃,不断进步的精神,迎难而上。最后我要感谢胡老师给了我们这样一次机会,不仅让我们所学的运用到实际中,还教会了许多除编程外的东西而这些是课堂上学不到了。2)张洋:数据结构设计已经接近尾声了,想想累肯定是有的,但我想相对于所收获的而言这是值得。这次程序设计的要求是老师新教学的改革,想说的是这样做真的很好,能很好的对大学生多种能力进行训练和提升。本次设计和彭俊彬一组,他的程序语言设计很强。开始讨论的时候,想做的好看些,所以决定用C++做。由于我对C++不是很熟,所以工作分配,彭俊彬作为主程序编写,我则负责程序的测试以及相关资料的查询。其间对我而说,有一个比较特殊的情况,就是从图书管借了C++的书做进一步的学习。在已经不上课的情况下静下心来看书还是有点难度的,不过还是看了。现在对C与C++的区别有的更清楚的了解。C与C++的最大区别在于它们的用于解决问题的思想方法不一样,其中C的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对环境条件进行运算处理得到实现过程控制,而对于C++,则首要考虑的是如何构造一个对象模型,让这个模型能够契合与之对应的问题域,这样就可以通过获取对象的状态信息得到输出或实现过程控制。我想在以后的生活中会经常遇到这种对你而言不是很熟悉的东西,需要你快速的学习并加以应用。这次程序设计收获很多,其中有团队程序的思想交流,工作分工的完成并与他人交接,遇到问题团队间的和谐商讨与解决,以及对C和C++语言的进一步理解和掌握。当然我觉的对C++的短时间学习并参与实践的过程,应该是我最大的收获了。程序设计到这里基本就结束了,再一次感谢胡老师大胆的教学风格给我们创造的这次机会,收获真的很大。(2)对课程感想: 时间总是让人感觉到一切是那么突然,这学期就像刚走过的花丛一样,虽依然可以问到她的芳香,却只能出现在你的背影中。还清楚的记得刚接触的数据结构这门课时的感觉。新的课程,新的老师而且是大学里第一个接触的教授级别的老师,内心充满的也只有动力。随着时间的推移开始对课程和胡老师有的进一步的了解。对什么是数据结构和数据结构中:表、栈、串、树、图等内容的了解、掌握以及应用。对胡老师的认识当然越来越深刻:胡老师对课堂纪律的要求是我见过老师中最有风格的一个了,当然也欣赏他那上课不准别人讲小话的态度。除此之外还有他那偶尔的幽默给人带来的轻松惬意以及教人先育人的教学理念,这些都无法不让我说胡老师是个很好的大学老师。在这次课程设计中,课堂学到了知识对解决我们遇到的问题也是起了很大的帮助的。(3)问题及解决方法1)界面设计: 其实我感觉做图形界面的程序要比以前的控制台程序要难很多,不知道是不是因为VC++的原因,还是因为图形界面设计就比较难的原因。记得以前学VB编程时做个图形界面挺简单的,VB都是可视化的。只要了解各个属性就能做出界面,程序员只要管程序功能函数的实现,而不用在界面上费多少精力。而VC++不同,你要做界面必须深入底层涉及到MFC的各种类(API编程除外),连显示一个空白窗口都得写上老长代码。首先你必须了解MFC各个基础类什么应用程序类、框架类等,然后还要清楚各个类的继承及调用关系。要让程序响应你点击按钮的消息,VB下只要双击按钮然后选择各种消息就行了,而在VC++中则需要对系统的消息响应原理及过程有一定的了解。在编写界面的时候,我遇到最大的困难就是做迷宫系统的工具栏。一般工具栏只需在资源中绘制工具栏然后在程序中加载就行了,但这样做出来的工具栏不好看而且不方便操作,于是我找了各种重绘工具栏的例子,最后才写出了工具栏的重载方法,写个工具栏就得调用类的7个方法还是比较烦人的。2)迷宫算法方面此部分是系统的灵魂所在,也是遇到问题最多的部分,暂且不说关于探索地图的操作,光是保存、读取及修改迷宫信息的函数就占这个类的一打部分。而用“穷举求解”探索迷宫的算法也让我想了好久。数据结构书上是虽然有探索迷宫的算法,但是书上利用类C描述性语言写的过于简单,我只能揣测作者的思想,然后把它运用到程序上,虽然做出改动,但思想是一样的,我猜测迷宫机器人道理也应该差不多吧,所以以后有机会要尝试着做个探索迷宫的机器人(有点跑题了!)。(4)仍未解决问题 我写程序有个习惯,总是喜欢把程序分成几个模块,然后在一个一个模块来实现,这种习惯也比较贴近与面向对象的编程思想,因此程序留下的问题并不多(经过多次测试及调试).但经过多次测试,我发现在显示最短路径时,有时并不是最短路径,而且迷宫越简单显示的路径更偏离最短路径,而程序在复杂的迷宫中就不会有这个问题。我想应该是在最短路径算法上出了点问题,因为程序只能按预定方向进行探索,如果找到出路者显示出路径。当初在考虑问题时并没有想到这一点:迷宫有出路不代表是最短路径。我想要解决这个问题,就必须再写一个算法,然后比较所有可能有出路的路径,再找到最短的一条路径才是最短路径。七.参考文献【1】 严蔚敏 吴伟民 <<数据结构(C语言版)>> ------清华大学出版社【2】 高守传 聂云铭 <> ------人民邮电出版社31
温馨提示
请用电脑打开本网页,即可以免费获取你想要的了。