如何基于cocos2dx3.x实现A星寻路算法_百度知道
如何基于cocos2dx3.x实现A星寻路算法
提问者采纳
还需要三个辅助方法实现A星算法 根据算法，第一步是添加当前坐标到open列表： - 一个方法用来插入一个ShortestPathStep对象到适当的位置（有序的F值） - 一个方法用来计算从一个方块到相邻方块的移动数值 - 一个方法是根据&曼哈顿距离&quot
来自团队：
其他类似问题
为您推荐：
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁>> Cocos2d-x类COC手游与RTS（即时战略）游戏的编程实践总结
Cocos2d-x类COC手游与RTS（即时战略）游戏的编程实践总结
&|&标签：&&&&&&
点击分享本文：&
文/ Siliphen
【游戏陀螺9月18日消息】-这一个月左右的时间里，我独自一人在家做了上面视频中技术演示的demo。用的是Cocos2d-x引擎。说到Cocos2d-x，我接触有一年了。
这个demo中的图片资源都是我自己网上找的。而按钮等UI是我用PS自己画的，主要是网上找不到合适的UI。下方的方形按钮，是我模仿COC的来画的。
下面截图是Windows上开发环境（VS2013）运行的效果：
下图是编译到了安卓手机运行的效果：
从上面的视频和截图可以看到，一个月里，对于制作类COC游戏，我在技术上进行了一些尝试和探索。我之前没怎么做过游戏，尝试去做，可以发现编写这类游戏会遇到哪些问题，并且思考怎样解决。算是一种积累经验吧。
关于COC，大家应该都不陌生。Supercell公司成立于3年前，后来推出了一款叫 Clash of Clans 的移动游戏，简称COC。这款手游后来成为了地球上2014年最赚钱的手游，并且Supercell市值飙到了30亿美元。
大家感兴趣的话，也可以网上自己搜搜关于COC的更多信息。
最初我是想模仿制作一个类COC的手游（也许最终会和COC有很大的不同），并且加入RTS游戏的元素。比如：可以直接选中和控制兵的移动和攻击，增加操作感等。
为什么我会想加入RTS的元素呢？因为，很久很久以前，我是一个魔兽3遭遇战玩家，曾经BN亚洲战网排名前100-200。
在视频中，你会看到。我已经实现的游戏功能有：摆放建筑，拖曳和缩放游戏场景，单位兵种移动和简单的攻击。我没有加入任何游戏的业务逻辑代码。因为我想搭建一个基础框架或者是理清一下思路。熟悉编写这种游戏后，可以改成：RPG（角色扮演），RTS（即时战略），SLG（策略），塔防等多种类型的游戏。
试想一下，如果用做RTS的技术来做一个塔防有多酷。RTS对现实世界有更仿真的模拟，但同时技术含量肯定也会比《保卫萝卜》等高。这就是之前为什么说“也许最终会和COC有很大的不同”的原因。
COC这类的游戏，相对其他手游来说，编写的难度要复杂很多。下面总结一下，目前我已知的，编写类COC游戏会遇到的技术点。
编写类COC游戏的一些技术点
1. 操作的策划
是先定义好操作规则然后实现，还是一面做一面想一面改？
我觉得可能是后者，除非一点都不创新，想原封不动地照搬“被抄袭的产品”。一开始谁都不太可能把整个系统，整个规则都想清楚，都定义下来。因为我是一个人，所以，我是一面做一面想一面改。我一开始不可能把各种细节都想清楚，所以是先做着看看。
腾讯的《城堡争霸》是一款仿COC的产品，操作上和COC有一些不同。比如：移动建筑，手指放开的时候，就直接摆下建筑了。而COC还要再点击一下确定摆下建筑。在操作上，COC多了一个再次点击。
2. 操作代码的编写
COC这种游戏，是一种游戏元素很多的游戏。通常上面有树、石头，建筑，各种兵种角色单位等。有3种基本操作。
1.单个手指滑动代表拖曳游戏场景。
2.两个手指代表缩放游戏场景。
3.点击屏幕同时也代表选中一个单位。
腾讯的《城堡争霸》的2个手指的捏合缩放是和COC不同的。《城堡争霸》的实现算是“中心缩放”，不能同时移动游戏场景。我的实现是仿COC，看视频就知道了，缩放场景的同时还能控制场景移动。
拖动与缩放还需要有限制：不能移动到游戏世界区域之外，看到游戏世界外面的黑块。不能无限放大和缩小。我目前只做了缩放的限制，还没做移动的限制。移动限制的话，有点麻烦，和缩放是有关系的。
观察COC就会发现，如果在一个建筑上面按下手指，如果没有拖动的话，就是选择这个建筑。如果拖动了，就不会选择这个建筑，而只是拖动游戏场景。所以，程序中要做一些判断和记录：是否有拖动等。
像我这种，还加入了RTS控制元素，可以选择行动体单位并且控制它进行移动和攻击，这会让操作控制代码变得更复杂。对于这种复杂的操作，我是用状态机来解决。在onTouchesBegan，onTouchesMoved，onTouchesEnded 3个触摸函数中都弄了状态机。触摸函数肯定用的是多点触摸，否者没法搞双手指捏合缩放。我新建一个触摸层来专门处理触摸，因为操作的控制本身就很复杂，这样做可以分割复杂度。
我的onTouchesMoved的代码截图：
外层代码，先判断是一个点触摸了，还是2个点同时触摸。然后在2个判断分支中都做switch-case的状态机处理。有看过设计模式的同学可能会知道，用switch-case写状态机代码是“幼稚的”，我觉得，如果在尝试阶段，还没想清楚的时候，用switch-case也无妨。等我想清楚的时候，我可能会改成状态模式的实现。
3. 角色的AI
COC中有一些“行动自治体”，比如，有一些角色，会到处走动，一下子摸摸树一下子摸摸石头。空降兵到敌人领地时会进行自动攻击等。这是一些什么三消，跑酷类游戏都没有的。编写这些AI，让玩家有一种在“世界”中的感觉，是相对于其他类型的手游额外多出来的部分。基本上用状态机建模，都可以搞定这些AI。但目前我的实现程度，还没有做“行动自治体”。
寻路也属于AI部分，求最短路径的A*算法就是人工智能领域中的算法。其实COC中的寻路是比较简单的，相比红警，帝国，魔兽等这种真正的RTS游戏来说。我的游戏中用的寻路也是A*，关于A*算法，可以参考下我写的这篇文章：
《Cocos2d-x 地图行走的实现3：A*算法》（请点击左下角“阅读原文”）
之前我有尝试，把寻路算法改成开一个线程来计算，这样的话，就可以不卡住界面。传统软件的编写经常这样用。但后来再改的过程中遇到不少麻烦和问题，遂暂时搁浅之。
编写真正的RTS游戏的技术点
COC其实并不是一个真正RTS游戏，而是一个经营策略类游戏。之前提到了，我想加入RTS游戏的元素，那么我们来看看RTS游戏有什么技术点。
1. 不允许行动体互相穿越的限制
COC的人物是允许互相穿越的，就是2个行动单位可以互相重叠在一起。魔兽3的行动单位则不允许。不允许互相穿越是基于现实的模拟。正是因为不允许穿越，魔兽3才有了“卡位”，”M围杀“等各种操作技巧。
我在实践的过程中发现，魔兽的限制穿越的编写处理是比较麻烦的。我个人猜测可能Supercell感觉这个问题实在是有点费神，所以就允许穿越了，不做那么真实的模拟。允许穿越，实际上会极大降低程序的编写复杂度，为什么这样说呢？听我娓娓道来。
不允许穿越通常是用碰撞检测的方法来做，如果游戏场景很大的话，为了降低碰撞检测的时间复杂度，需要做空间分割处理。
不允许穿越会涉及更多的AI问题。比如：”移动碰头死锁“。呵呵，”移动碰头死锁“是我自己发明的名词，用来描述这样一种场景：在一个狭小且长的通路中，比如一座桥、一个巷子里面、树林的间隙中，或者甚至是空地，有2个单位，A从左向右行走，B从右向左行走，这2个单位都在同一个水平线上，那么就有一个”你不让我，我不让你“的问题。
用我的游戏截图，如下图：
上图，A和B都往对方的方向走去，在某个时间上，他们会”碰头“，如下图：
如果没有AI控制的话，就会出现互不相让的”死锁“，双方都在不断往对方的方向”推“。这种情况，我们需要编写AI去决定A和B如何谦让，然后，再行动到各自的目的地。目前我的做法比较简单，有一个行动体可能会停下来，然后另一个行动体绕过他。或者是2个行动体都停下来。玩家需要重新控制行动。这种做法会让玩家觉得游戏中的人物很”蠢“且自己很麻烦，行动体不会聪明避让且需要自己重新控制行动。
还有就是”集体行动“时的控制。如下图：
控制了一帮人往一个地方走，他们之间是不允许互相重叠的。在碰撞检测中，如果发生了碰撞，需要判断，是之前说的“碰头”还是“大家往同一个方向走”的情况。如果是非碰头情况，我的做法是：等待前面的单位移动出空位之后，后面的单位才上前挪一点。
代码截图：
从上面代码可以看到，我仅仅是暂停了Node节点的移动Action。如果检测发现没有碰撞了，就恢复执行之前的MoveTo动作。目前我的实现还有缺陷，并不完善。在某种情况下，集体行动，会出现“穿越”的问题，但在大部分情况下是可以保持不穿越的。
实际上，防穿越还会涉及更多的细节问题，这里我就不一一列举了。
从上可以看到，如果加入了防穿越，会让程序复杂很多。允许穿越的话，什么“碰头死锁”，“集体移动”等问题都没有了。从复杂度、开发成本等各方面因素考虑，我想这是Supercell不做防穿越的原因。
2. 行军算法、布阵算法
在魔兽3中，控制部队达到某地，是有行动队形的。目前我还没有仔细去考虑如何做，但这个在RTS游戏中是存在的。另一个问题是关于布阵。仔细观察和研究魔兽3，选中8个农民到某地，那8个农民到目的地后，有一个类似于矩形的阵型。
规则布阵这个问题，我也没仔细考虑。但不可避免的是随机阵型总要考虑，就是说，如下这种情况：
选中了N个单位，然后指挥他们到某处。这N个单位因为受之前的仿穿越限制，他们不能集中在一个点上。那么，如何确定各个单位的目的点？
我的做法是：在目的点，进行BFS（宽度优先搜索），寻找每个单位可以被容纳的位置，为什么用BFS算法？因为BFS有圆形向外扩展的特性。
我的代码截图如下：
有一个细节是，如何保持原先的集体“布局”？
A，B，C 对于整个选中的单位集合来说，有自己所处的位置。移动这些单位到另一处，好的做法是，也同时保持他们原先在集体中的位置。因为，这样做是对整体行军来说，总体移动成本最小。总体移动成本就是说，对于集体中每个行动单位的行动耗时、路径长度等之和。总体移动成本越小，给玩家的感觉就越和谐。
我在实践中，发现了这个问题，做了一些简单处理。不过从目前来说，效果并不怎么好。
3. “A过去”如何做
玩魔兽的朋友都知道“A过去”的含义吧？A过去就是“攻击过去”的意思，源于魔兽3的A键控制。
“过去攻击”包括2个分解步骤，1.先走过去，2.达到攻击范围后，开始攻击。A过去有2个作用点：1.玩家A的是地板。2.玩家A的是一个游戏实体，某个敌军单位、建筑等。
玩家A的是地板的话，AI逻辑是：控制行动体走到A的目的点，如果在行动的过程中有敌军进入了攻击范围，就攻击，歼灭了敌军，继续走到目的点。玩家A的是某个游戏实体的话，AI逻辑是：记住被A的那个目标实体，追着他打，直到目标被歼灭。
红警的A，坦克会用炮弹攻击地面。魔兽3的A，只有控制投石车才会攻击地面。目前我还没实现A过去的逻辑。
4. 单位大小通过限制
魔兽3中的食尸鬼可以通过的地方，剑圣不一定能通过。因为，食尸鬼、剑圣、尸魔等的体积不一样。单纯的A*算法，只是能找到有联通的最短路径。
剑圣的寻路是怎样做的？是不是要在A*算法作用的瓦片方格上，把剑圣不能通过的地方，给填充上，再执行A*呢？这个问题我没想清楚。目前我的游戏也不处理这点。
综上浅谈的4点就可以看到像魔兽这样的RTS游戏编写的难度。实际上编写一个真正的RTS还远不止这4点那么简单，想想 战争迷雾、地形等等。肯定还有一些未知的技术难点，我还没意识到。
考虑用数据驱动的方式编写游戏
所谓的数据驱动，就是用一些配置来控制游戏的显示、行为等。我的demo目前是用COC和其他游戏的素材来做的，以后要改成 RPG，塔防什么的，肯定不能盗用别人的美术资源，是吧。
为了方便换皮。游戏实体的显示、动画的显示。我都用了配置来搞。如下面所示。
行动体的显示控制表：
等等。有10个表了。
这些配置表，用Excel来做，然后另存为CSV。程序去解析CSV文件数据。关于CSV数据的解析，我写过一个比较完善的类，有兴趣的话，看看我的这篇博客：《CSV文件格式解析器的实现：从字符串Split到FSM》。目前，我的这个demo也只用了CSV类型的数据做配置，并且也是我用之前博客中写的那个CSV类去做解析。
思考的过程
这里也和大家分享下，我思考的过程。
《暗时间》这本书中讲过，思考是要借助笔和纸的。记录下当前自己探索到的、思考到的步骤和环境。以便于回溯思维的时候，防止忘记自己推理到哪一步了。
一个人独立开发，很多时候是自己和自己对话。自己提出设想，自己论证。这种情况就更加需要笔和纸。
下面是我的一些草稿纸截图。
目前我没发现市面上有任何一本书去教如何写RTS游戏。一个月的尝试，还是有价值的。
仅仅是做类COC的话，感觉并不很复杂。而一旦加入真正的RTS元素，就知道红警、帝国、魔兽的技术含量有多高了。腾讯等公司可以模仿出COC，什么城堡争霸，陌陌争霸等。但他们目前做不了“类魔兽3”，“类星际2”，魔兽争霸3 不仅是一个真正的现代RTS，还是3D的。我估计，不是他们不想，而是“类魔兽3”这个玩意“确实有点难度”。
目前本人入游戏领域不久，菜鸟一枚，欢迎游戏同行与我交流讨论。
【扫描游戏陀螺微信二维码，获取更多干货爆料】【Cocos2d-x 3.x教程】如何基于cocos2dx3.x实现A星寻路算法
招聘信息：
在学习本篇教程之前，如果你有cocos2d-x的开发经验，将会有所帮助。如果没有也没关系，因为你可以将这里讲解的例子迁移到其他的语言或者框架中。
找到到达你键盘的最短路径，开始吧！
首先介绍下我们将要在本篇教程中开发的简单游戏。
前往下载本篇教程的。编译运行工程，你将看到以下画面。
在这款游戏中，你扮演着一只小偷猫，在一个由危险的狗守护着的地牢里小心穿行。如果你试图穿过一只狗，他会把你吃掉 & 除非你可以用骨头去贿赂它！
所以在这款游戏中，你的任务是尝试以正确的顺序捡起骨头，然后 寻找路线 穿过狗逃离。
注意到猫只能水平或者垂直的移动（例如不能斜线移动），并且会从一个方块的中心点移动到另一个中心点。每个方块既可以是可通行的也可以是不可通行的。
尝试下这款游戏，看看你能否找到出路！建议你阅读代码以熟悉它的原理。这是一款相当普通的方块-地图式游戏，我们会在接下来的教程中修改它并使用上A星寻路算法。
Maze猫和A星概览
正如你所看到的，当你点击地图某处时，猫会沿着你点击的方向跳到相邻的方块上。
我们想对程序做修改，让猫持续的往你点击的方块方向前进，就像许多RPGs或者point-and-click冒险类游戏。
让我们看下控制触摸事件代码的工作原理。如果你打开HelloWorldScene.cpp文件，你将看到像下面这样去实现触摸操作：
auto&listener&=&EventListenerTouchOneByOne::create();&listener->setSwallowTouches(true);&listener->onTouchBegan&=&[this](Touch&*touch,&Event&*event){&if&(_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&pR&&&&&}&&&&&else&&&&&{&&&&&&&&&CC_SAFE_DELETE(pRet);&&&&&&&&&return&&&&&&}&}&bool&CatSprite::ShortestPathStep::initWithPosition(const&Point&&pos)&{&&&&&bool&bRet&=&false;&&&&&do&&&&&{&&&&&&&&&this->setPosition(pos);&&&&&&&&&bRet&=&true;&&&&&}&while&(0);&&&&&return&bR&}&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&_spOpenS&cocos2d::Vector&_spClosedS&
检查开始和结束点
重新实现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;&&&&&}&&&&&if&(!_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&To:&20..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&<&&++i)&&&&&{&&&&&&&&&if&(stepFScore&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&1;&}&
接下来，需要一个方法去获取给定方块的所有相邻可行走方块。因为在这个游戏中，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&&}&
可以继续CatSprite.cpp中的moveToward方法了，在moveToward方法的后面，添加如下代码：
bool&pathFound&=&false;&_spOpenSteps.clear();&_spClosedSteps.clear();&&this->insertInOpenSteps(ShortestPathStep::createWithPosition(fromTileCoord));&do&{&&&&&&&&&&&&&&&ShortestPathStep&*currentStep&=&_spOpenSteps.at(0);&&&&&&&&&&_spClosedSteps.pushBack(currentStep);&&&&&&&&&&&&&&&_spOpenSteps.erase(0);&&&&&&&&&&if&(currentStep->getPosition()&==&toTileCoord)&&&&&{&&&&&&&&&pathFound&=&true;&&&&&&&&&ShortestPathStep&*tmpStep&=&currentS&&&&&&&&&CCLOG("PATH&FOUND&:");&&&&&&&&&do&&&&&&&&&{&&&&&&&&&&&&&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&count();&++i)&&&&&{&&&&&&&&&ShortestPathStep&*step&=&ShortestPathStep::createWithPosition(adjSteps->getControlPointAtIndex(i));&&&&&&&&&&&&&&&&&&if&(this->getStepIndex(_spClosedSteps,&step)&!=&-1)&&&&&&&&&{&&&&&&&&&&&&&continue;&&&&&&&&&}&&&&&&&&&&&&&&&&&&int&moveCost&=&this->costToMoveFromStepToAdjacentStep(currentStep,&step);&&&&&&&&&&&&&&&&&&ssize_t&index&=&this->getStepIndex(_spOpenSteps,&step);&&&&&&&&&&&&&&&&&&if&(index&==&-1)&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&&&&&&&step->setParent(currentStep);&&&&&&&&&&&&&&&&&&&&&&&&&&step->setGScore(currentStep->getGScore()&+&moveCost);&&&&&&&&&&&&&&&&&&&&&&&&&&step->setHScore(this->computeHScoreFromCoordToCoord(step->getPosition(),&toTileCoord));&&&&&&&&&&&&&&&&&&&&&&&&&&this->insertInOpenSteps(step);&&&&&&&&&}&&&&&&&&&else&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&&&&&&&step&=&_spOpenSteps.at(index);&&&&&&&&&&&&&&&&&&&&&&&&&&if&((currentStep->getGScore()&+&moveCost)&getGScore())&&&&&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&step->setGScore(currentStep->getGScore()&+&moveCost);&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&step->retain();&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&_spOpenSteps.erase(index);&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&this->insertInOpenSteps(step);&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&step->release();&&&&&&&&&&&&&}&&&&&&&&&}&&&&&}&}&while&(_spOpenSteps.size()&>&0);&if&(!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)&&&&&{&&&&&&&&&if&(steps.at(i)->isEqual(step))&&&&&&&&&{&&&&&&&&&&&&&return&i;&&&&&&&&&}&&&&&}&&&&&return&-1;&}&
编译运行，在地图上进行点击，如下图所示：
From:&24..000000&To:&23..000000&PATH&FOUND&:&pos=[23;3]&&g=10&&h=0&&f=10&pos=[22;3]&&g=9&&h=1&&f=10&pos=[21;3]&&g=8&&h=2&&f=10&pos=[20;3]&&g=7&&h=3&&f=10&pos=[20;2]&&g=6&&h=4&&f=10&pos=[20;1]&&g=5&&h=5&&f=10&pos=[21;1]&&g=4&&h=4&&f=8&pos=[22;1]&&g=3&&h=3&&f=6&pos=[23;1]&&g=2&&h=2&&f=4&pos=[24;1]&&g=1&&h=3&&f=4&pos=[24;0]&&g=0&&h=0&&f=0&
注意该路径是从后面建立的，所以必须从下往上看猫选择了哪条路径。
跟随路径前进
现在已经找到了路径，只需让猫跟随前进即可。需要创建一个数组去存储路径，打开CatSprite.h文件，添加如下代码：
cocos2d::Vector&_shortestP&
打开CatSprite.cpp文件，更改moveToward方法，注释掉语句**bool pathFound = false**;，如下：
替换语句**pathFound =**为如下：
&this->constructPathAndStartAnimationFromStep(currentStep);&
并且注释掉下方的调试语句：
&&&&&&&&&替换语句**if&(!pathFound)**为如下：&&if&(_shortestPath.empty())&&&现在创建一个方法，用来存储整个路径，并且负责动画的播放。添加方法如下：&void&CatSprite::constructPathAndStartAnimationFromStep(CatSprite::ShortestPathStep&*step)&{&&&&&_shortestPath.clear();&&&&&do&&&&&{&&&&&&&&&&&&&&&&&&if&(step->getParent())&&&&&&&&&{&&&&&&&&&&&&&&&&&&&&&&&&&&_shortestPath.insert(0,&step);&&&&&&&&&}&&&&&&&&&step&=&step->getParent();&&&&&&&&}&while&(step);&&&&&&&&&&&&&&&&&&&&&&for&(const&ShortestPathStep&*s&:&_shortestPath)&&&&&{&&&&&&&&&CCLOG("%s",&s->getDescription().c_str());&&&&&}&}&
编译运行，点击，就可以在控制台看到如下信息：
From:&24..000000&To:&24..000000&pos=[24;1]&&g=1&&h=2&&f=3&pos=[23;1]&&g=2&&h=3&&f=5&pos=[22;1]&&g=3&&h=4&&f=7&pos=[21;1]&&g=4&&h=5&&f=9&pos=[20;1]&&g=5&&h=6&&f=11&pos=[20;2]&&g=6&&h=5&&f=11&pos=[20;3]&&g=7&&h=4&&f=11&pos=[21;3]&&g=8&&h=3&&f=11&pos=[22;3]&&g=9&&h=2&&f=11&pos=[23;3]&&g=10&&h=1&&f=11&pos=[24;3]&&g=11&&h=0&&f=11&
这些信息跟之前的很类似，除了它是从开始到结束，而不是相反的，并且步骤都被很好的存储在数组中以供使用。最后要做的是遍历shortestPath数组，让猫沿着路径动画前进。为了实现这一点，创建一个方法，从数组中获取步骤，让猫移动到那个位置，然后添加一个回调函数去重复调用这个方法直到路径完成。添加方法如下：
void&CatSprite::popStepAndAnimate()&{&&&&&&&&&&if&(_shortestPath.size()&==&0)&&&&&{&&&&&&&&&return;&&&&&}&&&&&&&&&&ShortestPathStep&*s&=&_shortestPath.at(0);&&&&&&&&&&MoveTo&*moveAction&=&MoveTo::create(0.4f,&_layer->positionForTileCoord(s->getPosition()));&&&&&CallFunc&*moveCallback&=&CallFunc::create(CC_CALLBACK_0(CatSprite::popStepAndAnimate,&this));&&&&&&&&&&_shortestPath.erase(0);&&&&&&&&&&this->runAction(Sequence::create(moveAction,&moveCallback,&nullptr));&}&&&在constructPathAndStartAnimationFromStep方法里的最下面添加如下代码：&this->popStepAndAnimate();&
编译运行，点击地面，可以看到猫自动移动到所点击的位置了。如下图所示：
然而，会发现到以下问题：
- 猫看起来有点僵硬
- 猫没有带走骨头
- 猫可以穿过狗（没有带着骨头），而不被吃掉
- 当在猫走完路径之前，点击了一个新的路径的话，猫会有奇怪的行为
因此，为了解决猫的僵硬行为，还有游戏逻辑（胜利/失败，狗，骨头，等等......），必须加上之前实现的旧游戏逻辑。
重新添加游戏逻辑
为了修复这些问题，替换popStepAndAnimate方法为如下：
void&CatSprite::popStepAndAnimate()&{&&&&&Point&currentPosition&=&_layer->tileCoordForPosition(this->getPosition());&&&&&if&(_layer->isBoneAtTilecoord(currentPosition))&&&&&{&&&&&&&&&SimpleAudioEngine::getInstance()->playEffect("pickup.wav");&&&&&&&&&_numBones++;&&&&&&&&&_layer->showNumBones(_numBones);&&&&&&&&&_layer->removeObjectAtTileCoord(currentPosition);&&&&&}&&&&&else&if&(_layer->isDogAtTilecoord(currentPosition))&&&&&{&&&&&&&&&if&(_numBones&==&0)&&&&&&&&&{&&&&&&&&&&&&&_layer->loseGame();&&&&&&&&&&&&&return;&&&&&&&&&}&&&&&&&&&else&&&&&&&&&{&&&&&&&&&&&&&_numBones--;&&&&&&&&&&&&&_layer->showNumBones(_numBones);&&&&&&&&&&&&&_layer->removeObjectAtTileCoord(currentPosition);&&&&&&&&&&&&&SimpleAudioEngine::getInstance()->playEffect("catAttack.wav");&&&&&&&&&}&&&&&}&&&&&else&if&(_layer->isExitAtTilecoord(currentPosition))&&&&&{&&&&&&&&&_layer->winGame();&&&&&&&&&return;&&&&&}&&&&&else&&&&&{&&&&&&&&&SimpleAudioEngine::getInstance()->playEffect("step.wav");&&&&&}&&&&&&&&&&if&(_shortestPath.size()&==&0)&&&&&{&&&&&&&&&return;&&&&&}&&&&&&&&&&ShortestPathStep&*s&=&_shortestPath.at(0);&&&&&Point&futurePosition&=&s->getPosition();&&&&&Point&diff&=&futurePosition&-&currentP&&&&&if&(abs(diff.x)&>&abs(diff.y))&&&&&{&&&&&&&&&if&(diff.x&>&0)&&&&&&&&&{&&&&&&&&&&&&&this->runAnimation(_facingRightAnimation);&&&&&&&&&}&&&&&&&&&else&&&&&&&&&{&&&&&&&&&&&&&this->runAnimation(_facingLeftAnimation);&&&&&&&&&}&&&&&}&&&&&else&&&&&{&&&&&&&&&if&(diff.y&>&0)&&&&&&&&&{&&&&&&&&&&&&&this->runAnimation(_facingForwardAnimation);&&&&&&&&&}&&&&&&&&&else&&&&&&&&&{&&&&&&&&&&&&&this->runAnimation(_facingBackAnimation);&&&&&&&&&}&&&&&}&&&&&&&&&&MoveTo&*moveAction&=&MoveTo::create(0.4f,&_layer->positionForTileCoord(s->getPosition()));&&&&&CallFunc&*moveCallback&=&CallFunc::create(CC_CALLBACK_0(CatSprite::popStepAndAnimate,&this));&&&&&&&&&&_shortestPath.erase(0);&&&&&&&&&&Sequence&*moveSequence&=&Sequence::create(moveAction,&moveCallback,&nullptr);&&&&&moveSequence->setTag(1);&&&&&this->runAction(moveSequence);&}&
这里只是对原来的代码进行重构。接着在moveToward方法里面的最上面添加如下代码：
this->stopActionByTag(1);&
编译运行，可以看到一切正常了，如下图所示：
如何实现对角线移动
在A星算法中实现对角线移动十分简单，只需要更改以下两个方法：
- walkableAdjacentTilesCoordForTileCoord：更改以便包括对角线方块
- costToMoveFromStepToAdjacentStep：更改以让对角线移动跟水平/垂直移动有不一样的成本
如何计算出在对角线方向上的成本值？使用简单的数学即可。猫从一个方块的中心移动到另一个方块的中心，并且因为方块是正方形，A、B和C形成了一个三角形，如下图所示：
&所以对角线的移动成本等于1.41，这低于向左移动再向上移动的成本值2（1+1）。正如所知的，使用整型计算远比浮点型更高效，所以不是使用浮点型来标示对角线移动的成本值，而是简单地对成本值乘以10，然后四舍五入，所以水平/垂直移动的成本值为10，而对角线移动的成本值为14。更改costToMoveFromStepToAdjacentStep方法为如下：
int&CatSprite::costToMoveFromStepToAdjacentStep(const&ShortestPathStep&*fromStep,&const&ShortestPathStep&*toStep)&{&&&&&return&((fromStep->getPosition().x&!=&toStep->getPosition().x)&&&&&&&&&&&&&&&&(fromStep->getPosition().y&!=&toStep->getPosition().y))&?&14&:&10;&}&
更改walkableAdjacentTilesCoordForTileCoord方法为如下：
PointArray&*HelloWorld::walkableAdjacentTilesCoordForTileCoord(const&Point&&tileCoord)&const&{&&&&&PointArray&*tmp&=&PointArray::create(8);&&&&&bool&t&=&false;&&&&&bool&l&=&false;&&&&&bool&b&=&false;&&&&&bool&r&=&false;&&&&&&&&&&Point&p(tileCoord.x,&tileCoord.y&-&1);&&&&&if&(this->isValidTileCoord(p)&&&&!this->isWallAtTileCoord(p))&&&&&{&&&&&&&&&tmp->addControlPoint(p);&&&&&&&&&t&=&true;&&&&&}&&&&&&&&&&p.setPoint(tileCoord.x&-&1,&tileCoord.y);&&&&&if&(this->isValidTileCoord(p)&&&&!this->isWallAtTileCoord(p))&&&&&{&&&&&&&&&tmp->addControlPoint(p);&&&&&&&&&l&=&true;&&&&&}&&&&&&&&&&p.setPoint(tileCoord.x,&tileCoord.y&+&1);&&&&&if&(this->isValidTileCoord(p)&&&&!this->isWallAtTileCoord(p))&&&&&{&&&&&&&&&tmp->addControlPoint(p);&&&&&&&&&b&=&true;&&&&&}&&&&&&&&&&p.setPoint(tileCoord.x&+&1,&tileCoord.y);&&&&&if&(this->isValidTileCoord(p)&&&&!this->isWallAtTileCoord(p))&&&&&{&&&&&&&&&tmp->addControlPoint(p);&&&&&&&&&r&=&true;&&&&&}&&&&&&&&&&p.setPoint(tileCoord.x&-&1,&tileCoord.y&-&1);&&&&&if&(t&&&&l&&&&this->isValidTileCoord(p)&&&&!this->isWallAtTileCoord(p))&&&&&{&&&&&&&&&tmp->addControlPoint(p);&&&&&}&&&&&&&&&&p.setPoint(tileCoord.x&-&1,&tileCoord.y&+&1);&&&&&if&(b&&&&l&&&&this->isValidTileCoord(p)&&&&!this->isWallAtTileCoord(p))&&&&&{&&&&&&&&&tmp->addControlPoint(p);&&&&&}&&&&&&&&&&p.setPoint(tileCoord.x&+&1,&tileCoord.y&-&1);&&&&&if&(t&&&&r&&&&this->isValidTileCoord(p)&&&&!this->isWallAtTileCoord(p))&&&&&{&&&&&&&&&tmp->addControlPoint(p);&&&&&}&&&&&&&&&&p.setPoint(tileCoord.x&+&1,&tileCoord.y&+&1);&&&&&if&(b&&&&r&&&&this->isValidTileCoord(p)&&&&!this->isWallAtTileCoord(p))&&&&&{&&&&&&&&&tmp->addControlPoint(p);&&&&&}&&&&&return&&}&
重要提示：添加对角线方块的代码和添加水平/垂直方块的代码有些不同。事实上，例如，只有当顶部和左侧的方块被添加时，左上对角线才能够被添加。这是为了防止猫穿过墙壁的角落。以下是所有的详细情况处理：
- O = Origin
- B = Bottom
- L = Left
- R = Right
- TL = Top & Left
就拿上面图像的左上部分来进行举例。猫想要从原始点（O）到左下对角线方块（BL）。如果在左侧或者底部（或者都有）有一面墙，然后尝试走对角线，算法将会封掉墙壁的角落（或者两面墙壁的角落）。所以只有当左侧和底部没有墙壁时，左下对角线方块才可行走。如下图所示：
完整源码请下载。
本文改编自iOS Tutorial Team的成员的文章。以及博主的部分资源。
原帖地址：
CocoaChina是全球最大的苹果开发中文社区，官方微信每日定时推送各种精彩的研发教程资源和工具，介绍app推广营销经验，最新企业招聘和外包信息，以及Cocos2d引擎、Cocostudio开发工具包的最新动态及培训信息。关注微信可以第一时间了解最新产品和服务动态，微信在手，天下我有！
请搜索微信号&CocoaChina&关注我们！
微信扫一扫
订阅每日移动开发及APP推广热点资讯公众号：CocoaChina
点击量15926点击量10778点击量5957点击量5368点击量5062点击量5014点击量4965点击量4785点击量4699
&2015 Chukong Technologies,Inc.
京公网安备89