VC游戏编写中的求解最短路径算法源码

// 求解最短路径Dlg.cpp : implementation file /********************************* [学VC编游戏] 编著、程序设计：唐明理 2004.7 E-mail: cqtml@163.com **********************************/ //Download by http://www.codefans.net #include "stdafx.h" #include "求解最短路径.h" #include "求解最短路径Dlg.h" #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif ///////////////////////////////////////////////////////////////////////////// int a=3; int tml; CString cc; void CMyDlg::showmap()//显地图 {int i,j; CString cc; CClientDC dc(this); CBrush Brush0(RGB(0x0,0x0,0x0)); CBrush Brush1(RGB(200,200,200)); for (i=0;i<m_fd.map_h;i++) {for (j=0;j<m_fd.map_w;j++) { if (m_fd.map[i][j]!='0') { SelectObject(dc.m_hDC,Brush0); PatBlt(dc.m_hDC,i*a,j*a,a,a,PATCOPY);//cc="■"; } else { SelectObject(dc.m_hDC,Brush1); PatBlt(dc.m_hDC,i*a,j*a,a,a,PATCOPY);//cc="□"; } } } CBrush Brushs(RGB(0xf0,0x0,0x0)); SelectObject(dc.m_hDC,Brushs); PatBlt(dc.m_hDC,(m_fd.start_y)*a,(m_fd.start_x)*a,a,a,PATCOPY); CBrush Brushe(RGB(0x0,0x0,0xf0)); SelectObject(dc.m_hDC,Brushe); PatBlt(dc.m_hDC,(m_fd.end_y)*a,(m_fd.end_x)*a,a,a,PATCOPY); } ///////////////////////////////////////////////////////////////////////////// // CMyDlg dialog CMyDlg::CMyDlg(CWnd* pParent /*=NULL*/) : CDialog(CMyDlg::IDD, pParent) { //{{AFX_DATA_INIT(CMyDlg) // NOTE: the ClassWizard will add member initialization here //}}AFX_DATA_INIT m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME); } void CMyDlg::DoDataExchange(CDataExchange* pDX) { CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(CMyDlg) // NOTE: the ClassWizard will add DDX and DDV calls here //}}AFX_DATA_MAP } BEGIN_MESSAGE_MAP(CMyDlg, CDialog) //{{AFX_MSG_MAP(CMyDlg) ON_WM_PAINT() ON_WM_QUERYDRAGICON() ON_WM_TIMER() //}}AFX_MSG_MAP END_MESSAGE_MAP() ///////////////////////////////////////////////////////////////////////////// // CMyDlg message handlers BOOL CMyDlg::OnInitDialog() { CDialog::OnInitDialog(); SetIcon(m_hIcon, TRUE); // Set big icon SetIcon(m_hIcon, FALSE); // Set small icon MoveWindow(0,0,500,400);//窗口定位 CenterWindow(); //居中窗口 GetDlgItem(IDOK)->MoveWindow(500-60,0,55,18,TRUE);//确定按钮控件定位 GetDlgItem(IDC_EDIT1)->MoveWindow(500-180,20,170,340,TRUE); cc="这是自动寻径演示\r\n\r\n"; cc+="篮点是起点。\r\n\r\n"; cc+="红点是终点。\r\n\r\n"; cc+="按确定键开始。\r\n\r\n"; SetDlgItemText(IDC_EDIT1, cc); m_fd.readmap();//读地图 return TRUE; // return TRUE unless you set the focus to a control } // If you add a minimize button to your dialog, you will need the code below // to draw the icon. For MFC applications using the document/view model, // this is automatically done for you by the framework. void CMyDlg::OnPaint() { if (IsIconic()) { CPaintDC dc(this); // device context for painting SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0); // Center icon in client rectangle 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; // Draw the icon dc.DrawIcon(x, y, m_hIcon); } else { CDialog::OnPaint(); } showmap(); //显示地图 } HCURSOR CMyDlg::OnQueryDragIcon() { return (HCURSOR) m_hIcon; } //////////////////////////////////////////////////////////////////////////////////// void CMyDlg::OnOK() { showmap();//显示地图 int tim0=timeGetTime(); m_fd.findpath(m_fd.path);//找路 int tim1=timeGetTime(); CString cc; cc.Format("搜索时间%dms",tim1-tim0); SetWindowText(cc); //printpath(m_fd.path);//显示最佳路径 tml=0; SetTimer(1,10,NULL); // CDialog::OnOK(); } void CMyDlg::printpath(int *path)//显路径 {int i; CString cc; CClientDC dc(this); CBrush Brushe(RGB(0x0,0x0,0xf0)); SelectObject(dc.m_hDC,Brushe); for (i=0;path[i]>=0;i++) {//Sleep(50); int x=m_fd.path[i]%m_fd.map_w*a; int y=m_fd.path[i]/m_fd.map_w*a; PatBlt(dc.m_hDC,x,y,a,a,PATCOPY); } } void CMyDlg::OnTimer(UINT nIDEvent) { CClientDC dc(this); CBrush Brushe(RGB(0x0,0x80,0x80)); SelectObject(dc.m_hDC,Brushe); int x=m_fd.path[tml]%m_fd.map_w*a; int y=m_fd.path[tml]/m_fd.map_w*a; PatBlt(dc.m_hDC,y+1,x+1,a/2,a/2,PATCOPY); tml++;if(m_fd.path[tml]<0) {KillTimer(1); cc+="搜索结束。\r\n"; SetDlgItemText(IDC_EDIT1, cc); } CDialog::OnTimer(nIDEvent); }