a尋路演算法
『壹』 如何基於cocos2dx3.x實現A星尋路演算法
在學習本篇教程之前，如果你有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->(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.000000To: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::(constShortestPathStep*fromStep,constShortestPathStep*toStep){//因為不能斜著走，而且由於地形就是可行走和不可行走的成本都是一樣的//如果能夠對角移動，或者有沼澤、山丘等等，那麼它必須是不同的return1;}接下來，需要一個方法去獲取給定方塊的所有相鄰可行走方塊。因為在這個游戲中，HelloWorld管理著地圖，所以在那裡添加方法。打開HelloWorldScene.cpp文件，添加如下方法：PointArray*HelloWorld::(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->(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->(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.000000To:23.000000,3.000000PATHFOUND:pos=[23;3]g=10h=0f=10pos=[22;3]g=9h=1f=10pos=[21;3]g=8h=2f=10pos=[20;3]g=7h=3f=10pos=[20;2]g=6h=4f=10pos=[20;1]g=5h=5f=10pos=[21;1]g=4h=4f=8pos=[22;1]g=3h=3f=6pos=[23;1]g=2h=2f=4pos=[24;1]g=1h=3f=4pos=[24;0]g=0h=0f=0注意該路徑是從後面建立的，所以必須從下往上看貓選擇了哪條路徑。跟隨路徑前進現在已經找到了路徑，只需讓貓跟隨前進即可。需要創建一個數組去存儲路徑，打開CatSprite.h文件，添加如下代碼：cocos2d::Vector_shortestPath;打開CatSprite.cpp文件，更改moveToward方法，注釋掉語句**boolpathFound=false**;，如下：//boolpathFound=false;替換語句**pathFound=true;**為如下：//pathFound=true;this->(currentStep);並且注釋掉下方的調試語句：//ShortestPathStep*tmpStep=currentStep;//CCLOG("PATHFOUND:");//do//{//CCLOG("%s",tmpStep->getDescription().c_str());//tmpStep=tmpStep->getParent();//倒退/
『貳』 A* 尋路演算法
A*演算法
�6�1 啟發式搜索
– 在搜索中涉及到三個函數
�6�1 g(n) = 從初始結點到結點n的耗費
�6�1 h(n) = 從結點n到目的結點的耗費評估值，啟發函數
�6�1 f(n)=g(n)+h(n) 從起始點到目的點的最佳評估值
– 每次都選擇f(n)值最小的結點作為下一個結點，
直到最終達到目的結點
– A*演算法的成功很大程度依賴於h(n)函數的構建
�6�1 在各種游戲中廣泛應用 Open列表和Closed列表
– Open列表
�6�1 包含我們還沒有處理到的結點
�6�1 我們最開始將起始結點放入到Open列表中
– Closed列表
�6�1 包含我們已經處理過的結點
�6�1 在演算法啟動時，Closed列表為空 A* 演算法偽代碼初始化OPEN列表
初始化CLOSED列表
創建目的結點；稱為node_goal
創建起始結點；稱為node_start
將node_start添加到OPEN列表
while OPEN列表非空{
從OPEN列表中取出f(n)值最低的結點n
將結點n添加到CLOSED列表中
if 結點n與node_goal相等then 我們找到了路徑，程序返回n
else 生成結點n的每一個後繼結點n'
foreach 結點n的後繼結點n'{
將n』的父結點設置為n
計算啟發式評估函數h(n『)值，評估從n『到node_goal的費用
計算g(n『) = g(n) + 從n』到n的開銷
計算f(n') = g(n') + h(n')
if n『位於OPEN或者CLOSED列表and 現有f(n)較優then丟棄n』 ，處理後繼n』
將結點n『從OPEN和CLOSED中刪除
添加結點n『到OPEN列表
}
}
return failure （我們已經搜索了所有的結點，但是仍然沒有找到一條路徑）
『叄』 A星尋路演算法和Unity自帶的尋路相比有什麼優勢
在理解Navigation的時候，首先要明確兩個知識點：
AStar：AStar是路點尋路演算法中的一種，同時AStar不屬於貪婪演算法，貪婪演算法適合動態規劃，尋找局部最優解，不保證最優解。AStar是靜態網格中求解最短路最有效的方法。也是耗時的演算法，不宜尋路頻繁的場合。一般來說適合需求精確的場合。
性能和內存佔用率都還行，和啟發式的搜索一樣，能夠根據改變網格密度、網格耗散來進行調整精確度。
A Star一般使用場景：
策略游戲的策略搜索
方塊格子游戲中的格子尋路
Navigation：網格尋路演算法，嚴格意義上它屬於」拐角點演算法」，效率是比較高的，但是不保證最優解演算法。Navigation相對來說消耗內存更大，性能的話還不錯。
Navigation一般使用場景：
游戲場景的怪物尋路
動態規避障礙
它們二者事件的實現方式和原理都不同。
AStar的話，
『肆』 如何在Cocos2D游戲中實現A*尋路演算法
操作步驟如下：一win764位系統搭建Android開發環境需要的軟體1.cocos2d-x3.3beta02.VisualStudio2012/2013安裝完占硬碟空間近10G，VisualStudio2012/2013是需要注冊碼。4.AndroidSDK（其中包括Eclipse）5.AndroidNDK6.Ant7.Python2.7.8不要下載3.x以上版本二軟體安裝安裝軟體時不要安裝在C盤。1.VisualStudio2012/2013VisualStudio2012/2013安裝方法像安裝其他軟體一樣，一路下一步就可以，但是注意安裝前IE瀏覽器版本必須是IE10以上版本。2.Python2.7.8安裝方法同上，但是不要安裝在C盤。3.JAVAJDKJAVAJDK默認安裝，這個可以安裝在C盤。4.cocos2d-x3.3beta0 AndroidSDK AndroidNDK Ant這些軟體都是解壓包，不需要安裝，解壓就可以。三cocos2d-x3.3beta0環境調試1.打開cocos2d-x3.3beta0所在的文件[attachment=78978]按Shift+滑鼠右鍵，點在此次打開命令窗口。現在可以看見畫黃線的是軟體變數名稱，紅線是變數路徑。正常的是4個變數名稱4條變數路徑，如果不是就需要手動添加，方法如下：1.右鍵計算機（XP叫我的電腦，win7叫計算機）------2.屬性------3.高級系統設置------4.環境變數------5.新建6.在變數名中添加缺少的變數名，在變數值中添加路徑。如：變數名NDK_ROOT 變數值D:\android-ndk-r10b軟體名稱 變數名cocos2d-x3.3beta0 COCOS_CONSOLE_ROOTAndroidSDK ANDROID_SDK_ROOTAndroidNDK NDK_ROOTAnt ANT_ROOT再次.打開cocos2d-x3.3beta0所在的文件，按Shift+滑鼠右鍵，點在此次打開命令窗口。如果看到4個變數名稱4條變數路徑就說明變數調試正確。四創建項目1.打開cocos2d-x3.3beta0所在的文件，按Shift+滑鼠右鍵，點在此次打開命令窗口。2.鍵入setup.py回車3.鍵入cocosnew項目名稱-p包名-l語言cpp-d項目路徑如：cocosnewtest-ptiaoshi-lcpp-d/test/android/cheshi會在存放cocos2d-x3.3beta0的盤符里出現一個名稱為tset的文件，打開文件-----proj.win32-----TSET.sin在VisualStudio2013中點 調試------開始執行不調試
『伍』 夢幻西遊 尋路演算法
[HOTKEY]A [NAME]壓鏢大大王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 390 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至獅陀嶺線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 20 55 [SCRIPT]REM 進獅陀嶺 [SCRIPT]MOVEOUT 6 49 34 [SCRIPT]REM 獅陀嶺至獅王洞線路 [SCRIPT]MOVETO 108 58 [SCRIPT]MOVETO 65 35 [SCRIPT]MOVETO 65 6 [SCRIPT]MOVETO 112 20 [SCRIPT]REM 進獅王洞 [SCRIPT]MOVEOUT 118 25 35 [SCRIPT]REM 到達大大王跟前 [SCRIPT]MOVETO 22 12
－－－－－－－－－－－－－－－－－－
[HOTKEY]B [NAME]壓鏢二大王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至獅陀嶺線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 20 55 [SCRIPT]REM 進獅陀嶺 [SCRIPT]MOVEOUT 6 49 34 [SCRIPT]REM 獅陀嶺至大象洞線路 [SCRIPT]MOVETO 108 58 [SCRIPT]MOVETO 52 78 [SCRIPT]MOVETO 20 82 [SCRIPT]REM 進大象洞 [SCRIPT]MOVEOUT 28 84 37 [SCRIPT]REM 到達二大王跟前 [SCRIPT]MOVETO 20 10
－－－－－－－－－－－－－－－－
[HOTKEY]C [NAME]壓鏢三大王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 3 12 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 390 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至獅陀嶺線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 20 55 [SCRIPT]REM 進獅陀嶺 [SCRIPT]MOVEOUT 6 49 34 [SCRIPT]REM 獅陀嶺至老雕洞線路 [SCRIPT]MOVETO 108 58 [SCRIPT]MOVETO 55 60 [SCRIPT]MOVETO 30 48 [SCRIPT]REM 進老雕洞 [SCRIPT]MOVEOUT 13 43 36 [SCRIPT]REM 到達三大王跟前 [SCRIPT]MOVETO 15 12
－－－－－－－－－－－－－－－－
[HOTKEY]D [NAME]壓鏢牛魔王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至牛魔寨線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 35 42 [SCRIPT]MOVETO 72 105 [SCRIPT]REM 進牛魔寨 [SCRIPT]MOVEOUT 54 116 38 [SCRIPT]REM 獅陀嶺至魔王居線路 [SCRIPT]MOVETO 35 65 [SCRIPT]MOVETO 78 65 [SCRIPT]MOVETO 88 70 [SCRIPT]REM 進魔王居 [SCRIPT]MOVEOUT 93 73 39 [SCRIPT]REM 到達牛魔王跟前 [SCRIPT]MOVETO 20 12
－－－－－－－－－－－－－－－－
[HOTKEY]E [NAME]壓鏢楊戩 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 3 13 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 190 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至長壽郊外線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]REM 對話南瞻部洲土地 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 52 15 [SCRIPT]REM 長壽郊外至天宮線路 [SCRIPT]MOVETO 21 58 [SCRIPT]REM 對話天將 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 23 55 [SCRIPT]REM 天宮至靈宵寶殿線路 [SCRIPT]MOVETO 150 60 3 3 31 [SCRIPT]REM 進靈宵寶殿 [SCRIPT]MOVEOUT 144 64 32 [SCRIPT]REM 到達楊戩身旁 [SCRIPT]MOVETO 56 28
－－－－－－－－－－－－－－－－－
[HOTKEY]F [NAME]壓鏢李靖 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 3 13 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 190 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至長壽郊外線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]REM 對話南瞻部洲土地 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 52 15 [SCRIPT]REM 長壽郊外至天宮線路 [SCRIPT]MOVETO 21 58 [SCRIPT]REM 對話天將 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 23 55 [SCRIPT]REM 天宮至靈宵寶殿線路 [SCRIPT]MOVETO 150 60 3 3 31 [SCRIPT]REM 進靈宵寶殿 [SCRIPT]MOVEOUT 144 64 32 [SCRIPT]REM 到達李靖身旁 [SCRIPT]MOVETO 32 36
－－－－－－－－－－－－－－－－－
[HOTKEY]G [NAME]壓鏢普提老祖 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 390 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至長壽郊外線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]REM 對話南瞻部洲土地 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 52 15 [SCRIPT]REM 長壽郊外至長壽村線路 [SCRIPT]MOVETO 45 30 [SCRIPT]MOVETO 60 65 [SCRIPT]MOVETO 125 90 [SCRIPT]MOVETO 150 152 [SCRIPT]REM 進長壽村 [SCRIPT]MOVEOUT 154 162 28 [SCRIPT]REM 長壽村至方寸山線路 [SCRIPT]MOVETO 132 166 [SCRIPT]MOVETO 102 195 [SCRIPT]REM 出長壽村 [SCRIPT]MOVEOUT 111 206 29 [SCRIPT]REM 方寸山至靈台宮線路 [SCRIPT]MOVETO 126 26 [SCRIPT]MOVETO 135 60 [SCRIPT]MOVETO 55 90 [SCRIPT]MOVETO 125 130 [SCRIPT]REM 進靈台宮 [SCRIPT]MOVEOUT 125 136 30 [SCRIPT]MOVETO 39 25
如果是這個腳本 請採納我的 謝謝
『陸』 lua語言a星尋路演算法路徑怎麼平滑
在項目中遇到了自動尋路的需求，於是決定開始學習一下A星，對於A星我也沒有深究，只能說是勉強搞定了需求，在這和大家分享一下，相互進步，
A星有個公式 f(x) = g(x) + h(x)
,搞清楚這個公式就好辦了，f(x)就是當前位置到下一個位置的總價值，g(x)表示實際價，這是說這一部分代價是確定的，h(x)表示估價值，就是說我
從下一個位置到到終點的代價是未知的，所以叫估價值，如圖中所示，黑色格子表示當前位置，綠色格子表示下一步可能到達的位置，即上、下、左、右這幾個方
向，紅色格子表示終點，褐色表示障礙物，現在要從黑色格子到達紅色格子，那麼黑色格子的下一步肯定是綠色格子當中的一個，黑色格子到綠色格子之間是相挨著
的，所以我們可以很明確的知道它的實際代價為1（移動一步的代價）即g(x)，綠色格子到紅色格子之間隔著很長的距離，中間還有障礙物，所以這個代價是未
知的，即h(x)，所以總的代價就為f(x) = g(x) +
h(x)，我們看到周圍有4個綠色的格子，到底走那一步比較好呢，所以我們要把這4個格子的f(x)值都求出來，然後進行排序，選擇f(x)值最小的，即
總代價最少的那個格子，以此方法繼續下去，直到到達終點 或者 地圖上沒有綠色格子了
下面來看一下這個工具類，g(x)和h(x)要選的比較合適，一般就是採用的曼哈頓演算法，即兩點在x方向和y方向的距離之和，
-- Filename: PathUtil.lua
-- Author: bzx
-- Date: 2014-07-01
-- Purpose: 尋路
mole("PathUtil", package.seeall)
local _map_data -- 地圖數據
local _open_list -- 開放節點
local _open_map -- 開放節點，為了提高性能而加
local _close_map -- 關閉節點
local _deleget -- 代理
local _dest_point -- 目標點
local _start_point -- 起點
local _path -- 路徑
-- 尋找路徑
--[[
deleget = {
g = function(point1, point2)
-- add your code
-- 返回點point1到點point2的實際代價
end
h = function(point1, point2)
-- add your code
-- 返回點point1到點point2的估算代價
end
getValue = function(j, i)
-- 返回地圖中第i行，第j列的數據 1為障礙物，0為非障礙物
end
width -- 地圖寬度
height -- 地圖高度
}
--]]
function findPath(deleget, start_point, dest_point)
_deleget = deleget
_dest_point = dest_point
_start_point = start_point
init()
while not table.isEmpty(_open_list) do
local cur_point = _open_list[1]
table.remove(_open_list, 1)
_open_map[cur_point.key] = nil
if isEqual(cur_point, dest_point) then
return makePath(cur_point)
else
_close_map[cur_point.key] = cur_point
local next_points = getNextPoints(cur_point)
for i = 1, #next_points do
local next_point = next_points[i]
if _open_map[next_point.key] == nil and _close_map[next_point.key] == nil and isObstacle(next_point) == false then
_open_map[next_point.key] = next_point
table.insert(_open_list, next_point)
end
end
table.sort(_open_list, compareF)
end
end
return nil
end
function init()
_open_list = {}
_open_map = {}
_close_map = {}
_path = {}
_map_data = {}
for i = 1, _deleget.height do
_map_data[i] = {}
for j = 1, _deleget.width do
local value = _deleget.getValue(j, i)
_map_data[i][j] = value
end
end
_open_map[getKey(_start_point)] = _start_point
table.insert(_open_list, _start_point)
end
function createPoint(x, y)
local point = {
["x"] = x,
["y"] = y,
["last"] = nil,
["g_value"] = 0,
["h_value"] = 0,
["f_value"] = 0
}
point["key"] = getKey(point)
return point
end
-- 得到下一個可以移動的點
-- @param point 當前所在點
function getNextPoints(point)
local next_points = {}
for i = 1, #_deleget.directions do
local offset = _deleget.directions[i]
local next_point = createPoint(point.x + offset[1], point.y + offset[2])
next_point["last"] = point
if next_point.x >= 1 and next_point.x <= _deleget.width and next_point.y >= 1 and next_point.y <= _deleget.height then
next_point["g_value"] = _deleget.g(point, next_point)
next_point["h_value"] = _deleget.h(point, _dest_point)--math.abs(next_points.x - _dest_point.x) + math.abs(next_points.y - _dest_point.y)
next_point["f_value"] = next_point.g_value + next_point.h_value
table.insert(next_points, next_point)
end
end
return next_points
end
-- 得到路徑
-- @param end_point 目標點
function makePath(end_point)
_path = {}
local point = end_point
while point.last ~= nil do
table.insert(_path, createPoint(point.x, point.y))
point = point.last
end
local start_point = point
table.insert(_path, start_point)
return _path
end
-- 兩個點的代價比較器
function compareF(point1, point2)
return point1.f_value < point2.f_value
end
-- 是否是障礙物
function isObstacle(point)
local value = _map_data[point.y][point.x]
if value == 1 then
return true
end
return false
end
-- 兩個點是否是同一個點
function isEqual(point1, point2)
return point1.key == point2.key
end
-- 根據點得到點的key
function getKey(point)
local key = string.format("%d,%d", point.x, point.y)
return key
end
下面是工具類PathUtil的用法
local deleget = {}
deleget.g = function(point1, point2)
return math.abs(point1.x - point2.x) + math.abs(point1.y - point2.y)
end
deleget.h = deleget.g
deleget.getValue = function(j, i)
local index = FindTreasureUtil.getIndex(j, i)
local map_info = _map_info.map[index]
if map_info.display == 0 and map_info.eid ~= 1 then
return 0
end
return 1
end
deleget.directions = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}} -- 左，上，下，右
deleget.width = _cols
deleget.height = _rows
local dest_row, dest_col = FindTreasureUtil.getMapPosition(tag)
local dest_point = PathUtil.createPoint(dest_col, dest_row)
local start_row, start_col = FindTreasureUtil.getMapPosition(_player_index)
local start_point = PathUtil.createPoint(start_col, start_row)
_path = PathUtil.findPath(deleget, start_point, dest_point)
_path就是我們找到的路徑，起點為最後一個元素，終點為第一個元素
『柒』 a*尋路演算法如果f值和h值都相等怎麼取最優節點
首先，G值是從開始點到當前點的移動量，H值是從當前點到終點的移動估算量。既然F=G+H.如果F值和H值都相同，那麼G值也是相同的，也就是說從開始點走了同樣的距離，移動到兩個不同的節點，而這兩個節點距離重點的距離也是相同的。那就繼續往下進行演算法。如果繼續下去之後，這兩個節點還是一樣的情況，那說明有兩條最優路徑，不然一定會有一個節點會被淘汰。
『捌』 按鍵精靈a星演算法尋路怎麼製作地圖
你可以查找有關a星演算法走路，一步步去學，別人也不知道你說的是什麼地圖，怎麼判斷
『玖』 有關A* 尋路演算法。 看了這個演算法 大致都明白。就是有點不大清楚。
1. B的G值是指從起點A開始，到達該點的最短距離，和B在不在最短路徑上沒有關系。
2. 不是遍歷所有路徑，而是所有點。對於m*n的矩陣， 遍歷所有點的復雜度是m*n（多項式復雜度），而遍歷所有路徑的復雜度是4的(m*n)次冪(每個點都有4個可能的方向)。從冪指數復雜度降低到多項式復雜度，這就是A*演算法的意義所在。
3. 最優路徑是要從終點一步步倒退回來。比如終點的G值是k，那麼最多需要4*k次查找，依然是多項式復雜度。但多數問題(對於純演算法題來說)只是需要知道到達終點的步驟，很少要你找出固定路徑的。
『拾』 游戲中的常用的尋路演算法有哪些
f(n)=g(n)+h(n) 從起始點到目的點的最佳評估值
– 每次都選擇f(n)值最小的結點作為下一個結點，
直到最終達到目的結點
– A*演算法的成功很大程度依賴於h(n)函數的構建
?;) = g(n? 在各種游戲中廣泛應用 Open列表和Closed列表
– Open列表
A*演算法
? h(n) = 從結點n到目的結點的耗費評估值，啟發函數
?，程序返回n
else 生成結點n的每一個後繼結點n;
foreach 結點n的後繼結點n;{
將n』的父結點設置為n
計算啟發式評估函數h(n『)值，評估從n『到node_goal的費用
計算g(n『) = g(n) + 從n』到n的開銷
計算f(n?? 在演算法啟動時，Closed列表為空 A* 演算法偽代碼初始化OPEN列表
初始化CLOSED列表
創建目的結點；稱為node_goal
創建起始結點；稱為node_start
將node_start添加到OPEN列表
while OPEN列表非空{
從OPEN列表中取出f(n)值最低的結點n
將結點n添加到CLOSED列表中
if 結點n與node_goal相等then 我們找到了路徑;)
if n『位於OPEN或者CLOSED列表and 現有f(n)較優then丟棄n』 ;) + h(n?? 包含我們還沒有處理到的結點
? g(n) = 從初始結點到結點n的耗費
?? 包含我們已經處理過的結點
，處理後繼n』
將結點n『從OPEN和CLOSED中刪除
添加結點n『到OPEN列表
}
}
return failure （我們已經搜索了所有的結點?? 啟發式搜索
– 在搜索中涉及到三個函數
??? 我們最開始將起始結點放入到Open列表中
– Closed列表
?