findwaydlg.cpp

国内的一个A*算法演示

// findwayDlg.cpp : 实现文件
//

#include "stdafx.h"
#include "findway.h"
#include "findwayDlg.h"
#include ".\findwaydlg.h"
#include <math.h>
#include <fstream>
#include <list>
#include "geometrylib.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#endif

#define MAX_CLOSELIST 1024

//保存调节点的相关值
int g_nAdjArc;
int g_nAdjLen;
int g_nAdjLenBig;
using namespace std;
// CfindwayDlg 对话框
//排序用的比较函数x,y为比较点AB为比较直线
bool compare(const ObjPointLen &x,const ObjPointLen &y);

CfindwayDlg::CfindwayDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CfindwayDlg::IDD, pParent)
	, m_strHint(_T(""))
	, m_nAdjLen(6)
	, m_nAdjArc(40)
	, m_nAdjLenBig(10)
	, m_fWayLength(0)
	, m_dwStart(0)
	, m_bl(1.26)
	, m_DisplayTempWay(false)
{
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
	m_nState=0;
	m_nNumPolygons=0;
	m_nCurPoint=0;
	m_startPos.x=m_startPos.y=0;
	m_endPos=m_startPos;
	m_strHint1=_T("  请按住CTRL键，请点击鼠标左键开始画多边形");
}

void CfindwayDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	DDX_Text(pDX, IDC_EDIT1, m_strHint);
	DDX_Text(pDX, IDC_EDIT2, m_nAdjLen);
	DDX_Text(pDX, IDC_EDIT3, m_nAdjArc);
	DDX_Text(pDX, IDC_EDIT4, m_nAdjLenBig);
	DDX_Text(pDX, IDC_EDIT5, m_fWayLength);
	DDX_Text(pDX, IDC_EDIT6, m_dwStart);
	DDX_Text(pDX, IDC_EDIT7, m_bl);
}

BEGIN_MESSAGE_MAP(CfindwayDlg, CDialog)
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	//}}AFX_MSG_MAP
	ON_WM_MOUSEMOVE()
	ON_WM_LBUTTONUP()
	ON_COMMAND(ID_32774, OnRun32774)
	ON_COMMAND(ID_32773, OnExit32773)
	ON_COMMAND(ID_32771, OnOpenFile32771)
	ON_COMMAND(ID_32772, OnSaveFile32772)
	ON_WM_ACTIVATE()
	ON_WM_RBUTTONUP()
	ON_COMMAND(ID_FILE_NEW32776, OnFileNew32776)
	ON_BN_CLICKED(IDC_BUTTON1, OnBnClickedButton1)
	ON_BN_CLICKED(IDC_BUTTON2, OnBnClickedButton2)
	ON_COMMAND(ID_SYSTEM_DISPLAYTEMPWAY, OnSystemDisplaytempway)
END_MESSAGE_MAP()


// CfindwayDlg 消息处理程序

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

	// 设置此对话框的图标。当应用程序主窗口不是对话框时，框架将自动
	//  执行此操作
	SetIcon(m_hIcon, TRUE);			// 设置大图标
	SetIcon(m_hIcon, FALSE);		// 设置小图标
    
	// TODO: 在此添加额外的初始化代码
	m_pDC=GetDC();
	return TRUE;  // 除非设置了控件的焦点，否则返回 TRUE
}

// 如果向对话框添加最小化按钮，则需要下面的代码
//  来绘制该图标。对于使用文档/视图模型的 MFC 应用程序，
//  这将由框架自动完成。

void CfindwayDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // 用于绘制的设备上下文

		SendMessage(WM_ICONERASEBKGND, reinterpret_cast<WPARAM>(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);
	}
	else
	{
		CDialog::OnPaint();
	}
	
}

//当用户拖动最小化窗口时系统调用此函数取得光标显示。
HCURSOR CfindwayDlg::OnQueryDragIcon()
{
	return static_cast<HCURSOR>(m_hIcon);
}

void CfindwayDlg::OnMouseMove(UINT nFlags, CPoint point)
{
	UpdateData();
	m_CurPoint=point;
	m_strHint.Format("x=%d,y=%d",m_CurPoint.x,m_CurPoint.y);
	m_strHint=m_strHint+m_strHint1+m_strHint2;
	g_nAdjArc=m_nAdjArc;
	g_nAdjLen=m_nAdjLen;
	g_nAdjLenBig=m_nAdjLenBig;
	UpdateData(false);
	CDialog::OnMouseMove(nFlags, point);
}

void CfindwayDlg::OnLButtonUp(UINT nFlags, CPoint point)
{
	if(nFlags==MK_CONTROL)
	{	
		switch(m_nState) 
		{
		case 0:
			ZeroMemory(&m_CurPolygon,sizeof(ObjPolygon));
			m_nCurPoint=0;

			m_CurPolygon.LocalVertex[0]=point;
			m_nState=1;
			m_strHint1=_T("  松开CTRL按鼠标左键结束");
			m_pDC->SetPixel(point,RGB(255,100,100));
			m_strHint2.Format("   初始点是x=%d,y%d",point.x,point.y);
			m_pDC->MoveTo(point);
			break;
		case 1:
			if(m_nCurPoint>=MAXPOLYGENVERTEX-1)
			{
				m_pDC->LineTo(m_CurPolygon.LocalVertex[0]);
				m_nState=2;
				m_strHint1=_T("  请按住CTRL键，请选择多边形中心点");
				break;
			}		
			m_pDC->LineTo(point);
			if(point==m_CurPolygon.LocalVertex[0])
			{
				m_nState=2;
				m_strHint1=_T("  请按住CTRL键，请选择多边形中心点");
				break;
			}
			m_nCurPoint++;
			m_strHint1.Format("  顶点数=%d/%d",m_nCurPoint+1,MAXPOLYGENVERTEX);
			m_strHint1+=_T("  松开CTRL按鼠标左键结束");
			m_CurPolygon.LocalVertex[m_nCurPoint]=point;
			break;
		case 2:
			m_CurPolygon.Center=point;
			m_CurPolygon.nRadius=ComputeRadius(point);
			m_CurPolygon.nNumSides=m_nCurPoint+1;
			m_Polygon[m_nNumPolygons++]=m_CurPolygon;
			if(m_nNumPolygons>=MAX_POLYGON)
			{
				AfxMessageBox(_T("多边形数量达到最大值，不能再存储多边形!!!"));
			}
			m_nState=0;
			m_strHint1=_T("  请按住CTRL键，点击鼠标左键开始画多边形");
			m_strHint2="";
			m_pDC->MoveTo(point);
			m_pDC->AngleArc(point.x,point.y,m_CurPolygon.nRadius,0,360);
			m_pDC->SetPixel(point,RGB(100,100,255));
			break;
		default: 
			AfxMessageBox("State Error!");
		}

	}
	else
	{
		if(m_nState==1)
		{
			m_pDC->LineTo(m_CurPolygon.LocalVertex[0]);
			m_nState=2;
			m_strHint1=_T("  请按住CTRL键，请选择多边形中心点");
		}
	}
	CDialog::OnLButtonUp(nFlags, point);
}

// 计算检测圆的半径 使用多边形m_CurPolygon
int CfindwayDlg::ComputeRadius(POINT point)
{
	int max=0;
	for(int i=0;i<=m_nCurPoint;i++)
	{
		int x=point.x- m_CurPolygon.LocalVertex[i].x;
		int y=point.y- m_CurPolygon.LocalVertex[i].y;
		int d=sqrt((float)x*x+y*y);
		if(max<d)
		{
			max=d;
		}
	}
	return max;
}

// 绘画所有多边形
bool CfindwayDlg::DrawPolygon(void)
{
	//CPoint  curPos;
	CRect rect;
	GetClientRect(&rect);
	rect.bottom-=54;
	m_pDC->Rectangle(&rect);
	//画开始点
	for(int i=m_startPos.x-1;i<=m_startPos.x+1;i++)
		for(int j=m_startPos.y-1;j<=m_startPos.y+1;j++)
			m_pDC->SetPixel(i,j,RGB(255,0,0));
	//画结束点
	for(int i=m_endPos.x-1;i<=m_endPos.x+1;i++)
		for(int j=m_endPos.y-1;j<=m_endPos.y+1;j++)
			m_pDC->SetPixel(i,j,RGB(0,0,255));
	//curPos=m_pDC->GetCurrentPosition();
	ObjPolygon temp;
	for(int i=0;i<m_nNumPolygons;i++)
	{
		temp=m_Polygon[i];
		m_pDC->MoveTo(temp.LocalVertex[0]);
		for(int k=1;k<temp.nNumSides;k++)
		{
			m_pDC->LineTo(temp.LocalVertex[k]);
		}
		m_pDC->LineTo(temp.LocalVertex[0]);
		m_pDC->MoveTo(temp.Center);
		CPen *oldpen,newpen;
		oldpen=m_pDC->GetCurrentPen();
		newpen.CreatePen(PS_SOLID,1,RGB(150,200,250));
		m_pDC->SelectObject(&newpen);
		m_pDC->AngleArc(temp.Center.x,temp.Center.y,temp.nRadius,0,360);
		m_pDC->SetPixel(temp.Center,RGB(100,100,255));
		newpen.DeleteObject();
		m_pDC->SelectObject(oldpen);
	}
	return true;
}

void CfindwayDlg::OnRun32774()
{
	UpdateData();
	if(m_DisplayTempWay)
		OnBnClickedButton1();
	m_dwStart=GetTickCount();//获取开始时间
	//纪录查找的路径
	POINT way[MAX_WAY];
	POINT *pWay;
	int nWayNum;
	ObjPointLen start;
	start.l=start.lway=0.0;
	start.lend=dis_PP(m_startPos,m_endPos);
	start.FatherIndex=-1;
	start.old=start.p=m_startPos;
	//保存结束点
	POINT bp;
	bp=m_endPos;
	ObjPolygon *startPoly;
	ObjPolygon *endPoly;
	startPoly=CheckPointInsidePolygon(m_startPos);
	endPoly=CheckPointInsidePolygon(m_endPos);
	//判断开始点和终点是否都在外面，或都在一个多边形里，如不是调整终点
	if(startPoly==endPoly)
	{
		//空
	}
	else
	{	
		if(startPoly!=NULL)
		{
			AfxMessageBox(_T("开始点在多边形内！"));
			return ;
		}
		else
            m_endPos=AdjustEndPos(endPoly);
	}
	if(Run(start,m_endPos,way,&m_fWayLength,&nWayNum))
	{
		m_dwStart=GetTickCount()-m_dwStart;
		m_pDC->MoveTo(m_startPos);
		CPen *oldpen,newpen;
		oldpen=m_pDC->GetCurrentPen();
		newpen.CreatePen(PS_SOLID,2,RGB(0,250,0));
		m_pDC->SelectObject(&newpen);
		for(int i=nWayNum-1;i>=0;i--)
		{
			m_pDC->LineTo(way[i]);
		}
		newpen.DeleteObject();
		m_pDC->SelectObject(oldpen);
		MessageBeep(MB_ICONASTERISK);
	}
	else
	{
		//没有路径
		m_dwStart=GetTickCount()-m_dwStart;
		MessageBeep(MB_ICONHAND);
	}
	//恢复结束点
	m_endPos=bp;
	UpdateData(false);
}

void CfindwayDlg::OnExit32773()
{
	OnOK();
}

void CfindwayDlg::OnOpenFile32771()
{
	CFileDialog fileDialog(TRUE,"map","*.map",OFN_OVERWRITEPROMPT,NULL,this,0);
	CString strFileName;
	if(fileDialog.DoModal()!=IDOK)
	{
		return;
	}
	strFileName= fileDialog.GetPathName();
	SetWindowText("FindWay  "+strFileName);
	char szFileName[256];
	strncpy(szFileName,strFileName.GetBuffer(),256);
	ifstream File(szFileName);
	if(!File)
	{
		AfxMessageBox("file error!");
	}
	File>>m_nNumPolygons;
	for(int i=0;i<m_nNumPolygons;i++)
	{
		File>>m_Polygon[i].nID>>m_Polygon[i].nState>>m_Polygon[i].nNumSides;
		for(int k=0;k<m_Polygon[i].nNumSides;k++)
		{
			File>>m_Polygon[i].LocalVertex[k].x>>m_Polygon[i].LocalVertex[k].y;
		}
		File>>m_Polygon[i].Center.x>>m_Polygon[i].Center.y;
		File>>m_Polygon[i].nRadius;
	}
	File.close();
	DrawPolygon();
}

void CfindwayDlg::OnSaveFile32772()
{
	CFileDialog fileDialog(FALSE,"map","*.map",OFN_OVERWRITEPROMPT,NULL,this,0);
	CString strFileName;
	if(fileDialog.DoModal()!=IDOK)
	{
		return;
	}
	strFileName= fileDialog.GetPathName();
	char szFileName[256];
	strncpy(szFileName,strFileName.GetBuffer(),256);
	ofstream File(szFileName,ios::trunc);
	if(!File)
	{
		AfxMessageBox("file error!");
	}
	File<<m_nNumPolygons<<endl;
	for(int i=0;i<m_nNumPolygons;i++)
	{
		File<<m_Polygon[i].nID<<" "<<m_Polygon[i].nState<<" "<<m_Polygon[i].nNumSides<<endl;
		for(int k=0;k<m_Polygon[i].nNumSides;k++)
		{
			File<<m_Polygon[i].LocalVertex[k].x<<" "<<m_Polygon[i].LocalVertex[k].y<<endl;
		}
		File<<m_Polygon[i].Center.x<<" "<<m_Polygon[i].Center.y<<endl;
		File<<m_Polygon[i].nRadius<<endl;
	}
	File.close();

}