#define__ASTARPATHFINDER_H__
 
#include"cocos2d.h"
 
USING_NS_CC;
 
/**
*横向移动一格的路径评分
*/
staticconstintCOST_HORIZONTAL=20;
 
/**
*竖向移动一格的路径评分
*/
staticconstintCOST_VERTICAL=5;
 
/**
*斜向移动一格的路径评分
*/
staticconstintCOST_DIAGONAL=12;
 
classPathInfo;
 
/**
*A星寻路类
*@authorhpking
*
*/
classAStarPathFinder
{
	//未探索的节点列表
cocos2d::CCArray*_openSteps;
	//已探索的,不需要再寻路的节点列表
CCArray*_closedSteps;
 
	//地图相关数据
	PathInfo*_pathInfo;
 
public:
	AStarPathFinder(PathInfo*info);
	virtual~AStarPathFinder();
 
/**
*public寻路
*
*@paramCCPointstartPointtile开始坐标点
*@paramCCPointendPointtile结束坐标点
*@returnCCArray*读取方法:CCPointFromString(string->getCString())
*/
CCArray*find(CCPointstartTilePt,CCPointendTilePt);
 
private:
	//最短路径步数
	classShortestPathStep:publicCCObject
	{
	public:
		boolinitWithPosition(CCPointpos)
		{
			boolbRet=false;
 
			do
			{
				position=pos;
				gScore=0;
				hScore=0;
				parent=NULL;
				inOpen=false;
				inClose=false;
 
				bRet=true;
			}
			while(0);
 
			returnbRet;
		}
 
		intfScore()
		{
			returnthis->getGScore()+this->getHScore();
		}
 
		inlinebooloperator==(constShortestPathStep*other)
		{
			returnisEqual(other);
		}
 
		boolisEqual(constShortestPathStep*other)
		{
			returnthis->getPosition().equals(other->getPosition());
		}
 
		staticShortestPathStep*inst(CCPointpos)
		{
			AStarPathFinder::ShortestPathStep*sps=newShortestPathStep;
 
			if(sps&&sps->initWithPosition(pos))
			{
				sps->autorelease();
				returnsps;
			}
 
			CC_SAFE_DELETE(sps);
			returnNULL;
		}
 
		CC_SYNTHESIZE(CCPoint,position,Position);
		CC_SYNTHESIZE(int,gScore,GScore);
		hScore,HScore);
		ShortestPathStep*,parent,Parent);
		CC_SYNTHESIZE(bool,inOpen,InOpen);
		inClose,InClose);
 
	private:
		CCString*description()
		{
			returnCCString::createWithFormat("pos=[%f,%f],g=%d,h=%d,f=%d",this->getPosition().x,0)">getPosition().y,0)">getGScore(),0)">getHScore(),0)">fScore());
		}
	};
 
private:
voiddestroyLists();
 
createPath(ShortestPathStep*step);//intxStart,intyStart

	voidfindAndSort(ShortestPathStep*step);
 
	voidinsertAndSort(ShortestPathStep*step);
 
/**
*private判断是否超出边界或路点是否可走
*
*@paramCCPointtpt
*@returnbool
*/
boolisWalkable(CCPointtpt);
 
/**
*private计算G值
*
*@paramNode*curNode
*@paramNode*node
*@returnint
*/
intgetGValue(ShortestPathStep*curStep,133)">ShortestPathStep*step);
 
/**
*private计算H值
*
*@paramNode*curNode
*@paramNode*endNode
*@paramNode*node
*@returnint
*/
intgetHValue(ShortestPathStep*endStep,133)">ShortestPathStep*step);
 
getAroundsNode(CCPointtPt);
 
	boolisInClosed(CCPointtPt);
 
voidsetOpenSteps(CCArray*var);
voidsetClosedSteps(setShortestPath(CCArray*var);
};
 
#endif

#include"AStarPathFinder.h"
#include"map/PathInfo.h"
 
PathInfo*info)
{
_pathInfo=info;
_openSteps=NULL;
_closedSteps=NULL;
}
 
AStarPathFinder::~AStarPathFinder()
{
destroyLists();
}
 
//获取毫秒时间
longmsNow()
{
	structcc_timevalnow;
	CCTime::gettimeofdayCocos2d(&now,NULL);
	return(now.tv_sec*1000+now.tv_usec/1000);
}
 
CCArray*AStarPathFinder::CCPointendTilePt)
{
boolisFinded=false;//能否找到路径，true-已找到
 
//到达终点
if(startTilePt.equals(endTilePt))
{
CCLog("You'realreadythere!:P");
returnNULL;
}
 
//终点不可走,直接退出(可优化为最近的可走地点停止)
if(!isWalkable(endTilePt))
{
"blocked!:P");
returnNULL;
}
 
//设置打开和封闭步数
CCArray::create());
create());
 
//CCLog("From:(%f,%f)To(%f,%f)",startTilePt.x,startTilePt.y,endTilePt.x,endTilePt.y);
 
//结束坐标
ShortestPathStep*endStep=ShortestPathStep::inst(endTilePt);
 
//插入开始点
inst(startTilePt));
 
ShortestPathStep*curStep;
longtime1=msNow();
 
do
{
//取出并删除开放列表第一个元素
curStep=(ShortestPathStep*)_openSteps->objectAtIndex(0);
curStep->setInClose(true);
curStep->setInOpen(false);
_closedSteps->addObject(curStep);
_openSteps->removeObjectAtIndex(0);
 
//当前节点==目标节点
if(curStep->equals(endTilePt))
{
isFinded=true;//能达到终点，找到路径
break;
}
 
//取相邻八个方向的节点，去除不可通过和已在关闭列表中的节点
CCArray*aroundNodes=getAroundsNode(curStep->getPosition());
//CCLog("8dirc%d",aroundNodes->count());
CCObject*obj;
CCARRAY_FOREACH(aroundNodes,obj)
{
//计算G，H值
CCString*string=(CCString*)obj;
ShortestPathStep*nextStep=newShortestPathStep;
nextStep->initWithPosition(CCPointFromString(string->getCString()));
 
intg=getGValue(curStep,nextStep);
inth=getHValue(curStep,endStep,nextStep);
 
if(nextStep->getInOpen())//如果节点已在播放列表中
{
//如果该节点新的G值比原来的G值小,修改F,G值，设置该节点的父节点为当前节点
if(g<nextStep->getGScore())
{
nextStep->setGScore(g);
nextStep->setHScore(h);
nextStep->setParent(curStep);
findAndSort(nextStep);
nextStep->release();
}
}
else//如果节点不在开放列表中
{
//插入开放列表中，并按照估价值排序
nextStep->setParent(curStep);
 
insertAndSort(nextStep);
nextStep->release();
}
 
//CCLog("opennum:%d",_openSteps->count());
}
}
while(_openSteps->count()>0);
 
"a*time:%d",0)">msNow()-time1);
 
/*if(_openSteps)
CCLog("finded:%d,openlen%d,closelen%d",isFinded?1:0,_openSteps->count(),_closedSteps->count());*/
 
//找到路径
if(isFinded)
{
CCArray*path=createPath(curStep);
 
destroyLists();
 
returnpath;
}
else//没有找到路径
{
destroyLists();
 
returnNULL;
}
}
 
voiddestroyLists()
{
CC_SAFE_RELEASE_NULL(_openSteps);
CC_SAFE_RELEASE_NULL(_closedSteps);
}
 
ShortestPathStep*step)//intxStart,intyStart
{
CCArray*path=create();
 
CCString*str;
 
do
{
if(step->getParent()!=NULL)
{
str="{%f,%f}",step->getPosition().y);
path->insertObject(str,0);
}
 
step=step->getParent();
}
while(step!=NULL);
 
returnpath;
}
 
voidShortestPathStep*step)
{
unsignedintcount=_openSteps->count();
 
if(count<1)
return;
 
intstepFScore=step->fScore();
 
for(unsignedinti=0;i<count;i++)
{
ShortestPathStep*sps=(objectAtIndex(i);
 
if(stepFScore<=sps->fScore())
_openSteps->insertObject(step,i);
 
if(step->equals(sps->getPosition()))
_openSteps->removeObjectAtIndex(i);
}
}
 
voidShortestPathStep*step)
{
step->setInOpen(true);
 
intstepFScore=step->fScore();
unsignedintcount=_openSteps->count();
 
if(count==0)
_openSteps->addObject(step);
else
{
for(unsignedinti=0;i<count;i++)
{
fScore())
{
_openSteps->i);
return;
}
}
}
}
 
boolCCPointtPt)
{
//1.是否是有效的地图上点（数组边界检查）
if(tPt.x<_pathInfo->startPt.x||tPt.x>=_pathInfo->iCol)
returnfalse;
 
if(tPt.y<_pathInfo->startPt.y||tPt.y>=_pathInfo->iRow)
returnfalse;
 
//2.是否是walkable
return_pathInfo->isWalkable(tPt);
}
 
 
/**
*private计算G值
*
*@paramShortestPathStep*curStep
*@paramShortestPathStep*step
*@returnint
*/
intShortestPathStep*step)
{
intg=0;
 
if(curStep->getPosition().y==step->getPosition().y)//横向左右
{
g=curStep->getGScore()+COST_HORIZONTAL;
}
elseif(curStep->getPosition().y+2==step->getPosition().y||curStep->getPosition().y-2==step->getPosition().y)//竖向上下
{
g=curStep->getGScore()+COST_VERTICAL*2;
}
else//斜向左上左下右上右下
{
g=curStep->getGScore()+COST_DIAGONAL;
}
 
returng;
}
 
/**
*private计算H值
*
*@paramShortestPathStep*curStep
*@paramShortestPathStep*endStep
*@paramShortestPathStep*step
*@returnint
*/
intShortestPathStep*step)
{
if(curStep==NULL||endStep==NULL||step==NULL)
return0;
 
//节点到0，0点的x轴距离
intto0=step->getPosition().x*COST_HORIZONTAL+((int)step->getPosition().y&1)*COST_HORIZONTAL/2;
 
//终止节点到0，0点的x轴距离
intendTo0=endStep->getPosition().x*COST_HORIZONTAL+((int)endStep->getPosition().y&1)*COST_HORIZONTAL/2;
 
returnabs((float)endTo0-(float)to0)+abs((float)endStep->getPosition().y-(float)step->getPosition().y)*COST_VERTICAL;
}
 
CCPointtPt)
{
CCArray*aroundNodes=create();
 
///菱形组合的地图八方向与正常不同
 
//左
CCPointp=CCPointMake(tPt.x-1,tPt.y);
CCString*str;
 
if(isWalkable(p)&&!isInClosed(p))//可走并且不在关闭列表
{
str=p.x,p.y);
//CCLOG("left=%s",str->getCString());
aroundNodes->addObject(str);
}
 
//右
p=CCPointMake(tPt.x+1,tPt.y);
 
if(isInClosed(p))
{
str=p.y);
//CCLOG("right=%s",0)">addObject(str);
}
 
//上
p=CCPointMake(tPt.x,tPt.y-2);//-2
 
if(p.y);
//CCLOG("up=%s",0)">addObject(str);
}
 
//下
p=tPt.y+2);//+2
 
if(p.y);
//CCLOG("down=%s",0)">addObject(str);
}
 
//左上
p=CCPointMake(tPt.x-1+((int)tPt.y&1),tPt.y-1);
 
if(p.y);
//CCLOG("leftUp=%s",0)">addObject(str);
}
 
//左下
p=tPt.y+1);
 
if(p.y);
//CCLOG("leftDown=%s",0)">addObject(str);
}
 
//右上
p=CCPointMake(tPt.x+((int)tPt.y&1),p.y);
//CCLOG("rightUp=%s",0)">addObject(str);
}
 
//右下
p=p.y);
//CCLOG("rightDown=%s",0)">addObject(str);
}
 
returnaroundNodes;
}
 
boolCCPointpt)
{
CCObject*temp;
CCARRAY_FOREACH(_closedSteps,temp)
{
ShortestPathStep*)temp;
 
if(sps->equals(pt))
{
returntrue;
}
}
 
returnfalse;
}
 
voidCCArray*var)
{
if(_openSteps!=var)
{
CC_SAFE_RETAIN(var);
_openSteps=var;
}
}
 
voidCCArray*var)
{
if(_closedSteps!=var)
{
CC_SAFE_RELEASE_NULL(_closedSteps);
CC_SAFE_RETAIN(var);
_closedSteps=var;
}
}
 
voidCCArray*var)
{
/*if(shortestPath!=var)
{
CC_SAFE_RELEASE_NULL(shortestPath);
CC_SAFE_RETAIN(var);
shortestPath=var;
}*/
}