區域搜索演算法a星

『壹』 A星搜索演算法

A星演算法是定義了一個函數f，公式為：
f = g + h
其中g函數代表目前為止從出發地到達該節點的成本，h函數是預估的當前節點到到目的地的成本，即
g(path) = path cost
h(path) = h(s) = estimated distance to goal
朝著使函數f具有最小值的路徑拓展,該演算法可以找到消耗最小消耗的路徑

注意A星演算法並不是總能找到最優解，能否找到最優解依賴於h函數，條件是

『貳』 搜索演算法中,A演算法A*演算法的區別（急）

a*演算法：a*（a-star)演算法是一種靜態路網中求解最短路徑最有效的直接搜索方法。估價值與實際值越接近，估價函數取得就越好
a*
（a-star)演算法是一種靜態路網中求解最短路最有效的直接搜索方法。
注意是最有效的直接搜索演算法。之後涌現了很多預處理演算法（alt，ch，hl等等），在線查詢效率是a*演算法的數千甚至上萬倍。
公式表示為：
f(n)=g(n)+h(n),
其中
f(n)
是從初始點經由節點n到目標點的估價函數，
g(n)
是在狀態空間中從初始節點到n節點的實際代價，
h(n)
是從n到目標節點最佳路徑的估計代價。
保證找到最短路徑（最優解的）條件，關鍵在於估價函數f(n)的選取：
估價值h(n)<=
n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。並且如果h(n)=d(n)，即距離估計h(n)等於最短距離，那麼搜索將嚴格沿著最短路徑進行，
此時的搜索效率是最高的。
如果
估價值>實際值,搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。

『叄』 A星尋路演算法和Unity自帶的尋路相比有什麼優勢

在理解Navigation的時候，首先要明確兩個知識點：

AStar：AStar是路點尋路演算法中的一種，同時AStar不屬於貪婪演算法，貪婪演算法適合動態規劃，尋找局部最優解，不保證最優解。AStar是靜態網格中求解最短路最有效的方法。也是耗時的演算法，不宜尋路頻繁的場合。一般來說適合需求精確的場合。

性能和內存佔用率都還行，和啟發式的搜索一樣，能夠根據改變網格密度、網格耗散來進行調整精確度。

A Star一般使用場景：

• 策略游戲的策略搜索

• 方塊格子游戲中的格子尋路

Navigation：網格尋路演算法，嚴格意義上它屬於」拐角點演算法」，效率是比較高的，但是不保證最優解演算法。Navigation相對來說消耗內存更大，性能的話還不錯。

Navigation一般使用場景：

• 游戲場景的怪物尋路

• 動態規避障礙

它們二者事件的實現方式和原理都不同。

AStar的話，

『肆』 深度優先搜索和廣度優先搜索、A星演算法三種演算法的區別和聯系

1、何謂啟發式搜索演算法
在說它之前先提提狀態空間搜索.狀態空間搜索,如果按專業點的說法就是將問題求解過程表現為從初始狀態到目標狀態尋找這個路徑的過程.通俗點說,就是 在解一個問題時,找到一條解題的過程可以從求解的開始到問題的結果（好象並不通俗哦）.由於求解問題的過程中分枝有很多,定性,不完備性造成的,使得求解的路徑很多這就構成了一個圖,我們說這個圖就是狀態空間.問題的求解實際上就是在這個圖中找到一條路徑可以從開始到結果.這個尋找的過程就是狀態空間搜索.
常用的狀態空間搜索有深度優先和廣度優先.廣度優先是從初始狀態一層一層向下找,直到找到目標為止.深度優先是按照一定的順序前查找完一個分支,再查找另一個分支,以至找到目標為止.這兩種演算法在數據結構書中都有描述,可以參看這些書得到更詳細的解釋.
前面說的廣度和深度優先搜索有一個很大的缺陷就是他們都是在一個給定的狀態空間中窮舉.這在狀態空間不大的情況下是很合適的演算法,可是當狀態空間十分大,且不預測的情況下就不可取了.他的效率實在太低,甚至不可完成.在這里就要用到啟發式搜索了.
啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估,得到最好的位置,再從這個位置進行搜索直到目標.這樣可以省略大量無畏的搜索路徑,提 到了效率.在啟發式搜索中,對位置的估價是十分重要的.採用了不同的估價可以有不同的效果.我們先看看估價是如何表示的.
啟發中的估價是用估價函數表示的,如：
f(n) = g(n) + h(n)
其中f(n) 是節點n的估價函數,g(n)實在狀態空間中從初始節點到n節點的實際代價,h(n)是從n到目標節點最佳路徑的估計代價.在這里主要是h(n)體現了搜 索的啟發信息,因為g(n)是已知的.如果說詳細點,g(n)代表了搜索的廣度的優先趨勢.但是當h(n) >> g(n)時,可以省略g(n),而提高效率.這些就深了,不懂也不影響啦!我們繼續看看何謂A*演算法.
2、初識A*演算法
啟發式搜索其實有很多的演算法,比如：局部擇優搜索法、最好優先搜索法等等.當然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)

『伍』 大數據最常用的演算法有哪些

奧地利符號計算研究所(Research Institute for Symbolic Computation，簡稱RISC)的Christoph Koutschan博士在自己的頁面上發布了一篇文章，提到他做了一個調查，參與者大多數是計算機科學家，他請這些科學家投票選出最重要的演算法，以下是這次調查的結果，按照英文名稱字母順序排序。

大數據等最核心的關鍵技術：32個演算法

1、A* 搜索演算法——圖形搜索演算法，從給定起點到給定終點計算出路徑。其中使用了一種啟發式的估算，為每個節點估算通過該節點的最佳路徑，並以之為各個地點排定次序。演算法以得到的次序訪問這些節點。因此，A*搜索演算法是最佳優先搜索的範例。

2、集束搜索(又名定向搜索，Beam Search)——最佳優先搜索演算法的優化。使用啟發式函數評估它檢查的每個節點的能力。不過，集束搜索只能在每個深度中發現最前面的m個最符合條件的節點，m是固定數字——集束的寬度。

3、二分查找(Binary Search)——在線性數組中找特定值的演算法，每個步驟去掉一半不符合要求的數據。

4、分支界定演算法(Branch and Bound)——在多種最優化問題中尋找特定最優化解決方案的演算法，特別是針對離散、組合的最優化。

5、Buchberger演算法——一種數學演算法，可將其視為針對單變數最大公約數求解的歐幾里得演算法和線性系統中高斯消元法的泛化。

6、數據壓縮——採取特定編碼方案，使用更少的位元組數(或是其他信息承載單元)對信息編碼的過程，又叫來源編碼。

7、Diffie-Hellman密鑰交換演算法——一種加密協議，允許雙方在事先不了解對方的情況下，在不安全的通信信道中，共同建立共享密鑰。該密鑰以後可與一個對稱密碼一起，加密後續通訊。

8、Dijkstra演算法——針對沒有負值權重邊的有向圖，計算其中的單一起點最短演算法。

9、離散微分演算法(Discrete differentiation)。

10、動態規劃演算法(Dynamic Programming)——展示互相覆蓋的子問題和最優子架構演算法

11、歐幾里得演算法(Euclidean algorithm)——計算兩個整數的最大公約數。最古老的演算法之一，出現在公元前300前歐幾里得的《幾何原本》。

12、期望-最大演算法(Expectation-maximization algorithm，又名EM-Training)——在統計計算中，期望-最大演算法在概率模型中尋找可能性最大的參數估算值，其中模型依賴於未發現的潛在變數。EM在兩個步驟中交替計算，第一步是計算期望，利用對隱藏變數的現有估計值，計算其最大可能估計值;第二步是最大化，最大化在第一步上求得的最大可能值來計算參數的值。

13、快速傅里葉變換(Fast Fourier transform，FFT)——計算離散的傅里葉變換(DFT)及其反轉。該演算法應用范圍很廣，從數字信號處理到解決偏微分方程，到快速計算大整數乘積。

14、梯度下降(Gradient descent)——一種數學上的最優化演算法。

15、哈希演算法(Hashing)。

16、堆排序(Heaps)。

17、Karatsuba乘法——需要完成上千位整數的乘法的系統中使用，比如計算機代數系統和大數程序庫，如果使用長乘法，速度太慢。該演算法發現於1962年。

18、LLL演算法(Lenstra-Lenstra-Lovasz lattice rection)——以格規約(lattice)基數為輸入，輸出短正交向量基數。LLL演算法在以下公共密鑰加密方法中有大量使用：背包加密系統(knapsack)、有特定設置的RSA加密等等。

19、最大流量演算法(Maximum flow)——該演算法試圖從一個流量網路中找到最大的流。它優勢被定義為找到這樣一個流的值。最大流問題可以看作更復雜的網路流問題的特定情況。最大流與網路中的界面有關，這就是最大流-最小截定理(Max-flow min-cut theorem)。Ford-Fulkerson 能找到一個流網路中的最大流。

20、合並排序(Merge Sort)。

21、牛頓法(Newton』s method)——求非線性方程(組)零點的一種重要的迭代法。

22、Q-learning學習演算法——這是一種通過學習動作值函數(action-value function)完成的強化學習演算法，函數採取在給定狀態的給定動作，並計算出期望的效用價值，在此後遵循固定的策略。Q-leanring的優勢是，在不需要環境模型的情況下，可以對比可採納行動的期望效用。

23、兩次篩法(Quadratic Sieve)——現代整數因子分解演算法，在實踐中，是目前已知第二快的此類演算法(僅次於數域篩法Number Field Sieve)。對於110位以下的十位整數，它仍是最快的，而且都認為它比數域篩法更簡單。

24、RANSAC——是「RANdom SAmple Consensus」的縮寫。該演算法根據一系列觀察得到的數據，數據中包含異常值，估算一個數學模型的參數值。其基本假設是：數據包含非異化值，也就是能夠通過某些模型參數解釋的值，異化值就是那些不符合模型的數據點。

25、RSA——公鑰加密演算法。首個適用於以簽名作為加密的演算法。RSA在電商行業中仍大規模使用，大家也相信它有足夠安全長度的公鑰。

26、Sch?nhage-Strassen演算法——在數學中，Sch?nhage-Strassen演算法是用來完成大整數的乘法的快速漸近演算法。其演算法復雜度為：O(N log(N) log(log(N)))，該演算法使用了傅里葉變換。

27、單純型演算法(Simplex Algorithm)——在數學的優化理論中，單純型演算法是常用的技術，用來找到線性規劃問題的數值解。線性規劃問題包括在一組實變數上的一系列線性不等式組，以及一個等待最大化(或最小化)的固定線性函數。

28、奇異值分解(Singular value decomposition，簡稱SVD)——在線性代數中，SVD是重要的實數或復數矩陣的分解方法，在信號處理和統計中有多種應用，比如計算矩陣的偽逆矩陣(以求解最小二乘法問題)、解決超定線性系統(overdetermined linear systems)、矩陣逼近、數值天氣預報等等。

29、求解線性方程組(Solving a system of linear equations)——線性方程組是數學中最古老的問題，它們有很多應用，比如在數字信號處理、線性規劃中的估算和預測、數值分析中的非線性問題逼近等等。求解線性方程組，可以使用高斯—約當消去法(Gauss-Jordan elimination)，或是柯列斯基分解( Cholesky decomposition)。

30、Strukturtensor演算法——應用於模式識別領域，為所有像素找出一種計算方法，看看該像素是否處於同質區域( homogenous region)，看看它是否屬於邊緣，還是是一個頂點。

31、合並查找演算法(Union-find)——給定一組元素，該演算法常常用來把這些元素分為多個分離的、彼此不重合的組。不相交集(disjoint-set)的數據結構可以跟蹤這樣的切分方法。合並查找演算法可以在此種數據結構上完成兩個有用的操作：

查找：判斷某特定元素屬於哪個組。

合並：聯合或合並兩個組為一個組。

32、維特比演算法(Viterbi algorithm)——尋找隱藏狀態最有可能序列的動態規劃演算法，這種序列被稱為維特比路徑，其結果是一系列可以觀察到的事件，特別是在隱藏的Markov模型中。

以上就是Christoph博士對於最重要的演算法的調查結果。你們熟悉哪些演算法?又有哪些演算法是你們經常使用的?

『陸』 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即可。這兩種方法都會給出可靠地行動策略 。

『柒』 如何基於Cocos2d-x v3.x實現A星尋路演算法

實現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;
}

『捌』 什麼是A搜索演算法

A*搜索演算法，俗稱A星演算法，作為啟發式搜索演算法中的一種，這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的NPC的移動計算，或線上游戲的BOT的移動計算上。該演算法像Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。

『玖』 A*演算法介紹

姓名：車文揚 學號：16020199006

【嵌牛導讀】：A*演算法的逐步詳解

【嵌牛鼻子】：啟發式演算法

【嵌牛提問】：A*演算法的原理是什麼？

【嵌牛正文】：

A*演算法

路徑規劃是指的是機器人的最優路徑規劃問題，即依據某個或某些優化准則（如工作代價最小、行走路徑最短、行走時間最短等），在工作空間中找到一個從起始狀態到目標狀態能避開障礙物的最優路徑。機器人的路徑規劃應用場景極豐富，最常見如游戲中NPC及控制角色的位置移動，網路地圖等導航問題，小到家庭掃地機器人、無人機大到各公司正爭相開拓的無人駕駛汽車等。

目前路徑規劃演算法分為：

A*演算法原理：

在計算機科學中，A*演算法作為Dijkstra演算法的擴展，因其高效性而被廣泛應用於尋路及圖的遍歷，如星際爭霸等游戲中就大量使用。在理解演算法前，我們需要知道幾個概念：

搜索區域（The Search Area）：圖中的搜索區域被劃分為了簡單的二維數組，數組每個元素對應一個小方格，當然我們也可以將區域等分成是五角星，矩形等，通常將一個單位的中心點稱之為搜索區域節點（Node）。

開放列表(Open List)：我們將路徑規劃過程中待檢測的節點存放於Open List中，而已檢測過的格子則存放於Close List中。

父節點（parent）：在路徑規劃中用於回溯的節點，開發時可考慮為雙向鏈表結構中的父結點指針。

路徑排序（Path Sorting）：具體往哪個節點移動由以下公式確定：F(n) = G + H 。G代表的是從初始位置A沿著已生成的路徑到指定待檢測格子的移動開銷。H指定待測格子到目標節點B的估計移動開銷。

啟發函數（Heuristics Function）：H為啟發函數，也被認為是一種試探，由於在找到唯一路徑前，我們不確定在前面會出現什麼障礙物，因此用了一種計算H的演算法，具體根據實際場景決定。在我們簡化的模型中，H採用的是傳統的曼哈頓距離（Manhattan Distance），也就是橫縱向走的距離之和。

如下圖所示，綠色方塊為機器人起始位置A，紅色方塊為目標位置B，藍色為障礙物。

我們把要搜尋的區域劃分成了正方形的格子。這是尋路的第一步，簡化搜索區域。這個特殊的方法把我們的搜索區域簡化為了2 維數組。數組的每一項代表一個格子，它的狀態就是可走(walkalbe)或不可走(unwalkable) 。現用A*演算法尋找出一條自A到B的最短路徑，每個方格的邊長為10，即垂直水平方向移動開銷為10。因此沿對角移動開銷約等於14。具體步驟如下：

從起點 A 開始，把它加入到一個由方格組成的open list(開放列表) 中，這個open list像是一個購物清單。Open list里的格子是可能會是沿途經過的，也有可能不經過。因此可以將其看成一個待檢查的列表。查看與A相鄰的8個方格 ，把其中可走的 (walkable) 或可到達的(reachable) 方格加入到open list中。並把起點 A 設置為這些方格的父節點 (parent node) 。然後把 A 從open list中移除，加入到close list(封閉列表) 中，close list中的每個方格都是不需要再關注的。

如下圖所示，深綠色的方格為起點A，它的外框是亮藍色，表示該方格被加入到了close list 。與它相鄰的黑色方格是需要被檢查的，他們的外框是亮綠色。每個黑方格都有一個灰色的指針指向他們的父節點A。

下一步，我們需要從open list中選一個與起點A相鄰的方格。但是到底選擇哪個方格好呢？選F值最小的那個。我們看看下圖中的一些方格。在標有字母的方格中G = 10 。這是因為水平方向從起點到那裡只有一個方格的距離。與起點直接相鄰的上方，下方，左方的方格的G 值都是10 ，對角線的方格G 值都是14 。H值通過估算起點到終點( 紅色方格) 的Manhattan 距離得到，僅作橫向和縱向移動，並且忽略沿途的障礙。使用這種方式，起點右邊的方格到終點有3 個方格的距離，因此H = 30 。這個方格上方的方格到終點有4 個方格的距離( 注意只計算橫向和縱向距離) ，因此H = 40 。

比較open list中節點的F值後，發現起點A右側節點的F=40，值最小。選作當前處理節點，並將這個點從Open List刪除，移到Close List中。

對這個節點周圍的8個格子進行判斷，若是不可通過（比如牆，水，或是其他非法地形）或已經在Close List中，則忽略。否則執行以下步驟：

若當前處理節點的相鄰格子已經在Open List中，則檢查這條路徑是否更優，即計算經由當前處理節點到達那個方格是否具有更小的 G值。如果沒有，不做任何操作。相反，如果G值更小，則把那個方格的父節點設為當前處理節點 ( 我們選中的方格 ) ，然後重新計算那個方格的 F 值和 G 值。

若當前處理節點的相鄰格子不在Open List中，那麼把它加入，並將它的父節點設置為該節點。

按照上述規則我們繼續搜索，選擇起點右邊的方格作為當前處理節點。它的外框用藍線打亮，被放入了close list 中。然後我們檢查與它相鄰的方格。它右側的3個方格是牆壁，我們忽略。它左邊的方格是起點，在close list 中，我們也忽略。其他4個相鄰的方格均在open list 中，我們需要檢查經由當前節點到達那裡的路徑是否更好。我們看看上面的方格，它現在的G值為14 ，如果經由當前方格到達那裡，G值將會為20( 其中10為從起點到達當前方格的G值，此外還要加上從當前方格縱向移動到上面方格的G值10) ，因此這不是最優的路徑。看圖就會明白直接從起點沿對角線移動到那個方格比先橫向移動再縱向移動要好。

當把4個已經在open list 中的相鄰方格都檢查後，沒有發現經由當前節點的更好路徑，因此不做任何改變。接下來要選擇下一個待處理的節點。因此再次遍歷open list ，現在open list中只有7 個方格了，我們需要選擇F值最小的那個。這次有兩個方格的F值都是54，選哪個呢？沒什麼關系。從速度上考慮，選擇最後加入open list 的方格更快。因此選擇起點右下方的方格，如下圖所示。

接下來把起點右下角F值為54的方格作為當前處理節點，檢查其相鄰的方格。我們發現它右邊是牆（牆下面的一格也忽略掉，假定牆角不能直接穿越)，忽略之。這樣還剩下 5 個相鄰的方格。當前方格下面的 2 個方格還沒有加入 open list ，所以把它們加入，同時把當前方格設為他們的父親。在剩下的 3 個方格中，有 2 個已經在 close list 中 ( 一個是起點，一個是當前方格上面的方格，外框被加亮的 ) ，我們忽略它們。最後一個方格，也就是當前方格左邊的方格，檢查經由當前方格到達那裡是否具有更小的 G 值。沒有，因此我們准備從 open list 中選擇下一個待處理的方格。

不斷重復這個過程，直到把終點也加入到了open list 中，此時如下圖所示。注意在起點下方2 格處的方格的父親已經與前面不同了。之前它的G值是28並且指向它右上方的方格。現在它的G 值為20 ，並且指向它正上方的方格。這是由於在尋路過程中的某處使用新路徑時G值更小，因此父節點被重新設置，G和F值被重新計算。

那麼我們怎樣得到實際路徑呢？很簡單，如下圖所示，從終點開始，沿著箭頭向父節點移動，直至回到起點，這就是你的路徑。

A*演算法總結：

1. 把起點加入 open list 。

2. 重復如下過程：

a. 遍歷open list ，查找F值最小的節點，把它作為當前要處理的節點，然後移到close list中

b. 對當前方格的 8 個相鄰方格一一進行檢查，如果它是不可抵達的或者它在close list中，忽略它。否則，做如下操作：

□  如果它不在open list中，把它加入open list，並且把當前方格設置為它的父親

□  如果它已經在open list中，檢查這條路徑 ( 即經由當前方格到達它那裡 ) 是否更近。如果更近，把它的父親設置為當前方格，並重新計算它的G和F值。如果你的open list是按F值排序的話，改變後你可能需要重新排序。

c. 遇到下面情況停止搜索：

□  把終點加入到了 open list 中，此時路徑已經找到了，或者

□  查找終點失敗，並且open list 是空的，此時沒有路徑。

3. 從終點開始，每個方格沿著父節點移動直至起點，形成路徑。

『拾』 如何實現A星尋路演算法 Cocos2d-x 3.0 beta2

操作步驟如下：一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中點 調試------開始執行不調試