① A*演算法——啟發式路徑搜索
A*是一種路徑搜索演算法，比如為游戲中的角色規劃行動路徑。
A* 演算法的輸入是， 起點（初始狀態） 和 終點（目標狀態） ，以及兩點間 所有可能的路徑 ，以及涉及到的 中間節點（中間狀態） ，每兩個節點間的路徑的 代價 。
一般還需要某種 啟發函數 ，即從任意節點到終點的近似代價，啟發函數能夠非常快速的估算出皮好閉該代價值。
輸出是從 起點到終點的最優路徑 ，即代價最小。同時，好的啟發函數將使得這一搜索運算盡可能高效，即搜索盡量少的節點/可能的路徑。
f(n)=g(n)+h(n)
f(n) 是從初始狀態經由狀態n到目標狀態的代價估計
g(n) 是在狀態空間中從初始狀態到狀態n的實際代價
h(n) 是從狀態n到目標狀態的最佳路徑的估計代價
A*演算法是從起點開始，檢查所有可能的擴展點（它的相鄰點），對每個點計算g+h得到f，在所有可能的擴展點中，選擇f最小的那個點進行擴展，即計算該點的所有可能擴展點的f值，並將這些新的擴展點添加到擴展點列表（open list）。當然，忽略已經在列表中的點、已經考察燃裂過的點。
不斷從open list中選擇f值最小的點進行擴展，直到到達目標點（成功找到最優路徑），或者節點用完，路徑搜索失敗。
演算法步驟：
參考
A* 演算法步驟的詳細說明請參考 A*尋路演算法 ，它包含圖文案例清楚的解釋了A*演算法計算步驟的一些細節，本文不再詳細展開。
看一下上面參考文檔中的案例圖，最終搜索完成時，藍色邊框是close list中的節點，綠色邊框是open list中的節點，每個方格中三個數字，左上是f（=g+h），左下是g（已經過路徑襪旦的代價），右下是h（估計未經過路徑的代價）。藍色方格始終沿著f值最小的方向搜索前進，避免了對一些不好的路徑（f值較大）的搜索。（圖片來自 A*尋路演算法 ）
現在我們可以理解，A*演算法中啟發函數是最重要的，它有幾種情況：
1) h(n) = 0
一種極端情況，如果h(n)是0，則只有g(n)起作用，此時A*演變成Dijkstra演算法，這保證能找到最短路徑。但效率不高，因為得不到啟發。
2) h(n) < 真實代價
如果h(n)經常都比從n移動到目標的實際代價小（或者相等），則A*保證能找到一條最短路徑。h(n)越小，A*擴展的結點越多，運行就得越慢。越接近Dijkstra演算法。
3) h(n) = 真實代價
如果h(n)精確地等於從n移動到目標的代價，則A*將會僅僅尋找最佳路徑而不擴展別的任何結點，這會運行得非常快。盡管這不可能在所有情況下發生，你仍可以在一些特殊情況下讓它們精確地相等（譯者：指讓h(n)精確地等於實際值）。只要提供完美的信息，A*會運行得很完美，認識這一點很好。
4) h(n) > 真實代價
如果h(n)有時比從n移動到目標的實際代價高，則A*不能保證找到一條最短路徑，但它運行得更快。
5) h(n) >> 真實代價
另一種極端情況，如果h(n)比g(n)大很多，則只有h(n)起作用，A*演變成BFS演算法。
關於啟發函數h、Dijkstra演算法、BFS（最佳優先搜索）演算法、路徑規劃情況下啟發函數的選擇、演算法實現時List的數據結構、演算法變種等等更多問題，請參考： A*演算法
② 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 （我們已經搜索了所有的結點賣鬧腔，但是仍然沒有找到一條路徑）
③ 關於VB中A*尋路演算法的提問
定理：穿越於一組互不相交的多邊形障礙物S之納租間、從Pstart通往Pgoal的任何一條最短路徑，都是一條多邊形路徑，其中所有的內部頂點都是S的頂點。
推廣：所有最短路徑問題。
結論：只有普遍適用的演算法，沒有普遍適用的代碼。
補充：只有問題實例化才能寫出適用代碼。
你所遇到的可不只是尋路問題，二維尋路相對簡洞升兆單點，我猜測你的問題產生在「碰撞」上，建議你多學習一下「計算幾何學」、「計算機圖形學」、「機器人運動學」等，當然，編程的基本功也很重要。其實，帶有笑鍵運動的游戲編程是很復雜的。你也可以將你的程序包發給我等我有時間幫你看看。
④ 如何基於Cocos2d-x v3.x實現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)
{
// Figure out the shortest path to the target, and start following it!
}
創建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<ShortestPathStep*> _spOpenSteps;
cocos2d::Vector<ShortestPathStep*> _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<CatSprite::ShortestPathStep *> &steps, const CatSprite::ShortestPathStep *step)
{
for (ssize_t i = 0; i < steps.size(); ++i)
{
if (steps.at(i)->isEqual(step))
{
return i;
}
}
return -1;
}
⑤ 如何用Swift實現A*尋路演算法
A*演算法
?? 啟發式搜索
– 在搜索中涉及到三個函數
?? g(n) = 從初始結點到結點n的耗費
?? h(n) = 從結點n到目的結點的耗費評估值，啟發函數
?? f(n)=g(n)+h(n) 從起始點到目的點的最佳評估值
– 每次都選擇f(n)值最小的結點作為下一個結點，
直到最終達到目的結點
– A*演算法的成功很大程度依賴尺穗於h(n)函數的構建
?? 在各種游戲中廣泛應用 Open列表和Closed列表
– Open列表
?? 包含我們還沒有處理到的結點
?? 我們最開始將起始結點放入到Open列表中
–陵歷卜 Closed列表
?? 包含我們已經處理過的結點
?? 在演算法啟動時，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*尋路演算法 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的大小，從最小路徑的節點向下進行。
啟發式搜索其實有很多的演算法，比如：局部擇優搜索法、最好優先搜索法等等。當然A*也是。這些演算法都使用了啟發函數，但在具體的選取最佳搜索節點時的策略不同。象局部擇優搜索法，就是在搜索的過程中選取「最佳節點」後舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由於舍棄了其他的節點，可能也把最好的
節點都舍棄了，因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。最好優先就聰明多了，他在搜索時，便沒有舍棄節點（除非該節點是死節點），在每一步的估價
中都把當前的節點和以前的節點的估價值比較得到一個「最佳的節點」。這樣可以有效的防止「最佳節點」的丟失。那麼A*演算法又是一種什麼樣的演算法呢？其實A*演算法也是一種最
好優先的演算法。只不過要加上一些約束條件罷了。由於在一些問題求解時，我們希望能夠求解出狀態空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！
我們先下個定義，如果一個估價函數可以找出最短的路徑，我們稱之為可採納性。A*演算法是一個可採納的最好優先演算法。A*演算法的估價函數可表示為：
f'(n) = g'(n) + h'(n)
這里，f'(n)是估價函數，g'(n)是起點到終清源點的最短路徑值，h'(n)是n到目標的最斷路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以我們用前面的估價函數f(n)做
近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這一點特別的重要）。可以證明應用這樣的估答納態價
函數是可以找到最短路徑的，也就是可採納的。我們說應用這種估價函數的最好優先演算法就是A*演算法。哈。你懂了嗎？肯定沒懂。接著看。
舉一個例子，其實廣度優先演算法就是A*演算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小於h'(n)，所以由前述可知廣度優先演算法是一種可採納的。實際也是
。當然它是一種最臭的A*演算法。
再說一個問題，就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函
數越好或說這個演算法越好。這就是為什麼廣度優先演算法的那麼臭的原因了，誰叫它的h(n)=0，一點啟發信息都沒有。但在游戲開發中由於實時性的問題，h(n)的信息越多，它的計
算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但演算法的准確性就差了，這里就有一個平衡的問題。
}