大佬教程收集整理的这篇文章主要介绍了cocos2dx 45度Staggered格式A*寻路 曼哈顿算法(待优化),大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
#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); :rgb(111,hScore,Hscore); ShortestPathStep*,parent,Parent); CC_SYNTHESIZE(bool,inOpen,InOpen); :rgb(111,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(); } //获取毫秒时间 long@H_254_149@msnow() { 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=@H_254_149@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->:rgb(136,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=:rgb(33,p.x,p.y); //CCLOG("left=%s",str->getCString()); aroundNodes->addObject(str); } //右 p=CCPointMake(tPt.x+1,tPt.y); if(isInClosed(p)) { str=:rgb(33,p.y); //CCLOG("right=%s",0)">addObject(str); } //上 p=CCPointMake(tPt.x,tPt.y-2);//-2 if(:rgb(136,p.y); //CCLOG("up=%s",0)">addObject(str); } //下 p=:rgb(111,tPt.y+2);//+2 if(:rgb(136,p.y); //CCLOG("down=%s",0)">addObject(str); } //左上 p=CCPointMake(tPt.x-1+((int)tPt.y&1),tPt.y-1); if(:rgb(136,p.y); //CCLOG("leftUp=%s",0)">addObject(str); } //左下 p=:rgb(111,tPt.y+1); if(:rgb(136,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=:rgb(111,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*寻路 曼哈顿算法(待优化)所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。