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);
intm_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:
CCPointm_FromPoint;//
CCPointm_ToPoint;//
boolm_bSecondPoint;//
};#endif // __HELLOWORLD_SCENE_H__

HelloWorldScene.cpp

#include "HelloWorldScene.h"
#include "SimpleAudioEngine.h"using namespace cocos2d;
using namespace CocosDenshion;
#define AStar_Coord_Block32CCScene* 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)
{
}

效果图：