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

在学习本教程之前，如果你有开发COCOS2D-X的经验会有所帮助，如果没有也没关系，因为你可以把这里讲解的例子移植到其他语言或者框架上。找到到达键盘的最短路径并开始！迷宫猫首先介绍我们将在本教程中开发的简单游戏。请下载本教程的工程代码。编译并运行项目，您将看到下图。在这个游戏中，你扮演一个偷猫贼，在由危险的狗守卫的地牢中小心翼翼地行走。如果你试图和一只狗杂交，它会吃了你——除非你能用骨头贿赂它！所以在这个游戏中，你的任务就是尽量按照正确的顺序捡起骨头，然后通过狗找到逃跑的方法。注意，猫只能水平或垂直移动(比如不能斜向移动)，会从一个方块的中心点移动到另一个方块。每个方块可以是可通行的，也可以是不可通行的。试试这个游戏，看看你是否能找到出路！我建议你阅读代码来熟悉它的原理。这是一个相当常见的正方形地图游戏，我们将在下一个教程中修改它，并使用A-star寻路算法。迷宫猫和一颗星星概述正如你所看到的，当你点击地图上的某个地方，猫就会跳到你点击方向的相邻方块。我们想修改程序，让猫可以一直朝着你点击的方块方向移动，就像很多RPG或者点击式冒险游戏一样。让我们来看看控制触摸事件的代码是如何工作的。如果打开HelloWorldScene.cpp文件，会看到触摸操作是这样实现的:AutoListener = EventListenerTouchoneByone::Create()；监听器-& gt；setswallowcutches(true)；监听器-& gt；ontouchbegin =[this](Touch * Touch，Event * Event){ if(_ game over){ return false；} PointtouchLocation = _ tile map-& gt；convertTouchToNodeSpace(触摸)；_ cat-& gt；move forward(touch location)；returntrue};_ event dispatcher-& gt；addEventListenerWithSceneGraphPriority(监听器，this)；你可以看到这只是在猫精灵上调用的一个方法，让猫移动到你点击方块地图的地方。我们现在要做的是修改CatSprite.m文件中的以下方法，找到到这个点的最短路径，开始前进:void catsprite::Move against(const point & amp；Target) {}创建ShortestPathStep类我们开始创建一个内部类，它表示路径上的一个步骤。在这种情况下，它是一个正方形和由A-star算法计算的F、G和Hscores。classShortestPathStep:public cocos 2d::Object { public:ShortestPathStep()；~ ShortestPathStep()；staticShortestPathStep * createWithPosition(const cocos 2d::Point & amp；pos)；boolinitWithPosition(constcocos 2d::Point & amp；pos)；intgetFScore()常量；boolisEqual(constShortestPathStep * other)const；STD::stringgetDescription()const；CC _ synthese(cocos2d::Point，_position，Position)；CC _ synthese(int，_gScore，GS core)；CC _ synthese(int，_hScore，hs core)；CC _ synthese(ShortestPathStep *，_parent，Parent)；};现在，将以下代码添加到CatSprite.cpp文件的顶部。cat sprite::ShortestPathStep::ShortestPathStep():_ position(Point::ZERO)、_gScore(0)、_ parent(nullptr){ } cat sprite::ShortestPathStep::~ ShortestPathStep(){ } cat sprite::ShortestPathStep * cat sprite::ShortestPathStep::createWithPosition(const Point & amp；pos){ ShortestPathStep * pRet = newShortestPathStep()；if(pRet & amp；& amppRet->；initWithPosition(pos)){ pRet-& gt；autorelease()；returnpRet} else { CC _ SAFE _ DELETE(pRet)；returnnullptr} } boolCatSprite::ShortestPathStep::initWithPosition(const point & amp；pos){ boolbRet = false；执行{ this-& gt；设定位置；bRet = true} while(0)；returnbRet} intCatSprite::ShortestPathStep::getFScore()const { return this-& gt；getGScore()+this-& gt；geth score()；} boolCatSprite::ShortestPathStep::is equal(constcastsprite::ShortestPathStep * other)const { return this-& gt；getPosition()= =其他-& gt；getPosition()；} STD::stringCatSprite::ShortestPathStep::get description()const { returnStringUtils::format(" pos =[% . 0f；%.0f]g=%dh=%df=%d "，this-& gt；getPosition()。x，这-& gt；getPosition()。y，这-& gt；getGScore()，this-& gt；getHScore()，this-& gt；getfs core())；}你可以看到，这是一个非常简单的类，它记录了以下内容:-方块的坐标-G值(记住，这是从起点到当前点的方块数)-H值(记住，这是从当前点到目标点的估计方块数)-Parent是它之前的运算-F值，这是平方和(它是G+H的值)。这里定义了getDescription方法。创建isEquals方法，当且仅当两个ShortestPathSteps的盒子坐标相同时，它们相等(例如，它们表示同一个盒子)。创建开放和封闭列表，打开CatSprite.h文件，添加以下代码:cocos2d::Vector _ spOpenSteps；cocos2d::Vector _ spClosedSteps；检查起点和终点重新实现move against方法，得到当前盒子坐标和目标盒子坐标，然后检查是否需要计算路径，最后测试目标盒子坐标是否可走(这里只有墙不可走)。打开CatSprite.cpp文件，修改movetower方法如下:Voidcastsprite::move tower(const point & amp；target){ PointfromTileCoord = _ layer-& gt；tileCoordForPosition(this-& gt；getPosition())；PointtoTileCoord = _ layer-& gt；tileCoordForPosition(目标)；if(fromTileCoord = = toilecoord){ cc log(" You ' reallyreadythere！:P”)；返回；}如果(！_ layer-& gt；isvalidilecord(toTileCoord)| | _ layer-& gt；isWallAtTileCoord(toilecoord)){ simple audio engine::getInstance()-& gt；playEffect(" hit wall . wav ")；返回；} CCLOG("From:%f，%f "，fromTileCoord.x，fromtilecoord . y)；CCLOG("To:%f，%f "，toTileCoord.x，totelecoord . y)；}编译运行，点击地图。如果不点击墙壁，可以在控制台上看到以下信息:from: 24.000000，0.000000 to: 20.000000，0.00000其中**From**是猫的盒子坐标，**To**是点击的盒子坐标。根据算法，第一步是将当前坐标添加到开放列表中。还需要三个辅助方法:-一个方法用于将ShortestPathStep对象插入适当的位置(有序的F值)-一个方法用于计算从一个正方形到相邻正方形的移动值-一个方法是通过根据曼哈顿距离算法计算正方形的H值来打开CatSprite.cpp文件。添加以下方法:Voidcatsprite::insertionsteps(cat sprite::shorttestpathstep * step){ intstepscore = step-> getfs core()；ssize _ tcount = _ spopensteps . size()；ssize _ ti = 0；for(；igetFScore()){ break；} } _spOpenSteps.insert(i，step)；} intCatSprite::computehscorefromcoordtocord(const point & amp；fromCoord，constPoint & ampto code){//忽略路上可能出现的各种障碍物。将ABS(返回坐标。x-来自坐标。x)+ABS(坐标。y-来自坐标。y)；} INTCATSPRITE::cost to move Fromstead AdjacentStep(恒短测试路径step * from step，恒短测试路径step * to step){//因为不能侧着走，而且因为地形跟走和不走是一样的//如果可以斜着走，或者有沼泽，丘陵等。，那么一定是不同的return 1；接下来，我们需要一种方法来获得给定正方形的所有相邻可行走正方形。因为在这个游戏中，HelloWorld管理地图，所以在那里添加方法。打开HelloWorldScene.cpp文件，添加以下方法:point array * hello world::walkableleadjacenttilecoord(const point & amp；tile cord)const { point array * tmp = point array::create(4)；//on pointp(tile cord . x，tile cord . y-1)；如果(this-& gt；isvalidilecord(p)和amp& amp！这-& gt；isWallAtTileCoord(p)){ tmp-& gt；addControlPoint(p)；}//left p . setpoint(tile cord . x-1，tile cord . y)；如果(this-& gt；isvalidilecord(p)和amp& amp！这-& gt；isWallAtTileCoord(p)){ tmp-& gt；addControlPoint(p)；p.setpoint下(tilecoord.x，tile cord . y+1)；如果(this-& gt；isvalidilecord(p)和amp& amp！这-& gt；isWallAtTileCoord(p)){ tmp-& gt；addControlPoint(p)；}//right p . setpoint(tile cord . x+1，tile cord . y)；如果(this-& gt；isvalidilecord(p)和amp& amp！这-& gt；isWallAtTileCoord(p)){ tmp-& gt；addControlPoint(p)；} returntmp}可以在CatSprite.cpp中继续movetower方法在movetower方法之后，添加以下代码:boolpathFound = false_ spopensteps . clear()；_ spclosedsteps . clear()；//首先将猫的盒子坐标添加到开放列表this->；insertInOpenSteps(ShortestPathStep::createWithPosition(fromTileCoord))；Do {// Step获取最小的f值//因为是有序列表，所以第一步总是最小的f值shorttestpathstep * current Step = _ spopensteps。在(0)；//将当前步骤添加到关闭的list _ spclosedsteps.pushback(当前步骤)；//从开放列表中移除//需要注意的是，如果要先从开放列表中移除，要小心object _spOpenSteps.erase(0)的内存；//如果当前步是目标方坐标，那么If(current step->-->；getPosition()= = toilecoord){ path found = true；ShortestPathStep * tmp step = current step；cc log(" path found:")；do { CCLOG("%s "，tmpStep-& gt；getDescription()。c _ str())；tmpStep=tmpStep->get parent()；//Backward } while(tmpStep)；//直到没有之前的step _ spopensteps . clear()；_ spclosedsteps . clear()；打破；}//获取当前步骤相邻方块的坐标，point array * adj steps = _ layer-& gt；walkableAdjacentTilesCoordForTileCoord(current step-& gt；getPosition())；for(ssize _ ti = 0；icount()；++ I){ ShortestPathStep * step = ShortestPathStep::createWithPosition(adj steps-& gt；getControlPointAtIndex(I))；//检查该步骤是否已经在封闭列表中，如果(this->；getStepIndex(_spClosedSteps，step)！=-1) {继续；}//计算从当前步骤到该步骤的开销intmoveCost = this-& gt；costToMoveFromStepToAdjacentStep(current step，step)；//检查该步骤是否已经在开放列表中ssize _ tindex = this-& gt；getStepIndex(_spOpenSteps，step)；//不在开放列表中，添加它if(index==-1) {//将当前步骤设置为上一步-->；set parent(current step)；//G的值等于上一步G的值+上一步到此步的代价-->；setGScore(current step-& gt；getGScore()+move cost)；//H值是从这一步到目标方坐标步的移动量估算值-->；Seth score(this-& gt；computeHScoreFromCoordToCoord(步骤-& gt；getPosition()、totelecoord))；//在开放列表中添加this-& gt；insertInOpenSteps(步骤)；} else {//获取旧步骤，其值已计算为step = _ spopensteps . at(index)；//检查g的值是否低于if的值((当前步->；getgscore()+move cost)getgscore(){//g的值等于上一步g的值+上一步到此步的代价-->；setGScore(current step-& gt；getGScore()+move cost)；//因为g的值变了，f的值也会变//所以为了保持开放列表的有序，你需要去掉这个步骤，然后按顺序重新插入//在去掉之前，你需要保持引用step-& gt；retain()；//现在可以放心删除了，不用担心被释放_ spopensteps . erase(index)；//重新插入这个-& gt；insertInOpenSteps(步骤)；//现在可以释放了，因为开放列表应该持有它step->；发布()；} } } } while(_ spopensteps . size()& gt；0);如果(！path found){ simple audio engine::getInstance()-& gt；playEffect(" hit wall . wav ")；}添加以下方法:ssize _ tcatssprite::getstepindex(const cocos 2d::vector &；steps，constcastsprite::ShortestPathStep * step){ for(ssize _ ti = 0；IIS equal(step)){ returni；} } return-1；}编译运行，点击地图，如下图所示:从:24.000000，0.000000到:23.000000，3.0000000 path found:POS =[23；3]g = 10h = 0f = 10 pos =[22；3]g = 9h = 1f = 10 pos =[21；3]g = 8h = 2f = 10 pos =[20；3]g = 7h = 3f = 10 pos =[20；2]g = 6h = 4f = 10 pos =[20；1]g = 5h = 5f = 10 pos =[21；1]g = 4h = 4f = 8 pos =[22；1]g = 3h = 3f = 6 pos =[23；1]g = 2h = 2f = 4 pos =[24；1]g = 1h = 3f = 4 pos =[24；0]g=0h=0f=0注意，路径是从后面建立的，所以一定要从下往上看猫选择了哪条路径。跟着小路走既然已经找到了小路，就让猫跟着走吧。你需要创建一个数组来存储路径，打开CatSprite.h文件，添加以下代码:cocos2d::Vector _ shortest path；打开CatSprite.cpp文件，更改moveToward方法，注释掉语句* * boolpathFound = false * *，如下://boolpath found = false；替换语句* * pathFound = true* *如下://path found = true；这-& gt；construtpathandstartanimationfromstep(current step)；并注释掉下面的调试语句://shorttestpathstep * tmp step = current step；//cc log(" path found:")；//do //{ //CCLOG("%s "，tmpStep-& gt；getDescription()。c _ str())；//tmp step = tmp step-& gt；get parent()；//向后/