pathfinder.cpp

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

/***********************
*   _PathFinder_cpp_   *
*    A* path finder    *
*    create by si.si   *
*       07.11.18       *
************************/

#include <cmath>

#include "PathFinder.h"

using namespace SSGameAI;


PathFinder::PathFinder(int tlen, int *tArray, long SceneW, long SceneH , long mw ,long mh)
{
	TileLen = tlen;
	HalfTLen = tlen / 2;
	TileArray = tArray;
	StepCount = 0;
	SceneWidth = SceneW;
	SceneHeight = SceneH;
	SceneTWidth = SceneWidth / TileLen;
	SceneTHeight = SceneHeight / TileLen;
	maxw = mw;
	maxh = mh;
	MaxStep = ( mw / tlen ) * ( mh / tlen );
}

PathFinder::PathFinder()
{
	TileLen = 0;
	HalfTLen = 0;
	TileArray = 0;
	MaxStep = 0;
	StepCount = 0;
	SceneWidth = 0;
	SceneHeight = 0;
	SceneTWidth = 0;
	SceneTHeight = 0;
}

PathFinder::~PathFinder()
{
}

//============================Set Method=================================//

void PathFinder::setTileLen(int tlen)
{
	TileLen = tlen;
	HalfTLen = tlen / 2;
}


void PathFinder::setTileArray(int *tArray)
{
	TileArray = tArray;
}

void PathFinder::setSceneWidth(long SceneW)
{
	SceneWidth = SceneW;
	if( TileLen != 0 )
		SceneTWidth = SceneWidth / TileLen;
}

void PathFinder::setSceneHeight(long SceneH)
{
	SceneHeight = SceneH;
	if( TileLen != 0 )
		SceneTHeight = SceneHeight / TileLen;
}

void PathFinder::setMaxRange( long mw , long mh )
{
	maxw = mw;
	maxh = mh;
	MaxStep = ( mw / TileLen ) * ( mh / TileLen );
}

//===============================Get Method=================================//

int PathFinder::getTileLen() const
{
	return TileLen;
}

int PathFinder::getHalfTileLen() const
{
	return HalfTLen;
}

int* PathFinder::getTileArray() const
{
	return TileArray;
}

long PathFinder::getMaxStep() const
{
	return MaxStep;
}

long PathFinder::getStepCount() const
{
	return StepCount;
}

long PathFinder::getSceneWidth() const
{
	return SceneWidth;
}

long PathFinder::getSceneHeight() const
{
	return SceneHeight;
}

long PathFinder::getSceneTWidth() const
{
	return SceneTWidth;
}

long PathFinder::getSceneTHeight() const
{
	return SceneTHeight;
}

//==========================function method======================//

long PathFinder::makeTile(int x, int y)
{
	if( y >= SceneTHeight || y < 0 )
		return -1;
	if( x >= SceneTWidth || x < 0 )
		return -1;
	return y * SceneTWidth + x;
}

long PathFinder::getTileFromPos(SSGameAI::Point pos)
{
	return makeTile( pos.x , pos.y );
}

Point PathFinder::getPointFromTile(long t)
{
	long y = t / SceneTWidth;
	long x = t - t * SceneTWidth;

	Point Pos;
	Pos.x = x * TileLen + HalfTLen;
	Pos.y = y * TileLen + HalfTLen;

	return Pos;
}

long PathFinder::distance(SSGameAI::Point StartPos, SSGameAI::Point DestPos)
{
	long dx = StartPos.x - DestPos.x;
	long dy = StartPos.y - DestPos.y;
	return (long)sqrt((double)( dx * dx + dy * dy ));
}

long PathFinder::distance(long StartTile, long DestTile)
{
	Point start = getPointFromTile( StartTile );
	Point dest = getPointFromTile( DestTile );
	return distance( start , dest );
}

Point PathFinder::adjustPos(SSGameAI::Point pos)
{
	return getPointFromTile( getTileFromPos( pos ) );
}

long* PathFinder::getAroundTile(SSGameAI::Point pos)
{
	long* NearTiles = new long[8];

	long midTile = getTileFromPos( pos );
	long index = midTile / SceneTWidth;
	long leave = midTile - index * SceneTWidth;

	if( midTile == 0 )
	{
		NearTiles[0] = -1;
		NearTiles[1] = -1;
		NearTiles[2] = -1;
		NearTiles[3] = 1;
		NearTiles[4] = SceneTWidth + 1;
		NearTiles[5] = SceneTWidth;
		NearTiles[6] = -1;
		NearTiles[7] = -1;
	}
	else if( midTile == SceneTWidth - 1 )
	{
		NearTiles[0] = -1;
		NearTiles[1] = -1;
		NearTiles[2] = -1;
		NearTiles[3] = -1;
		NearTiles[4] = SceneTWidth + midTile;
		NearTiles[5] = SceneTWidth + midTile -1;
		NearTiles[6] = -1;
		NearTiles[7] = -1;
	}
	else if( midTile == SceneTHeight * SceneTWidth - 1 )
	{
		NearTiles[0] = midTile - SceneTWidth - 1;
		NearTiles[1] = midTile - SceneTWidth;
		NearTiles[2] = -1;
		NearTiles[3] = -1;
		NearTiles[4] = -1;
		NearTiles[5] = -1;
		NearTiles[6] = -1;
		NearTiles[7] = midTile - 1;
	}
	else if( (index == SceneTHeight - 1) && leave == 0 )
	{
		NearTiles[0] = -1;
		NearTiles[1] = midTile - SceneTWidth;
		NearTiles[2] = midTile - SceneTWidth + 1;
		NearTiles[3] = midTile + 1;
		NearTiles[4] = -1;
		NearTiles[5] = -1;
		NearTiles[6] = -1;
		NearTiles[7] = -1;
	}

	else if( leave == 0 )
	{
	    NearTiles[0] = -1;
		NearTiles[1] = midTile - SceneTWidth;
		NearTiles[2] = midTile - SceneTWidth + 1;
		NearTiles[3] = midTile + 1;
		NearTiles[4] = midTile + SceneTWidth + 1;
		NearTiles[5] = midTile + SceneTWidth;
		NearTiles[6] = -1;
		NearTiles[7] = -1;
	}
	else if( index == 0 )
	{
		NearTiles[0] = -1;
		NearTiles[1] = -1;
		NearTiles[2] = -1;
		NearTiles[3] = midTile + 1;
		NearTiles[4] = midTile + SceneTWidth + 1;
		NearTiles[5] = midTile + SceneTWidth;
		NearTiles[6] = midTile + SceneTWidth - 1;
		NearTiles[7] = midTile - 1;
	}
	else if( index == SceneTHeight - 1 )
	{
		NearTiles[0] = midTile - SceneTWidth - 1 ;
		NearTiles[1] = midTile - SceneTWidth;
		NearTiles[2] = midTile - SceneTWidth + 1;
		NearTiles[3] = midTile + 1;
		NearTiles[4] = -1;
		NearTiles[5] = -1;
		NearTiles[6] = -1;
		NearTiles[7] = midTile - 1;
	}
	else if( leave == SceneTWidth -1 )
	{
		NearTiles[0] = midTile - SceneTWidth - 1 ;
		NearTiles[1] = midTile - SceneTWidth;
		NearTiles[2] = -1;
		NearTiles[3] = -1;
		NearTiles[4] = -1;
		NearTiles[5] = midTile + SceneTWidth;
		NearTiles[6] = midTile + SceneTWidth - 1;
		NearTiles[7] = midTile - 1;
	}
	else
	{
		NearTiles[0] = midTile - SceneTWidth - 1 ;
		NearTiles[1] = midTile - SceneTWidth;
		NearTiles[2] = midTile - SceneTWidth + 1;
		NearTiles[3] = midTile + 1;
		NearTiles[4] = midTile + SceneTWidth + 1;
		NearTiles[5] = midTile + SceneTWidth;
		NearTiles[6] = midTile + SceneTWidth - 1;
		NearTiles[7] = midTile - 1;
	}
	return NearTiles;
}

long PathFinder::getNearTile(SSGameAI::Point pos, SSGameAI::Point DestPos)
{
	long* Tiles = 0;
	long destTile = 0;
	long distances[8];
	int Min = 0;

	destTile = getTileFromPos( DestPos );
	Tiles = getAroundTile( pos );
	
	int i = 0;
	for( i ; i < 8 ; i++ )
	{
		distances[i] = distance( Tiles[i] , destTile );	
		if( distances[Min] > distances[i] )
			Min = i;
	}
	destTile = Tiles[Min];
	if( Tiles )
		delete[] Tiles; 
	return destTile;
}

bool PathFinder::movable(SSGameAI::Point StartPos, SSGameAI::Point DestPos, SSGameAI::Path *&pPath, bool flags)
{
	pPath = 0;

	long step;
	long ex = 0 , ey = 0,dx , dy , incx , incy;

	//======Bresenham, direction searching========

	long StartTile = getTileFromPos( StartPos );
	long DestTile = getTileFromPos( DestPos );
	long StartY = StartTile / SceneTWidth;
	long StartX = StartTile - SceneTWidth * StartY;
	long DestY = DestTile / SceneTWidth;
	long DestX = DestTile - SceneTWidth * DestY;

	dx = DestX - StartX;
	dy = DestY - StartY;

	if( dx == 0 )
		incx = 0;
	else
		incx = dx > 0 ? 1 : -1;

	if( dy == 0 )
		incy = 0;
	else 
		incy = dy > 0 ? 1 : -1;

	if( dx < 0 )
		dx = -dx;
	if( dy < 0 )
		dy = -dy;

	step = dx > dy ? dx : dy;

	//========Bresenham , tile searching===============
	long aimTile;
	Path* pStep = NULL ;
	Path* pTemp = NULL;
	Point tempPos;
	tempPos.x = 0;
	tempPos.y = 0;

	ex = dx;
	ey = dy;
	int i = 0;
	for( i ; i < step && StepCount < MaxStep ; i++ )
	{
		ex += dx;
		ey += dy;
		
		if( ex > step )
		{
			ex -= step;
			StartX += incx;
		}
		if( ey > step )
		{
			ey -= step;
			StartY += incy;
		}

		aimTile = makeTile( StartX , StartY );
		if( aimTile == -1 )
			return false;

		if( TileArray[aimTile] != 0 )
			return false;

		if( flags == true )
		{
			StepCount++;
			pTemp = Path::getNewNode( tempPos );
			if( pStep == NULL )
			{
				pPath = pTemp;
				pPath->prev = NULL;
				pStep = pPath;
			}
			else
			{
				pStep->next = pTemp;
				pTemp->prev = pStep;
				pStep = pStep->next;
			}
			pStep->item = getPointFromTile( aimTile );
		}

	}
	return true;
}

Path* PathFinder::getLastMember(SSGameAI::Path *pPath)
{
	if( pPath == NULL)
		return NULL;
	while( pPath->next != NULL )
	{
		pPath = pPath->next;
	}
	return pPath;
}

bool PathFinder::isWalkableTile(long tileId)
{
	if( tileId == -1 )
		return false;
	if( this->TileArray[tileId] == 0 )
		return true;

	return false;
}

long PathFinder::doFor(long index, long flags)
{
	if( flags > 0 )
	{
		if(  index < 7 && index > 0 )
			index++;
		else
			index = 0;
	}
	else
	{
		if( index <= 7 && index > 0 )
			--index;
		else 
			index = 7;
	}
	return index;
}

Point PathFinder::getNextPos(SSGameAI::Point pos, long *RelateTile, long flags)
{
	long* pAroTile = getAroundTile( pos );
	long index = -1;