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