lich_a_sardlg.cpp

本人实现的A*算法

// Lich_A_SarDlg.cpp : implementation file
//
//A_Star_程序（李川）108060835
#include "stdafx.h"
#include "Lich_A_Sar.h"
#include "Lich_A_SarDlg.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:
	CString start,goal;
	CAboutDlg();

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

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	public:
	virtual BOOL Create(LPCTSTR lpszClassName, LPCTSTR lpszWindowName, DWORD dwStyle, const RECT& rect, CWnd* pParentWnd, UINT nID, CCreateContext* pContext = NULL);
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	virtual void OnOK();
	//}}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)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CLich_A_SarDlg dialog

CLich_A_SarDlg::CLich_A_SarDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CLich_A_SarDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CLich_A_SarDlg)
		// 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);
}

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

BEGIN_MESSAGE_MAP(CLich_A_SarDlg, CDialog)
	//{{AFX_MSG_MAP(CLich_A_SarDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_BN_A_STAR, OnBnAStar)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CLich_A_SarDlg message handlers

BOOL CLich_A_SarDlg::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
//	OnBnAStar();
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CLich_A_SarDlg::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 CLich_A_SarDlg::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();
	}
}

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


#include <afxtempl.h> 
CString GetSavePath()
{
	CString filePathName; 
	CFileDialog dlg(false,NULL,"",OFN_CREATEPROMPT | OFN_OVERWRITEPROMPT);///TRUE为OPEN对话框，FALSE为SAVE AS对话框 
	if(dlg.DoModal()==IDOK) 
		filePathName=dlg.GetPathName(); 
	filePathName.TrimLeft();
	return filePathName;	 
}
//写文件
bool WriteFile(CString pathStr,CString textStr,CString mode="write")
{ 
	CFile   file;
	if(mode=="write"){
		if(!file.Open(pathStr,CFile::modeCreate |CFile::modeNoTruncate | CFile::modeWrite)) {
			return false;
		}
	}
	else if(mode=="clear")
	{
		if(!file.Open(pathStr,CFile::modeCreate )){
			return false;
		}
		file.Close();
		return true;
	}
	else return false;
	
	file.SeekToEnd();  
	
	file.Write(textStr,textStr.GetLength());   
    file.Close();
	
	return TRUE;
}

//分割字符串，以 sep[0]作为分隔符，分割结果存于CStringArray中
int SplitString(CStringArray& strarr, LPSTR str, LPCSTR sep = ",")
{
	int i=0;
	CString strTemp;
	char ch;
	char Sep=sep[0];
	for(i=0;i<strlen(str);i++)
	{
		ch=str[i];
		if(ch==Sep)
		{
			strarr.Add(strTemp);
			strTemp="";
		}
		else
			strTemp+=ch;
	}
	strarr.Add(strTemp);
	return strarr.GetSize();
}

class CState
{
	public:
	CString  m_id;
	CString  m_data;//可以指该状态的信息，也可以表示该状态的相邻的另一个状态的id
	int      m_distance;//到目标状态的估价距离
	int      m_goneDistance;
	CState*  m_pNextState;//下一个节点


	bool     Equals(CState* pState)
	{
		if(pState!=NULL && m_id==pState->m_id)
			return true;
		else return false;
	} 
};
class CStateSet
{
	public:
	CArray<CState*,CState*&> m_StateSet;
	
	CStateSet();
	CStateSet(const CStateSet &Other);
	int      GetSize();
	bool     AddItem(CState* pState);
	bool     RemoveAt(int num);
	bool     RemoveAll();
	bool     DeleteAll();
	CState*  GetAt(int num);
	bool RemoveFirstItem(CState* pState);
	bool ExpendItem(CState* pState);
	CState*  GetAt(CString id);
	bool HaveItem(CState*pState);
	int  GetMinStateNum();
	void ExpendItem(CState* pState,CStateSet stateInfoList);
	void PrintAllItem(CString path,CString setType="");
 

	static CStateSet  GetStatesInfoSet(CString setType);
	

};

CStateSet::CStateSet()
{
}
CStateSet::CStateSet(const CStateSet &Other)
{
	m_StateSet.Copy(Other.m_StateSet);
}

int CStateSet::GetSize()
{
	return m_StateSet.GetSize();
}
bool CStateSet::AddItem(CState* pState)
{
 	m_StateSet.Add(pState);
	return true;
}
bool CStateSet::RemoveAt(int num)
{
	m_StateSet.RemoveAt(num);
	return true;
}

bool CStateSet::RemoveAll()
{
	m_StateSet.RemoveAll();
	return true;
}
bool CStateSet::DeleteAll()
{
	for(int i=0;i<m_StateSet.GetSize();i++)
		delete m_StateSet.GetAt(i);
	m_StateSet.RemoveAll();
	return true;
}
CState* CStateSet::GetAt(int i)
{
	return m_StateSet.GetAt(i);
}
CState* CStateSet::GetAt(CString id)
{
 
	for(int i=0;i<m_StateSet.GetSize();i++)
	{
		if(m_StateSet.GetAt(i)->m_id==id)
		{
   
			return m_StateSet.GetAt(i);
		}
	}
	return NULL;
}
bool CStateSet::HaveItem(CState*pState)
{
	if(pState==NULL) return NULL;
	CState* pTemp=GetAt(pState->m_id);
	if(pTemp==NULL) return false;
	else return true;

}


int  CStateSet::GetMinStateNum()
{
	CState *pState=NULL;
	int num=-1;
	int size=m_StateSet.GetSize();
	if(size>0) pState=m_StateSet.GetAt(0);
	num=0;
	for(int i=1;i<size;i++)
	{
		if(m_StateSet.GetAt(i)->m_distance<pState->m_distance)
		{
			pState=m_StateSet.GetAt(i);		
			num=i;
		}
	}
	return num;
}
void CStateSet::ExpendItem(CState* pState,CStateSet stateInfoList)
{
	CString id=pState->m_id;
	CState *pTemp;
	for(int i=0;i<stateInfoList.GetSize();i++)
	{
		if(stateInfoList.GetAt(i)->m_id==id || stateInfoList.GetAt(i)->m_data==id)
		{
			pTemp=new CState;		
			if(stateInfoList.GetAt(i)->m_id==id)
				pTemp->m_id=stateInfoList.GetAt(i)->m_data;
			else  pTemp->m_id=stateInfoList.GetAt(i)->m_id;
			pTemp->m_distance=stateInfoList.GetAt(i)->m_distance;
			AddItem(pTemp);
		}
	}
}
void CStateSet::PrintAllItem(CString path,CString setType)
{
	CString str,str1,str2;
	str="";
	if(setType=="open_set")
	{
		str2.Format("\n\n\nopen表(经过的地点,估计路径总距离,已经通过的距离):\n");			
	}
	else if(setType=="closed_set")
	{
		str2.Format("\nclosed表(经过的地点,估计路径总距离,已经通过的距离):\n");
	}
	else if(setType=="expend_set")
	{
		str2.Format("\n待扩展节点的子节点集(经过的地点,该点到目标的估计值):\n");
	}

	for(int i=0;i<GetSize();i++)
	{
		if(setType=="open_set" || setType=="closed_set")
		{
			str1.Format("(%s,%d,%d) ",m_StateSet.GetAt(i)->m_id,m_StateSet.GetAt(i)->m_distance,m_StateSet.GetAt(i)->m_goneDistance);			
		}
		else if(setType=="expend_set")
		{
			str1.Format("(%s,%d) ",m_StateSet.GetAt(i)->m_id,m_StateSet.GetAt(i)->m_distance);			
		}
		str=str1+str;
	}
	str=str2+str+"\n";
	WriteFile(path,str);

}

CStateSet  CStateSet::GetStatesInfoSet(CString setType)//根据返回CStateSet的元素个数判断
{
	CStateSet stateSet;
	CState*pTemp;
	CString filePathName; 
	CString   str; 
	CStringArray strArray;
	CState* pState;
	
	//获取文件路径
	CFileDialog dlg(TRUE,NULL,"",OFN_CREATEPROMPT | OFN_OVERWRITEPROMPT);///TRUE为OPEN对话框，FALSE为SAVE AS对话框 
	if(dlg.DoModal()==IDOK) 
		filePathName=dlg.GetPathName(); 
	filePathName.TrimLeft();
	if(filePathName=="")  return stateSet;
	
	//读文件
	CStdioFile   file; 
	if( !file.Open(filePathName,CFile::modeRead |CFile::shareDenyNone| CFile::typeText ) )   
	{   
		AfxMessageBox("文件打开错误");
		return   stateSet;   
	}  
	while (file.ReadString(str))
	{	
		strArray.RemoveAll();
		SplitString(strArray,(LPSTR)(LPCTSTR)str,",");
		if(setType=="state_info_list")
		{
			if(strArray.GetSize()<3) continue;
			CState state;
			pState=new CState();//&state;////有什么不同						
			pState->m_id=strArray.GetAt(0);
			pState->m_data=strArray.GetAt(1);
			pState->m_distance=atoi(strArray.GetAt(2));
		}
		else
		{
			if(strArray.GetSize()<2) continue;
			pState=new CState();
			pState->m_id=strArray.GetAt(0);
			pState->m_distance=atoi(strArray.GetAt(1));
		}
		stateSet.AddItem(pState);
		
	}	
	file.Close(); 
	return  stateSet;
}





void CLich_A_SarDlg::OnBnAStar() 
{
	
	

	AfxMessageBox("第一步:导入关于地点数据的文本，文本每行的格式为“地点,该地点到目标点的估计距离”。");
	CStateSet stateList=CStateSet::GetStatesInfoSet("state_list");
	if(stateList.GetSize()==0) 
	{
		AfxMessageBox("导入相关数据失败");
		return;
	}

	AfxMessageBox("第二步:导入关于地图数据的文本，文本每行的格式为“地点1,地点2,两个地点之间的距离”。");
	CStateSet stateInfoList=CStateSet::GetStatesInfoSet("state_info_list");//获取相邻节点之间的距离
	if(stateInfoList.GetSize()==0) 
	{
		AfxMessageBox("导入相关数据失败");
		return;
	}



	AfxMessageBox("第三步:选择保存open表、closed表、分析过程中的数据以及结果信息的路径。");
    CString savePath=GetSavePath();

	CAboutDlg dlg;
	dlg.DoModal();
	CString start,goal;
	if(dlg.start!="") start=dlg.start;
	else start="Arad";
	if(dlg.goal!="") goal=dlg.goal;
	else goal="Bucharest";

 
	 
 

	int i;
	int temp;
	CString str;
	CStateSet openSet,closedSet,stateSet;
	CState *pStartState,*pGoalState,*pCurrentState,*pState;
	//////////////////////////////////////////////////////////////////////////////////////////////////////////
	///主程序
	pStartState=new CState();
	pStartState->m_id=start;
	pStartState->m_distance=stateList.GetAt(start)->m_distance;
	pStartState->m_goneDistance=0;
	pStartState->m_pNextState=NULL;
	str.Format("%s , %d",pStartState->m_id,pStartState->m_distance);
 
	pGoalState=new CState();
	pGoalState->m_id=goal;


   	openSet.AddItem(pStartState);//存储元素的集合
 	while(1)
 	{

WriteFile(savePath,"\n————————————————————————————————\n");
openSet.PrintAllItem(savePath,"open_set");
closedSet.PrintAllItem(savePath,"closed_set");

 		if(openSet.GetSize()==0)
		{
			break;
			AfxMessageBox("FAILED");
		}
		temp=openSet.GetMinStateNum();



		pCurrentState=openSet.GetAt(temp);
WriteFile(savePath,"\n选取扩展的节点:"+pCurrentState->m_id+"\n");

		openSet.RemoveAt(temp);//取出open中距离值最小的元素
 		closedSet.AddItem(pCurrentState);


		

 		if(pCurrentState->m_id==pGoalState->m_id) 
		{
			CString str1,str2,str3;
			str1=str2=str3="";
			if(pCurrentState!=NULL) str1.Format("路径长度:%d",pCurrentState->m_goneDistance);
			while(pCurrentState!=NULL)
			{
				str2="——"+pCurrentState->m_id+str2;			
				pCurrentState=pCurrentState->m_pNextState;
			}
			str3="最短路径:"+str2+"\n"+str1;
			AfxMessageBox(str3);
			WriteFile(savePath,"\n\n\n"+str3);
			break;
		}
 		stateSet.RemoveAll();/////??????
		stateSet.ExpendItem(pCurrentState,stateInfoList);//计算state的distance
 stateSet.PrintAllItem(savePath,"expend_set");

  
		str.Format("%d",stateSet.GetSize());

 		for(i=0;i<stateSet.GetSize();i++)
 		{
			pState=stateSet.GetAt(i);
			
			if(!openSet.HaveItem(pState) && !closedSet.HaveItem(pState))
			{
				openSet.AddItem(pState);//计算state的指针
				pState->m_pNextState=pCurrentState;
				pState->m_goneDistance=pCurrentState->m_goneDistance+pState->m_distance;
				pState->m_distance=pState->m_goneDistance+stateList.GetAt(pState->m_id)->m_distance;
			}
			else if(openSet.HaveItem(pCurrentState))
			{	
				delete pState;				
			}
			else if(closedSet.HaveItem(pCurrentState))
			{
				delete pState;
			}
		}
 	  }
//	exit(0);
	///////////////////////////////////////////////////////////	
}

void CAboutDlg::OnOK() 
{
	// TODO: Add extra validation here
	UpdateData(true);
	GetDlgItemText(IDC_EDIT1,start);
	GetDlgItemText(IDC_EDIT2,goal);
	CDialog::OnOK();
}

BOOL CAboutDlg::Create(LPCTSTR lpszClassName, LPCTSTR lpszWindowName, DWORD dwStyle, const RECT& rect, CWnd* pParentWnd, UINT nID, CCreateContext* pContext) 
{
	// TODO: Add your specialized code here and/or call the base class
	
	return CDialog::Create(IDD, pParentWnd);
}