astardlg.cpp

用A形算法寻找迷宫的最短路径,VC实现,非常值得一看

// AStarDlg.cpp : implementation file
//

#include "stdafx.h"
#include "AStar.h"
#include "AStarDlg.h"
#include "AstarFindPath.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CAStarDlg dialog

CAStarDlg::CAStarDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CAStarDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CAStarDlg)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
	m_bIsStart = FALSE;
	m_bIsEnd = FALSE;
	m_nRectWidth = 0;
	m_nRectHeight = 0;
	m_nGridWidth = 0;
	m_nGridHeight = 0;
	m_SPoint.x=0;
	m_SPoint.y=0;
	m_DPoint.x=0;
	m_DPoint.y=0;

	for(int width = 0; width < MAP_WIDTH; width++)
	{
		for(int height = 0; height < MAP_HEIGHT; height++)
		{
			m_nState[width][height] = FREETILE;
		}
	}
}

void CAStarDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAStarDlg)
		// NOTE: the ClassWizard will add DDX and DDV calls here
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAStarDlg, CDialog)
	//{{AFX_MSG_MAP(CAStarDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_BEGINFIND, OnBeginfind)
	ON_BN_CLICKED(IDC_LOADMAP, OnLoadmap)
	ON_BN_CLICKED(IDC_RESET, OnReset)
	ON_BN_CLICKED(IDC_SAVEMAP, OnSavemap)
	ON_WM_LBUTTONDOWN()
	ON_WM_RBUTTONDOWN()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CAStarDlg message handlers

BOOL CAStarDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CAStarDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// 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 CAStarDlg::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
	{
		CWnd* pMap;
		pMap=GetDlgItem(IDC_MAPAREA);
		CRect maprect;
		pMap->GetClientRect(&maprect);
		CClientDC dc(pMap);

		m_nGridWidth = maprect.Width() / MAP_WIDTH;
		m_nRectWidth = m_nGridWidth*MAP_WIDTH; 
		m_nGridHeight = maprect.Height() / MAP_HEIGHT;
		m_nRectHeight = m_nGridHeight*MAP_HEIGHT;
		pMap->MoveWindow(20, 20, m_nRectWidth, m_nRectHeight);
		pMap->GetClientRect(&maprect);

		pMap->UpdateWindow();
		CBrush brush(RGB(255,255,255));
		CBrush* pOldBrush=dc.SelectObject(&brush);
		dc.Rectangle(&maprect);
		dc.SelectObject(pOldBrush);
		
		for(int i = 0; i < MAP_WIDTH; i++)
		{
			dc.MoveTo(0,m_nGridHeight*i);
			dc.LineTo(m_nRectWidth,m_nGridHeight*i);		
			dc.MoveTo(m_nGridWidth*i,0);
			dc.LineTo(m_nGridWidth*i,m_nRectHeight);
		}
	
		CPen pen(PS_SOLID,1,RGB(255,255,255));
		CPen* pOldPen=dc.SelectObject(&pen);
		
		dc.SelectObject(&brush);
		for(int width = 0; width < MAP_WIDTH; width++)
		{
			for(int height = 0; height < MAP_HEIGHT; height++)
			{
				if(m_nState[width][height]== BLOCKTILE)
				{
					CBrush brush(RGB(0,0,255));
					CBrush* pOldBrush=dc.SelectObject(&brush);
					dc.Rectangle(width * m_nGridWidth + 2,
						height * m_nGridHeight + 2,
						(width + 1) * m_nGridWidth - 2,
						(height + 1) * m_nGridHeight -2);
					dc.SelectObject(pOldBrush);					
				}
				else if(m_nState[width][height]==STARTTILE)
				{
					CBrush brush(RGB(255,0,0));
					CBrush* pOldBrush=dc.SelectObject(&brush);
					dc.Rectangle(width * m_nGridWidth + 2,
						height * m_nGridHeight + 2,
						(width + 1) * m_nGridWidth - 2,
						(height + 1) * m_nGridHeight -2);	
					dc.SelectObject(pOldBrush);					
				}
				else if(m_nState[width][height]==ENDTILE)
				{
					CBrush brush(RGB(255,255,0));
					CBrush* pOldBrush=dc.SelectObject(&brush);
					dc.Rectangle(width * m_nGridWidth + 2,
						height * m_nGridHeight + 2,
						(width + 1) * m_nGridWidth - 2,
						(height + 1) * m_nGridHeight -2);	
					dc.SelectObject(pOldBrush);					
				}
				else if(m_nState[width][height]==ROUTETILE)
				{
					CBrush brush(RGB(0,255,0));
					CBrush* pOldBrush=dc.SelectObject(&brush);
					dc.Rectangle(width * m_nGridWidth + 2,
						height * m_nGridHeight + 2,
						(width + 1) * m_nGridWidth - 2,
						(height + 1) * m_nGridHeight -2);	
					dc.SelectObject(pOldBrush);					
				}
			}
		}     
		dc.SelectObject(pOldPen);
		
		//CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CAStarDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CAStarDlg::OnBeginfind() 
{
	// TODO: Add your control notification handler code here
	if(!m_bIsEnd || !m_bIsStart)
		return;
	BYTE temp[8] = {0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
	
	BYTE map[((MAP_WIDTH * MAP_HEIGHT + 7) >> 3)];
	
	int x=0;
	int y=0;
	ZeroMemory(map,((MAP_WIDTH * MAP_HEIGHT + 7) >> 3));
	
	for(y=0; y < MAP_HEIGHT; y++)
	{
		for(x=0; x < MAP_WIDTH; x++)
		{
			if(m_nState[x][y] == BLOCKTILE)
				map[(y*MAP_WIDTH+x)/8]^=temp[(y*MAP_WIDTH+x)%8];
		}
	}
	
	AStarFindPath findpath;
	findpath.InitAstarTileMap(map,MAP_WIDTH,MAP_HEIGHT);

	if(findpath.NewPath(m_SPoint.x, m_SPoint.y, m_DPoint.x, m_DPoint.y))
	{
			
		do{
			findpath.PathNextNode();
			x=findpath.NodeGetX();
			y=findpath.NodeGetY();
			m_nState[x][y]=ROUTETILE;
			Sleep(200);
			Invalidate();
			UpdateWindow();
		}while(findpath.ReachedGoal());
	}
		m_nState[x][y]=ENDTILE;
		Invalidate();
}

void CAStarDlg::OnLoadmap() 
{
	// TODO: Add your control notification handler code here
	static char BASED_CODE szFilter[] = 
		"Map Files (*.map)";
	CString PathName;
	
	
	CFileDialog dlg(TRUE, "map","*.map", OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT, szFilter, NULL);
	if (dlg.DoModal() == IDOK) {
		PathName = dlg.GetFileName();
	}
	else
		return;
	FILE* fp;
	int tmp;
	fp = fopen(PathName.GetBuffer(MAX_PATH), "rb");
	for(int width = 0; width < MAP_WIDTH; width++)
	{
		for(int height = 0; height < MAP_HEIGHT; height++)
		{
			memset(&tmp, 0, 4);
			fread(&tmp, 4, 1, fp);
			m_nState[width][height] = tmp;
			if (m_nState[width][height] == STARTTILE)
			{
				m_bIsStart = TRUE;
			}
			if (m_nState[width][height] == ENDTILE)
			{
				m_bIsEnd = TRUE;
			}	
		}
	}
	fclose(fp);
	OnPaint();
}

void CAStarDlg::OnReset() 
{
	// TODO: Add your control notification handler code here
	for(int i=0;i<MAP_WIDTH;i++)
	{
		for(int j=0;j<MAP_HEIGHT;j++)
		{
			m_nState[i][j]=FREETILE;
		}
	}
	m_bIsStart = FALSE;
	m_bIsEnd = FALSE;
	Invalidate();
}

void CAStarDlg::OnSavemap() 
{
	// TODO: Add your control notification handler code here
	static char BASED_CODE szFilter[] = 
		"Map Files (*.map)";
	CString PathName;
	
	
	CFileDialog dlg(FALSE, "map", "*.map", OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT, szFilter, NULL);
	if (dlg.DoModal() == IDOK) {
		PathName = dlg.GetFileName();
	}
	else
		return;
	FILE* fp;
	fp = fopen(PathName.GetBuffer(MAX_PATH), "wb");
	for(int width = 0; width < MAP_WIDTH; width++)
	{
		for(int height = 0; height < MAP_HEIGHT; height++)
			fwrite(&m_nState[width][height], 4, 1, fp);			
	}
	fclose(fp);
}

void CAStarDlg::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	CClientDC dc(this);
	CPen pen(PS_SOLID,1,RGB(255,255,255));
	CPen* pOldPen=dc.SelectObject(&pen);
	if((point.x < 20)||(point.y < 20))
		return;
	int x=(point.x - 20) / m_nGridWidth;
	int y=(point.y - 20) / m_nGridHeight;
	
    if(x < MAP_WIDTH && y < MAP_HEIGHT)
	{
		if(m_nState[x][y]== FREETILE)
		{
			m_nState[x][y]= BLOCKTILE;
			CBrush brush(RGB(0,0,255));
			CBrush* pOldBrush=dc.SelectObject(&brush);
			dc.Rectangle(x*m_nGridWidth + 20 + 2,
				y*m_nGridHeight + 20 + 2,
				(x+1)*m_nGridWidth + 20 -2,
				(y+1)*m_nGridHeight + 20 - 2);
			dc.SelectObject(pOldBrush);
		}
		else if(m_nState[x][y]==BLOCKTILE)
		{
			m_nState[x][y]=FREETILE;
			dc.Rectangle(x*m_nGridWidth + 20 + 2,
				y*m_nGridHeight + 20 + 2,
				(x+1)*m_nGridWidth + 20 - 2,
				(y+1)*m_nGridHeight + 20 - 2);
		}
		
	}
    dc.SelectObject(pOldPen);
	
	CDialog::OnLButtonDown(nFlags, point);
}

void CAStarDlg::OnRButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	CClientDC dc(this);
	CPen pen(PS_SOLID,1,RGB(255,255,255));
	CPen* pOldPen=dc.SelectObject(&pen);
	if((point.x < 20)||(point.y < 20))
		return;
	int x=(point.x-20) / m_nGridWidth;
	int y=(point.y-20)/ m_nGridHeight;
	
    if(x < MAP_WIDTH && y < MAP_HEIGHT)
	{
		if(m_nState[x][y]==FREETILE)
		{
			if(!m_bIsStart)
			{
				m_nState[x][y] = STARTTILE;
				m_bIsStart = TRUE;
				CBrush brush(RGB(255,0,0));
				CBrush* pOldBrush=dc.SelectObject(&brush);
				dc.Rectangle(x*m_nGridWidth + 20 + 2,
					y*m_nGridHeight + 20 + 2,
					(x+1)*m_nGridWidth + 20 - 2,
					(y+1)*m_nGridHeight + 20 - 2);
				dc.SelectObject(pOldBrush);
				m_SPoint.x=x;
				m_SPoint.y=y;
			}
			else if(!m_bIsEnd)
			{
					m_bIsEnd = TRUE;
					m_nState[x][y]=ENDTILE;
					CBrush brush(RGB(255,255,0));
					CBrush* pOldBrush=dc.SelectObject(&brush);
					dc.Rectangle(x*m_nGridWidth + 20 + 2,
						y*m_nGridHeight + 20 + 2,
						(x+1)*m_nGridWidth + 20 - 2,
						(y+1)*m_nGridHeight + 20 - 2);
					dc.SelectObject(pOldBrush);
					m_DPoint.x=x;
					m_DPoint.y=y;
			}
		}
		else if(m_nState[x][y]== STARTTILE)
		{			
			m_bIsStart = FALSE;
			m_nState[x][y]=FREETILE;
			dc.Rectangle(x*m_nGridWidth + 20 + 2,
				y*m_nGridHeight + 20 + 2,
				(x+1)*m_nGridWidth + 20 - 2,
				(y+1)*m_nGridHeight + 20 - 2);
		}
		else if (m_nState[x][y]== ENDTILE) 
		{
			m_bIsEnd = FALSE;
			m_nState[x][y]=FREETILE;
			dc.Rectangle(x*m_nGridWidth + 20 + 2,
				y*m_nGridHeight + 20 + 2,
				(x+1)*m_nGridWidth + 20 - 2,
				(y+1)*m_nGridHeight + 20 - 2);
		}
		
	}
    dc.SelectObject(pOldPen);
	CDialog::OnRButtonDown(nFlags, point);
}

void CAStarDlg::OnCancel() 
{
	// TODO: Add extra cleanup here
	
	CDialog::OnCancel();
}