astar.cpp

网络游戏魔域源代码 测试可以完整变异

//		地图坐标原点在左上角

#include <string.h>
#include "astar.h"
#include "error_code.h"


#define NULL				0

const int CHECKSTEP			= 25;					//目标行走检测
const int CONTINUESTEP		= 15;					//追加搜索步

const int MAN_BODILY4_COORDINATE[ BODILY4 ][ 2 ] = { { 0, 0 }, { -1, 0 }, { 0, -1 }, { -1, -1 } };
//	   3 2
//	   1 0
const int COORDINATE_8WAY[ 8 ][ 2 ] = { { 0, 1 }, { -1, 1 }, { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 }, { 1, 0 }, { 1, 1 },  };
//     3 4 5
//     2   6
//     1 0 7
const char DISTANCE2DIRECTION[ 16 ] =		{ -1, 0, -1, 4, 6, 7, -1, 5, -1, -1, -1, -1, 2, 1, -1, 3 };
const char DISTANCE2MIRRORDIRECTION[ 16 ] = { -1, 4, -1, 0, 2, 3, -1, 1, -1, -1, -1, -1, 6, 5, -1, 7 };
//const int StepLong[ 8 ] = { 2, 3, 2, 3, 2, 3, 2, 3 };
const int StepLong[ 8 ] = { 4, 6, 4, 6, 4, 6, 4, 6 };
const char MirrorTrasDirectTab[ 8 ] = { 4, 5, 6, 7, 0, 1, 2, 3 };

//-----------------------------------------------------------------------------

void ASTAR_8WAY::CHAINASN_O::Insert( ASTAR_NODE * pSuccessor )
{
	ASTAR_NODE * pTmp1, * pTmp2;
	int nF;
	
	pSuccessor->cWhere = INOPEN;
	if ( pNode == NULL ){
		pSuccessor->pNextNode = pNode;
		pNode = pSuccessor;
		return;
	}
	
	// insert into OPEN successor wrt f
	nF = pSuccessor->nF;
	pTmp1 = pNode;
	pTmp2 = pNode->pNextNode;
	while ( ( pTmp2 != NULL) && ( pTmp2->nF < nF) ){
		pTmp1 = pTmp2;
		pTmp2 = pTmp2->pNextNode;
	}
	pSuccessor->pNextNode = pTmp2;
	pTmp1->pNextNode = pSuccessor;
}

//-----------------------------------------------------------------------------

ASTAR_8WAY::ASTAR_8WAY( void )
{
	nMapHeight = nMapWidth = 0;
	pAStarIdx = NULL;
	unPathCount = 0;
}

//初始化
int ASTAR_8WAY::InitAStar( int nSizeX, int nSizeY )
{
	int i;
	
	nMapWidth = nSizeX;
	nMapHeight = nSizeY;
	if( ( pAStarIdx = new ASTAR_IDX[ nMapWidth * nMapHeight ] ) == NULL )
		return ERROR_OUTOFMEMORY;
	ClearAstarIdx();
	FreeNodes();
	
	for( i = 0; i < BODILY4; i++ )
		MAN_BODILY_OFFSET[ i ] = nMapWidth * MAN_BODILY4_COORDINATE[ i ][ 1 ] + MAN_BODILY4_COORDINATE[ i ][ 0 ];
	MAN_BODILY_AROUND[ 0 ] = nMapWidth * COORDINATE_8WAY[ 0 ][ 1 ] + COORDINATE_8WAY[ 0 ][ 0 ];
	LINEOFF[ 0 ] = MAN_BODILY_AROUND[ 0 ];
	for( i = 1; i < 8; i++ ){
		MAN_BODILY_AROUND[ i ] = nMapWidth * COORDINATE_8WAY[ i ][ 1 ] + COORDINATE_8WAY[ i ][ 0 ];
		LINEOFF[ i ] = MAN_BODILY_AROUND[ i ] - MAN_BODILY_AROUND[ i - 1 ];
	}
	
	return ALL_OK;
}

inline void ASTAR_8WAY::ClearAstarIdx( void )
{
	memset( pAStarIdx, 0, sizeof( ASTAR_IDX ) * nMapWidth * nMapHeight );
}

void ASTAR_8WAY::SetSafelyZone( void )
{
	int i;
	
	for( i = 0; i < nMapWidth; i++ ){
		SetAStarAtr( i, 0, UNSTAY );
		SetAStarAtr( i, nMapHeight - 1, UNSTAY );
	}
	for( i = 0; i < nMapHeight; i++ ){
		SetAStarAtr( 0, i, UNSTAY );
		SetAStarAtr( nMapWidth - 1, i, UNSTAY );
	}
}

//释放
void ASTAR_8WAY::Release( void )
{
	if( pAStarIdx ) delete []pAStarIdx;
	nMapHeight = nMapWidth = 0;
	pAStarIdx = NULL;
	unPathCount = 0;
}

//清除
void ASTAR_8WAY::FreeNodes( void )
{
	OpenChain.Clear();
	CloseChain.Clear();
	AstarStack.Clear();
	AstarNode.Clear();
}

//设置人占用
void ASTAR_8WAY::SetManInAStarAtr( int nCount, BODYSIZE cType )
{
	return;
	pAStarIdx[ nCount ].SetHasman();
	if( cType == BODILY1 ) return;
	
	ASTAR_IDX * _AStarIdx = pAStarIdx + nCount;
	
	for( int i = 1; i < BODILY4; i++ )
		_AStarIdx[ MAN_BODILY_OFFSET[ i ] ].SetHasman();
}

//清除人占用
void ASTAR_8WAY::ClrManInAStarAtr( int nCount, BODYSIZE cType )
{
	pAStarIdx[ nCount ].SetNoman();
	if( cType == BODILY1 ) return;
	
	ASTAR_IDX * _AStarIdx = pAStarIdx + nCount;
	
	for( int i = 1; i < BODILY4; i++ )
		_AStarIdx[ MAN_BODILY_OFFSET[ i ] ].SetNoman();
}

bool ASTAR_8WAY::TestStayHasMan( ASTAR_IDX * AStarIdx, BODYSIZE cType )
{
	if( AStarIdx->IsUnstayCM() )
		return false;
	for( int i = 1; i < cType; i++ )
		if( AStarIdx[ MAN_BODILY_OFFSET[ i ] ].IsUnstayCM() )
			return false;
		return true;
}

bool ASTAR_8WAY::TestStayNoMan( ASTAR_IDX * AStarIdx, BODYSIZE cType )
{
	if( AStarIdx->IsUnstay() )
		return false;
	for( int i = 1; i < cType; i++ )
		if( AStarIdx[ MAN_BODILY_OFFSET[ i ] ].IsUnstay() )
			return false;
		return true;
}

//寻路
int ASTAR_8WAY::FindPath( int nNowX, int nNowY, int nGoX, int nGoY, STEPDATA * pMan, int nFlags )
{
#ifndef _NOTUSETRY
	try {
#endif
		int nEndCode, nLimitStep;
		int nSX, nSY;
		
		if( nGoX == nNowX && nGoY == nNowY )
			return ATTARGET;
		nEndCode = 0;
		pStepPtr = pMan;
		BSize = pMan->GetBodySize();
		
		if( nFlags & CONTINUESEARCH ){							//测试局部寻路
			if( ( CheckContinue( nNowX, nNowY, nGoX, nGoY ) ) == CONTINUESEARCH ){
				nFlags |= S_TO_E;								//不检测起点,强制正向搜索
				nEndCode |= CONTINUESEARCH;						//局部搜索
				nLimitStep = CONTINUESTEP * 3;
			}
			else
				return NOENOUGHSTEP;							//剩余步数不足
		}
		else
			if( !( nFlags & NOCHECKFRONT ) ){
				nEndCode |= CheckFront( nNowX, nNowY, nGoX, nGoY, nFlags );		//目标封闭检测
				if( nEndCode & ( HAVEPATH | NOPATH | UNWALKABLE ) )		//发现路线或被封死
					return nEndCode;
				nLimitStep = MAXSEARCHSTEP;
			}
			
			if( nFlags & S_TO_E ){
				nSX = nNowX;	//正向搜索
				nSY = nNowY;
				nEndX = nGoX;
				nEndY = nGoY;
			}
			else{
				nSX = nGoX;	//反向搜索
				nSY = nGoY;
				nEndX = nNowX;
				nEndY = nNowY;
			}
			
			ASTAR_NODE * pBestNode, * pNode;
			int i, nEndN;
			
			FreeNodes();
			if( ( pNode = AstarNode.CGetOne() ) == NULL )
				goto error;
			
			i = nMapWidth * nSY + nSX;										//检查目标点是否不可停留
			if( nFlags & HAS_MAN )
				ClrManInAStarAtr( nNowX, nNowY, BSize );
			if( !( nFlags & S_TO_E ) ){
				switch( BSize ){
				case BODILY1:
				default:
					if( nFlags & HAS_MAN ){
						if( pAStarIdx[ i ].IsUnstayCM() ){
							SetManInAStarAtr( nNowX, nNowY, BODILY1 );
							FreeNodes();
							return nEndCode | TARGETNOPATH;
						}
					}
					else
						if( pAStarIdx[ i ].IsUnstay() ){
							FreeNodes();
							return nEndCode | TARGETNOPATH;
						}
						break;
				case BODILY4:
					if( nFlags & HAS_MAN ){
						if( !TestStayHasMan( pAStarIdx + i, BODILY4 ) ){
							SetManInAStarAtr( nNowX, nNowY, BODILY4 );
							FreeNodes();
							return nEndCode | TARGETNOPATH;
						}
					}
					else
						if( !TestStayNoMan( pAStarIdx + i, BODILY4 ) ){
							FreeNodes();
							return nEndCode | TARGETNOPATH;
						}
						break;
				}
			}
			pNode->nG = 0;
			pNode->nH = Calculate( nSX, nSY, nEndX, nEndY );
			pNode->nF = pNode->nH;
			pNode->nX = nSX;
			pNode->nY = nSY;
			pNode->nNumber = i;
			pNode->cWhere = INOPEN;
			OpenChain.Insert( pNode );
			if( ( unPathCount += 0x10 ) <= 0xf ){
				ClearAstarIdx();
				unPathCount = 0x10;
			}
			pAStarIdx[ i ].SetNode( pNode );
			pAStarIdx[ i ].SetCount( unPathCount );
			
			nEndN = nMapWidth * nEndY + nEndX;
			pEndASI = pAStarIdx + nEndN;
			
			if( nFlags & HAS_MAN )
				for( i = 0; i < nLimitStep; i++ ){
					if( ( pBestNode = ReturnBestNode() ) == NULL ){	//不可到达的情况
						FreeNodes();
						nEndCode |= ( nFlags & S_TO_E )? SOURCECLOSE : TARGETCLOSE;
						goto error;
					}
					if( pBestNode->nNumber == nEndN )					//到达
						break;
					nEndCode |= GenerateSuccessorsHasMan( pBestNode );
				}
				else
				{
					for( i = 0; i < nLimitStep; i++ ){
						if( ( pBestNode = ReturnBestNode() ) == NULL ){	//不可到达的情况
							FreeNodes();
							nEndCode |= ( nFlags & S_TO_E )? SOURCECLOSE : TARGETCLOSE;
							goto error;
						}
						if( pBestNode->nNumber == nEndN )					//到达
							break;
						nEndCode |= GenerateSuccessorsNoMan( pBestNode );
					}
				}
				
				ASTAR_NODE * pTemp1, * pTemp2;
				char * pRecordWalkDirect;
				
				if( nFlags & CONTINUESEARCH ){
					if( i == nLimitStep ){								//局部搜索路径满
						if( nFlags & HAS_MAN )
							SetManInAStarAtr( nNowX, nNowY, BSize );
						FreeNodes();
						pStepPtr->AddStep( CONTINUESTEP );
						return NOFOUND | nEndCode;
					}
					else
						pRecordWalkDirect = pStepPtr->GetStepArrayTail();
				}
				else{
					if( i == nLimitStep )
						nEndCode |= NOFOUND;
					pStepPtr->ClearStep();
					pRecordWalkDirect = pStepPtr->GetStepArray();
				}
				i = 0;
				pTemp1 = CloseChain.Get();
				if( nFlags & S_TO_E ){
					while( pTemp1->pParent ){								//记录路径,正向
						pTemp2 = pTemp1->pParent;
						*pRecordWalkDirect = ( pTemp1->cDirect >= 0 )? pTemp1->cDirect : CalculateWay( pTemp1, pTemp2 );
						pTemp1 = pTemp2;
						pRecordWalkDirect++;
						i++;
					}
				}
				else{
					char MirrorPath[ MAXSEARCHSTEP ];
					
					pRecordWalkDirect = MirrorPath + MAXSEARCHSTEP - 1;		//记录路径,反向
					while( pTemp1->pParent ){
						pTemp2 = pTemp1->pParent;
						*pRecordWalkDirect = ( pTemp1->cDirect >= 0 )? MirrorTrasDirectTab[ pTemp1->cDirect ]
							: CalculateMirrWay( pTemp1, pTemp2 );
						pTemp1 = pTemp2;
						pRecordWalkDirect--;
						i++;
					}
					memcpy( pStepPtr->GetStepArrayTail(), pRecordWalkDirect + 1, i );
				}
				if( nFlags & CONTINUESEARCH )
					pStepPtr->AddStep( i );
				else
					pStepPtr->SetStep( i );
				if( nFlags & HAS_MAN )
					SetManInAStarAtr( nNowX, nNowY, BSize );
				FreeNodes();
				return ( HAVEPATH | RECORDPATH | nEndCode );
error:
				FreeNodes();
				if( nFlags & CONTINUESEARCH )
					pStepPtr->AddStep( CONTINUESTEP );
				if( nFlags & HAS_MAN )
					SetManInAStarAtr( nNowX, nNowY, BSize );
				return ( NOPATH | nEndCode );
				
#ifndef _NOTUSETRY
	}
	catch(...)
	{
		FreeNodes();
		return NOPATH;
	}
#endif
}

char ASTAR_8WAY::CalculateWay( ASTAR_NODE * pT1, ASTAR_NODE * pT2 )
{
	return DISTANCE2DIRECTION[ ( ( ( pT2->nX - pT1->nX ) & 0x3 ) << 2 ) | ( ( pT2->nY - pT1->nY ) & 0x3 ) ];
}

char ASTAR_8WAY::CalculateMirrWay( ASTAR_NODE * pT1, ASTAR_NODE * pT2 )
{
	return DISTANCE2MIRRORDIRECTION[ ( ( ( pT2->nX - pT1->nX ) & 0x3 ) << 2 ) | ( ( pT2->nY - pT1->nY ) & 0x3 ) ];
}

ASTAR_NODE * ASTAR_8WAY::ReturnBestNode( void )
{
	ASTAR_NODE * pTmp;
	
	if ( OpenChain.IsEmpty() )
		return NULL;
	pTmp = OpenChain.Get();							// point to first node on OPEN
	CloseChain.Insert( pTmp );
	return pTmp;
}

int ASTAR_8WAY::GenerateSuccessorsNoMan( ASTAR_NODE * pBestNode )
{
	int i;
	int nG, nH, nX, nY;
	ASTAR_IDX * pASI;
	ASTAR_NODE * pSuccessor, * pOld;//, ** ppTemp;
	
	pASI = pAStarIdx + pBestNode->nNumber;
	for( i =0; i < 8; i++ ){
		pASI += LINEOFF[ i ];
		switch( BSize ){
		case BODILY1:
		default:
			if( pASI->IsUnstay() )
				continue;
			break;
		case BODILY4:
			if( !TestStayNoMan( pASI, BODILY4 ) )
				continue;
			break;
		}
		nG = StepLong[ i ] + pBestNode->nG;
		if( pASI->IsAvail( unPathCount ) ){
			pOld = pASI->GetNode();
			pBestNode->pChild[ i ] = pOld;
			/*			ppTemp = pBestNode->pChild;