尋路演算法源碼
❶ 如何基於cocos2dx3.x實現A星尋路演算法
在學習本篇教程之前，如果你有cocos2d-x的開發經驗，將會有所幫助。如果沒有也沒關系，因為你可以將這里講解的例子遷移到其他的語言或者框架中。
找到到達你鍵盤的最短路徑，開始吧！
Maze貓
首先介紹下我們將要在本篇教程中開發的簡單游戲。
前往下載本篇教程的 工程代碼 。編譯運行工程，你將看到以下畫面。
在這款游戲中，你扮演著一隻小偷貓，在一個由危險的狗守護著的地牢里小心穿行。如果你試圖穿過一隻狗，他會把你吃掉 – 除非你可以用骨頭去賄賂它！
所以在這款游戲中，你的任務是嘗試以正確的順序撿起骨頭，然後 尋找路線 穿過狗逃離。
注意到貓只能水平或者垂直的移動（例如不能斜線移動），並且會從一個方塊的中心點移動到另一個中心點。每個方塊既可以是可通行的也可以是不可通行的。
嘗試下這款游戲，看看你能否找到出路！建議你閱讀代碼以熟悉它的原理。這是一款相當普通的方塊-地圖式游戲，我們會在接下來的教程中修改它並使用上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->(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 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的值）
這里定義了getDescription方法，以方便調試。創建了isEquals方法，當且僅當兩個ShortestPathSteps的方塊坐標相同時，它們相等（例如它們代表著相同的方塊）。
創建Open和Closed列表
打開CatSprite.h文件，添加如下代碼：
cocos2d::Vector _spOpenSteps;
cocos2d::Vector _spClosedSteps;
檢查開始和結束點
重新實現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, 0.000000
To: 20.000000, 0.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 < 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;
}
接下來，需要一個方法去獲取給定方塊的所有相鄰可行走方塊。因為在這個游戲中，HelloWorld管理著地圖，所以在那裡添加方法。打開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;
}
可以繼續CatSprite.cpp中的moveToward方法了，在moveToward方法的後面，添加如下代碼：
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);
// 將它從open列表裡面移除
// 需要注意的是，如果想要先從open列表裡面移除，應小心對象的內存
_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));
// 檢查步驟是不是已經在closed列表
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));
// 按序添加到open列表
this ->insertInOpenSteps(step);
}
else
{
// 獲取舊的步驟，其值已經計算過
step = _spOpenSteps.at(index);
// 檢查G值是否低於當前步驟到此步驟的值
if ((currentStep->getGScore() + moveCost) < step->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_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文件，更改moveToward方法，注釋掉語句**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(); // 倒退
/
❷ 手機游戲開發中怎麼實現怪物自動尋路（希望給段代碼）
我有，但是有誰會無償把這些資源給你。
我覺得我辦不到。
❸ vc環境 最短路徑演算法
單源最短路徑演算法---Dijkstra演算法
轉自:http://space.flash8.net/space/html/07/14107_itemid_400760.html
演算法介紹
Dijkstra演算法是由荷蘭計算機科學家艾茲格·迪科斯徹發現的。演算法解決的是有向圖中最短路徑問題。
舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離。 Dijkstra演算法可以用來找到兩個城市之間的最短路徑。
Dijkstra 演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。 (u,v)表示從頂點u到v有路徑相連。我們以E所有邊的集合，而邊的權重則由權重函數w: E → [0, ∞]定義。因此，w(u,v)就是從頂點u到頂點v的非負花費值(cost)。邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑 上所有邊的花費值總和。已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低花費路徑(i.e. 最短路徑)。這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。
演算法描述
這個演算法是通過為每個頂點v保留目前為止所找到的從s到v的最短路徑來工作的。 初始時，源點s的路徑長度值被賦為0（d[s]=0），同時把所有其他頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑（對於V中所有 頂點v除s外d[v]= ∞）。當演算法結束時，d[v]中儲存的便是從s到v的最短路徑，或者如果路徑不存在的話是無窮大。 Dijstra演算法的基礎操作是邊的拓展：如果存在一條從u到v的邊，那麼從s到u的最短路徑可以通過將邊(u,v)添加到尾部來拓展一條從s到v的路 徑。這條路徑的長度是d[u]+w(u,v)。如果這個值比目前已知的d[v]的值要小，我們可以用新值來替代當前d[v]中的值。拓展邊的操作一直執行 到所有的d[v]都代表從s到v最短路徑的花費。這個演算法經過組織因而當d[u]達到它最終的值的時候沒條邊(u,v)都只被拓展一次。
演算法維護兩個頂點集S和Q。集合S保留了我們已知的所有d[v]的值已經是最短路徑的值頂點，而集合Q則保留其他所有頂點。集合S初始狀態為空，而後每一步 都有一個頂點從Q移動到S。這個被選擇的頂點是Q中擁有最小的d[u]值的頂點。當一個頂點u從Q中轉移到了S中，演算法對每條外接邊(u,v)進行拓展。
偽碼
在下面的演算法中,u:=Extract_Min(Q)在在頂點集Q中搜索有最小的d[u]值的頂點u。這個頂點被從集合Q中刪除並返回給用戶。
function Dijkstra(G, w, s)
// 初始化
for each vertex v in V[G] {
d[v] := infinity
previous[v] := undefined
d[s] := 0
}
S := empty set
Q := set of all vertices
while Q is not an empty set { // Dijstra演算法主體
u := Extract_Min(Q)
S := S union {u}
for each edge (u,v) outgoing from u
if d[v] > d[u] + w(u,v) // 拓展邊(u,v)
d[v] := d[u] + w(u,v)
previous[v] := u
}
如果我們只對在s和t之間尋找一條最短路徑的話，我們可以在第9行添加條件如果滿足u=t的話終止程序。
現在我們可以通過迭代來回溯出s到t的最短路徑
1 S := empty sequence
2 u := t
3 while defined u
4 insert u to the beginning of S
5 u := previous[u]
現在序列S就是從s到t的最短路徑的頂點集.
時間復雜度
我們可以用大O符號將Dijkstra演算法的運行時間表示為邊數m和頂點數n的函數。
Dijkstra演算法最簡單的實現方法是用一個鏈表或者數組來存儲所有頂點的集合Q,所以搜索Q中最小元素的運算(Extract-Min(Q))只需要線性搜索Q中的所有元素。這樣的話演算法的運行時間是O(n2)。
對 於邊數少於n2稀疏圖來說，我們可以用鄰接表來更有效的實現Dijkstra演算法。同時需要將一個二叉堆或者斐波納契堆用作優先隊列來尋找最小的頂點 (Extract-Min)。當用到二叉堆的時候，演算法所需的時間為O((m+n)log n)，斐波納契堆能稍微提高一些性能，讓演算法運行時間達到O(m + n log n)。
相關問題和演算法
在Dijkstra 演算法的基礎上作一些改動，可以擴展其功能。例如，有時希望在求得最短路徑的基礎上再列出一些次短的路徑。為此，可先在原圖上計算出最短路徑，然後從圖中刪 去該路徑中的某一條邊，在餘下的子圖中重新計算最短路徑。對於原最短路徑中的每一條邊，均可求得一條刪去該邊後子圖的最短路徑，這些路徑經排序後即為原圖 的一系列次短路徑。
OSPF（open shortest path first, 開放最短路徑優先）演算法是Dijkstra演算法在網路路由中的一個具體實現。
與Dijkstra演算法不同，Bellman-Ford演算法可用於具有負花費邊的圖，只要圖中不存在總花費為負值且從源點 s 可達的環路（如果有這樣的環路，則最短路徑不存在，因為沿環路循環多次即可無限制的降低總花費）。
與最短路徑問題有關的一個問題是旅行商問題(traveling salesman problem)，它要求找出通過所有頂點恰好一次且最終回到源點的最短路徑。該問題是NP難的；換言之，與最短路徑問題不同，旅行商問題不太可能具有多項式時間演算法。
如果有已知信息可用來估計某一點到目標點的距離，則可改用A*演算法 ，以減小最短路徑的搜索范圍。
另外，用於解決最短路徑問題的演算法被稱做「最短路徑演算法」， 有時被簡稱作「路徑演算法」。 最常用的路徑演算法有：
Dijkstra演算法
A*演算法
SPFA演算法
Bellman-Ford演算法
Floyd-Warshall演算法
Johnson演算法
所謂單源最短路徑問題是指：已知圖G＝（V，E），我們希望找出從某給定的源結點S∈V到V中的每個結點的最短路徑。
首先，我們可以發現有這樣一個事實：如果P是G中從vs到vj的最短路，vi是P中的一個點，那麼，從vs沿P到vi的路是從vs到vi的最短路。
❹ 游戲中的常用的尋路演算法有哪些
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列表
?
❺ RMXP尋路演算法
#==============================================================================
# ■ Find_Path
#------------------------------------------------------------------------------
# 尋路演算法--完整滑鼠系統（四方向）專用版
# By whbm
#==============================================================================
class Find_Path
#--------------------------------------------------------------------------
def initialize #初始化
@open_list = []
@close_lise = []
@path = []
end #結束初始化
#--------------------------------------------------------------------------
def fp_passable?(x, y, d, tr_x = -2, tr_y = -2) #開始判定通行
return false if (tr_x == @unable_xa or
tr_x == @unable_xb or
tr_y == @unable_ya or
tr_y == @unable_yb)
if $game_player.passable?(x, y, d)
return true
else
return false
end
end #結束判定通行
#--------------------------------------------------------------------------
def get_g(now_point) #開始計算G值
d = now_point[2]
return 0 if d == 5
father_point = get_father_point(now_point)
g = father_point[3] + 10
return g
end #結束計算G值
#--------------------------------------------------------------------------
def get_h(now_point) #開始計算H值
now_x = now_point[0]
now_y = now_point[1]
#print @trg_x,now_x,@trg_y,now_y
h = (@trg_x - now_x).abs + (@trg_y - now_y).abs
return h * 10
end #結束計算H值
#--------------------------------------------------------------------------
def get_f(now_point) #開始計算F值
f = now_point[3] + now_point[4]
return f
end #結束計算F值
#--------------------------------------------------------------------------
def get_point(x, y) #取已知坐標點
if @open_list.size != 0
@open_list.each do |point|
if point[0] == x and point[1] == y
return point
break
end
end
end
if @close_list.size != 0
@close_list.each do |point|
if point[0] == x and point[1] == y
return point
break
end
end
end
end #結束取已知坐標點
#--------------------------------------------------------------------------
def get_father_point(now_point) #取已知點的父節點
d = now_point[2]
return now_point if d == 5
x = now_point[0] + (d == 6 ? 1 : (d == 4 ? -1 : 0))
y = now_point[1] + (d == 2 ? 1 : (d == 8 ? -1 : 0))
return get_point(x, y)
end #結束取已知點的父節點
#--------------------------------------------------------------------------
def new_point(x, y, d) #開始建立新節點
#print x,y,d
point = [x, y, d]
point.push get_g(point)
point.push get_h(point)
point.push get_f(point)
return point
end #結束建立新節點
#--------------------------------------------------------------------------
def get_direction(self_x, self_y, trg_x, trg_y)
if trg_x > self_x
if trg_y - self_y > - ( trg_x - self_x ) and
trg_y - self_y < ( trg_x - self_x )
return 6
end
if trg_y - self_y > ( trg_x - self_x )
return 2
end
if trg_y - self_y < - ( trg_x - self_x )
return 8
end
end
if trg_x < self_x
if trg_y - self_y > - ( self_x - trg_x ) and
trg_y - self_y < ( self_x - trg_x )
return 4
end
if trg_y - self_y > ( self_x - trg_x )
return 2
end
if trg_y - self_y < - ( self_x - trg_x )
return 8
end
end
end
#--------------------------------------------------------------------------
def get_d_x_y(x, y, d)
d_x = x + (d == 6 ? 1 : (d == 4 ? -1 : 0))
d_y = y + (d == 2 ? 1 : (d == 8 ? -1 : 0))
return d_x, d_y
end
#--------------------------------------------------------------------------
def find_short_path_other(self_x, self_y, trg_x, trg_y,
real_self_x, real_self_y, real_trg_x, real_trg_y)
@self_x = self_x
@self_y = self_y
@now_x = self_x
@now_y = self_y
@trg_x = trg_x
@trg_y = trg_y
@path = []
direction = get_direction(real_self_x, real_self_y, real_trg_x, real_trg_y)
@now_trg_x, @now_trg_y = get_d_x_y(@self_x, @self_y, direction)
while fp_passable?(@now_x, @now_y, direction)
@path.push direction
@now_x = @now_trg_x
@now_y = @now_trg_y
@now_trg_x, @now_trg_y = get_d_x_y(@now_x, @now_y, direction)
end
return @path
end
#--------------------------------------------------------------------------
def find_short_path(self_x, self_y, trg_x, trg_y,
real_self_x, real_self_y, real_trg_x, real_trg_y) #開始搜索路徑
return find_short_path_other(self_x, self_y, trg_x, trg_y,
real_self_x, real_self_y, real_trg_x, real_trg_y) if not
(fp_passable?(trg_x, trg_y + 1, 8) or
fp_passable?(trg_x + 1, trg_y, 4) or
fp_passable?(trg_x - 1, trg_y, 6) or
fp_passable?(trg_x, trg_y - 1, 2)) and @goal_type != 1
#根據屏幕限定搜索麵積..加速
@unable_xa = $game_map.display_x / 128 - 1
@unable_ya = $game_map.display_y / 128 - 1
@unable_xb = $game_map.display_x / 128 + 20
@unable_yb = $game_map.display_y / 128 + 20
@self_x = self_x
@self_y = self_y
@now_x = self_x
@now_y = self_y
@trg_x = trg_x
@trg_y = trg_y
@open_list = []
@close_list = []
#准備搜索
#print @self_x,@self_y
@now_point = new_point(@self_x, @self_y, 5) #令起始點為當前點
@open_list.push @now_point #將當前點加入關閉列表
#開始搜索
begin
loop do
check_trg = check_around_point(@now_point)
if check_trg == true
@path = get_path
break
end
@now_point = get_lowest_f_point
if @now_point == [] or @now_point == nil
@path = []
break
end
end
rescue Hangup
retry
end
return @path
end #結束搜索路徑
#--------------------------------------------------------------------------
def find_player_short_path(trg_x, trg_y,
real_trg_x, real_trg_y) #尋找角色的最短路徑
self_x = $game_player.x
self_y = $game_player.y
real_self_x = $game_player.screen_x
real_self_y = $game_player.screen_y
@goal_type, event = $game_map.check_event_custom_exist(real_trg_x, real_trg_y)
if @goal_type == 1
trg_x = event.x
trg_y = event.y
end
return find_short_path(self_x, self_y, trg_x, trg_y,
real_self_x, real_self_y, real_trg_x, real_trg_y)
end #結束角色的尋找路徑
#--------------------------------------------------------------------------
def get_path #取得最終的路徑
path = []
now_point = @open_list[@open_list.size - 1]
path.push(10 - now_point[2])
last_point = now_point
loop do
now_point = get_father_point(now_point)
break if now_point[2] == 5
path.push(10 - now_point[2])
end
return path.reverse
end #結束取得最終的路徑
#--------------------------------------------------------------------------
def get_lowest_f_point #開始取得最低F值的點
if @open_list == []
return []
end
last_lowest_f_point = @open_list[0]
@open_list.each do |point|
last_lowest_f_point = point if point[5] < last_lowest_f_point[5]
end
return last_lowest_f_point
end #結束取得最低F值點
#--------------------------------------------------------------------------
def check_around_point(point) #開始檢查已知點的八方節點
for d in [2, 4, 6, 8]
x = point[0] + (d == 6 ? 1 : (d == 4 ? -1 : 0))
y = point[1] + (d == 2 ? 1 : (d == 8 ? -1 : 0))
if in_close_list?(x, y) #在關閉列表中
next
elsif in_open_list?(x, y) #在開啟列表中
get_new_g_point = new_point(x, y, 10 - d)
get_last_g_point = get_point(x, y)
if get_new_g_point[3] >= get_last_g_point[3]
next
else
#如果改變父節點是新G值更小則確定改變
@open_list[@open_list.index(get_last_g_point)] = get_new_g_point
end
else
if fp_passable?(point[0], point[1], d, x, y)
# 如果不在開啟列表中、且不在關閉列表中、且通行則添加它到新八周節點
@open_list.push new_point(x, y, 10 - d)
#如果將目標點添加到了開啟列表中就返回true
return true if x == @trg_x and y == @trg_y
return true if @goal_type == 1 and ([1, -1].include?(x - @trg_x) and y - @trg_y == 0) or ([1, -1].include?(y - @trg_y) and x - @trg_x == 0)
end
end
end
#此刻沒有找到目標點並將當前點加入關閉列表並在開啟列表中刪除
@close_list.push point
@open_list.delete(point)
#此刻沒找到目標點並返回false
return false
end #結束計算已知點的八方節點
#--------------------------------------------------------------------------
def in_open_list?(x, y) #開始檢查謀點是否在開啟列表中
@open_list.each do |point|
return true if point[0] == x and point[1] == y
end
return false
end #結束檢查謀點是否在開啟列表中
#--------------------------------------------------------------------------
def in_close_list?(x, y) #開始檢查謀點是否在關閉列表中
@close_list.each do |point|
return true if point[0] == x and point[1] == y
end
return false
end #結束檢查謀點是否在關閉列表中
#--------------------------------------------------------------------------
end
❻ 星際爭霸2的尋路演算法思路是怎樣的
首先地圖整體開始前，會用多層可達矩陣演算法，算出路徑關鍵點
2，創建關鍵節點可達矩陣
3，再每個兵當前位置對關鍵節點進行路徑計算
這樣可以最小化資源佔用就可以完成路徑計算了，高數的離散數學，挺容易解的
❼ 製作一個A*演算法的尋路插件，或者用其他演算法也可以。 但是效率必須高。
1000*1000可以直接廣搜啊。效率應該可以的
❽ 從原點出發，遍歷50個點，再回到原點的最短路徑，求matlab程序
據 Drew 所知最短路經演算法現在重要的應用有計算機網路路由演算法，機器人探路，交通路線導航，人工智慧，游戲設計等等。美國火星探測器核心的尋路演算法就是採用的D*（D Star）演算法。
最短路經計算分靜態最短路計算和動態最短路計算。
靜態路徑最短路徑演算法是外界環境不變，計算最短路徑。主要有Dijkstra演算法，A*（A Star）演算法。
動態路徑最短路是外界環境不斷發生變化，即不能計算預測的情況下計算最短路。如在游戲中敵人或障礙物不斷移動的情況下。典型的有D*演算法。這是Drew程序實現的10000個節點的隨機路網三條互不相交最短路真實路網計算K條路徑示例：節點5696到節點3006，三條最快速路，可以看出路徑基本上走環線或主幹路。黑線為第一條，蘭線為第二條，紅線為第三條。約束條件系數為1.2。共享部分路段。 顯示計算部分完全由Drew自己開發的程序完成。 參見 K條路演算法測試程序
Dijkstra演算法求最短路徑：
Dijkstra演算法是典型最短路演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。
Dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。
Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 演算法和 D* 演算法表述一致，這里均採用OPEN,CLOSE表的方式。
大概過程：
創建兩個表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
1． 訪問路網中里起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。
2． 從OPEN表中找出距起始點最近的點，找出這個點的所有子節點，把這個點放到CLOSE表中。
3． 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值，放子節點到OPEN表中。
4． 重復2，3，步。直到OPEN表為空，或找到目標點。
這是在drew 程序中4000個節點的隨機路網上Dijkstra演算法搜索最短路的演示，黑色圓圈表示經過遍歷計算過的點由圖中可以看到Dijkstra演算法從起始點開始向周圍層層計算擴展，在計算大量節點後，到達目標點。所以速度慢效率低。
提高Dijkstra搜索速度的方法很多，據Drew所知，常用的有數據結構採用Binary heap的方法，和用Dijkstra從起始點和終點同時搜索的方法。
推薦網頁：http://www.cs.ecnu.e.cn/assist/js04/ZJS045/ZJS04505/zjs045050a.htm
簡明扼要介紹Dijkstra演算法，有圖解顯示和源碼下載。
A*（A Star）演算法：啟發式（heuristic）演算法
A*（A-Star)演算法是一種靜態路網中求解最短路最有效的方法。
公式表示為： f(n)=g(n)+h(n),
其中f(n) 是節點n從初始點到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n)是從n到目標節點最佳路徑的估計代價。
保證找到最短路徑（最優解的）條件，關鍵在於估價函數h(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。
如果 估價值>實際值, 搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。
估價值與實際值越接近，估價函數取得就越好。
例如對於幾何路網來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優於Dijstra演算法的毫無無方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索過程：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,->算X的估價值->
While(OPEN!=NULL)
{
從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
else
{
if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於OPEN表的估價值 )
更新OPEN表中的估價值; //取最小路徑的估價值
if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於CLOSE表的估價值 )
更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
if(X not in both)
求X的估價值;
並將X插入OPEN表中;//還沒有排序
}
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
}
❾ 求一個戰棋游戲的六邊形地圖尋路演算法(AS3實現)
樓上的都講完了，我也沒啥好說的，拿走兩分好了
❿ 如何基於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();//倒退/