如何基于cocos2dx3.x实现A星寻路算法

在这款游戏中，你扮演着一只小偷猫，在一个由危险的狗守护着的地牢里小心穿行。如果你试图穿过一只狗，他会把你吃掉 –

除非你可以用骨头去贿赂它！

所以在这款游戏中，你的任务是尝试以正确的顺序捡起骨头，然后寻找路线

穿过狗逃离。

注意到猫只能水平或者垂直的移动（例如不能斜线移动），并且会从一个方块的中心点移动到另一个中心点。每个方块既可以是可通行的也可以是不可通行的。

尝试下这款游戏，看看你能否找到出路！建议你阅读代码以熟悉它的原理。这是一款相当普通的方块-地图式游戏，我们会在接下来的教程中修改它并使用上A星寻路算法。

Maze猫和A星概览

正如你所看到的，当你点击地图某处时，猫会沿着你点击的方向跳到相邻的方块上。

我们想对程序做修改，让猫持续的往你点击的方块方向前进，就像许多RPGs或者point-and-click冒险类游戏。

让我们看下控制触摸事件代码的工作原理。如果你打开HelloWorldScene.cpp文件，你将看到像下面这样去实现触摸操作：

auto

listener =

EventListenerTouchOneByOne::create();

listener->setSwallowTouches( true

);

listener->onTouchBegan = [ this ](Touch *touch, Event *event){

(_gameOver)

{

return false ;

}

Point touchLocation =

_tileMap->convertTouchToNodeSpace(touch);

_cat->moveToward(touchLocation);

return

true

};

_eventDispatcher->addEventListenerWithSceneGraphPriority(listener,

this

);

你可以看到这里只是对猫精灵调用了一个方法，让猫在方块地图上往你点击的地方移动。

我们现在要做的是修改在CatSprite.m文件中的以下方法，寻找到达该点的最短路径，并且开始前进：

void

CatSprite::moveToward( const Point &target)

{

}

创建ShortestPathStep类

我们开始创建一个内部类，代表路径上的一步操作。在这种情况下，它是一个方块和由A星算法计算出来的的F,G和H

scores。

class ShortestPathStep : public cocos2d::Object

{

public

ShortestPathStep();

~ShortestPathStep();

static ShortestPathStep

*createWithPosition( const cocos2d::Point &pos);

bool initWithPosition(

const cocos2d::Point &pos);

int getFScore() const ;

bool isEqual(

const ShortestPathStep *other) const ;

std::string getDescription() const

CC_SYNTHESIZE(cocos2d::Point, _position, Position);

CC_SYNTHESIZE( int ,

_gScore, GScore);

CC_SYNTHESIZE( int , _hScore,

HScore);

CC_SYNTHESIZE(ShortestPathStep*, _parent,

Parent);

};

现在添加以下代码到CatSprite.cpp文件的顶部。

CatSprite::ShortestPathStep::ShortestPathStep()

_position(Point::ZERO),

_gScore(0),

_hScore(0),

_parent(nullptr)

{

}

CatSprite::ShortestPathStep::~ShortestPathStep()

{

}

CatSprite::ShortestPathStep

*CatSprite::ShortestPathStep::createWithPosition( const Point

&pos)

{

ShortestPathStep *pRet = new ShortestPathStep();

if (pRet

pRet->initWithPosition(pos))

{

pRet->autorelease();

return

pRet;

}

else

{

CC_SAFE_DELETE(pRet);

return

nullptr;

}

bool CatSprite::ShortestPathStep::initWithPosition( const

Point &pos)

{

bool bRet = false ;

{

this

->setPosition(pos);

bRet = true ;

} while (0);

return

bRet;

}

int CatSprite::ShortestPathStep::getFScore() const

{

return

this ->getGScore() + this ->getHScore();

}

bool

CatSprite::ShortestPathStep::isEqual( const CatSprite::ShortestPathStep *other)

const

{

return this ->getPosition() ==

other->getPosition();

}

std::string

CatSprite::ShortestPathStep::getDescription() const

{

return

StringUtils::format( "pos=[%.0f;%.0f] g=%d h=%d f=%d" ,

this

->getPosition().x, this ->getPosition().y,

this ->getGScore(), this

->getHScore(), this ->getFScore());

}

正如所见，这是一个很简单的类，记录了以下内容：

方块的坐标

- G值（记住，这是开始点到当前点的方块数量）

- H值（记住，这是当前点到目标点的方块估算数量）

Parent是它的上一步操作

F值，这是方块的和值（它是G+H的值）

这里定义了getDescription方法，以方便调试。创建了isEquals方法，当且仅当两个ShortestPathSteps的方块坐标相同时，它们相等（例如它们代表着相同的方块）。

创建Open和Closed列表

打开CatSprite.h文件，添加如下代码：

cocos2d::Vector

_spOpenSteps;

cocos2d::Vector

_spClosedSteps;

检查开始和结束点

重新实现moveToward方法，获取当前方块坐标和目标方块坐标，然后检查是否需要计算一条路径，最后测试目标方块坐标是否可行走的（在这里只有墙壁是不可行走的）。打开CatSprite.cpp文件，修改moveToward方法，为如下：

void

CatSprite::moveToward( const Point &target)

{

Point fromTileCoord =

_layer->tileCoordForPosition( this ->getPosition());

Point toTileCoord

= _layer->tileCoordForPosition(target);

if (fromTileCoord ==

toTileCoord)

{

CCLOG( "You're already there! :P" );

return ;

}

(!_layer->isValidTileCoord(toTileCoord) ||

_layer->isWallAtTileCoord(toTileCoord))

{

SimpleAudioEngine::getInstance()->playEffect(

"hitWall.wav" );

return ;

}

CCLOG( "From: %f, %f" , fromTileCoord.x,

fromTileCoord.y);

CCLOG( "To: %f, %f" , toTileCoord.x,

toTileCoord.y);

}

编译运行，在地图上进行点击，如果不是点击到墙壁的话，可以在控制台看到如下信息：

From:

24.000000, 0.000000

To: 20.000000, 0.000000

其中 **From**

就是猫的方块坐标，**To**就是所点击的方块坐标。

实现A星算法

根据算法，第一步是添加当前坐标到open列表。还需要三个辅助方法：

一个方法用来插入一个ShortestPathStep对象到适当的位置（有序的F值）

- 一个方法用来计算从一个方块到相邻方块的移动数值

一个方法是根据"曼哈顿距离"算法，计算方块的H值

打开CatSprite.cpp文件，添加如下方法：

void

CatSprite::insertInOpenSteps(CatSprite::ShortestPathStep *step)

{

int

stepFScore = step->getFScore();

ssize_t count =

_spOpenSteps.size();

ssize_t i = 0;

for (; i < count; ++i)

{

(stepFScore <= _spOpenSteps.at(i)->getFScore())

{

break

}

_spOpenSteps.insert(i, step);

}

int

CatSprite::computeHScoreFromCoordToCoord( const Point &fromCoord, const

Point &toCoord)

{

// 忽略了可能在路上的各种障碍

return abs(toCoord.x - fromCoord.x) + abs(toCoord.y -

fromCoord.y);

}

int CatSprite::costToMoveFromStepToAdjacentStep( const

ShortestPathStep *fromStep, const ShortestPathStep *toStep)

{

因为不能斜着走，而且由于地形就是可行走和不可行走的成本都是一样的

// 如果能够对角移动，或者有沼泽、山丘等等，那么它必须是不同的

return

}

接下来，需要一个方法去获取给定方块的所有相邻可行走方块。因为在这个游戏中，HelloWorld管理着地图，所以在那里添加方法。打开HelloWorldScene.cpp文件，添加如下方法：

PointArray

*HelloWorld::walkableAdjacentTilesCoordForTileCoord( const Point &tileCoord)

const

{

PointArray *tmp = PointArray::create(4);

// 上

Point

p(tileCoord.x, tileCoord.y - 1);

if ( this ->isValidTileCoord(p)

&& ! this

->isWallAtTileCoord(p))

{

tmp->addControlPoint(p);

}

左

p.setPoint(tileCoord.x - 1, tileCoord.y);

if ( this

->isValidTileCoord(p) && ! this

->isWallAtTileCoord(p))

{

tmp->addControlPoint(p);

}

下

p.setPoint(tileCoord.x, tileCoord.y + 1);

if ( this

->isValidTileCoord(p) && ! this

->isWallAtTileCoord(p))

{

tmp->addControlPoint(p);

}

右

p.setPoint(tileCoord.x + 1, tileCoord.y);

if ( this

->isValidTileCoord(p) && ! this

->isWallAtTileCoord(p))

{

tmp->addControlPoint(p);

}

return

tmp;

}

可以继续CatSprite.cpp中的moveToward方法了，在moveToward方法的后面，添加如下代码：

bool

pathFound = false ;

_spOpenSteps.clear();

_spClosedSteps.clear();

首先，添加猫的方块坐标到open列表

this

->insertInOpenSteps(ShortestPathStep::createWithPosition(fromTileCoord));

{

得到最小的F值步骤

// 因为是有序列表，第一个步骤总是最小的F值

ShortestPathStep *currentStep =

_spOpenSteps.at(0);

添加当前步骤到closed列表

_spClosedSteps.pushBack(currentStep);

将它从open列表里面移除

需要注意的是，如果想要先从open列表里面移除，应小心对象的内存

_spOpenSteps.erase(0);

如果当前步骤是目标方块坐标，那么就完成了

if (currentStep->getPosition() ==

toTileCoord)

{

pathFound = true ;

ShortestPathStep *tmpStep =

currentStep;

CCLOG( "PATH FOUND :" );

{

CCLOG( "%s" ,

tmpStep->getDescription().c_str());

tmpStep = tmpStep->getParent(); //

倒退

} while (tmpStep); //

直到没有上一步

_spOpenSteps.clear();

_spClosedSteps.clear();

break

}

// 得到当前步骤的相邻方块坐标

PointArray *adjSteps =

_layer->walkableAdjacentTilesCoordForTileCoord(currentStep->getPosition());

for

(ssize_t i = 0; i < adjSteps->count(); ++i)

{

ShortestPathStep *step

ShortestPathStep::createWithPosition(adjSteps->getControlPointAtIndex(i));

检查步骤是不是已经在closed列表

if ( this ->getStepIndex(_spClosedSteps, step) !=

-1)

{

continue ;

}

// 计算从当前步骤到此步骤的成本

int moveCost = this

->costToMoveFromStepToAdjacentStep(currentStep, step);

检查此步骤是否已经在open列表

ssize_t index = this ->getStepIndex(_spOpenSteps,

step);

// 不在open列表，添加它

if (index == -1)

{

设置当前步骤作为上一步操作

step->setParent(currentStep);

// G值等同于上一步的G值 +

从上一步到这里的成本

step->setGScore(currentStep->getGScore() + moveCost);

H值即是从此步骤到目标方块坐标的移动量估算值

step->setHScore( this

->computeHScoreFromCoordToCoord(step->getPosition(), toTileCoord));

按序添加到open列表

this ->insertInOpenSteps(step);

}

else

{

获取旧的步骤，其值已经计算过

step = _spOpenSteps.at(index);

// 检查G值是否低于当前步骤到此步骤的值

((currentStep->getGScore() + moveCost) < step->getGScore())

{

G值等同于上一步的G值 + 从上一步到这里的成本

step->setGScore(currentStep->getGScore() +

moveCost);

// 因为G值改变了，F值也会跟着改变

// 所以为了保持open列表有序，需要将此步骤移除，再重新按序插入

在移除之前，需要先保持引用

step->retain();

现在可以放心移除，不用担心被释放

_spOpenSteps.erase(index);

// 重新按序插入

this

->insertInOpenSteps(step);

现在可以释放它了，因为open列表应该持有它

step->release();

}

} while

(_spOpenSteps.size() > 0);

(!pathFound)

{

SimpleAudioEngine::getInstance()->playEffect(

"hitWall.wav" );

}

添加以下方法：

ssize_t CatSprite::getStepIndex( const

cocos2d::Vector &steps, const CatSprite::ShortestPathStep *step)

{

for

(ssize_t i = 0; i < steps.size(); ++i)

{

(steps.at(i)->isEqual(step))

{

return i;

}

return

-1;

}