cocos2dxA*算法

#ifndef __HELLOWORLD_SCENE_H__
#define __HELLOWORLD_SCENE_H__

#include "cocos2d.h"
#include "vector"
using namespace std;
USING_NS_CC;


class PathSprite : public cocos2d::Sprite//繼承Sprite類(lèi), 因?yàn)橐诶锩婕有┢渌兞?{
 PathSprite():Sprite()
 {
 m_parent = NULL;
 m_child = NULL;
 m_costToSource = 0;
 m_FValue = 0;
 };
public:
 static PathSprite* create(const char* ch)
 {
 PathSprite *pRet = new PathSprite();
 if (pRet )
 {
 pRet->initWithFile(ch);
 pRet->autorelease();
 return pRet;
 }
 else
 {
 delete pRet;
 pRet = NULL;
 return NULL;
 }
 }
 PathSprite* m_parent;//父節(jié)點(diǎn)
 PathSprite* m_child;//子節(jié)點(diǎn)
 float m_costToSource;//到起始點(diǎn)的距離
 int m_x;//地圖坐標(biāo)
 int m_y;
 float m_FValue;
};

class PathSearchInfo//尋路類(lèi)(主要負(fù)責(zé)尋路的參數(shù)和邏輯)
{
public:
 
 static int m_startX;//開(kāi)始點(diǎn)
 static int m_startY;
 static int m_endX;//結(jié)束點(diǎn)
 static int m_endY;
 
 static vector m_openList;//開(kāi)放列表(里面存放相鄰節(jié)點(diǎn))
 static vector m_inspectList;//檢測(cè)列表(里面存放除了障礙物的節(jié)點(diǎn))
 static vector m_pathList;//路徑列表
 static void barrierTest( vector &pathList,int x, int y)//模擬障礙物
 {
 PathSprite* _z = getObjByPointOfMapCoord(pathList, x, y);
 if (_z)
 {
 _z->setColor(ccColor3B::MAGENTA);
 removeObjFromList(pathList, _z);
 }
 }
 static float calculateTwoObjDistance(PathSprite* obj1, PathSprite* obj2)//計(jì)算兩個(gè)物體間的距離
 {
// float _offsetX = obj1->m_x - obj2->m_x;
// float _offsetY = obj1->m_y - obj2->m_y;
// return sqrt( _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;
 }
 static void inspectTheAdjacentNodes(PathSprite* node, PathSprite* adjacent, PathSprite* endNode)//把相鄰的節(jié)點(diǎn)放入開(kāi)放節(jié)點(diǎn)中
 {
 if (adjacent)
 {
 float _x = abs(endNode->m_x - adjacent->m_x);
 float _y = abs(endNode->m_y - adjacent->m_y);
 
 float F , G, H1, H2, H3;
 adjacent->m_costToSource = node->m_costToSource + calculateTwoObjDistance(node, adjacent);//獲得累計(jì)的路程
 G = adjacent->m_costToSource;
 
 //三種算法, 感覺(jué)H2不錯(cuò)
 H1 = _x + _y;
 H2 = hypot(_x, _y);
 H3 = max(_x, _y);

#if 1 //A*算法 = Dijkstra算法 + 最佳優(yōu)先搜索
 F = G + H2;
#endif
#if 0//Dijkstra算法
 F = G;
#endif
#if 0//最佳優(yōu)先搜索
 F = H2;
#endif
 adjacent->m_FValue = F;
 
 adjacent->m_parent = node;//設(shè)置父節(jié)點(diǎn)
 adjacent->setColor(Color3B::ORANGE);//搜尋過(guò)的節(jié)點(diǎn)設(shè)為橘色
 node->m_child = adjacent;//設(shè)置子節(jié)點(diǎn)
 PathSearchInfo::removeObjFromList(PathSearchInfo::m_inspectList, adjacent);//把檢測(cè)過(guò)的點(diǎn)從檢測(cè)列表中刪除
 PathSearchInfo::m_openList.push_back(adjacent);//加入開(kāi)放列表
 }
 }
 static PathSprite* getMinPathFormOpenList()//從開(kāi)放節(jié)點(diǎn)中獲取路徑最小值
 {
 if (m_openList.size()>0) {
 PathSprite* _sp =* m_openList.begin();
 for (vector::iterator iter = m_openList.begin(); iter != m_openList.end(); iter++)
 {
 if ((*iter)->m_FValue < _sp->m_FValue)
 {
 _sp = *iter;
 }
 }
 return _sp;
 }
 else
 {
 return NULL;
 }
 
 }
 static PathSprite* getObjByPointOfMapCoord( vector &spriteVector, int x, int y)//根據(jù)點(diǎn)獲取對(duì)象
 {
 for (int i = 0; i < spriteVector.size(); i++)
 {
 if (spriteVector[i]->m_x == x && spriteVector[i]->m_y == y)
 {
 return spriteVector[i];
 }
 }
 return NULL;
 }
 static bool removeObjFromList(vector &spriteVector, PathSprite* sprite)//從容器中移除對(duì)象
 {
 for (vector::iterator iter = spriteVector.begin(); iter != spriteVector.end(); iter++)
 {
 if (*iter == sprite)
 {
 spriteVector.erase(iter);
 return true;
 }
 }
 return false;
 
 }
};

class HelloWorld : public cocos2d::Layer
{
public:
 // there's no 'id' in cpp, so we recommend returning the class instance pointer
 static cocos2d::Scene* createScene();
 
 // Here's a difference. Method 'init' in cocos2d-x returns bool, instead of returning 'id' in cocos2d-iphone
 virtual bool init(); 
 
 // a selector callback
 void menuCloseCallback(cocos2d::Ref* pSender);
 
 // implement the "static create()" method manually
 CREATE_FUNC(HelloWorld);
 
 bool onTouchBegan(Touch* touch, Event* event);
 void onTouchMoved(Touch* touch, Event* event);
 void onTouchEnded(Touch* touch, Event* event);
 
 void calculatePath();//計(jì)算路徑
 void drawPath();//繪制路徑
 vector m_mapList;//地圖
 
 void clearPath();//清理路徑
 
 PathSprite* m_player;//人物 用于演示行走
 int m_playerMoveStep;//人物當(dāng)前的行程
 void playerMove();//人物走動(dòng)
};

#endif // __HELLOWORLD_SCENE_H__

#include "HelloWorldScene.h"

vector PathSearchInfo::m_openList;

vector PathSearchInfo::m_inspectList;

vector PathSearchInfo::m_pathList;

int PathSearchInfo::m_startX;

int PathSearchInfo::m_startY;

int PathSearchInfo::m_endX;

int PathSearchInfo::m_endY;

Scene* HelloWorld::createScene()
{
 // 'scene' is an autorelease object
 auto scene = Scene::create();
 
 // 'layer' is an autorelease object
 auto layer = HelloWorld::create();
 
 // add layer as a child to scene
 scene->addChild(layer);
 
 // return the scene
 return scene;
}

// on "init" you need to initialize your instance
bool HelloWorld::init()
{
 //////////////////////////////
 // 1. super init first
 if ( !Layer::init() )
 {
 return false;
 }
 
 Size visibleSize = Director::getInstance()->getVisibleSize();
 Vec2 origin = Director::getInstance()->getVisibleOrigin();
 Size winSize = Director::getInstance()->getWinSize();
 
 /////////////////////////////
 // 2. add a menu item with "X" image, which is clicked to quit the program
 // you may modify it.
 
 // add a "close" icon to exit the progress. it's an autorelease object
 
 auto listener = EventListenerTouchOneByOne::create();
 listener->setSwallowTouches(true);
 
 listener->onTouchBegan = CC_CALLBACK_2(HelloWorld::onTouchBegan, this);
 listener->onTouchMoved = CC_CALLBACK_2(HelloWorld::onTouchMoved, this);
 listener->onTouchEnded = CC_CALLBACK_2(HelloWorld::onTouchEnded, this);
 
 _eventDispatcher->addEventListenerWithSceneGraphPriority(listener, this);
 
 
 
 //模擬一張地圖 左上角 為(0,0) 主要是模擬tiledmap 每塊的寬度為1
 int _width = 25;
 int _heigth = 15;
 for (int i = 0; i < _heigth; i++)
 {
 for (int j = 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);
 }
 }
 
 //設(shè)置障礙物
// for (int i = 0; i < _heigth*_width/2; i++)
// {
// 
// int _x = CCRANDOM_0_1()*_width;
// int _y = CCRANDOM_0_1()*_heigth;
// if (_x ==0 && _y == 0) {
// continue;
// }
// PathSearchInfo::barrierTest(m_mapList,_x,_y);
// }
 for (int i = 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();
 
 //設(shè)置起始和終點(diǎn)
 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());
 return true;
}

void HelloWorld::calculatePath()
{
 
 //得到開(kāi)始點(diǎn)的節(jié)點(diǎn)
 PathSprite* _sp = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, PathSearchInfo::m_startX, PathSearchInfo::m_startY);
 //得到開(kāi)始點(diǎn)的節(jié)點(diǎn)
 PathSprite* _endNode = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, PathSearchInfo::m_endX, PathSearchInfo::m_endY);
 //因?yàn)槭情_(kāi)始點(diǎn) 把到起始點(diǎn)的距離設(shè)為0
 _sp->m_costToSource = 0;
 _sp->m_FValue = 0;
 //把已經(jīng)檢測(cè)過(guò)的點(diǎn)從檢測(cè)列表中刪除
 PathSearchInfo::removeObjFromList(PathSearchInfo::m_inspectList, _sp);
 //然后加入開(kāi)放列表
 PathSearchInfo::m_openList.push_back(_sp);
 
 PathSprite* _node = NULL;
 while (true)
 {
 //得到離起始點(diǎn)最近的點(diǎn)
 _node = PathSearchInfo::getMinPathFormOpenList();
 if (!_node)
 {
 //找不到路徑
 break;
 }
 //把計(jì)算過(guò)的點(diǎn)從開(kāi)放列表中刪除
 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)
 {
 break;
 }
 
 //檢測(cè)8個(gè)方向的相鄰節(jié)點(diǎn)是否可以放入開(kāi)放列表中
 PathSprite* _adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x + 1, _y + 1);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 _adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x +1, _y);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 _adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x +1, _y-1);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 _adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x , _y -1);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 _adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x -1, _y - 1);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 _adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x -1, _y);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 _adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x -1, _y+1);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 _adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x , _y+1);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 }
 
 while (_node)
 {
 //PathSprite* _sp = node;
 PathSearchInfo::m_pathList.insert(PathSearchInfo::m_pathList.begin(), _node);
 _node = _node->m_parent;
 }
}


void HelloWorld::drawPath( )
{
 for (vector::iterator iter = PathSearchInfo::m_pathList.begin(); iter != PathSearchInfo::m_pathList.end(); iter++)
 {
 (*iter)->setColor(ccColor3B::GREEN);
 }
 
}


bool HelloWorld::onTouchBegan(Touch* touch, Event* event)
{
 //清除之前的路徑
 clearPath();
 
 auto nodePosition = convertToNodeSpace( touch->getLocation() );
 log("%f, %f", nodePosition.x, nodePosition.y);
 for (int i = 0; i < PathSearchInfo::m_inspectList.size(); i++)
 {
 PathSprite* _sp = PathSearchInfo::m_inspectList[i];
 
 if (_sp->getBoundingBox().containsPoint(nodePosition))
 {
 //獲取觸摸點(diǎn), 設(shè)置為終點(diǎn)
 PathSearchInfo::m_endX = _sp->m_x;
 PathSearchInfo::m_endY = _sp->m_y;
 //計(jì)算路徑
 calculatePath();
 //繪制路徑
 drawPath( );
 playerMove();
 
 }
 
 }
 return true;
}

void HelloWorld::onTouchMoved(Touch* touch, Event* event)
{
 // If it weren't for the TouchDispatcher, you would need to keep a reference
 // to the touch from touchBegan and check that the current touch is the same
 // as that one.
 // Actually, it would be even more complicated since in the Cocos dispatcher
 // you get Sets instead of 1 UITouch, so you'd need to loop through the set
 // in each touchXXX method.
 
}
void HelloWorld::onTouchEnded(Touch* touch, Event* event)
{
 
} 


void HelloWorld::menuCloseCallback(Ref* pSender)
{
#if (CC_TARGET_PLATFORM == CC_PLATFORM_WP8) || (CC_TARGET_PLATFORM == CC_PLATFORM_WINRT)
 MessageBox("You pressed the close button. Windows Store Apps do not implement a close button.","Alert");
 return;
#endif
 
 Director::getInstance()->end();
 
#if (CC_TARGET_PLATFORM == CC_PLATFORM_IOS)
 exit(0);
#endif
}

void HelloWorld::clearPath()
{
 for (vector::iterator iter = 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;
 }
 
 //把移除了障礙物的地圖放入檢測(cè)列表中
 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;
}

void HelloWorld::playerMove()
{
 m_playerMoveStep++;
 
 if (m_playerMoveStep >= PathSearchInfo::m_pathList.size()) {
 return;
 }
 
 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));
 
}