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即可。这两种方法都会给出可靠地行动策略 。