cocos2dx A*算法

前端之家收集整理的这篇文章主要介绍了cocos2dx A*算法前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

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

使用cocos2dx 3.2 原理都一样

淡蓝色的点是地图

深蓝色的点是障碍物

绿色的点是路径

暗绿色的点是搜寻过的点

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



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

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

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

  1. #ifndef__HELLOWORLD_SCENE_H__
  2. #define__HELLOWORLD_SCENE_H__
  3. #include"cocos2d.h"
  4. #include"vector"
  5. usingnamespacestd;
  6. USING_NS_CC;
  7. classPathSprite:publiccocos2d::Sprite//继承Sprite类,因为要在里面加些其他变量
  8. {
  9. PathSprite():Sprite()
  10. m_parent=NULL;
  11. m_child=NULL;
  12. m_costToSource=0;
  13. m_FValue=0;
  14. };
  15. public:
  16. staticPathSprite*create(constchar*ch)
  17. PathSprite*pRet=newPathSprite();
  18. if(pRet)
  19. {
  20. pRet->initWithFile(ch);
  21. pRet->autorelease();
  22. returnpRet;
  23. }
  24. else
  25. deletepRet;
  26. pRet=NULL;
  27. returnNULL;
  28. }
  29. PathSprite*m_parent;//父节点
  30. PathSprite*m_child;//子节点
  31. floatm_costToSource;//到起始点的距离
  32. intm_x;//地图坐标
  33. intm_y;
  34. floatm_FValue;
  35. classPathSearchInfo//寻路类(主要负责寻路的参数和逻辑)
  36. public:
  37. staticintm_startX;//开始点
  38. intm_startY;
  39. intm_endX;//结束点
  40. intm_endY;
  41. staticvector<PathSprite*>m_openList;//开放列表(里面存放相邻节点)
  42. staticvector<PathSprite*>m_inspectList;//检测列表(里面存放除了障碍物的节点)
  43. staticvector<PathSprite*>m_pathList;//路径列表
  44. staticvoidbarrierTest(vector<PathSprite*>&pathList,intx,87); font-weight:bold; background-color:inherit">inty)//模拟障碍物
  45. PathSprite*_z=getObjByPointOfMapCoord(pathList,x,y);
  46. if(_z)
  47. _z->setColor(ccColor3B::MAGENTA);
  48. removeObjFromList(pathList,_z);
  49. floatcalculateTwoObjDistance(PathSprite*obj1,PathSprite*obj2)//计算两个物体间的距离
  50. //float_offsetX=obj1->m_x-obj2->m_x;
  51. //float_offsetY=obj1->m_y-obj2->m_y;
  52. //returnsqrt(_offsetX*_offsetX+_offsetY*_offsetY);
  53. float_x=abs(obj2->m_x-obj1->m_x);
  54. float_y=abs(obj2->m_y-obj1->m_y);
  55. return_x+_y;
  56. voidinspectTheAdjacentNodes(PathSprite*node,PathSprite*adjacent,PathSprite*endNode)//把相邻的节点放入开放节点中
  57. if(adjacent)
  58. float_x=abs(endNode->m_x-adjacent->m_x);
  59. float_y=abs(endNode->m_y-adjacent->m_y);
  60. floatF,G,H1,H2,H3;
  61. adjacent->m_costToSource=node->m_costToSource+calculateTwoObjDistance(node,adjacent);//获得累计的路程
  62. G=adjacent->m_costToSource;
  63. //三种算法,感觉H2不错
  64. H1=_x+_y;
  65. H2=hypot(_x,_y);
  66. H3=max(_x,_y);
  67. #if1//A*算法=Dijkstra算法+最佳优先搜索
  68. F=G+H2;
  69. #endif
  70. #if0//Dijkstra算法
  71. F=G;
  72. #endif
  73. #if0//最佳优先搜索
  74. F=H2;
  75. adjacent->m_FValue=F;
  76. adjacent->m_parent=node;//设置父节点
  77. adjacent->setColor(Color3B::ORANGE);//搜寻过的节点设为橘色
  78. node->m_child=adjacent;//设置子节点
  79. PathSearchInfo::removeObjFromList(PathSearchInfo::m_inspectList,0); background-color:inherit">//把检测过的点从检测列表中删除
  80. PathSearchInfo::m_openList.push_back(adjacent);//加入开放列表
  81. staticPathSprite*getMinPathFormOpenList()//从开放节点中获取路径最小值
  82. if(m_openList.size()>0){
  83. PathSprite*_sp=*m_openList.begin();
  84. for(vector<PathSprite*>::iteratoriter=m_openList.begin();iter!=m_openList.end();iter++)
  85. if((*iter)->m_FValue<_sp->m_FValue)
  86. _sp=*iter;
  87. return_sp;
  88. staticPathSprite*getObjByPointOfMapCoord(vector<PathSprite*>&spriteVector,0); background-color:inherit">//根据点获取对象
  89. for(inti=0;i<spriteVector.size();i++)
  90. if(spriteVector[i]->m_x==x&&spriteVector[i]->m_y==y)
  91. returnspriteVector[i];
  92. returnNULL;
  93. boolremoveObjFromList(vector<PathSprite*>&spriteVector,PathSprite*sprite)//从容器中移除对象
  94. for(vector<PathSprite*>::iteratoriter=spriteVector.begin();iter!=spriteVector.end();iter++)
  95. if(*iter==sprite)
  96. spriteVector.erase(iter);
  97. returntrue;
  98. false;
  99. };
  100. classHelloWorld:publiccocos2d::Layer
  101. //there'sno'id'incpp,sowerecommendreturningtheclassinstancepointer
  102. staticcocos2d::Scene*createScene();
  103. //Here'sadifference.Method'init'incocos2d-xreturnsbool,insteadofreturning'id'incocos2d-iphone
  104. virtualboolinit();
  105. //aselectorcallback
  106. voidmenuCloseCallback(cocos2d::Ref*pSender);
  107. //implementthe"staticcreate()"methodmanually
  108. CREATE_FUNC(HelloWorld);
  109. boolonTouchBegan(Touch*touch,Event*event);
  110. voidonTouchMoved(Touch*touch,Event*event);
  111. voidonTouchEnded(Touch*touch,153); font-weight:bold; background-color:inherit">voidcalculatePath();//计算路径
  112. voiddrawPath();//绘制路径
  113. vector<PathSprite*>m_mapList;//地图
  114. voidclearPath();//清理路径
  115. PathSprite*m_player;//人物用于演示行走
  116. intm_playerMoveStep;//人物当前的行程
  117. voidplayerMove();//人物走动
  118. #endif//__HELLOWORLD_SCENE_H__
    #include"HelloWorldScene.h"
  1. vector<PathSprite*>PathSearchInfo::m_openList;
  2. vector<PathSprite*>PathSearchInfo::m_inspectList;
  3. vector<PathSprite*>PathSearchInfo::m_pathList;
  4. intPathSearchInfo::m_startX;
  5. intPathSearchInfo::m_startY;
  6. intPathSearchInfo::m_endX;
  7. intPathSearchInfo::m_endY;
  8. Scene*HelloWorld::createScene()
  9. //'scene'isanautoreleaSEObject
  10. autoscene=Scene::create();
  11. //'layer'isanautoreleaSEObject
  12. autolayer=HelloWorld::create();
  13. //addlayerasachildtoscene
  14. scene->addChild(layer);
  15. //returnthescene
  16. returnscene;
  17. //on"init"youneedtoinitializeyourinstance
  18. boolHelloWorld::init()
  19. //////////////////////////////
  20. //1.superinitfirst
  21. if(!Layer::init())
  22. false;
  23. SizevisibleSize=Director::getInstance()->getVisibleSize();
  24. Vec2origin=Director::getInstance()->getVisibleOrigin();
  25. SizewinSize=Director::getInstance()->getWinSize();
  26. /////////////////////////////
  27. //2.addamenuitemwith"X"image,whichisclickedtoquittheprogram
  28. //youmaymodifyit.
  29. //adda"close"icontoexittheprogress.it'sanautoreleaSEObject
  30. autolistener=EventListenerTouchOneByOne::create();
  31. listener->setSwallowTouches(true);
  32. listener->onTouchBegan=CC_CALLBACK_2(HelloWorld::onTouchBegan,this);
  33. listener->onTouchMoved=CC_CALLBACK_2(HelloWorld::onTouchMoved,153); font-weight:bold; background-color:inherit">this);
  34. 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
  35. int_width=25;
  36. int_heigth=15;
  37. inti=0;i<_heigth;i++)
  38. intj=0;j<_width;j++)
  39. PathSprite*_sp=PathSprite::create("CloseNormal.png");
  40. _sp->m_x=j;
  41. _sp->m_y=i;
  42. Size_size=_sp->getContentSize();
  43. _sp->setPosition(CCPoint(j*_size.width+100,-i*_size.height+600));
  44. m_mapList.push_back(_sp);
  45. this->addChild(_sp);
  46. //设置障碍物
  47. //for(inti=0;i<_heigth*_width/2;i++)
  48. //{
  49. //
  50. //int_x=CCRANDOM_0_1()*_width;
  51. //int_y=CCRANDOM_0_1()*_heigth;
  52. //if(_x==0&&_y==0){
  53. //continue;
  54. //}
  55. //PathSearchInfo::barrierTest(m_mapList,_x,_y);
  56. inti=0;i<10;i++){
  57. PathSearchInfo::barrierTest(m_mapList,5+i,10);
  58. PathSearchInfo::barrierTest(m_mapList,15,i+1);
  59. //PathSprite::getObjByPointOfMapCoord(m_inspectList,2,5)->removeFromParent();
  60. //设置起始和终点
  61. PathSearchInfo::m_startX=0;
  62. PathSearchInfo::m_startY=0;
  63. PathSearchInfo::m_endX=4;
  64. PathSearchInfo::m_endY=9;
  65. m_player=PathSprite::create("CloseSelected1.png");
  66. m_player->setColor(Color3B::RED);
  67. this->addChild(m_player);
  68. m_player->m_x=PathSearchInfo::m_startX;
  69. m_player->m_y=PathSearchInfo::m_startY;
  70. m_player->setPosition(PathSearchInfo::getObjByPointOfMapCoord(m_mapList,PathSearchInfo::m_startX,PathSearchInfo::m_startY)->getPosition());
  71. true;
  72. voidHelloWorld::calculatePath()
  73. //得到开始点的节点
  74. PathSprite*_sp=PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList,PathSearchInfo::m_startY);
  75. PathSprite*_endNode=PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList,PathSearchInfo::m_endX,PathSearchInfo::m_endY);
  76. //因为是开始点把到起始点的距离设为0
  77. _sp->m_costToSource=0;
  78. _sp->m_FValue=0;
  79. //把已经检测过的点从检测列表中删除
  80. //然后加入开放列表
  81. PathSearchInfo::m_openList.push_back(_sp);
  82. PathSprite*_node=NULL;
  83. while(true)
  84. //得到离起始点最近的点
  85. _node=PathSearchInfo::getMinPathFormOpenList();
  86. if(!_node)
  87. //找不到路径
  88. break;
  89. //把计算过的点从开放列表中删除
  90. PathSearchInfo::removeObjFromList(PathSearchInfo::m_openList,_node);
  91. int_x=_node->m_x;
  92. int_y=_node->m_y;
  93. if(_x==PathSearchInfo::m_endX&&_y==PathSearchInfo::m_endY)
  94. //检测8个方向的相邻节点是否可以放入开放列表中
  95. PathSprite*_adjacent=PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList,_x+1,_y+1);
  96. PathSearchInfo::inspectTheAdjacentNodes(_node,_adjacent,_endNode);
  97. _adjacent=PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList,248)"> PathSearchInfo::inspectTheAdjacentNodes(_node,_endNode);
  98. _adjacent=PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList,_y-1);
  99. while(_node)
  100. //PathSprite*_sp=node;
  101. PathSearchInfo::m_pathList.insert(PathSearchInfo::m_pathList.begin(),248)"> _node=_node->m_parent;
  102. voidHelloWorld::drawPath()
  103. for(vector<PathSprite*>::iteratoriter=PathSearchInfo::m_pathList.begin();iter!=PathSearchInfo::m_pathList.end();iter++)
  104. (*iter)->setColor(ccColor3B::GREEN);
  105. boolHelloWorld::onTouchBegan(Touch*touch,Event*event)
  106. //清除之前的路径
  107. clearPath();
  108. autonodePosition=convertToNodeSpace(touch->getLocation());
  109. log("%f,%f",nodePosition.x,nodePosition.y);
  110. inti=0;i<PathSearchInfo::m_inspectList.size();i++)
  111. PathSprite*_sp=PathSearchInfo::m_inspectList[i];
  112. if(_sp->getBoundingBox().containsPoint(nodePosition))
  113. //获取触摸点,设置为终点
  114. PathSearchInfo::m_endX=_sp->m_x;
  115. PathSearchInfo::m_endY=_sp->m_y;
  116. //计算路径
  117. calculatePath();
  118. drawPath();
  119. playerMove();
  120. voidHelloWorld::onTouchMoved(Touch*touch,0); background-color:inherit">//Ifitweren'tfortheTouchDispatcher,youwouldneedtokeepareference
  121. //tothetouchfromtouchBeganandcheckthatthecurrenttouchisthesame
  122. //asthatone.
  123. //Actually,itwouldbeevenmorecomplicatedsinceintheCocosdispatcher
  124. //yougetSetsinsteadof1UITouch,soyou'dneedtoloopthroughtheset
  125. //ineachtouchXXXmethod.
  126. voidHelloWorld::onTouchEnded(Touch*touch,153); font-weight:bold; background-color:inherit">voidHelloWorld::menuCloseCallback(Ref*pSender)
  127. #if(CC_TARGET_PLATFORM==CC_PLATFORM_WP8)||(CC_TARGET_PLATFORM==CC_PLATFORM_WINRT)
  128. MessageBox("Youpressedtheclosebutton.WindowsStoreAppsdonotimplementaclosebutton.","Alert");
  129. return;
  130. Director::getInstance()->end();
  131. #if(CC_TARGET_PLATFORM==CC_PLATFORM_IOS)
  132. exit(0);
  133. voidHelloWorld::clearPath()
  134. for(vector<PathSprite*>::iteratoriter=m_mapList.begin();iter!=m_mapList.end();iter++)
  135. (*iter)->setColor(ccColor3B::WHITE);
  136. (*iter)->m_costToSource=0;
  137. (*iter)->m_FValue=0;
  138. (*iter)->m_parent=NULL;
  139. (*iter)->m_child=NULL;
  140. //把移除了障碍物的地图放入检测列表中
  141. PathSearchInfo::m_inspectList=m_mapList;
  142. PathSearchInfo::m_openList.clear();
  143. PathSearchInfo::m_pathList.clear();
  144. PathSearchInfo::m_startX=m_player->m_x;
  145. PathSearchInfo::m_startY=m_player->m_y;
  146. m_player->stopAllActions();
  147. m_playerMoveStep=0;
  148. voidHelloWorld::playerMove()
  149. m_playerMoveStep++;
  150. if(m_playerMoveStep>=PathSearchInfo::m_pathList.size()){
  151. m_player->m_x=PathSearchInfo::m_pathList[m_playerMoveStep]->m_x;
  152. m_player->m_y=PathSearchInfo::m_pathList[m_playerMoveStep]->m_y;
  153. m_player->runAction(Sequence::create(MoveTo::create(0.2,PathSearchInfo::m_pathList[m_playerMoveStep]->getPosition()),CallFunc::create(this,SEL_CallFunc(&HelloWorld::playerMove)),NULL));
  154. }

转载自http://blog.csdn.net/w18767104183/article/details/39650409
原文链接:https://www.f2er.com/cocos2dx/345914.html

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