testdlg.cpp

简单实现了A*寻路算法

		int count=m_ListOpen.GetCount();
		POSITION pInOpen,pInClose;
		pInOpen=pInClose=NULL;
		
		if (0!=count)
		{
			InList(m_ListOpen,x,y,pInOpen);
		}
		else
		{
			m_bStop=TRUE;
			m_bFind=FALSE;
		}
		
		count=m_ListClose.GetCount();		
		if (0!=count)
		{
			InList(m_ListClose,x,y,pInClose);
		}
		
		if (!pInClose)
		{
			continue;
		}

		if (!pInOpen)
		{
			CCell * pNewCell=new CCell(x,y);
			pNewCell->pParent=&center;			
			pNewCell->h=GetH(m_nxDest,m_nyDest,x,y);
			pNewCell->ComputeGHF();
			m_ListOpen.AddTail((void *)pNewCell);			
		}		
	}	
}

void CTestDlg::FindPath()
{
	int tx[8]={1,1,0,-1,-1,-1,0,1};
	int ty[8]={0,-1,-1,-1,0,1,1,1};
	int x,y;
	CString strOut,strBuffer;
	//int num=0;
	POSITION pTemp;	
	
	int dx,dy;
	dx=abs(m_nxDest-m_cellStart.px);
	dy=abs(m_nyDest-m_cellStart.py);

	if (dx<2 && dy<2)
	{
		m_bStop=TRUE;
		m_bFind=FALSE;
	}
	while (!m_bStop)
	{	
		pTemp=NULL;
		GetMinF(&m_ListOpen,pTemp);
		m_nCheck++;
		if (!pTemp)			
		{
			m_bStop=TRUE;
			m_bFind=FALSE;
			MessageBox("No path that call walk to the destination!");
			break;
		}

		m_pcellCur=(CCell * )m_ListOpen.GetAt(pTemp);
		//if (m_pcellCur->px==8 && m_pcellCur->py==4)
		//{
			//strOut.Format("Position: x=%d,y=%d have the lowest value f=%d!",m_pcellCur->px,m_pcellCur->py,m_pcellCur->f);
			//MessageBox(strOut);
		//}
		m_ListOpen.RemoveAt(pTemp);
		m_ListClose.AddTail((void *)m_pcellCur);
		//CString strOut,strBuffer;
		int count=0;
		BOOL bEmpty;
		
		for (int i=0;i<8;i++)
		{
			x=m_pcellCur->px+tx[i];
			y=m_pcellCur->py+ty[i];

			/*if (m_pcellCur->px==1 && m_pcellCur->py==3 && i==6)
			{
				//strOut.Format("Checking Node: x=%d,y=%d",x,y);
				bEmpty=m_ListOpen.IsEmpty();
				//if (bEmpty)
					//MessageBox(strOut);
			}*/
			
			if (x<0 || y<0 || x>=nx || y>=ny)
				continue;
			if (0==map[x][y])
				continue;		

			bEmpty=m_ListOpen.IsEmpty();
			
			POSITION pInOpen,pInClose;
			pInOpen=pInClose=NULL;
			
			//if (!bEmpty)
			//{
				InList(m_ListOpen,x,y,pInOpen);
			//}
			/*else
			{
				//int num=m_ListOpen.GetCount();
				//strBuffer.Format("Current Node: x=%d,y=%d\n",m_pcellCur->px,m_pcellCur->py);
				//MessageBox(strBuffer);
				m_bStop=FALSE;
				m_bFind=FALSE;
				//MessageBox("Haven't found the path!");
				((CWnd *)GetDlgItem(IDC_BTN_INIT))->EnableWindow(TRUE);
				((CWnd *)GetDlgItem(IDC_BTN_FIND))->EnableWindow(FALSE);
				((CWnd *)GetDlgItem(IDC_BTN_SHOW))->EnableWindow(FALSE);				
				
				return;
			}*/
			
			count=m_ListClose.GetCount();		
			if (0!=count)
			{
				InList(m_ListClose,x,y,pInClose);
			}
			
			if (pInClose)
			{
				continue;
			}	
			

			if ( pInOpen==NULL)
			{	
				if (i%2!=0 && (map[m_pcellCur->px][m_pcellCur->py+ty[i]]==0 || map[m_pcellCur->px+tx[i]][m_pcellCur->py]==0))
					continue;
				CCell * pNewCell=new CCell(x,y);
				m_nAdd++;
				//strOut="";
				/*
				strBuffer.Format("Current Node: x=%d,y=%d\n",m_pcellCur->px,m_pcellCur->py);
				strOut=strBuffer;				
				strBuffer.Format("Add new Node: x=%d,y=%d\n",pNewCell->px,pNewCell->py);
				strOut+=strBuffer;
				strBuffer.Format("OpenList have %d elements.",m_ListOpen.GetCount()+1);
				strOut+=strBuffer;
				MessageBox(strOut);
				*/
				pNewCell->pParent=m_pcellCur;				
				pNewCell->h=GetH(m_nxDest,m_nyDest,x,y);
				pNewCell->ComputeGHF();
				m_ListOpen.AddHead((void *)pNewCell);				
				
				
			}		
			else 
			{
				CCell * pExist=(CCell *)m_ListOpen.GetAt(pInOpen);				
				int tempG=ComputeG(*pExist,*m_pcellCur);
				if (pExist->g>tempG && (i%2==0 || (map[pExist->px][pExist->py-ty[i]]==1 && map[pExist->px-tx[i]][pExist->py]==1)))
				{					
					pExist->pParent=m_pcellCur;
					pExist->g=tempG;
					pExist->f=pExist->g+pExist->h;									
				}
			}
			if (x==m_nxDest && y==m_nyDest )					
			{
				/*CTime timeEnd=CTime::GetCurrentTime();
				m_sEnd=timeEnd.GetSecond();				
				
				CString str;
				str.Format("Use %d seconds.",m_sEnd-m_sStart);
				MessageBox(str);*/
				m_bStop=TRUE;
				m_bFind=TRUE;
				((CWnd *)GetDlgItem(IDC_BTN_INIT))->EnableWindow(TRUE);
				((CWnd *)GetDlgItem(IDC_BTN_SHOW))->EnableWindow(TRUE);
				OnBtnShow();
				return;	
			}
		}
	}

}

void CTestDlg::InList(CPtrList &list,int x,int y,POSITION &pos)
{
	CCell * pCell;
	POSITION pTemp;
	for (pTemp=list.GetHeadPosition();pTemp!= NULL;)
	{
		pCell=(CCell * )list.GetNext(pTemp);
		if (pCell->px==x && pCell->py==y)
		{
			pos=list.Find((void *)pCell);			
			break;
		}		
	}	
	return;
}



void CTestDlg::GetMinF(CPtrList *plist, POSITION &pos)
{
	CCell *pMin,*pTemp;
	if (plist->IsEmpty())
	{
		pos=NULL;
		return;
	}

	pMin=(CCell * )plist->GetHead();
	POSITION posTemp=plist->GetTailPosition();

	if (pMin)
	{
		for (pTemp=pMin; posTemp!= NULL; pTemp=(CCell * )plist->GetPrev(posTemp))
		{				
			if (pTemp->f<=pMin->f)
			{
				pMin=pTemp;	
				continue;
			}		
		}
		pos=plist->Find((void *)pMin);
	}
	else
		pos=NULL;	

	pMin=NULL;
	pTemp=NULL;
	
}

int CTestDlg::GetH(int xdest, int ydest,int xorgin,int yorgin)
{
	int xa,ya,npow;

	xa=abs(xdest-xorgin);
	ya=abs(ydest-yorgin);
    //npow=xa*xa+ya*ya;
	//npow=__min(xa,ya);//
	npow=(xa+ya)*10;

	//return int((sqrt(npow))*10);
	return npow;
}

void CTestDlg::ClearList()
{
	CCell * pTemp;
	POSITION posTemp=m_ListOpen.GetHeadPosition();
	for (posTemp;posTemp!= NULL; )
	{
		pTemp=(CCell *)m_ListOpen.GetNext(posTemp);		
		if (!pTemp)
			delete pTemp;
	}
	for (posTemp=m_ListClose.GetHeadPosition(); posTemp!= NULL; )
	{
		pTemp=(CCell *)m_ListClose.GetNext(posTemp);		
		if (!pTemp)
			delete pTemp;
	}
	m_ListOpen.RemoveAll();
	m_ListClose.RemoveAll();
}

void CTestDlg::OnBtnFind() 
{
	// TODO: Add your control notification handler code here	

	((CWnd *)GetDlgItem(IDC_BTN_FIND))->EnableWindow(FALSE);
	FindPath();
	/*
	CString str;
	str.Format("Have added %d nodes and checked %d nodes.",m_nAdd,m_nCheck);
	MessageBox(str);
	*/
}

void CTestDlg::OnBtnShow() 
{
	// TODO: Add your control notification handler code here
	if (m_bStop)
	{
		//MessageBox("Stoped!");
		if (m_bFind)
		{
			//MessageBox("Found!");
			int dx,dy;
			dx=abs(m_nxDest-m_cellStart.px);
			dy=abs(m_nyDest-m_cellStart.py);

			if (dx<2 && dy<2) 
				return;

			POSITION ps;			
			InList(m_ListClose,m_nxDest,m_nyDest,ps);
			if (!ps)
				return;
			m_pEnd=(CCell *)m_ListOpen.GetHead();
			DrawPath();			
		}

	}

}

int CTestDlg::ComputeG(CCell &cellA, CCell &cellB)
{
	int x,y;
	x=abs(cellA.px-cellB.px);
	y=abs(cellA.py-cellB.py);
	
	if (1==x && 1==y)
		return 14+cellB.g;
	else	
	return 10+cellB.g;
}

void CTestDlg::DrawPath()
{
	CClientDC dc(this);	
	CBitmap bmp;
	bmp.CreateCompatibleBitmap(&dc,1,1);

	InitDC(5);
	CCell * pCell,*pChild;
	//MessageBox("");
	pChild=m_pEnd;
	for (pCell=m_pEnd->pParent;pCell!=NULL;pChild=pCell,pCell=pCell->pParent)
	{
		//dc.BitBlt(px1+i*36,py1+j*27,36,27,&compdc,36,0,SRCCOPY);
		//if (pCell->px!=m_cellStart.px || pCell->py!=m_cellStart.py)	
			if (pChild->px<pCell->px && pChild->py==pCell->py)
				TransparentBlt(dc.m_hDC,px1+pCell->px*36,py1+pCell->py*27,30,30,compdc.m_hDC,0,0,30,30,RGB(255,0,255));
			else if (pChild->px<pCell->px && pChild->py<pCell->py )
				TransparentBlt(dc.m_hDC,px1+pCell->px*36,py1+pCell->py*27,30,30,compdc.m_hDC,30,0,30,30,RGB(255,0,255));
			else if (pChild->px==pCell->px && pChild->py<pCell->py)
				TransparentBlt(dc.m_hDC,px1+pCell->px*36,py1+pCell->py*27,30,30,compdc.m_hDC,60,0,30,30,RGB(255,0,255));
			else if (pChild->px>pCell->px && pChild->py<pCell->py)
				TransparentBlt(dc.m_hDC,px1+pCell->px*36,py1+pCell->py*27,30,30,compdc.m_hDC,90,0,30,30,RGB(255,0,255));
			else if (pChild->px>pCell->px && pChild->py==pCell->py)
				TransparentBlt(dc.m_hDC,px1+pCell->px*36,py1+pCell->py*27,30,30,compdc.m_hDC,120,0,30,30,RGB(255,0,255));
			else if (pChild->px>pCell->px && pChild->py>pCell->py )
				TransparentBlt(dc.m_hDC,px1+pCell->px*36,py1+pCell->py*27,30,30,compdc.m_hDC,150,0,30,30,RGB(255,0,255));
			else if (pChild->px==pCell->px && pChild->py>pCell->py)
				TransparentBlt(dc.m_hDC,px1+pCell->px*36,py1+pCell->py*27,30,30,compdc.m_hDC,180,0,30,30,RGB(255,0,255));
			else if (pChild->px<pCell->px && pChild->py>pCell->py)
				TransparentBlt(dc.m_hDC,px1+pCell->px*36,py1+pCell->py*27,30,30,compdc.m_hDC,210,0,30,30,RGB(255,0,255));
			else 
				continue;
		//else
			//break;

	}	
	
	compdc.SelectObject(&bmp);
	DeleteDC(compdc.m_hDC);
	compdc.Detach();
	DeleteObject(m_bmpQZ.m_hObject);
	m_bmpQZ.Detach();
}

void CTestDlg::OnBtnInit() 
{
	// TODO: Add your control notification handler code here
	InitBoard();
	((CWnd *)GetDlgItem(IDC_BTN_FIND))->EnableWindow(TRUE);
	((CWnd *)GetDlgItem(IDC_BTN_SHOW))->EnableWindow(FALSE);
	OnBtnFind();
}

void CTestDlg::InitBoard()
{
	int tx[8]={1,1,0,-1,-1,-1,0,1};
	int ty[8]={0,-1,-1,-1,0,1,1,1};
	int x,y;
	CCell * pNew;
	ClearList();
	CString str;
		
	int nxRnd,nyRnd;
	srand( (unsigned)time( NULL ) );
	for (nxRnd=rand()%nx,nyRnd=rand()%ny;;nxRnd=rand()%nx,nyRnd=rand()%ny)
	{
		if (map[nxRnd][nyRnd]!=0)
		{
			m_nxDest=nxRnd;
			m_nyDest=nyRnd;
			break;
		}
	}
	
	for (nxRnd=rand()%nx,nyRnd=rand()%ny;;nxRnd=rand()%nx,nyRnd=rand()%ny)
	{
		if (nxRnd!=m_nxDest && nyRnd!=m_nyDest && map[nxRnd][nyRnd]!=0)
		{			
			m_cellStart=CCell(nxRnd,nyRnd);
			m_cellStart.g=0;			
			m_cellStart.pParent=NULL;
			m_cellStart.f=GetH(m_nxDest,m_nyDest,nxRnd,nyRnd);
			break;
		}
	}
	

	//////////////////////////////////////////////////////
	/*
	m_nxDest=12;
	m_nyDest=1;
	m_cellStart=CCell(1,1);
	m_cellStart.g=0;			
	m_cellStart.pParent=NULL;
	m_cellStart.f=GetH(m_nxDest,m_nyDest,m_cellStart.px,m_cellStart.py);
	*/
	////////////////////////////////////////////////////////

	m_bStop=FALSE;
	m_bFind=FALSE;
	m_bStart=TRUE;

	CClientDC dc(this);	
	
	for (int i=0;i<8;i++)
	{
		x=m_cellStart.px+tx[i];
		y=m_cellStart.py+ty[i];

		if (x<0 || y<0 || x>=nx || y>=ny)
			continue;
		if (0==map[x][y])
			continue;
		else if(i%2==0 || (map[x][y-ty[i]]==1 && map[x-tx[i]][y]==1))
		{
			pNew=new CCell(x,y);						
			pNew->pParent=&m_cellStart;
			pNew->h=GetH(m_nxDest,m_nyDest,x,y);
			pNew->ComputeGHF();
			//str.Format("Position: x=%d,y=%d  g=%d,h=%d,f=%d!",x,y,pNew->g,pNew->h,pNew->f);
			//MessageBox(str);
			m_ListOpen.AddTail((void *)pNew);
			m_nAdd++;
			pNew=NULL;
		}
	}
	m_ListClose.AddTail((void *)&m_cellStart);
	
	//CRect rc;
	//GetClientRect(&rc);
	Invalidate();
	DrawBmp();

}



void CTestDlg::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	CDialog::OnLButtonDown(nFlags, point);
	//CTime tStart=CTime::GetCurrentTime();
	//m_sStart=tStart.GetSecond();
	OnBtnInit();
	
}


BOOL CTestDlg::WalkAble(int x,int y, int i)
{
	if ((i+2)%2==0)
		return TRUE;
	
	int tx[8]={1,1,0,-1,-1,-1,0,1};
	int ty[8]={0,-1,-1,-1,0,1,1,1};
	int nxA=x+tx[i-1];
	int nyA=y+ty[i-1];	

	if (i==7)
		i=-1;

	int nxB=x+tx[i+1];
	int nyB=y+ty[i+1];
	
	//CString str;
	//str.Format("nxA=%d,nyA=%d,nxB=%d,nyB=%d,i=%d",nxA,nyA,nxB,nyB,i);
	//MessageBox(str);

	if (map[nxA][nyA]==1 && map[nxB][nyB]==1)
		return TRUE;

	return FALSE;

}