MFC实现迷宫自寻路径

1、 数据结构与VC编程实习实习报告 学生姓名： 专业班级： 指导教师： 20*年7月7 日实习题目迷宫一、任务描述及要求任意确定一个迷宫的规模和形态，用非递归的方法走出迷宫，并输出至少一条通路的路径。基本要求：（75分）迷宫的存储结构由学生自行选择。合理设计窗口界面，首先创建一个迷宫，迷宫的元素可以预先设计好，也可以通过界面建立或修改，建立后的迷宫在窗口界面上显示出来；通过单击“开始”按钮，显示从入口到出口的行进路线，迷宫的显示尽量美观逼真。功能菜单或按钮自行设计，以合理为目的。扩展要求：（20分）动态显示在迷宫中的行进、回溯路线。二、概要设计1抽象数据类型链式栈。自动演示模块编辑模块

2、设置模块2整个程序包含功能模块及模块间的调用关系自动演示线程回调初始化模块三、详细设计1虚拟实现即数据结构的C+语言描述template<class T>/栈节点定义struct stackNodeT data;stackNode<T> *link;stackNode(stackNode<T> *ptr = NULL)link = ptr;/仅初始化指针成员的初始函数.stackNode(const T& d,stackNode<T> *ptr=NULL)data=d;link=ptr; /初始化数据与指针成员的构造函数.stackNod

3、e();template<class T>/栈类定义class stack private: stackNode<T> *top;/栈顶元素public:stack():top(NULL);void makeempty();/置栈空virtual stack()stack<T>:makeempty();/析构函数void push(T &x);/入栈bool pop(T &x);/出栈int getSize()const;/获得栈元素个数bool gettop(T &x) const;/获得栈顶元素bool Isempty() con

4、st return top=NULL?true:false;/判栈空;2抽象数据类型中定义的操作算法实现用伪代码描述（见源代码）3函数之间的调用关系工程名为：MistyRainMaze（烟雨迷宫）。OnAutoPlay()OnSetting()CMistyRainMazeView()AutoPlayProc()InitGame()链式栈的封装操作DrawBlock()四、调试分析1程序在调试过程中出现的问题及解决方法由于之前准备充分，程序编写过程中没有遇到多少问题，很快就解决了。CSDN、pudn及百度文库是解决问题的快捷通道，Visual Assist X是避免不必要错误产生的根本之道。2算

5、法的时间复杂度分析O(m*n),可以考虑用A*或B*算法进行改进。五、测试结果根据一组提供的测试数据得到什么样的结果六、心得体会七、实现工程首先新建一个基于单文档的工程MistyRainMaze，在第四步中注意View类的基类选择CScrollView，然后在MistyRainMazeView.h的CMistyRainMazeView类前面加入宏定义及线程回调声明。#include "stack.h"#if _MSC_VER > 1000#pragma once#endif / _MSC_VER > 1000struct AutoPlayPARAMint *m_

6、nMaze;/迷宫数组UINT m_nMazeRowSize;/迷宫行规模UINT m_nMazeColSize;/迷宫列规模int m_nRowStart;/起点位置int m_nColStart;/int m_nRowEnd;/终点位置int m_nColEnd;/CPoint m_ptStart;/图像左上角坐标int m_ntimedelay;/演示延迟时间CDC *pDC;UINT m_nRowSpace;/迷宫行距UINT m_nColSpace;/迷宫列距;typedef enum tagCurrorStateCURROR_STAND,/标准光标CURROR_BLOCK,/画墙时

7、的光标CURROR_START,/画起点光标CURROR_END,/画终点光标CURROR_EREASE/擦出光标CurrorState;typedef struct tagitemsint row;int col;int dir;items;/定义位置偏移typedef struct tagoffsetint row;int col;offset;/偏移数组static DWORD WINAPI AutoPlayProc( LPVOID lpParameter / thread data);/ 自动演示线程回调函数添加图像资源及光标资源,标好ID号。为CMistyRainMazeView类添

8、加成员变量及函数private:int *m_nMaze;/迷宫数组UINT m_nMazeRowSize;/迷宫行规模UINT m_nMazeColSize;/迷宫列规模UINT m_nRowSpace;/迷宫行距UINT m_nColSpace;/迷宫列距CPoint m_ptStart;/图像左上角坐标BOOL m_bStop;/初始停止标志为FALSECBitmap m_bitmap4;/加载图像HCURSOR m_hcursor5;/加载光标int m_ntimedelay;/演示延迟时间CurrorState m_currorstate;/光标状态指示int m_nRowStart

9、;/起点位置int m_nColStart;/int m_nRowEnd;/终点位置int m_nColEnd;/HANDLE m_hThreadAuotPlay;void DrawBlock(int x,int y,CDC* pDC,int nState=1);/ Operationspublic:void InitGame();/初始化迷宫，每次重新设置需调用CMistyRainMazeView:CMistyRainMazeView()/ TODO: add construction code herem_nRowSpace=16;/初始化行距16m_nColSpace=16;/m_nMa

10、zeRowSize=20;/初始化迷宫20×20m_nMazeColSize=20;/m_ptStart.x=0;/左上角暂定0，0，以后会调整m_ptStart.y=0;/m_ntimedelay=50;/初始化延迟100毫秒m_nRowStart=1;/初始化起点和终点m_nColStart=1;/m_nRowEnd=m_nMazeRowSize-2;/m_nColEnd=m_nMazeColSize-2;/m_currorstate=CURROR_STAND;/初始化标准光标m_bitmap0.LoadBitmap(IDB_BLOCK);/墙的图像m_bitmap1.LoadB

11、itmap(IDB_START);/起点的图像m_bitmap2.LoadBitmap(IDB_BACKGROUND);/背景图像m_bitmap3.LoadBitmap(IDB_END);/终点图像/从资源加载图像及光标m_hcursor0=(HCURSOR)LoadImage(AfxGetResourceHandle(),MAKEINTRESOURCE(IDC_STANDARD),IMAGE_CURSOR,15, 15, LR_DEFAULTSIZE);m_hcursor1=(HCURSOR)LoadImage(AfxGetResourceHandle(),MAKEINTRESOURCE(

12、IDC_BLOCK),IMAGE_CURSOR,15, 15, LR_DEFAULTSIZE);m_hcursor2=(HCURSOR)LoadImage(AfxGetResourceHandle(),MAKEINTRESOURCE(IDC_START),IMAGE_CURSOR,15, 15, LR_DEFAULTSIZE);m_hcursor3=(HCURSOR)LoadImage(AfxGetResourceHandle(),MAKEINTRESOURCE(IDC_END),IMAGE_CURSOR,15, 15, LR_DEFAULTSIZE);m_hcursor4=(HCURSOR)

13、LoadImage(AfxGetResourceHandle(),MAKEINTRESOURCE(IDC_EREASE),IMAGE_CURSOR,15, 15, LR_DEFAULTSIZE);m_bStop=FALSE;srand( (unsigned)time( NULL ) );InitGame();CMistyRainMazeView:CMistyRainMazeView()if(m_nMaze!=NULL)for(int i=0;i<m_nMazeRowSize;i+)delete m_nMazei;/释放内存空间if(m_hThreadAuotPlay) CloseHand

14、le(m_hThreadAuotPlay);/实现InitGame()，每次初始化迷宫用void CMistyRainMazeView:InitGame()m_nMaze=new int*m_nMazeRowSize;/分配空间for(int i=0;i<m_nMazeRowSize;i+)m_nMazei=new intm_nMazeColSize;for(i=0;i<m_nMazeRowSize;i+)for(int j=0;j<m_nMazeColSize;j+)m_nMazeij=1;for(i=0;i<m_nMazeRowSize;i+)for(int j=0

15、;j<m_nMazeColSize;j+)if(i=0|j=0|i=m_nMazeRowSize-1|j=m_nMazeColSize-1)m_nMazeij=1;elsem_nMazeij=rand()%3+4;if(m_nMazeij=4)m_nMazeij=1;elsem_nMazeij=0;m_nMazem_nRowStartm_nColStart=2;/设置起始位置m_nMazem_nRowEndm_nColEnd=3;/设置终点位置/重载CMistyRainMazeView的OnSetCursor函数,实现编译时光标指示。BOOL CMistyRainMazeView:OnS

16、etCursor(CWnd* pWnd, UINT nHitTest, UINT message) / TODO: Add your message handler code here and/or call defaultif(nHitTest=HTCLIENT)switch(m_currorstate)/ case CURROR_STAND:/ SetCursor(m_hcursor0);/ return 1;/ break;case CURROR_BLOCK:SetCursor(m_hcursor1);return 1;break;case CURROR_START:SetCursor(

17、m_hcursor2);return 1;break;case CURROR_END:SetCursor(m_hcursor3);return 1;break;case CURROR_EREASE:SetCursor(m_hcursor4);return 1;break;default:return CScrollView:OnSetCursor(pWnd, nHitTest, message);return CScrollView:OnSetCursor(pWnd, nHitTest, message);教师评语评语： 指导教师（签名）：下面给出关键文件代码/ MistyRainMazeVi

18、ew.cpp : implementation of the CMistyRainMazeView class/#include "stdafx.h"#include "MistyRainMaze.h"#include <stdlib.h>#include "SettingDlg.h"#include "MistyRainMazeDoc.h"#include "MistyRainMazeView.h"#include "MainFrm.h"#ifdef _DEBU

19、G#define new DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE = _FILE_;#endif/ CMistyRainMazeViewIMPLEMENT_DYNCREATE(CMistyRainMazeView, CScrollView)BEGIN_MESSAGE_MAP(CMistyRainMazeView, CScrollView)/AFX_MSG_MAP(CMistyRainMazeView)ON_WM_MOUSEMOVE()ON_COMMAND(IDM_AUTO_PLAY, OnAutoPlay)ON_WM_LBUTTONDOWN

20、()ON_WM_SETCURSOR()ON_COMMAND(IDM_EDIT_START, OnEditStart)ON_COMMAND(IDM_EDIT_END, OnEditEnd)ON_COMMAND(IDM_EDIT_BLOCK, OnEditBlock)ON_COMMAND(IDM_EREASE, OnErease)ON_COMMAND(IDM_EDIT_EXIT, OnEditExit)ON_COMMAND(IDM_RANDOM_GENERATE, OnRandomGenerate)ON_COMMAND(IDM_SETTING, OnSetting)ON_WM_RBUTTONDOW

21、N()ON_COMMAND(IDM_ONLINE_HELP, OnOnlineHelp)ON_WM_LBUTTONUP()ON_WM_KEYDOWN()/AFX_MSG_MAP/ Standard printing commandsON_COMMAND(ID_FILE_PRINT, CScrollView:OnFilePrint)ON_COMMAND(ID_FILE_PRINT_DIRECT, CScrollView:OnFilePrint)ON_COMMAND(ID_FILE_PRINT_PREVIEW, CScrollView:OnFilePrintPreview)END_MESSAGE_

22、MAP()/ CMistyRainMazeView construction/destructionCMistyRainMazeView:CMistyRainMazeView()/ TODO: add construction code herem_bLeftButtonDown=FALSE;m_bStop=FALSE;m_nRowSpace=18;/初始化行距16m_nColSpace=18;/m_nMazeRowSize=20;/初始化迷宫20×20m_nMazeColSize=20;/m_ptStart.x=0;/左上角暂定0，0，以后会调整m_ptStart.y=0;/m_n

23、timedelay=100;/初始化延迟100毫秒m_nRowStart=1;/初始化起点和终点m_nColStart=1;/m_nRowEnd=m_nMazeRowSize-2;/m_nColEnd=m_nMazeColSize-2;/m_currorstate=CURROR_STAND;/初始化标准光标/从资源加载图像光标m_hcursor0=(HCURSOR)LoadImage(AfxGetResourceHandle(),MAKEINTRESOURCE(IDC_STANDARD),IMAGE_CURSOR,15, 15, LR_DEFAULTSIZE);m_hcursor1=(HCUR

24、SOR)LoadImage(AfxGetResourceHandle(),MAKEINTRESOURCE(IDC_BLOCK),IMAGE_CURSOR,15, 15, LR_DEFAULTSIZE);m_hcursor2=(HCURSOR)LoadImage(AfxGetResourceHandle(),MAKEINTRESOURCE(IDC_START),IMAGE_CURSOR,15, 15, LR_DEFAULTSIZE);m_hcursor3=(HCURSOR)LoadImage(AfxGetResourceHandle(),MAKEINTRESOURCE(IDC_END),IMAG

25、E_CURSOR,15, 15, LR_DEFAULTSIZE);m_hcursor4=(HCURSOR)LoadImage(AfxGetResourceHandle(),MAKEINTRESOURCE(IDC_EREASE),IMAGE_CURSOR,15, 15, LR_DEFAULTSIZE);m_bStop=FALSE;/初始化停止为falsesrand( (unsigned)time( NULL ) );/设置时间种子，用于随机参数InitGame();/初始化迷宫CMistyRainMazeView:CMistyRainMazeView()if(m_nMaze!=NULL)for(

26、int i=0;i<m_nMazeRowSize;i+)delete m_nMazei;/释放内存空间if(m_hThreadAuotPlay) CloseHandle(m_hThreadAuotPlay);BOOL CMistyRainMazeView:PreCreateWindow(CREATESTRUCT& cs)/ TODO: Modify the Window class or styles here by modifying/ the CREATESTRUCT csreturn CScrollView:PreCreateWindow(cs);/ CMistyRainM

27、azeView drawing/烟雨迷宫1.0版/开发历程：2011年6月4日，创建工程，实现获取屏幕坐标位置，后来发现其实没大用，后来忙于考试、实习/2011年7月9日规划工程，实现加载图像、迷宫编辑功能/2011年7月10日实现随机生成，栈计算通行结果正确/2011年7月11日实现自动演示（只加了4句代码!）/2011年7月11日验收通过，转向3D智能导航员项目开发/2011年7月14日实现多线程演示功能/2011年7月16日润色注释，更便于阅读/2011年7月19加入支持键盘走迷宫，支持实现自动与手动的完美结合/代码规范，简洁易懂，注释完整、清晰，是符合面向思维规范不可多得的佳作/烟雨集

28、团 水惊云科技/作者：迷若烟雨(面向思维创始人)/2011年7月16日/特别鸣谢：/孙鑫VC+深入详解/候捷深入浅出MFC/殷人昆数据结构/CSDN、pudn及百度文库无私奉献的开源爱好者/void CMistyRainMazeView:OnDraw(CDC* pDC)CMistyRainMazeDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);/获取客户区域信息CRect rectWindow;GetClientRect(&rectWindow);CPoint ptCenter;ptCenter.x=rectWindow.left+(rectW

29、indow.right-rectWindow.left)/2;ptCenter.y=rectWindow.top+(rectWindow.bottom-rectWindow.top)/2;int i=0,j=0;m_ptStart.x=ptCenter.x-m_nMazeRowSize*m_nRowSpace/2.0;m_ptStart.y=ptCenter.y-m_nMazeColSize*m_nColSpace/2.0;/画背景,若使用双缓存技术会更好，时间所限，后继实现就交给广大开源爱好者啦CBitmap bmMistyRain;bmMistyRain.LoadBitmap(IDB_MI

30、STYRAIN);BITMAP bitmapMistyRain;bmMistyRain.GetBitmap(&bitmapMistyRain);CDC dcCompatible;dcCompatible.CreateCompatibleDC(pDC);dcCompatible.SelectObject(&bmMistyRain);pDC->StretchBlt(rectWindow.left,rectWindow.top,rectWindow.right,rectWindow.bottom,&dcCompatible,0,0,bitmapMistyRain.bmW

31、idth,bitmapMistyRain.bmHeight,SRCCOPY);CBrush brush(RGB(0,0,255);CBrush *pOldBrush=pDC->SelectObject(&brush);CBitmap bmpAccessible;/画迷宫for(i=0;i<m_nMazeRowSize;i+)for(j=0;j<m_nMazeColSize;j+)DrawBlock(i,j,pDC,m_nMazeij);/画区块pDC->SelectObject(pOldBrush);/画刷归位void CMistyRainMazeView:Sh

32、owStep(int x,int y,CDC *pDC,int nStep)CString strStep;strStep.Format("%d",nStep);CPen pen(PS_SOLID,1,RGB(0,0,255);CPen *pOldPen=pDC->SelectObject(&pen);pDC->TextOut(m_ptStart.x+x*m_nRowSpace+1,m_ptStart.y+y*m_nColSpace+1,strStep);pDC->SelectObject(*pOldPen);void CMistyRainMaze

33、View:DrawBlock(int x,int y,CDC* pDC,int nState)/封装画迷宫区块的操作，只需提供数组行列值，pDC，/和nState该位置状态，0、通行，1、墙，2、起点，3、终点CBitmap bitmapAccessible;switch(nState)case 0:bitmapAccessible.LoadBitmap(IDB_BACKGROUND);break;case 1:bitmapAccessible.LoadBitmap(IDB_BLOCK);break;case 2:bitmapAccessible.LoadBitmap(IDB_START);b

34、reak;case 3:bitmapAccessible.LoadBitmap(IDB_END);break;CDC dcCompatible;dcCompatible.CreateCompatibleDC(pDC);dcCompatible.SelectObject(&bitmapAccessible);BITMAP bmAccesible;bitmapAccessible.GetBitmap(&bmAccesible);pDC->StretchBlt(m_ptStart.x+x*m_nRowSpace,m_ptStart.y+y*m_nColSpace,m_nRowS

35、pace,m_nColSpace,&dcCompatible,0,0,bmAccesible.bmWidth,bmAccesible.bmHeight,SRCCOPY);/ CMistyRainMazeView printingBOOL CMistyRainMazeView:OnPreparePrinting(CPrintInfo* pInfo)/ default preparationreturn DoPreparePrinting(pInfo);void CMistyRainMazeView:OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*p

36、Info*/)/ TODO: add extra initialization before printingvoid CMistyRainMazeView:OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)/ TODO: add cleanup after printing/ CMistyRainMazeView diagnostics#ifdef _DEBUGvoid CMistyRainMazeView:AssertValid() constCScrollView:AssertValid();void CMistyRainMazeView

37、:Dump(CDumpContext& dc) constCScrollView:Dump(dc);CMistyRainMazeDoc* CMistyRainMazeView:GetDocument() / non-debug version is inlineASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CMistyRainMazeDoc);return (CMistyRainMazeDoc*)m_pDocument;#endif /_DEBUG/ CMistyRainMazeView message handlersvoid CMist

38、yRainMazeView:OnMouseMove(UINT nFlags, CPoint point) / TODO: Add your message handler code here and/or call defaultCString strPosition;/显示鼠标位置CClientDC dc(this);OnPrepareDC(&dc);CMainFrame * pFrame = (CMainFrame *) AfxGetApp()->m_pMainWnd;CStatusBar * pStatus = (CStatusBar *) &pFrame->

39、m_wndStatusBar;strPosition.Format ("当前坐标:%i,%i", point.x, point.y);CSize sz=dc.GetTextExtent(strPosition);pStatus->SetPaneInfo(pStatus->CommandToIndex(IDS_CURRENT_POSITION),IDS_CURRENT_POSITION,SBPS_NORMAL,sz.cx);pStatus->SetPaneText(pStatus->CommandToIndex(IDS_CURRENT_POSITION

40、),strPosition);if(m_bLeftButtonDown)if(m_currorstate=CURROR_STAND)return;int fx=(m_ptFore.x-m_ptStart.x)/m_nRowSpace;int fy=(m_ptFore.y-m_ptStart.y)/m_nColSpace;int x=(point.x-m_ptStart.x)/m_nRowSpace;int y=(point.y-m_ptStart.y)/m_nColSpace;if(x<=0|y<=0|x>=m_nMazeRowSize-1|y>=m_nMazeColS

41、ize-1)return;switch(m_currorstate)case CURROR_BLOCK:if(fx=x)if(fy<=y)for(int j=fy;j<y;j+)DrawBlock(x,j,&dc,1);m_nMazexj=1;elsefor(int j=y;j<fy;j+)DrawBlock(x,j,&dc,1);m_nMazexj=1;if(fy=y)if(fx<=x)for(int i=fx;i<x;i+)DrawBlock(i,y,&dc,1);m_nMazeiy=1;elsefor(int i=x;i<fx;

42、i+)for(int i=x;i<fx;i+)DrawBlock(i,y,&dc,1);m_nMazeiy=1;break;case CURROR_EREASE:if(fx=x)if(fy<=y)for(int j=fy;j<y;j+)DrawBlock(x,j,&dc,0);m_nMazexj=0;elsefor(int j=y;j<fy;j+)DrawBlock(x,j,&dc,0);m_nMazexj=0;if(fy=y)if(fx<=x)for(int i=fx;i<x;i+)DrawBlock(i,y,&dc,0);

43、m_nMazeiy=0;elsefor(int i=x;i<fx;i+)DrawBlock(i,y,&dc,0);m_nMazeiy=0;default:break;DrawBlock(m_nRowStart,m_nColStart,&dc,2);m_nMazem_nRowStartm_nColStart=2;DrawBlock(m_nRowEnd,m_nColEnd,&dc,3);m_nMazem_nRowEndm_nColEnd=3;CScrollView:OnMouseMove(nFlags, point);void CMistyRainMazeView:O

44、nInitialUpdate() CScrollView:OnInitialUpdate();/ TODO: Add your specialized code here and/or call the base classSetScrollSizes(MM_TEXT,CSize(1366,768);void CMistyRainMazeView:InitGame()/初始化迷宫，用于每次重新生成迷宫m_nMaze=new int*m_nMazeRowSize;/动态分配数组空间for(int i=0;i<m_nMazeRowSize;i+)m_nMazei=new intm_nMaze

45、ColSize;for(i=0;i<m_nMazeRowSize;i+)for(int j=0;j<m_nMazeColSize;j+)m_nMazeij=1;/随机生成迷宫的状态for(i=0;i<m_nMazeRowSize;i+)for(int j=0;j<m_nMazeColSize;j+)if(i=0|j=0|i=m_nMazeRowSize-1|j=m_nMazeColSize-1)m_nMazeij=1;elsem_nMazeij=rand()%3+4;if(m_nMazeij=4)m_nMazeij=1;elsem_nMazeij=0;m_nMazem_

46、nRowStartm_nColStart=2;/设置起始位置m_nMazem_nRowEndm_nColEnd=3;/设置终点位置void CMistyRainMazeView:OnAutoPlay() / TODO: Add your command handler code here/由于自动演示的延迟时间会占用大量的系统资源，导致假死现象，因此采用多线程技术改进m_hThreadAuotPlay=CreateThread(NULL,0,AutoPlayProc,LPVOID(atparam),0,NULL);/Invalidate();int nStep=0;CDC *pDC=GetDC

47、();int *mark;/标记数组int i,j,d,g,h;stack<items>st;mark=new int*m_nMazeRowSize;for(i=0;i<m_nMazeRowSize;i+)marki=new intm_nMazeColSize;for(i=0;i<m_nMazeRowSize;i+)for(j=0;j<m_nMazeColSize;j+)markij=0;offset move4;move0.row=1;move0.col=0;/顺时针方向搜索move1.row=0;move1.col=1;move2.row=-1;move2.col=0;move3.row=0;move3.col=-1;items tmp;tmp.row=m_nRowStart;tmp.col=m_nColStart;tmp.dir=0;i=m_nRowStart;j=m_nColStart;st.push(tmp);nStep+;while(st.Isempty()=false)DrawBlock(i,j,pDC,0);st.pop(tmp);i=tmp.row;j=tmp.col;d=tmp.dir;DrawBlock(i,j,pDC,2);nStep-;ShowStep(i,j,pDC,nStep);while(d<4)g=