pathfinder.cpp

一个基于A*算法的寻路类。完全C++实现。

	long oldIndex = 0;
	int i = 0;

	for( i = 0 ; i < 8 ; i++ )
	{
		if( pAroTile[i] == (*RelateTile) )
		{
			index = i;
			break;
		}
	}

	if( index == -1 )
	{
		pos.x = -1;
		pos.y = -1;
		return pos;
	}

	for( i = 0 ; i < 7 ; i++ )
	{
		oldIndex = index;
		index = doFor( index , flags );
		if( isWalkableTile( pAroTile[index] ))
		{
			pos = getPointFromTile( pAroTile[index] );
			*RelateTile = pAroTile[oldIndex];
			break;
		}
	}
	if( pAroTile != NULL )
		delete[] pAroTile;
	return pos;
}

bool PathFinder::isOldPos(SSGameAI::Point NextPos, SSGameAI::Path *pPath)
{
	if( pPath == NULL )
		return false;

	long PreTile;
	long OldTile;
	long dn ,dx;
	long tile = getTileFromPos( NextPos );

	Path* p = getLastMember( pPath );
	OldTile = getTileFromPos( p->item );
	while( pPath != NULL )
	{
		PreTile = getTileFromPos( pPath->item );
		if( PreTile == tile )
			return true;

		dn = OldTile - PreTile;
		dx = OldTile - tile;

		if( dn == SceneTWidth + 1 )
		{
			if( dx == SceneTWidth || dx == 1)
				return true;
		}
		else if( dn == -SceneTWidth - 1 )
		{
			if( dx == -SceneTWidth || dx == -1 )
				return true;
		}
		else if( dn == SceneTWidth - 1 )
		{
			if( dx == SceneTWidth || dx == -1 )
				return true;
		}
		else if( dn == 1 - SceneTWidth )
		{
			if( dx == -SceneTWidth || dx == 1)
				return true;
		}
	}
	return false;
}

void PathFinder::deletePath(SSGameAI::Path *pPath)
{
	Path* pTemp = 0;
	while( pPath != NULL )
	{
		pTemp = pPath;
		pPath = pPath->next;
		delete pTemp;
	}
}

bool PathFinder::arcSearch(SSGameAI::Point StartPos, SSGameAI::Point DestPos, SSGameAI::Path *&pPath, SSGameAI::Path *pOldPath, long flags)
{
	//===================半吸附========================
	Path* pStep = NULL;
	Path* pTemp = NULL;
	Path* pPath1 = NULL;
	long PosTile;
	long StartTile = getTileFromPos(StartPos);
	Point pos = StartPos;
	Point temp;
	temp.x = 0;
	temp.y = 0;

	long RelateTile = getNearTile( pos , DestPos );
	while( StepCount < MaxStep )
	{
		pos = getNextPos( pos , &RelateTile , flags );
		PosTile = getTileFromPos( pos );

		if( PosTile == StartTile || pos.x == -1 )
		{
			deletePath( pPath );
			pPath = 0;
			return false;
		}

		pTemp = Path::getNewNode( temp );
		pTemp->next = NULL;
		if( pStep == NULL )
		{
			pPath = pTemp;
			pPath->prev = NULL;
			pStep = pPath;
		}
		else
		{
			pStep->next = pTemp;
			pTemp->prev = pStep;
			pStep = pStep->next;
		}
		pStep->item = pos;

		if( this->movable( pos , DestPos , pPath1 , true ) )
		{
			pStep->next = pPath1;
			pPath1->prev = pStep;
			return false;
		}
		else if( pPath1 != NULL )
		{
			Path* p = getLastMember( pPath1 );
			if( isOldPos( p->item , pOldPath) )
			{
				deletePath( pPath1 );
				pPath1 = NULL;
			}
			else if( isOldPos( p->item , pPath ) )
			{
				deletePath(pPath1);
				pPath1 = NULL;
			}
			else
			{
				pStep->next = pPath1;
				pPath1->prev = pStep;
				return true;
			}
		}
		StepCount++;
	}
	deletePath( pPath );
	pPath = NULL;
	return false;
}

bool PathFinder::roundSearch(SSGameAI::Point StartPos, SSGameAI::Point DestPos, SSGameAI::Path *&pPath, long flags)
{
	//=========================吸附式搜索=================================
	Path* pStep = NULL;
	Path* pTemp = NULL;
	Path* pPath1 = NULL;
	long PosTile;
	long StartTile = getTileFromPos(StartPos);
	Point pos = StartPos;
	Point temp;
	temp.x = 0;
	temp.y = 0;

	long RelateTile = getNearTile( pos , DestPos );
	while( StepCount < MaxStep )
	{
		pos = getNextPos( pos , &RelateTile , flags );
		PosTile = getTileFromPos( pos );
	
		pTemp = Path::getNewNode( temp );
		pTemp->next = NULL;
		if( pStep == NULL )
		{
			pPath = pTemp;
			pPath->prev = NULL;
			pStep = pPath;
		}
		else
		{
			pStep->next = pTemp;
			pTemp->prev = pStep;
			pStep = pStep->next;
		}
		pStep->item = pos;

		if( PosTile == StartTile || pos.x == -1 )
			return true;

		if( movable( pos , DestPos , pPath1 , true ) )
		{
			pStep->next = pPath1;
			pPath1->prev = pStep;
			return false;
		}
		else
		{
			deletePath( pPath1 );
			pPath1 = NULL;
		}
		StepCount++;
	}
	deletePath(pPath);
	return false;
}

Path* PathFinder::method1(SSGameAI::Point pos, SSGameAI::Point DestPos, long *get, long flags)
{
	long oldCount;
	Path* pPath2 = NULL,
		* pPath3 = NULL,
		* pStep = NULL,
		* pTemp = NULL;

	while( StepCount < MaxStep )
	{
		oldCount = StepCount;
		if( roundSearch( pos , DestPos , pPath3 , flags ) )
		{
			StepCount = oldCount;
			pTemp = pPath3;
			if( arcSearch( pos , DestPos , pPath3 ,pTemp , flags ) )
			{
				deletePath(pTemp);
				pTemp = NULL;
				if( pStep == NULL )
					pPath2 = pPath3;
				else
					pStep->next = pPath3;
			}
			else if( pPath3 != NULL )
			{
				deletePath( pTemp );
				pTemp = NULL;
				if( pStep == NULL )
					pPath2 = pPath3;
				else
					pStep->next = pPath3;
				*get = true;
				break;
			}
			else
			{
				deletePath( pTemp );
				pTemp = NULL;
				deletePath( pPath3 );
				pPath3 = NULL;
				break;
			}
		}
		else if( pPath3 != NULL )
		{
			if( pStep == NULL )
				pPath2 = pPath3;
			else 
				pStep->next = pPath3;
			*get = true;
			break;
		}
		else
			break;
		pStep = getLastMember( pPath2 );
		pos = pStep->item;
	}
	return pPath2;
}

Path* PathFinder::method2(SSGameAI::Point pos, SSGameAI::Point DestPos, long *get, long flags)
{
	Path* pPath2 = NULL;
	if( roundSearch( pos , DestPos , pPath2 , flags ) )
	{
		deletePath( pPath2 );
		pPath2 = NULL;
		*get = false;
	}
	else if( pPath2 != NULL )
	{
		*get = true;
	}
	else
		*get = false;

	return pPath2;
}

Path* PathFinder::method3(SSGameAI::Point pos, SSGameAI::Point DestPos,Path* pPath1, long *get, long flags)
{
	Path* pPath2 = NULL;
	if( arcSearch( pos , DestPos , pPath2 ,pPath1 , flags ) )
	{
		deletePath( pPath2 );
		pPath2 = NULL;
		*get = false;
	}
	else if( pPath2 != NULL )
	{
		*get = true;
	}
	else
		*get = false;

	return pPath2;
}

bool PathFinder::getBasicPath(SSGameAI::Point StartPos, SSGameAI::Point DestPos,Path* &pPath ,  long *get, long flags)
{
	StartPos = adjustPos( StartPos );
	DestPos = adjustPos( DestPos );

	StepCount = 0;

	*get = false;

	Path* pPath1 = NULL;

	if( movable( StartPos , DestPos , pPath1 , true ) )
	{
		pPath = pPath1;
		return false;
	}

	Point pos1;
	Path* pPath1LastMem = NULL;
	Path* pPath2 = NULL;

	pPath1LastMem = getLastMember( pPath1 );
	if( pPath1LastMem != NULL )
		pos1 = pPath1LastMem->item;
	else
		pos1 = StartPos;
	
	if( flags == 1 || flags == -1 )
		pPath2 = method1( pos1 , DestPos , get , flags );
	else if( flags == 2 || flags == -2 )
		pPath2 = method2( pos1 , DestPos , get , flags );
	else if( flags == 3 || flags == -3 )
		pPath2 = method3( pos1 , DestPos ,pPath1 , get , flags );

	if( pPath2 != NULL )
	{
		if( pPath1LastMem != NULL )
		{
			pPath1LastMem->next = pPath2;
			pPath2->prev = pPath1LastMem;
			pPath = pPath1;
		}
		else
			pPath = pPath2;
		return true;
	}
	else
		pPath = pPath1;
	return false;
}

long PathFinder::getPathCount(SSGameAI::Path *pPath)
{
	long count = 0;
	while( pPath != NULL )
	{
		count++;
		pPath = pPath->next;
	}
	return count;
}

Path* PathFinder::getTheBestPath(SSGameAI::Point StartPos, SSGameAI::Point DestPos, long flags)
{
	Path* pPath1 = NULL;
	Path* pPath2 = NULL;
	long get1 , get2;

	if( TileArray[getTileFromPos( StartPos )] != 0 )
		return NULL;

	getBasicPath( StartPos ,DestPos , pPath1 , &get1 , flags );
	getBasicPath( StartPos ,DestPos , pPath2 , &get2 , -flags );

	if( get1 == get2 && get1 )
	{
		long Path1Count , Path2Count;
		Path1Count = getPathCount( pPath1 );
		Path2Count = getPathCount( pPath2 );

		if( Path1Count < Path2Count )
		{
			deletePath( pPath2 );
			pPath2 = NULL;
			return pPath1;
		}
		else
		{
			deletePath( pPath1 );
			pPath1 = NULL;
			return pPath2;
		}
	}
	else if( get1 == 1 )
	{
		deletePath( pPath2 );
		pPath2 = NULL;
		return pPath1;
	}

	else if( get2 == 1 )
	{
		deletePath( pPath1 );
		pPath1 = NULL;
		return pPath2;
	}

	else if( get1 ==3 )
	{
		deletePath( pPath2 );
		pPath2 = NULL;
		return pPath1;
	}
	else if( get2 ==3 )
	{
		deletePath( pPath1 );
		pPath1 = NULL;
		return pPath2;
	}

	deletePath( pPath2 );
	pPath2 = NULL;
	return pPath1;

}