第1个回答 2016-07-17
在学习本篇教程之前,如果你有cocos2d-x的开发经验,将会有所帮助。如果没有也没关系,因为你可以将这里讲解的例子迁移到其他的语言或者框架中。 找到到达你键盘的最短路径,开始吧! Maze猫 首先介绍下我们将要在本篇教程中开发的简单游戏。 前往下载本篇教程的工程代码。编译运行工程,你将看到以下画面。 在这款游戏中,你扮演着一只小偷猫,在一个由危险的狗守护着的地牢里小心穿行。如果你试图穿过一只狗,他会把你吃掉–除非你可以用骨头去贿赂它! 所以在这款游戏中,你的任务是尝试以正确的顺序捡起骨头,然后寻找路线穿过狗逃离。 注意到猫只能水平或者垂直的移动(例如不能斜线移动),并且会从一个方块的中心点移动到另一个中心点。每个方块既可以是可通行的也可以是不可通行的。 尝试下这款游戏,看看你能否找到出路!建议你阅读代码以熟悉它的原理。这是一款相当普通的方块-地图式游戏,我们会在接下来的教程中修改它并使用上A星寻路算法。 Maze猫和A星概览 正如你所看到的,当你点击地图某处时,猫会沿着你点击的方向跳到相邻的方块上。 我们想对程序做修改,让猫持续的往你点击的方块方向前进,就像许多RPGs或者point-and-click冒险类游戏。 让我们看下控制触摸事件代码的工作原理。如果你打开HelloWorldScene.cpp文件,你将看到像下面这样去实现触摸操作: autolistener=EventListenerTouchOneByOne::create(); listener->setSwallowTouches(true); listener->onTouchBegan=[this](Touch*touch,Event*event){ if(_gameOver) { returnfalse; } PointtouchLocation=_tileMap->convertTouchToNodeSpace(touch); _cat->moveToward(touchLocation); returntrue; }; _eventDispatcher->addEventListenerWithSceneGraphPriority(listener,this); 你可以看到这里只是对猫精灵调用了一个方法,让猫在方块地图上往你点击的地方移动。 我们现在要做的是修改在CatSprite.m文件中的以下方法,寻找到达该点的最短路径,并且开始前进: voidCatSprite::moveToward(constPoint&target) { } 创建ShortestPathStep类 我们开始创建一个内部类,代表路径上的一步操作。在这种情况下,它是一个方块和由A星算法计算出来的的F,G和Hscores。 classShortestPathStep:publiccocos2d::Object { public: ShortestPathStep(); ~ShortestPathStep(); staticShortestPathStep*createWithPosition(constcocos2d::Point&pos); boolinitWithPosition(constcocos2d::Point&pos); intgetFScore()const; boolisEqual(constShortestPathStep*other)const; std::stringgetDescription()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(constPoint&pos) { ShortestPathStep*pRet=newShortestPathStep(); if(pRet&&pRet->initWithPosition(pos)) { pRet->autorelease(); returnpRet; } else { CC_SAFE_DELETE(pRet); returnnullptr; } } boolCatSprite::ShortestPathStep::initWithPosition(constPoint&pos) { boolbRet=false; do { this->setPosition(pos); bRet=true; }while(0); returnbRet; } intCatSprite::ShortestPathStep::getFScore()const { returnthis->getGScore()+this->getHScore(); } boolCatSprite::ShortestPathStep::isEqual(constCatSprite::ShortestPathStep*other)const { returnthis->getPosition()==other->getPosition(); } std::stringCatSprite::ShortestPathStep::getDescription()const { returnStringUtils::format("pos=[%.0f;%.0f]g=%dh=%df=%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方法,为如下: voidCatSprite::moveToward(constPoint&target) { PointfromTileCoord=_layer->tileCoordForPosition(this->getPosition()); PointtoTileCoord=_layer->tileCoordForPosition(target); if(fromTileCoord==toTileCoord) { CCLOG("You'realreadythere!: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,0.000000 To:20.000000,0.000000 其中**From**就是猫的方块坐标,**To**就是所点击的方块坐标。 实现A星算法 根据算法,第一步是添加当前坐标到open列表。还需要三个辅助方法: -一个方法用来插入一个ShortestPathStep对象到适当的位置(有序的F值) -一个方法用来计算从一个方块到相邻方块的移动数值 -一个方法是根据"曼哈顿距离"算法,计算方块的H值 打开CatSprite.cpp文件,添加如下方法: voidCatSprite::insertInOpenSteps(CatSprite::ShortestPathStep*step) { intstepFScore=step->getFScore(); ssize_tcount=_spOpenSteps.size(); ssize_ti=0; for(;igetFScore()) { break; } } _spOpenSteps.insert(i,step); } intCatSprite::computeHScoreFromCoordToCoord(constPoint&fromCoord,constPoint&toCoord) { //忽略了可能在路上的各种障碍 returnabs(toCoord.x-fromCoord.x)+abs(toCoord.y-fromCoord.y); } intCatSprite::costToMoveFromStepToAdjacentStep(constShortestPathStep*fromStep,constShortestPathStep*toStep) { //因为不能斜着走,而且由于地形就是可行走和不可行走的成本都是一样的 //如果能够对角移动,或者有沼泽、山丘等等,那么它必须是不同的 return1; } 接下来,需要一个方法去获取给定方块的所有相邻可行走方块。因为在这个游戏中,HelloWorld管理着地图,所以在那里添加方法。打开HelloWorldScene.cpp文件,添加如下方法: PointArray*HelloWorld::walkableAdjacentTilesCoordForTileCoord(constPoint&tileCoord)const { PointArray*tmp=PointArray::create(4); //上 Pointp(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); } returntmp; } 可以继续CatSprite.cpp中的moveToward方法了,在moveToward方法的后面,添加如下代码: boolpathFound=false; _spOpenSteps.clear(); _spClosedSteps.clear(); //首先,添加猫的方块坐标到open列表 this->insertInOpenSteps(ShortestPathStep::createWithPosition(fromTileCoord)); do { //得到最小的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("PATHFOUND:"); 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_ti=0;icount();++i) { ShortestPathStep*step=ShortestPathStep::createWithPosition(adjSteps->getControlPointAtIndex(i)); //检查步骤是不是已经在closed列表 if(this->getStepIndex(_spClosedSteps,step)!=-1) { continue; } //计算从当前步骤到此步骤的成本 intmoveCost=this->costToMoveFromStepToAdjacentStep(currentStep,step); //检查此步骤是否已经在open列表 ssize_tindex=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值是否低于当前步骤到此步骤的值 if((currentStep->getGScore()+moveCost)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); if(!pathFound) { SimpleAudioEngine::getInstance()->playEffect("hitWall.wav"); } 添加以下方法: ssize_tCatSprite::getStepIndex(constcocos2d::Vector&steps,constCatSprite::ShortestPathStep*step) { for(ssize_ti=0;iisEqual(step)) { returni; } } return-1; } 编译运行,在地图上进行点击,如下图所示: From:24.000000,0.000000 To:23.000000,3.000000 PATHFOUND: 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_shortestPath; 打开CatSprite.cpp文件,更改moveToward方法,注释掉语句**boolpathFound=false**;,如下: //boolpathFound=false; 替换语句**pathFound=true;**为如下: //pathFound=true; this->constructPathAndStartAnimationFromStep(currentStep); 并且注释掉下方的调试语句: //ShortestPathStep*tmpStep=currentStep; //CCLOG("PATHFOUND:"); //do //{ //CCLOG("%s",tmpStep->getDescription().c_str()); //tmpStep=tmpStep->getParent();//倒退 /