你是否在做一款游戏的时候想创造一些怪兽或者游戏主角，让它们移动到特定的位置，避开墙壁和障碍物呢？如果是的话，请看这篇教程，我们会展示如何使用A星寻路算法来实现它！

A星算法简介：

A*搜寻算法俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。

实现原理：

可参考这两篇文章：

http://www.raywenderlich.com/zh-hans/21503/a星寻路算法介绍 

http://www.raywenderlich.com/zh-hans/21315/如何使用cocos2d实现a星寻路算法

实现代码：

1.创建ShortestPathStep类，代表路径上的一步操作；

ShortestPathStep.h

 

#ifndef __AStarDemo__ShortestPathStep__#define __AStarDemo__ShortestPathStep__#include "cocos2d.h"USING_NS_CC;class ShortestPathStep:public CCNode{public:    ShortestPathStep(void);    ~ShortestPathStep(void);    //CREATE_FUNC(ShortestPathStep);        //m_pos表示方块的坐标;  GScore表示这是开始点到当前点之间的方块数目;    //HScore表示当前点到终点之前的方块估算值;  m_Parent表示它自身的前继    CC_SYNTHESIZE(CCPoint, m_pos, Pos);	CC_SYNTHESIZE(float,m_fGScore,GScore);	CC_SYNTHESIZE(float,m_fHScore,HScore);    CC_SYNTHESIZE(ShortestPathStep*,m_Parent,Parent);        bool InitWithPosition(CCPoint point);	bool IsEqual(ShortestPathStep* step);        //方块的score值（它是F和G的和)    float getFScore();    	bool operator == (const ShortestPathStep& other);};#endif /* defined(__AStarDemo__ShortestPathStep__) */

ShortestPathStep.cpp

 

#include "ShortestPathStep.h"ShortestPathStep::ShortestPathStep(void){    }ShortestPathStep::~ShortestPathStep(void){    }bool ShortestPathStep::InitWithPosition(CCPoint point){    bool pRet = false;    if (CCNode::node()) {        m_pos = point;        m_fGScore = 0;        m_fHScore = 0;        m_Parent = NULL;        pRet = true;    }    return pRet;}bool ShortestPathStep::IsEqual(ShortestPathStep *step){    return this->m_pos.equals(step->getPos());}float ShortestPathStep::getFScore(){    return (m_fGScore+m_fHScore);}bool ShortestPathStep::operator==(const ShortestPathStep &other){    return (other.getPos().equals(this->m_pos));}

2.创建头文件resource,添加必要宏定义

resource.h

 

#ifndef AStarDemo_resource_h#define AStarDemo_resource_h#define IDS_PROJNAME                100#define IDR_ASTARDEMO               100#define ID_FILE_NEW_WINDOW          32771#ifdef APSTUDIO_INVOKED#ifndef APSTUDIO_READONLY_SYMBOLS#define _APS_NEXT_RESOURCE_VALUE     201#define _APS_NEXT_CONTROL_VALUE      1000#define _APS_NEXT_SYMED_VALUE        101#define _APS_NEXT_COMMAND_VALUE      32775#endif#endif

3.创建AStar类，实现A星算法基本操作

AStar.h

 

#ifndef __AStarDemo__AStar__#define __AStarDemo__AStar__#include "cocos2d.h"USING_NS_CC;class ShortestPathStep;typedef struct st_AStar_Coord_Info{    CCPoint pointOrg;    CCPoint point;    int nType;}AStar_Coord_Info;class AStar:public CCNode{public:        AStar(void);    ~AStar(void);    //创建open和closed列表    CC_SYNTHESIZE_RETAIN(CCArray*,openArray,OpenArray);    CC_SYNTHESIZE_RETAIN(CCArray*,closeArray,CloseArray);        //检查开始和结束点    void MoveToward(CCPoint fromPos,CCPoint toPos);        void InsertInOpenArrays(ShortestPathStep *step);    virtual CCPoint AStarCoordForPosition(CCPoint point);    virtual bool IsValidPos(CCPoint point);    void ConstructShortestPath(ShortestPathStep* step);    void EndAStar();	int costToMoveFromStep(ShortestPathStep *fromStep ,ShortestPathStep *toStep);        //实现对角线移动    void walkableAdjacentTilesCoordForTileCoord(CCPoint point, std::vector
    
     & tmp);        int computeHScoreFromCoord(CCPoint fromCoord ,CCPoint toCoord);    void setBlockSize(int size = 32);    int indexOfObject(CCArray *array,ShortestPathStep *st);    bool ContainObject(CCArray *array,ShortestPathStep *st);    int		m_nBlockSize;	    CCArray *m_shortestPaths;public:    virtual void SetMapSize(CCSize size,CCPoint orgPoint = CCPointZero);    virtual void InitAStarCoord();    std::vector
     
         m_AstarCoordInfo;};#endif /* defined(__AStarDemo__AStar__) */
     
    

AStar.cpp

 

#include "AStar.h"#include "ShortestPathStep.h"#include 
    
     AStar::AStar(void){    m_nBlockSize = 32;    m_shortestPaths = NULL;}AStar::~AStar(){    }void AStar::setBlockSize(int size){    m_nBlockSize = size;}CCPoint AStar::AStarCoordForPosition(CCPoint point){    return CCPointMake(((int)point.x) / m_nBlockSize ,((int)point.y) / m_nBlockSize);}bool AStar::IsValidPos(CCPoint point){    std::vector
     
      ::iterator it = m_AstarCoordInfo.begin();    for (; it!=m_AstarCoordInfo.end(); it++) {        if ((*it).point.equals(point))             return ((*it).nType == 0);    }    return false;}void AStar::InsertInOpenArrays(ShortestPathStep *step){    int stepFScore = step->getFScore();    int count = openArray->count();    int i = 0;    for (; i
      
       objectAtIndex(i))->getFScore()) {            break;        }    }        openArray->insertObject(step, i);}void AStar::ConstructShortestPath(ShortestPathStep *step){    m_shortestPaths = CCArray::create();    m_shortestPaths->retain();    do{        if (step->getParent() != NULL)        {            m_shortestPaths->insertObject(step, 0);        }        step = step->getParent();    }while (step != NULL);         }void AStar::EndAStar(){    openArray->removeAllObjects();    openArray->release();    closeArray->removeAllObjects();    closeArray->release();}void AStar::walkableAdjacentTilesCoordForTileCoord(cocos2d::CCPoint point, std::vector
       
         &tmp){    bool t = false;    bool l = false;    bool b = false;    bool r = false;        //Top    CCPoint p = CCPointMake(point.x, point.y-1);    if (IsValidPos(p))    {        tmp.push_back(p);        t = true;    }        // Left    p = CCPointMake(point.x - 1, point.y);    if (IsValidPos(p)) {        tmp.push_back(p);        l = true;    }        // Bottom    p = CCPointMake(point.x, point.y + 1);    if (IsValidPos(p)) {        tmp.push_back(p);        b = true;    }        // Right    p = CCPointMake(point.x + 1, point.y);    if (IsValidPos(p)) {        tmp.push_back(p);        r = true;    }        // Top Left    p = CCPointMake(point.x - 1, point.y - 1);    if (t && l && IsValidPos(p)) {        tmp.push_back(p);    }        // Bottom Left    p = CCPointMake(point.x - 1, point.y + 1);    if (b && l && IsValidPos(p)) {        tmp.push_back(p);    }        // Top Right    p = CCPointMake(point.x + 1, point.y - 1);    if (t && r && IsValidPos(p)) {        tmp.push_back(p);    }        // Bottom Right    p = CCPointMake(point.x + 1, point.y + 1);    if (b && r && IsValidPos(p)) {        tmp.push_back(p);    }}void AStar::MoveToward(cocos2d::CCPoint fromPos, cocos2d::CCPoint toPos){    if (m_shortestPaths) {        m_shortestPaths->removeAllObjects();    }        CCPoint fromAStarCoor = AStarCoordForPosition(fromPos);	CCPoint toAStarCoord = AStarCoordForPosition(toPos);        if(fromAStarCoor.equals(toAStarCoord))	{		return;	}    	if(!IsValidPos(toAStarCoord))	{		return;	}    		openArray = CCArray::create();	openArray->retain();	closeArray = CCArray::create();	closeArray->retain();    	ShortestPathStep *step =  new ShortestPathStep();	step->retain();		step->InitWithPosition(fromAStarCoor);    	InsertInOpenArrays(step);        do{        ShortestPathStep *curStep = (ShortestPathStep *)openArray->objectAtIndex(0);        curStep->retain();        closeArray->addObject(curStep);                openArray->removeObjectAtIndex(0);                if (curStep->getPos().equals(toAStarCoord))        {            ConstructShortestPath(curStep);                        EndAStar();            break;        }                std::vector
        
          pointVec;		walkableAdjacentTilesCoordForTileCoord(curStep->getPos(),pointVec);        for (int i = 0; i
         
          autorelease(); st->InitWithPosition(pointVec[i]); if (ContainObject(closeArray, st)) { st->release(); continue; } int moveCost = costToMoveFromStep(curStep, st); int index = indexOfObject(openArray, st); if (index == UINT_MAX) { st->setParent(curStep); st->setHScore(computeHScoreFromCoord(st->getPos(), toAStarCoord)); InsertInOpenArrays(st); st->release(); } else { st->release(); st = (ShortestPathStep*) openArray->objectAtIndex(index); if ((curStep->getGScore() + moveCost)
          
           getGScore()) { st->setGScore(curStep->getGScore() + moveCost); st->retain(); openArray->removeObjectAtIndex(index); InsertInOpenArrays(st); st->release(); } } } }while (openArray->count() > 0); EndAStar();}int AStar::costToMoveFromStep(ShortestPathStep *fromStep ,ShortestPathStep *toStep){ return ((fromStep->getPos().x != toStep->getPos().x) && (fromStep->getPos().y != toStep->getPos().y)) ? 14 : 10;}int AStar::computeHScoreFromCoord(CCPoint fromCoord ,CCPoint toCoord){ // Here we use the Manhattan method, which calculates the total number of step moved horizontally and vertically to reach the // final desired step from the current step, ignoring any obstacles that may be in the way return abs(toCoord.x - fromCoord.x) + abs(toCoord.y - fromCoord.y);}bool AStar::ContainObject(CCArray *array,ShortestPathStep *st){ if(array == NULL) return false; for(int i=0; i
           
            count(); i++) { ShortestPathStep *t = (ShortestPathStep *)array->objectAtIndex(i); if(t->getPos().equals(st->getPos())) { return true; } } return false;}int AStar::indexOfObject(CCArray *array,ShortestPathStep *st){ if(array == NULL) return UINT_MAX; for(int i=0; i
            
             count(); i++) { ShortestPathStep *t = (ShortestPathStep *)array->objectAtIndex(i); if(t->getPos().equals(st->getPos())) { return i; } } return UINT_MAX;}void AStar::SetMapSize(CCSize size,CCPoint orgPoint){ }void AStar::InitAStarCoord(){ // CCSize size = CCDirector::sharedDirector()->getWinSize(); int AStarWidth = size.width/m_nBlockSize ; // int AStarHeight = size.height/m_nBlockSize; for (int w=-1; w 
             
              3 && w <= 8) && h == 4) { coordInfo.nType = 1; } else if ((w>3 && w <= 6) && h == 2) { coordInfo.nType = 1; } else if ((h>4 && h <= 8) && w == 8) { coordInfo.nType = 1; }else { coordInfo.nType = 0; } m_AstarCoordInfo.push_back(coordInfo); } } }
             
            
           
          
         
        
       
      
     
    

4.测试代码：

HelloWorldScene.h

 

#ifndef __HELLOWORLD_SCENE_H__#define __HELLOWORLD_SCENE_H__#include "cocos2d.h"#include "AStar.h"#include "ShortestPathStep.h"USING_NS_CC;class HelloWorld : public cocos2d::CCLayer{public:    // Method 'init' in cocos2d-x returns bool, instead of 'id' in cocos2d-iphone (an object pointer)    virtual bool init();    // there's no 'id' in cpp, so we recommend to return the class instance pointer    static cocos2d::CCScene* scene();        // a selector callback    void menuCloseCallback(CCObject* pSender);    // preprocessor macro for "static create()" constructor ( node() deprecated )    CREATE_FUNC(HelloWorld);        void ClearPath();	void PaintPath();private:	AStar *m_AStar;	CCArray *m_PathArray;	CCLayerColor *m_colorFrom;	CCLayerColor *m_colorEnd;public:	//ccTouches	virtual void ccTouchesBegan(CCSet *pTouches, CCEvent *pEvent);	virtual void ccTouchesMoved(CCSet *pTouches, CCEvent *pEvent);	virtual void ccTouchesEnded(CCSet *pTouches, CCEvent *pEvent);	virtual void ccTouchesCancelled(CCSet *pTouches, CCEvent *pEvent);    private:	CCPoint		m_FromPoint;		//	CCPoint		m_ToPoint;			//	bool		m_bSecondPoint;		//};#endif // __HELLOWORLD_SCENE_H__

HelloWorldScene.cpp

 

#include "HelloWorldScene.h"#include "SimpleAudioEngine.h"using namespace cocos2d;using namespace CocosDenshion;#define  AStar_Coord_Block	32CCScene* HelloWorld::scene(){    // 'scene' is an autorelease object    CCScene *scene = CCScene::create();        // 'layer' is an autorelease object    HelloWorld *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 instancebool HelloWorld::init(){    //    // 1. super init first    if ( !CCLayer::init() )    {        return false;    }    m_bSecondPoint = false;    m_AStar = new AStar;    m_AStar->InitAStarCoord();    m_PathArray = CCArray::create();    m_PathArray->retain();       std::vector
    
     ::iterator it = m_AStar->m_AstarCoordInfo.begin();        for (; it != m_AStar->m_AstarCoordInfo.end(); it++) {        CCLayerColor *color = CCLayerColor::create(ccc4(124, 124, 124, 124));        if ((*it).nType == 0)        {            color->setColor(ccc3(255, 0, 255));        }        else        {            color->setColor(ccc3(125, 125, 0));        }        color->setContentSize(CCSizeMake(AStar_Coord_Block,AStar_Coord_Block));        color->setPosition((*it).pointOrg);        this->addChild(color);    }    PaintPath();    this->setTouchEnabled(true);        return true;}void HelloWorld::menuCloseCallback(CCObject* pSender){    CCDirector::sharedDirector()->end();#if (CC_TARGET_PLATFORM == CC_PLATFORM_IOS)    exit(0);#endif}void HelloWorld::PaintPath(){	if(m_AStar->m_shortestPaths != NULL)	{        		for (int i=0; i
     
      m_shortestPaths->count();i++)		{			CCLayerColor *color = CCLayerColor::create(ccc4(255,124,124,124),AStar_Coord_Block,AStar_Coord_Block);            			ShortestPathStep* s =(ShortestPathStep*) (m_AStar->m_shortestPaths->objectAtIndex(i));                        CCPoint point = CCPointMake(s->getPos().x *AStar_Coord_Block +AStar_Coord_Block/2,s->getPos().y*AStar_Coord_Block+AStar_Coord_Block/2);            			color->setPosition(point);			this->addChild(color);			m_PathArray->addObject(color);		}	}}void HelloWorld::ClearPath(){	CCObject* it = NULL;	CCARRAY_FOREACH(m_PathArray, it)	{		CCLayerColor *color = (CCLayerColor *)it;		this->removeChild(color,true);	}	m_PathArray->removeAllObjects();        this->removeChild(m_colorEnd, true);    this->removeChild(m_colorFrom, true);}void HelloWorld::ccTouchesBegan(CCSet *pTouches, CCEvent *pEvent){    CCSetIterator it = pTouches->begin();    CCTouch *pTouch = (CCTouch*)(*it);    CCPoint touchLocation = convertTouchToNodeSpace(pTouch);    touchLocation = m_AStar->AStarCoordForPosition(touchLocation);    touchLocation = CCPointMake(AStar_Coord_Block*touchLocation.x+AStar_Coord_Block/2,AStar_Coord_Block*touchLocation.y+AStar_Coord_Block/2);    if (m_bSecondPoint)	{		m_ToPoint = touchLocation;        		//		m_AStar->MoveToward(m_FromPoint,m_ToPoint);        		//		m_colorEnd = CCLayerColor::create(ccc4(255,0,0,255),AStar_Coord_Block,AStar_Coord_Block);		m_colorEnd->setPosition(m_ToPoint);		this->addChild(m_colorEnd);        		//		PaintPath();		m_bSecondPoint = false;	}	else	{		m_FromPoint = touchLocation;		//		ClearPath();		//		m_colorFrom = CCLayerColor::create(ccc4(255,0,255,255),AStar_Coord_Block,AStar_Coord_Block);		m_colorFrom->setPosition(m_FromPoint);		this->addChild(m_colorFrom);        		m_bSecondPoint = true;	}    }void HelloWorld::ccTouchesMoved(CCSet *pTouches, CCEvent *pEvent){	CCSetIterator it = pTouches->begin();	CCTouch *pTouch = (CCTouch*)(*it);	switch (pTouches->count())	{        case 1:		{			CCPoint touchLocation = convertTouchToNodeSpace(pTouch);		}            break;        case 2:		{		}            break;	}}void HelloWorld::ccTouchesEnded(CCSet *pTouches, CCEvent *pEvent){}void HelloWorld::ccTouchesCancelled(CCSet *pTouches, CCEvent *pEvent){}
     
    

效果图：