a星演算法教程

A. 濡備綍鍩轟簬cocos2dx3.x瀹炵幇A鏄熷昏礬綆楁硶

銆銆鍦ㄥ︿範鏈綃囨暀紼嬩箣鍓嶏紝濡傛灉浣犳湁cocos2d-x鐨勫紑鍙戠粡楠岋紝灝嗕細鏈夋墍甯鍔┿傚傛灉娌℃湁涔熸病鍏崇郴錛屽洜涓轟綘鍙浠ュ皢榪欓噷璁茶В鐨勪緥瀛愯縼縐誨埌鍏朵粬鐨勮璦鎴栬呮嗘灦涓銆
銆銆鎵懼埌鍒拌揪浣犻敭鐩樼殑鏈鐭璺寰勶紝寮濮嬪惂錛
銆銆Maze鐚
銆銆棣栧厛浠嬬粛涓嬫垜浠灝嗚佸湪鏈綃囨暀紼嬩腑寮鍙戠殑綆鍗曟父鎴忋
銆銆鍓嶅線涓嬭澆鏈綃囨暀紼嬬殑 宸ョ▼浠ｇ爜 銆傜紪璇戣繍琛屽伐紼嬶紝浣犲皢鐪嬪埌浠ヤ笅鐢婚潰銆

銆銆鍦ㄨ繖嬈炬父鎴忎腑錛屼綘鎵婕旂潃涓鍙灝忓伔鐚錛屽湪涓涓鐢卞嵄闄╃殑鐙楀畧鎶ょ潃鐨勫湴鐗㈤噷灝忓績絀胯屻傚傛灉浣犺瘯鍥劇┛榪囦竴鍙鐙楋紝浠栦細鎶婁綘鍚冩帀 鈥 闄ら潪浣犲彲浠ョ敤楠ㄥご鍘昏純璧傚畠錛
銆銆鎵浠ュ湪榪欐炬父鎴忎腑錛屼綘鐨勪換鍔℃槸灝濊瘯浠ユｇ『鐨勯『搴忔崱璧烽ㄥご錛岀劧鍚 瀵繪壘璺綰 絀胯繃鐙楅冪匯
銆銆娉ㄦ剰鍒扮尗鍙鑳芥按騫蟲垨鑰呭瀭鐩寸殑縐誨姩錛堜緥濡備笉鑳芥枩綰跨Щ鍔錛夛紝騫朵笖浼氫粠涓涓鏂瑰潡鐨勪腑蹇冪偣縐誨姩鍒板彟涓涓涓蹇冪偣銆傛瘡涓鏂瑰潡鏃㈠彲浠ユ槸鍙閫氳岀殑涔熷彲浠ユ槸涓嶅彲閫氳岀殑銆
銆銆灝濊瘯涓嬭繖嬈炬父鎴忥紝鐪嬬湅浣犺兘鍚︽壘鍒板嚭璺錛佸緩璁浣犻槄璇諱唬鐮佷互鐔熸倝瀹冪殑鍘熺悊銆傝繖鏄涓嬈劇浉褰撴櫘閫氱殑鏂瑰潡-鍦板浘寮忔父鎴忥紝鎴戜滑浼氬湪鎺ヤ笅鏉ョ殑鏁欑▼涓淇鏀瑰畠騫朵嬌鐢ㄤ笂A鏄熷昏礬綆楁硶銆
銆銆Maze鐚鍜孉鏄熸傝
銆銆姝ｅ備綘鎵鐪嬪埌鐨勶紝褰撲綘鐐瑰嚮鍦板浘鏌愬勬椂錛岀尗浼氭部鐫浣犵偣鍑葷殑鏂瑰悜璺沖埌鐩擱偦鐨勬柟鍧椾笂銆
銆銆鎴戜滑鎯沖圭▼搴忓仛淇鏀癸紝璁╃尗鎸佺畫鐨勫線浣犵偣鍑葷殑鏂瑰潡鏂瑰悜鍓嶈繘錛屽氨鍍忚稿歊PGs鎴栬卲oint-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->(listener, this );
銆銆浣犲彲浠ョ湅鍒拌繖閲屽彧鏄瀵圭尗綺劇伒璋冪敤浜嗕竴涓鏂規硶錛岃╃尗鍦ㄦ柟鍧楀湴鍥句笂寰浣犵偣鍑葷殑鍦版柟縐誨姩銆
銆銆鎴戜滑鐜板湪瑕佸仛鐨勬槸淇鏀瑰湪CatSprite.m鏂囦歡涓鐨勪互涓嬫柟娉曪紝瀵繪壘鍒拌揪璇ョ偣鐨勬渶鐭璺寰勶紝騫朵笖寮濮嬪墠榪涳細
銆銆void CatSprite::moveToward( const Point &target)
銆銆{
銆銆}
銆銆鍒涘緩ShortestPathStep綾
銆銆鎴戜滑寮濮嬪壋寤轟竴涓鍐呴儴綾伙紝浠ｈ〃璺寰勪笂鐨勪竴姝ユ搷浣溿傚湪榪欑嶆儏鍐典笅錛屽畠鏄涓涓鏂瑰潡鍜岀敱A鏄熺畻娉曡＄畻鍑烘潵鐨勭殑F,G鍜孒 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);
銆銆};
銆銆鐜板湪娣誨姞浠ヤ笅浠ｇ爜鍒癈atSprite.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 ;
銆銆do
銆銆{
銆銆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鐨勫礆級
銆銆榪欓噷瀹氫箟浜唃etDescription鏂規硶錛屼互鏂逛究璋冭瘯銆傚壋寤轟簡isEquals鏂規硶錛屽綋涓斾粎褰撲袱涓猄hortestPathSteps鐨勬柟鍧楀潗鏍囩浉鍚屾椂錛屽畠浠鐩哥瓑錛堜緥濡傚畠浠浠ｈ〃鐫鐩稿悓鐨勬柟鍧楋級銆
銆銆鍒涘緩Open鍜孋losed鍒楄〃
銆銆鎵撳紑CatSprite.h鏂囦歡錛屾坊鍔犲備笅浠ｇ爜錛
銆銆cocos2d::Vector _spOpenSteps;
銆銆cocos2d::Vector _spClosedSteps;
銆銆媯鏌ュ紑濮嬪拰緇撴潫鐐
銆銆閲嶆柊瀹炵幇moveToward鏂規硶錛岃幏鍙栧綋鍓嶆柟鍧楀潗鏍囧拰鐩鏍囨柟鍧楀潗鏍囷紝鐒跺悗媯鏌ユ槸鍚﹂渶瑕佽＄畻涓鏉¤礬寰勶紝鏈鍚庢祴璇曠洰鏍囨柟鍧楀潗鏍囨槸鍚﹀彲琛岃蛋鐨勶紙鍦ㄨ繖閲屽彧鏈夊欏佹槸涓嶅彲琛岃蛋鐨勶級銆傛墦寮CatSprite.cpp鏂囦歡錛屼慨鏀筸oveToward鏂規硶錛屼負濡備笅錛
銆銆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, 0.000000
銆銆To: 20.000000, 0.000000
銆銆鍏朵腑 **From** 灝辨槸鐚鐨勬柟鍧楀潗鏍囷紝**To**灝辨槸鎵鐐瑰嚮鐨勬柟鍧楀潗鏍囥
銆銆瀹炵幇A鏄熺畻娉
銆銆鏍規嵁綆楁硶錛岀涓姝ユ槸娣誨姞褰撳墠鍧愭爣鍒皁pen鍒楄〃銆傝繕闇瑕佷笁涓杈呭姪鏂規硶錛
銆銆- 涓涓鏂規硶鐢ㄦ潵鎻掑叆涓涓猄hortestPathStep瀵硅薄鍒伴傚綋鐨勪綅緗錛堟湁搴忕殑F鍊礆級
銆銆- 涓涓鏂規硶鐢ㄦ潵璁＄畻浠庝竴涓鏂瑰潡鍒扮浉閭繪柟鍧楃殑縐誨姩鏁板
銆銆- 涓涓鏂規硶鏄鏍規嵁"鏇煎搱欏胯窛紱"綆楁硶錛岃＄畻鏂瑰潡鐨凥鍊
銆銆鎵撳紑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)
銆銆{
銆銆if (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::( const ShortestPathStep *fromStep, const ShortestPathStep *toStep)
銆銆{
銆銆// 鍥犱負涓嶈兘鏂滅潃璧幫紝鑰屼笖鐢變簬鍦板艦灝辨槸鍙琛岃蛋鍜屼笉鍙琛岃蛋鐨勬垚鏈閮芥槸涓鏍風殑
銆銆// 濡傛灉鑳藉熷硅掔Щ鍔錛屾垨鑰呮湁娌兼辰銆佸北涓樼瓑絳夛紝閭ｄ箞瀹冨繀欏繪槸涓嶅悓鐨
銆銆return 1;
銆銆}
銆銆鎺ヤ笅鏉ワ紝闇瑕佷竴涓鏂規硶鍘昏幏鍙栫粰瀹氭柟鍧楃殑鎵鏈夌浉閭誨彲琛岃蛋鏂瑰潡銆傚洜涓哄湪榪欎釜娓告垙涓錛孒elloWorld綆＄悊鐫鍦板浘錛屾墍浠ュ湪閭ｉ噷娣誨姞鏂規硶銆傛墦寮HelloWorldScene.cpp鏂囦歡錛屾坊鍔犲備笅鏂規硶錛
銆銆PointArray *HelloWorld::( 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;
銆銆}
銆銆鍙浠ョ戶緇瑿atSprite.cpp涓鐨刴oveToward鏂規硶浜嗭紝鍦╩oveToward鏂規硶鐨勫悗闈錛屾坊鍔犲備笅浠ｇ爜錛
銆銆bool pathFound = false ;
銆銆_spOpenSteps.clear();
銆銆_spClosedSteps.clear();
銆銆// 棣栧厛錛屾坊鍔犵尗鐨勬柟鍧楀潗鏍囧埌open鍒楄〃
銆銆this ->insertInOpenSteps(ShortestPathStep::createWithPosition(fromTileCoord));
銆銆do
銆銆{
銆銆// 寰楀埌鏈灝忕殑F鍊兼ラ
銆銆// 鍥犱負鏄鏈夊簭鍒楄〃錛岀涓涓姝ラゆ繪槸鏈灝忕殑F鍊
銆銆ShortestPathStep *currentStep = _spOpenSteps.at(0);
銆銆// 娣誨姞褰撳墠姝ラゅ埌closed鍒楄〃
銆銆_spClosedSteps.pushBack(currentStep);
銆銆// 灝嗗畠浠巓pen鍒楄〃閲岄潰縐婚櫎
銆銆// 闇瑕佹敞鎰忕殑鏄錛屽傛灉鎯寵佸厛浠巓pen鍒楄〃閲岄潰縐婚櫎錛屽簲灝忓績瀵硅薄鐨勫唴瀛
銆銆_spOpenSteps.erase(0);
銆銆// 濡傛灉褰撳墠姝ラゆ槸鐩鏍囨柟鍧楀潗鏍囷紝閭ｄ箞灝卞畬鎴愪簡
銆銆if (currentStep->getPosition() == toTileCoord)
銆銆{
銆銆pathFound = true ;
銆銆ShortestPathStep *tmpStep = currentStep;
銆銆CCLOG( "PATH FOUND :" );
銆銆do
銆銆{
銆銆CCLOG( "%s" , tmpStep->getDescription().c_str());
銆銆tmpStep = tmpStep->getParent(); // 鍊掗
銆銆} while (tmpStep); // 鐩村埌娌℃湁涓婁竴姝
銆銆_spOpenSteps.clear();
銆銆_spClosedSteps.clear();
銆銆break ;
銆銆}
銆銆// 寰楀埌褰撳墠姝ラょ殑鐩擱偦鏂瑰潡鍧愭爣
銆銆PointArray *adjSteps = _layer->(currentStep->getPosition());
銆銆for (ssize_t i = 0; i < adjSteps->count(); ++i)
銆銆{
銆銆ShortestPathStep *step = ShortestPathStep::createWithPosition(adjSteps->getControlPointAtIndex(i));
銆銆// 媯鏌ユラゆ槸涓嶆槸宸茬粡鍦╟losed鍒楄〃
銆銆if ( this ->getStepIndex(_spClosedSteps, step) != -1)
銆銆{
銆銆continue ;
銆銆}
銆銆// 璁＄畻浠庡綋鍓嶆ラゅ埌姝ゆラょ殑鎴愭湰
銆銆int moveCost = this ->(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));
銆銆// 鎸夊簭娣誨姞鍒皁pen鍒楄〃
銆銆this ->insertInOpenSteps(step);
銆銆}
銆銆else
銆銆{
銆銆// 鑾峰彇鏃х殑姝ラわ紝鍏跺煎凡緇忚＄畻榪
銆銆step = _spOpenSteps.at(index);
銆銆// 媯鏌G鍊兼槸鍚︿綆浜庡綋鍓嶆ラゅ埌姝ゆラょ殑鍊
銆銆if ((currentStep->getGScore() + moveCost) < step->getGScore())
銆銆{
銆銆// G鍊肩瓑鍚屼簬涓婁竴姝ョ殑G鍊 + 浠庝笂涓姝ュ埌榪欓噷鐨勬垚鏈
銆銆step->setGScore(currentStep->getGScore() + moveCost);
銆銆// 鍥犱負G鍊兼敼鍙樹簡錛孎鍊間篃浼氳窡鐫鏀瑰彉
銆銆// 鎵浠ヤ負浜嗕繚鎸乷pen鍒楄〃鏈夊簭錛岄渶瑕佸皢姝ゆラょЩ闄わ紝鍐嶉噸鏂版寜搴忔彃鍏
銆銆// 鍦ㄧЩ闄や箣鍓嶏紝闇瑕佸厛淇濇寔寮曠敤
銆銆step->retain();
銆銆// 鐜板湪鍙浠ユ斁蹇冪Щ闄わ紝涓嶇敤鎷呭績琚閲婃斁
銆銆_spOpenSteps.erase(index);
銆銆// 閲嶆柊鎸夊簭鎻掑叆
銆銆this ->insertInOpenSteps(step);
銆銆// 鐜板湪鍙浠ラ噴鏀懼畠浜嗭紝鍥犱負open鍒楄〃搴旇ユ寔鏈夊畠
銆銆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, 0.000000
銆銆To: 23.000000, 3.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 _shortestPath;
銆銆鎵撳紑CatSprite.cpp鏂囦歡錛屾洿鏀筸oveToward鏂規硶錛屾敞閲婃帀璇鍙**bool pathFound = false**;錛屽備笅錛
銆銆//bool pathFound = false;
銆銆鏇挎崲璇鍙**pathFound = true;**涓哄備笅錛
銆銆//pathFound = true;
銆銆this ->(currentStep);
銆銆騫朵笖娉ㄩ噴鎺変笅鏂圭殑璋冭瘯璇鍙ワ細
銆銆//ShortestPathStep *tmpStep = currentStep;
銆銆//CCLOG("PATH FOUND :");
銆銆//do
銆銆//{
銆銆// CCLOG("%s", tmpStep->getDescription().c_str());
銆銆// tmpStep = tmpStep->getParent(); // 鍊掗
銆銆/

B. 演算法過程是什麼

C. A*搜尋演算法的演算法描述

f(x) = g(x) + h(x)
function A*(start,goal)
var closed := the empty set
var q := make_queue(path(start))
while q is not empty
var p := remove_first(q)
var x := the last node of p
if x in closed
continue
if x = goal
return p
add x to closed
foreach y in successors(x)
enqueue(q, p, y)
return failure A*改變它自己行為的能力基於啟發式代價函數，啟發式函數在游戲中非常有用。在速度和精確度之間取得折衷將會讓你的游戲運行得更快。在很多游戲中，你並不真正需要得到最好的路徑，僅需要近似的就足夠了。而你需要什麼則取決於游戲中發生著什麼，或者運行游戲的機器有多快。假設你的游戲有兩種地形，平原和山地，在平原中的移動代價是1而在山地的是3，那麼A星演算法就會認為在平地上可以進行三倍於山地的距離進行等價搜尋。 這是因為有可能有一條沿著平原到山地的路徑。把兩個鄰接點之間的評估距離設為1.5可以加速A*的搜索過程。然後A*會將3和1.5比較，這並不比把3和1比較差。然而，在山地上行動有時可能會優於繞過山腳下進行行動。所以花費更多時間尋找一個繞過山的演算法並不經常是可靠的。 同樣的，想要達成這樣的目標，你可以通過減少在山腳下的搜索行為來打到提高A星演算法的運行速率。弱項如此可以將A星演算法的山地行動耗費從3調整為2即可。這兩種方法都會給出可靠地行動策略 。