cocos2dx 45度Staggered格式A*寻路 曼哈顿算法(待优化)

概述cocos2dx 45度Staggered格式A*寻路 曼哈顿算法(待优化)  转自：http://blog.csdn.net/hpking/article/details/9775289 #ifndef __ASTARPATHFINDER_H__ #define __ASTARPATHFINDER_H__ #include "cocos2d.h" USING_NS_CC; /**  cocos2dx 45度Staggered格式A*寻路 曼哈顿算法(待优化)
转自：http://blog.csdn.net/hpking/article/details/9775289
#ifndef__ASTARpathfinder_H__

#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.是否是walkablereturn_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;}*/}

总结

以上是内存溢出为你收集整理的cocos2dx 45度Staggered格式A*寻路 曼哈顿算法(待优化)全部内容，希望文章能够帮你解决cocos2dx 45度Staggered格式A*寻路 曼哈顿算法(待优化)所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。