cocos2dx A*算法

头文件和源文件复制到项目中就能用了! have fun

使用cocos2dx 3.2 原理都一样

淡蓝色的点是地图

深蓝色的点是障碍物

绿色的点是路径

暗绿色的点是搜寻过的点

红色的点是按路径行走的点

dijkstra算法会发现路径最短,但寻找过的路径比较多(计算速度慢)

最佳优先搜索算法会发现寻找过的路径少了(计算速度提高了),但走了许多弯路

A星算法结合了上面2种算法即寻找到了最短路径,搜寻过的路径也比较少

[cpp]view plaincopy 
   @L_301_3@ 
    
   
 #ifndef__HELLOWORLD_SCENE_H__
 #define__HELLOWORLD_SCENE_H__
 
 #include"cocos2d.h"
 #include"vector"
 usingnamespacestd;
 USING_NS_CC;
 
classPathSprite:publiccocos2d::Sprite//继承Sprite类,因为要在里面加些其他变量
 {
 PathSprite():Sprite()
 m_parent=NULL;
 m_child=NULL;
 m_costToSource=0;
 m_FValue=0;
 };
 public:
staticPathSprite*create(constchar*ch)
 PathSprite*pRet=newPathSprite();
if(pRet)
 {
 pRet->initWithFile(ch);
 pRet->autorelease();
returnpRet;
 }
else
deletepRet;
 pRet=NULL;
returnNULL;
 }
 PathSprite*m_parent;//父节点
 PathSprite*m_child;//子节点
 floatm_costToSource;//到起始点的距离
 intm_x;//地图坐标
intm_y;
floatm_FValue;
classPathSearchInfo//寻路类(主要负责寻路的参数和逻辑)
public:
staticintm_startX;//开始点
intm_startY;
intm_endX;//结束点
intm_endY;
staticvector<PathSprite*>m_openList;//开放列表(里面存放相邻节点)
staticvector<PathSprite*>m_inspectList;//检测列表(里面存放除了障碍物的节点)
staticvector<PathSprite*>m_pathList;//路径列表
staticvoidbarrierTest(vector<PathSprite*>&pathList,intx,87); font-weight:bold; background-color:inherit">inty)//模拟障碍物
 PathSprite*_z=getObjByPointOfMapCoord(pathList,x,y);
if(_z)
 _z->setColor(ccColor3B::MAGENTA);
 removeObjFromList(pathList,_z);
floatcalculateTwoObjDistance(PathSprite*obj1,PathSprite*obj2)//计算两个物体间的距离
 //float_offsetX=obj1->m_x-obj2->m_x;
 //float_offsetY=obj1->m_y-obj2->m_y;
 
  @H_404_418@//returnsqrt(_offsetX*_offsetX+_offsetY*_offsetY);float_x=abs(obj2->m_x-obj1->m_x);
float_y=abs(obj2->m_y-obj1->m_y);
return_x+_y;
voidinspectTheAdjacentNodes(PathSprite*node,PathSprite*adjacent,PathSprite*endNode)//把相邻的节点放入开放节点中
if(adjacent)
float_x=abs(endNode->m_x-adjacent->m_x);
float_y=abs(endNode->m_y-adjacent->m_y);
floatF,G,H1,H2,H3;
 adjacent->m_costToSource=node->m_costToSource+calculateTwoObjDistance(node,adjacent);//获得累计的路程
 G=adjacent->m_costToSource;
//三种算法,感觉H2不错
 H1=_x+_y;
 H2=hypot(_x,_y);
 H3=max(_x,_y);
 #if1//A*算法=Dijkstra算法+最佳优先搜索
 F=G+H2;
 #endif
 #if0//Dijkstra算法
 F=G;
 #endif
 #if0//最佳优先搜索
 F=H2;
 adjacent->m_FValue=F;
 adjacent->m_parent=node;//设置父节点
 adjacent->setColor(Color3B::ORANGE);//搜寻过的节点设为橘色
 node->m_child=adjacent;//设置子节点
 PathSearchInfo::removeObjFromList(PathSearchInfo::m_inspectList,0); background-color:inherit">//把检测过的点从检测列表中删除
 PathSearchInfo::m_openList.push_back(adjacent);//加入开放列表
staticPathSprite*getMinPathFormOpenList()//从开放节点中获取路径最小值
if(m_openList.size()>0){
 PathSprite*_sp=*m_openList.begin();
for(vector<PathSprite*>::iteratoriter=m_openList.begin();iter!=m_openList.end();iter++)
if((*iter)->m_FValue<_sp->m_FValue)
 _sp=*iter;
return_sp;
staticPathSprite*getObjByPointOfMapCoord(vector<PathSprite*>&spriteVector,0); background-color:inherit">//根据点获取对象
for(inti=0;i<spriteVector.size();i++)
if(spriteVector[i]->m_x==x&&spriteVector[i]->m_y==y)
returnspriteVector[i];
returnNULL;
boolremoveObjFromList(vector<PathSprite*>&spriteVector,PathSprite*sprite)//从容器中移除对象
for(vector<PathSprite*>::iteratoriter=spriteVector.begin();iter!=spriteVector.end();iter++)
if(*iter==sprite)
 spriteVector.erase(iter);
returntrue;
false;
 };
classHelloWorld:publiccocos2d::Layer
//there'sno'id'incpp,sowerecommendreturningtheclassinstancepointer
staticcocos2d::Scene*createScene();
//Here'sadifference.Method'init'incocos2d-xreturnsbool,insteadofreturning'id'incocos2d-iphone
virtualboolinit();
 
  @H_404_418@//aselectorcallbackvoidmenuCloseCallback(cocos2d::Ref*pSender);
//implementthe"staticcreate()"methodmanually
 CREATE_FUNC(HelloWorld);
boolonTouchBegan(Touch*touch,Event*event);
voidonTouchMoved(Touch*touch,Event*event);
voidonTouchEnded(Touch*touch,153); font-weight:bold; background-color:inherit">voidcalculatePath();//计算路径
voiddrawPath();//绘制路径
 vector<PathSprite*>m_mapList;//地图
voidclearPath();//清理路径
 PathSprite*m_player;//人物用于演示行走
intm_playerMoveStep;//人物当前的行程
voidplayerMove();//人物走动
 #endif//__HELLOWORLD_SCENE_H__

 
   
#include"HelloWorldScene.h" vector<PathSprite*>PathSearchInfo::m_openList;
 vector<PathSprite*>PathSearchInfo::m_inspectList;
 vector<PathSprite*>PathSearchInfo::m_pathList;
intPathSearchInfo::m_startX;
intPathSearchInfo::m_startY;
intPathSearchInfo::m_endX;
intPathSearchInfo::m_endY;
 Scene*HelloWorld::createScene()
//'scene'isanautoreleaSEObject
 autoscene=Scene::create();
 
  @H_404_418@//'layer'isanautoreleaSEObject autolayer=HelloWorld::create();
//addlayerasachildtoscene
 scene->addChild(layer);
 
  @H_404_418@//returnthescenereturnscene;
//on"init"youneedtoinitializeyourinstance
boolHelloWorld::init()
//////////////////////////////
//1.superinitfirst
if(!Layer::init())
false;
 SizevisibleSize=Director::getInstance()->getVisibleSize();
 Vec2origin=Director::getInstance()->getVisibleOrigin();
 SizewinSize=Director::getInstance()->getWinSize();
 
  @H_404_418@///////////////////////////// 
  @H_404_418@//2.addamenuitemwith"X"image,whichisclickedtoquittheprogram//youmaymodifyit.
 
  @H_404_418@//adda"close"icontoexittheprogress.it'sanautoreleaSEObject autolistener=EventListenerTouchOneByOne::create();
 listener->setSwallowTouches(true);
 listener->onTouchBegan=CC_CALLBACK_2(HelloWorld::onTouchBegan,this);
 listener->onTouchMoved=CC_CALLBACK_2(HelloWorld::onTouchMoved,153); font-weight:bold; background-color:inherit">this);
 listener->onTouchEnded=CC_CALLBACK_2(HelloWorld::onTouchEnded,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> _eventDispatcher->addEventListenerWithSceneGraPHPriority(listener,0); background-color:inherit">//模拟一张地图左上角为(0,0)主要是模拟tiledmap每块的宽度为1
int_width=25;
int_heigth=15;
inti=0;i<_heigth;i++)
intj=0;j<_width;j++)
 PathSprite*_sp=PathSprite::create("CloseNormal.png");
 _sp->m_x=j;
 _sp->m_y=i;
 Size_size=_sp->getContentSize();
 _sp->setPosition(CCPoint(j*_size.width+100,-i*_size.height+600));
 m_mapList.push_back(_sp);
this->addChild(_sp);
 
  @H_404_418@//设置障碍物 
  @H_404_418@//for(inti=0;i<_heigth*_width/2;i++)//{
 
  @H_404_418@////int_x=CCRANDOM_0_1()*_width;
 
  @H_404_418@//int_y=CCRANDOM_0_1()*_heigth;//if(_x==0&&_y==0){
 
  @H_404_418@//continue;//}
 
  @H_404_418@//PathSearchInfo::barrierTest(m_mapList,_x,_y);inti=0;i<10;i++){
 PathSearchInfo::barrierTest(m_mapList,5+i,10);
 PathSearchInfo::barrierTest(m_mapList,15,i+1);
//PathSprite::getObjByPointOfMapCoord(m_inspectList,2,5)->removeFromParent();
 
  @H_404_418@//设置起始和终点 PathSearchInfo::m_startX=0;
 PathSearchInfo::m_startY=0;
 PathSearchInfo::m_endX=4;
 PathSearchInfo::m_endY=9;
 m_player=PathSprite::create("CloseSelected1.png");
 m_player->setColor(Color3B::RED);
this->addChild(m_player);
 m_player->m_x=PathSearchInfo::m_startX;
 m_player->m_y=PathSearchInfo::m_startY;
 m_player->setPosition(PathSearchInfo::getObjByPointOfMapCoord(m_mapList,PathSearchInfo::m_startX,PathSearchInfo::m_startY)->getPosition());
true;
voidHelloWorld::calculatePath()
//得到开始点的节点
 PathSprite*_sp=PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList,PathSearchInfo::m_startY);
 PathSprite*_endNode=PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList,PathSearchInfo::m_endX,PathSearchInfo::m_endY);
//因为是开始点把到起始点的距离设为0
 _sp->m_costToSource=0;
 _sp->m_FValue=0;
 
  @H_404_418@//把已经检测过的点从检测列表中删除404_418@//然后加入开放列表
 PathSearchInfo::m_openList.push_back(_sp);
 PathSprite*_node=NULL;
while(true)
//得到离起始点最近的点
 _node=PathSearchInfo::getMinPathFormOpenList();
if(!_node)
//找不到路径
break;
 
  @H_404_418@//把计算过的点从开放列表中删除 PathSearchInfo::removeObjFromList(PathSearchInfo::m_openList,_node);
int_x=_node->m_x;
int_y=_node->m_y;
if(_x==PathSearchInfo::m_endX&&_y==PathSearchInfo::m_endY)
 
  @H_404_418@//检测8个方向的相邻节点是否可以放入开放列表中 PathSprite*_adjacent=PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList,_x+1,_y+1);
 PathSearchInfo::inspectTheAdjacentNodes(_node,_adjacent,_endNode);
 _adjacent=PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList,248)"> PathSearchInfo::inspectTheAdjacentNodes(_node,_endNode);
 _adjacent=PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList,_y-1);
while(_node)
 
  @H_404_418@//PathSprite*_sp=node; PathSearchInfo::m_pathList.insert(PathSearchInfo::m_pathList.begin(),248)"> _node=_node->m_parent;
voidHelloWorld::drawPath()
for(vector<PathSprite*>::iteratoriter=PathSearchInfo::m_pathList.begin();iter!=PathSearchInfo::m_pathList.end();iter++)
 (*iter)->setColor(ccColor3B::GREEN);
boolHelloWorld::onTouchBegan(Touch*touch,Event*event)
//清除之前的路径
 clearPath();
 autonodePosition=convertToNodeSpace(touch->getLocation());
 log("%f,%f",nodePosition.x,nodePosition.y);
inti=0;i<PathSearchInfo::m_inspectList.size();i++)
 PathSprite*_sp=PathSearchInfo::m_inspectList[i];
if(_sp->getBoundingBox().containsPoint(nodePosition))
 
  @H_404_418@//获取触摸点,设置为终点 PathSearchInfo::m_endX=_sp->m_x;
 PathSearchInfo::m_endY=_sp->m_y;
 
  @H_404_418@//计算路径 calculatePath();
 drawPath();
 playerMove();
voidHelloWorld::onTouchMoved(Touch*touch,0); background-color:inherit">//Ifitweren'tfortheTouchDispatcher,youwouldneedtokeepareference
//tothetouchfromtouchBeganandcheckthatthecurrenttouchisthesame
 
  @H_404_418@//asthatone.//Actually,itwouldbeevenmorecomplicatedsinceintheCocosdispatcher
 
  @H_404_418@//yougetSetsinsteadof1UITouch,soyou'dneedtoloopthroughtheset//ineachtouchXXXmethod.
voidHelloWorld::onTouchEnded(Touch*touch,153); font-weight:bold; background-color:inherit">voidHelloWorld::menuCloseCallback(Ref*pSender)
 #if(CC_TARGET_PLATFORM==CC_PLATFORM_WP8)||(CC_TARGET_PLATFORM==CC_PLATFORM_WINRT)
 MessageBox("Youpressedtheclosebutton.WindowsStoreAppsdonotimplementaclosebutton.","Alert");
return;
 Director::getInstance()->end();
 #if(CC_TARGET_PLATFORM==CC_PLATFORM_IOS)
 exit(0);
voidHelloWorld::clearPath()
for(vector<PathSprite*>::iteratoriter=m_mapList.begin();iter!=m_mapList.end();iter++)
 (*iter)->setColor(ccColor3B::WHITE);
 (*iter)->m_costToSource=0;
 (*iter)->m_FValue=0;
 (*iter)->m_parent=NULL;
 (*iter)->m_child=NULL;
//把移除了障碍物的地图放入检测列表中
 PathSearchInfo::m_inspectList=m_mapList;
 PathSearchInfo::m_openList.clear();
 PathSearchInfo::m_pathList.clear();
 PathSearchInfo::m_startX=m_player->m_x;
 PathSearchInfo::m_startY=m_player->m_y;
 m_player->stopAllActions();
 m_playerMoveStep=0;
voidHelloWorld::playerMove()
 m_playerMoveStep++;
if(m_playerMoveStep>=PathSearchInfo::m_pathList.size()){
 m_player->m_x=PathSearchInfo::m_pathList[m_playerMoveStep]->m_x;
 m_player->m_y=PathSearchInfo::m_pathList[m_playerMoveStep]->m_y;
 m_player->runAction(Sequence::create(MoveTo::create(0.2,PathSearchInfo::m_pathList[m_playerMoveStep]->getPosition()),CallFunc::create(this,SEL_CallFunc(&HelloWorld::playerMove)),NULL));
 }
 
  
  
 
 
  转载自http://blog.csdn.net/w18767104183/article/details/39650409 
 

cocos2dx A*算法

猜你在找的Cocos2d-x相关文章