cocos2d-x学习日志(13) --A星寻路算法demo

你是否在做一款游戏的时候想创造一些怪兽或者游戏主角，让它们移动到特定的位置，避开墙壁和障碍物呢？如果是的话，请看这篇教程，我们会展示如何使用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<CCPoint>& 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<AStar_Coord_Info>   m_AstarCoordInfo;

};

#endif /* defined(__AStarDemo__AStar__) */

AStar.cpp

#include "AStar.h"
#include "ShortestPathStep.h"
#include <algorithm>

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<AStar_Coord_Info>::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<count; i++) {
        if (stepFScore <= ((ShortestPathStep*)openArray->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<CCPoint> &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<CCPoint> pointVec;
		walkableAdjacentTilesCoordForTileCoord(curStep->getPos(),pointVec);
        for (int i = 0; i<pointVec.size(); i++)
        {
            ShortestPathStep *st = new ShortestPathStep();
            st->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)<st->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<array->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<array->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 <AStarWidth; w++)
	{
		for (int h=-1; h<AStarHeight; h++)
		{
			AStar_Coord_Info coordInfo;
			coordInfo.point =  CCPointMake(w,h);
			coordInfo.pointOrg = CCPointMake(m_nBlockSize/2+w*m_nBlockSize,m_nBlockSize/2+m_nBlockSize*h);
			//
			if (w == -1 || h==-1 || w == AStarWidth-1 || h == AStarHeight-1)
			{
				coordInfo.nType = 1;
			}

			//
			else if ((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	32

CCScene* 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 instance
bool 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<AStar_Coord_Info>::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_AStar->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)
{
}

效果图：