cfindpath.cpp

一个个人开发的rpg游戏＜亚特兰蒂斯传奇＞的源码

//--------------------------------------------------------------------------------------------------------
//                        游戏旬路模块
//CFindPath.cpp
//游戏引擎中的旬路部分
//作者:吴振华(kylinx)(中国科大01级11系)
//E-mail:[e-mail]
//创建于：2003/6/27 by Kylinx
//--------------------------------------------------------------------------------------------------------

#include<math.h>
#include"CFindPath.h"
#include"CError.h"
#include"CMap.h"
#include"CMacro.h"
////////////////////////////////////////////////////////////////////////////////////////////
//构造
////////////////////////////////////////////////////////////////////////////////////////////
CAStarFindPath::CAStarFindPath()
{
	m_ppBest=NULL;
	m_pOpen=NULL;
	m_pClose=NULL;
}
////////////////////////////////////////////////////////////////////////////////////////////
//析构
////////////////////////////////////////////////////////////////////////////////////////////
CAStarFindPath::~CAStarFindPath()
{
	Release();
}
////////////////////////////////////////////////////////////////////////////////////////////
//评估函数
////////////////////////////////////////////////////////////////////////////////////////////
int CAStarFindPath::Evaluation(int x,int y)					//评估函数
{
	return abs(m_nDestX-x)+abs(m_nDestY-y);
}
////////////////////////////////////////////////////////////////////////////////////////////
//释放资源
////////////////////////////////////////////////////////////////////////////////////////////
void CAStarFindPath::Release()
{
	if(m_ppBest)
	{
		for(int i=0;i<this->m_pMap->m_head.Width;i++)
		{
			if(m_ppBest[i])
			{
				delete [] m_ppBest[i];
			}
		}
		delete [] m_ppBest;
		m_ppBest=NULL;
	}
	if(m_pOpen)
	{
		STPathTree*pTemp;
		while(m_pOpen->DeQueue(pTemp))
		{
			delete pTemp;
		}
		delete m_pOpen;
		m_pOpen=NULL;
	}
	if(m_pClose)
	{
		STPathTree*pTemp;
		while(m_pClose->Pop(pTemp))
		{
			delete pTemp;
		}
		delete m_pClose;
		m_pClose=NULL;
	}
}
////////////////////////////////////////////////////////////////////////////////////////////
//尝试一个点
////////////////////////////////////////////////////////////////////////////////////////////
BOOL CAStarFindPath::TryTile(int x,int y,STPathTree*pRoot)
{
	if(x<0 || x>=m_pMap->m_head.Width
		|| y<0 || y>=m_pMap->m_head.Height)
		return false;
	if(m_pMap->m_ppTile[x][y].bCross==false)
		return false;

	STPathTree*pTemp=pRoot;

	while(pTemp)
	{
		if(x==pTemp->nMapX && y==pTemp->nMapY)				//遇到祖先
			return false;
		pTemp=pTemp->pParent;
	}

	if(m_ppBest[x][y]<=pRoot->nSearchDepth+1)				//如果不是最优方案
		return false;

	m_ppBest[x][y]=pRoot->nSearchDepth+1;					//保存最好纪录

	pTemp=new STPathTree(x,y,m_ppBest[x][y],pRoot);
	if(!pTemp)
	{
		m_pLog->WriteMessage("FindPath:New Path Tree Node Failed!\n");
		return false;
	}

	m_pOpen->EnQueue(pTemp,m_ppBest[x][y]+Evaluation(x,y));
	return true;
}
////////////////////////////////////////////////////////////////////////////////////////////
//寻路，返回路径Path
////////////////////////////////////////////////////////////////////////////////////////////
BOOL CAStarFindPath::FindPath(CLog*pLog,CMap*pMap,int SourX,int SourY,int DestX,int DestY,STPath&Path)
{
	LOA_ASSERT(pLog);
	LOA_ASSERT(pMap);

	m_pLog=pLog;
	m_pMap=pMap;

	if(SourX<0 || SourX>=m_pMap->m_head.Width 
		|| SourY<0 || SourY>=m_pMap->m_head.Height
		|| DestX<0 || DestX>=m_pMap->m_head.Width
		|| DestY<0 || DestY>=m_pMap->m_head.Height)			//如果源点或者目标点不在地图范围内
	{
		m_pLog->WriteMessage("FindPath:Source Postion(%d,%d) or Destination Postion(%d,%d) Out Of Map!\n",
							SourX,SourY,DestX,DestY);
		return false;
	}
	m_pOpen=CLagQueue<STPathTree*>::ForeCreate();		//创建Open表
	if(!m_pOpen)
	{
		m_pLog->WriteMessage("Find Path:Create Open Table Failed!\n");
		Release();
		return false;
	}
	m_pClose=KGDStack<STPathTree*>::ForeCreate();			//创建Close表
	if(!m_pClose)
	{
		m_pLog->WriteMessage("Find Path:Create Close Table Failed!\n");
		Release();
		return false;
	}
	m_nSourX=SourX;
	m_nSourY=SourY;
	m_nDestX=DestX;
	m_nDestY=DestY;
															
	m_ppBest=new int*[m_pMap->m_head.Width];
	if(!m_ppBest)
	{
		m_pLog->WriteMessage("FindPath:New Best history table Failed!\n");
		Release();
		return false;
	}
	for(int i=0;i<m_pMap->m_head.Width;i++)
	{
		m_ppBest[i]=new int[m_pMap->m_head.Height];
		if(!m_ppBest[i])
		{
			m_pLog->WriteMessage("FindPath:New Best history table Failed!\n");
			Release();
			return false;
		}
	}
	//初始化历史最好纪录

	for(i=0;i<m_pMap->m_head.Width;i++)
	{
		for(int j=0;j<m_pMap->m_head.Height;j++)
		{
			m_ppBest[i][j]=LOA_MAX_DISTANCE;
		}
	}

	STPathTree*pRoot=new STPathTree(m_nSourX,m_nSourY,0,NULL);
	if(!pRoot)
	{
		m_pLog->WriteMessage("Find Path:Out of memory in new pathtree!\n");
		Release();
		return false;
	}

	m_pOpen->EnQueue(pRoot,Evaluation(m_nSourX,m_nSourY));				//入队
	
	STPathTree*pTemp=pRoot;
	STPathTree*pNode;
	int oldx,oldy;
	int newx,newy;
	int oldcost,newcost;
	while(1)
	{
		if(m_pOpen->GetLength()==0)							//如果open表空了
			break;
		m_pOpen->DeQueue(pNode);							//从open表中取出一个最优的

		m_pClose->Push(pNode);								//放到Close表中
		
		oldx=pTemp->nMapX;
		oldy=pTemp->nMapY;

		newx=pNode->nMapX;
		newy=pNode->nMapY;
		
		oldcost=Evaluation(oldx,oldy);						//旧的代价
		newcost=Evaluation(newx,newy);						//新的代价

		if(newcost<oldcost)									//比较两个的代价
			pTemp=pNode;

		if(newx==m_nDestX && newy==m_nDestY)				//到达目的地
		{
			break;
		}

		TryTile(newx,newy-1,pNode);							//尝试上
		TryTile(newx-1,newy,pNode);							//尝试左
		TryTile(newx,newy+1,pNode);							//尝试下
		TryTile(newx+1,newy,pNode);							//尝试右
	}

	Path.~STPath();
	Path.nLength=pTemp->nSearchDepth+1;
	Path.pPos=new POINT[Path.nLength];
	if(!Path.pPos)
	{
		m_pLog->WriteMessage("FindPath:New Path Failed!\n");
		Release();
		return false;
	}


	for(i=pTemp->nSearchDepth;pTemp!=NULL;i--)				//回溯，保存路径
	{
		Path.pPos[i].x=pTemp->nMapX;
		Path.pPos[i].y=pTemp->nMapY;

		pTemp=pTemp->pParent;
	}
	

	Release();
	return true;
}