尋路演算法php

⑴ 誰能介紹一下JPS尋路演算法的思想

這是一個近年來發現的高效尋路演算法。不過有一個限制就是只能在規則的網格地圖上尋路，而且圖上的點或邊不能帶權重，也就是不能有復雜的地形，只支持平坦和障礙兩種地形。

其
思想就是跳過矩形平坦區域的大量對稱路徑，只尋找所謂的跳躍點，作為搜索的節點。這樣做的好處是裁剪了矩形區域內大量的節點，使open
list中的節點數相對較少。要知道，通常啟發式搜索演算法如A*，大量時間耗費在對open
list的操作上。實現得好的A*演算法會使用優先隊列，甚至HOT(heap on top）來對操作進行優化。但當open
list中的節點過多，這些操作還是會變得很昂貴。不過JPS有個缺點是每生成一個節點，也就是要找到一個跳躍點，相比較A*演算法，是比較昂貴的。幸好通
常來說，得到的收益更多些。所以，在適用的情況下，還是推薦使用JPS的。

具體的實現，主要有兩部分。第一部分，從open list中取一個最佳節點，然後從幾個特定方向展開搜索，把每個方向得到的跳躍點，加入open list里。第二部分，就是找到一個跳躍點。

對於起始點，可以向所有方向展開搜索。對於其他節點，要看父節點指向本節點的方向，向所有自然鄰居和被迫鄰居節點方向進行搜索。
例如下圖的例子，對於節點n和父節點p和障礙x，+是n的自然鄰居，也就是說從p到n到+是最佳路徑。如果x不是障礙，從p到n到-不是最佳路徑，因為從p到x到-最近。但是如果x是障礙，那麼從p到n到-就是最佳路徑了，所以這時候稱-為被迫鄰居。
- + +
x n +
p x -
以上是n和p對角的例子。還有種情況是n和p是直線：
x x -
p n +
x x -

搜
尋跳躍點是遞歸進行的。首先判斷一個節點是否是跳躍點。如果這個點有被迫鄰居，那麼這個節點就是跳躍點。第二種情況，如果這個節點是目的地節點那麼也當作
跳躍點。如果不是，那麼就遞歸地沿本來方向繼續搜尋下去。對於對角方向要額外多做兩步，即先對其相應的（左右兩個）直線方向進行搜索，如果找到跳躍點，就
把自身也當作跳躍點返回。如果直線沒找到，那麼就一樣繼續按對角方向遞歸尋找跳躍點，並返回那個跳躍點。

⑵ 從頭理解JPS尋路演算法

本文的思路受到博客： http://blog.sina.com.cn/s/blog_4a5c75d40102wo5l.html
和論文： http://www.doc88.com/p-6099778647749.html 的啟發和借鑒。
JPS(jump point search)演算法實際上是對A 尋路演算法的一個改進，即在擴展搜索節點時，提出了更優化的策略，A 在擴展節點時會把節點所有鄰居都考慮進去，這樣openlist中點的數量會很多，搜索效率較慢。JPS演算法通過尋找跳點的方式，排除了大量不感興趣的點，減少了openlist中搜索的點的數量，速度大大提高。

水平(垂直)搜索：如圖右邊部分描述，點1和4如果經過x到達，還不如從點p(x)到達，所以不用考慮點1,4，同理繼續向右搜索時，點2,5和點3,6，都是類似的情況，直到遇到黑色的障礙，沒有發現感興趣的點，x處水平方向搜索完成，垂直方向搜索類似。如圖左邊部分描述，在點x處向右搜索至點y時，點y有一個強迫鄰居(點7)，因此y是從點x處沿水平方向搜索的一個跳點，需要將y加入到openlist中。水平搜索結束。

對角搜索：斜向搜索時，需要先在當前點的水平和垂直方向搜索一下，看能否找到感興趣的點，如果找到，則將當前點加到openlist，結束斜向搜索，如果找不到，則繼續斜向多走一步，繼續，直到找到感興趣的點或者斜向方向遇到障礙。

一條完整路線的搜索過程：

搜索演算法：

下面兩張對比圖，摘自上面的論文，可以看出，JPS演算法實在優秀。

github鏈接

上圖中紅色塊為節點x，基於前節點為P(x)的情況下的自然鄰居節點。而被迫鄰居則是圖中綠色的方塊（其對稱情況未畫出）。x被迫鄰居包含三層隱藏含義：首先被迫鄰居的位置是基於P(x)、x、阻擋塊的相對關系定的，如第三個圖所示，如果第三個圖中，P(x)的位置在節點6的位置，那麼綠色方塊就不是x的被迫鄰居了。其次，被迫鄰居一點是考察非自然鄰居的節點。最後被迫鄰居一定是P(x)經過x到達才能取得最短路徑的點。

起點S，終點T，黑色塊為阻擋黃色塊為跳點，紅色箭頭是搜索方向，但是沒有找到跳點，綠色箭頭表示找到跳點。橫坐標A-N，縱坐標1-10。

起始位置S，將A10加入openlist里，開始演算法流程。
從openlist里取出代價最小的節點(現在為S)，當前節點沒有方向，所以需要搜索8個方向，只有右上方B9點是跳點。因為根據跳點定義iii，斜向搜索時，需要在兩個分量方向查找跳點，右方是牆壁，略過，上方B8點有強迫鄰居點C7，所以B8是跳點（根據跳點定義ii），所以B9是跳點。將B9加入openlist里。A10處理完後，將其從openlist中移除，加入closelist里。

從openlist中取出B9點，該點的父親是S，所以搜索方向為右斜上，需要在右斜上，右方，上方搜索跳點，只有B8滿足要求，將B8加入openlist。處理完B9點將其移到closelist。

從openlist取出B8點，該點搜索方向為上，B8有被鄰居C7點，在斜上方搜索跳點，可以看出D8是C7的被迫鄰居，所以C7是跳點，B8處繼續向上搜索結束。

從openlist中取出C7點。需要搜索右上，右，上三個方向。水平搜索時發現被迫鄰居D8，加入openlist。右上搜索時發現跳點G3（因其在上方搜索時發現具有被迫鄰居節點的G2），將G3加入openlist。C7點處理結束。

取出G3點（為啥是G3，而不是D8點呢，因為從總代價來說G3比D8更小，總代價=已經走過的距離 + 估值，估值可採用曼哈頓距離或者高斯距離），需要搜索右上，右，上三個方向。向上搜索到跳點G2。

其餘點路徑在圖上標注，就不再重復了。

(1) 若current方向是直線
i. 如果current左後方不可走且左方可走，則沿current左前方和左方尋找跳點。
ii. 如果current當前方向可走，則沿current方向尋找跳點。
iii. 如果current右後方不可走且右方可走，則沿current右前方和右方尋找跳點。
(2) 若current方向是斜線
i. 如果當前方向的水平分量可走，則沿current方向的水平分量方向尋找跳點。
ii. 如果當前方向可走，沿current方向尋找跳點。
iii. 如果當前方向的垂直分量可走，則沿current方向的垂直分量方向尋找跳點。

上述演算法流程是建立在斜向不可穿過阻擋基礎上。

⑶ 游戲開發需要學什麼編程語言

游戲編程也是編程，都是需要敲代碼的。所以基本的語言基本功是不能少的，比如C語言或者C++或者C#至少要精通其中一門。精通到什麼地步呢，基本數據結構和基礎的演算法還有設計模式你得非常熟悉。這樣算是入門了。

接下來你就可以選擇一個游戲引擎了，市面上主流的游戲引擎有兩種一個Unity3D一個虛幻四。但是這兩款引擎的腳本語言並不一樣，Unity是C#虛幻四是C++所以在學習之前要想好使用引擎開發什麼類型的游戲。

主要學的內容如下：

1.游戲程序設計：C++程序設計入門；基本數據類型和輸入輸出；流程式控制制語句；數組、指針和引用、函數；程序結構和書寫規；范結構體和聯合體、類；繼承與多態；異常處理與程序調試。

2.演算法與數據結構：演算法分析；數據結構；基本演算法；STL的概念與使用；靜態庫與動態庫；XML庫的使用。

3.Win32程序設計：Windows程序入門；Windows消息；GDI繪圖游戲工具與MFC；網路編程基礎。

4.游戲數學和智能應用：游戲中的坐標系；矢量、矩陣；幾何碰撞；物理模擬；人工智慧與尋路演算法。

5.2D游戲技術與應用：2D游戲技術概論；游戲地圖系統；GUI系統；戰斗系統設計；任務系統；優秀的聲音引擎BASS；Cocos2D-X引擎；Box2D物理引擎。

互聯網行業目前還是最熱門的行業之一，學習IT技能之後足夠優秀是有機會進入騰訊、阿里、網易等互聯網大廠高薪就業的，發展前景非常好，普通人也可以學習。

想要系統學習，你可以考察對比一下開設有相關專業的熱門學校，好的學校擁有根據當下企業需求自主研發課程的能力，能夠在校期間取得大專或本科學歷，中博軟體學院、南京課工場、南京北大青鳥等開設相關專業的學校都是不錯的，建議實地考察對比一下。

祝你學有所成，望採納。

⑷ 最短路徑演算法

Dijkstra演算法，A*演算法和D*演算法

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表為空，或找到目標點。

提高Dijkstra搜索速度的方法很多，常用的有數據結構採用Binary heap的方法，和用Dijkstra從起始點和終點同時搜索的方法。

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*演算法和Dijistra演算法的區別在於有無估價值，Dijistra演算法相當於A*演算法中估價值為0的情況。

動態路網，最短路演算法 D*A* 在靜態路網中非常有效（very efficient for static worlds），但不適於在動態路網，環境如權重等不斷變化的動態環境下。

D*是動態A*（D-Star,Dynamic A*） 卡內及梅隆機器人中心的Stentz在1994和1995年兩篇文章提出，主要用於機器人探路。是火星探測器採用的尋路演算法。

主要方法：
1.先用Dijstra演算法從目標節點G向起始節點搜索。儲存路網中目標點到各個節點的最短路和該位置到目標點的實際值h,k（k為所有變化h之中最小的值,當前為k=h。每個節點包含上一節點到目標點的最短路信息1(2),2(5),5(4)，4（7）。則1到4的最短路為1-2-5-4。
原OPEN和CLOSE中節點信息保存。
2.機器人沿最短路開始移動，在移動的下一節點沒有變化時，無需計算，利用上一步Dijstra計算出的最短路信息從出發點向後追述即可，當在Y點探測到下一節點X狀態發生改變，如堵塞。機器人首先調整自己在當前位置Y到目標點G的實際值h(Y)，h(Y)=X到Y的新權值c(X,Y)+X的原實際值h(X).X為下一節點(到目標點方向Y->X->G），Y是當前點。k值取h值變化前後的最小。
3.用A*或其它演算法計算，這里假設用A*演算法,遍歷Y的子節點，點放入CLOSE,調整Y的子節點a的h值，h(a)=h(Y)+Y到子節點a的權重C(Y,a),比較a點是否存在於OPEN和CLOSE中，方法如下：
while()
{
從OPEN表中取k值最小的節點Y;
遍歷Y的子節點a,計算a的h值 h(a)=h(Y)+Y到子節點a的權重C(Y,a)
{
if(a in OPEN) 比較兩個a的h值
if( a的h值小於OPEN表a的h值 )
{ 更新OPEN表中a的h值;k值取最小的h值
有未受影響的最短路經存在
break;
}
if(a in CLOSE) 比較兩個a的h值 //注意是同一個節點的兩個不同路徑的估價值
if( a的h值小於CLOSE表的h值 )
{
更新CLOSE表中a的h值; k值取最小的h值;將a節點放入OPEN表
有未受影響的最短路經存在
break;
}
if(a not in both)
將a插入OPEN表中; //還沒有排序
}
放Y到CLOSE表；
OPEN表比較k值大小進行排序；
}
機器人利用第一步Dijstra計算出的最短路信息從a點到目標點的最短路經進行。

D*演算法在動態環境中尋路非常有效，向目標點移動中，只檢查最短路徑上下一節點或臨近節點的變化情況，如機器人尋路等情況。對於距離遠的最短路徑上發生的變化，則感覺不太適用。

⑸ PHP程序員想轉入游戲開發，需要學習哪些知識

游戲開發根據平台有PC游戲開發、移動設備游戲開發（如手機游戲，PSP）、網頁游戲開發等。一般還可以分為2D游戲開發和3D游戲開發。在PC上開發大型的3D游戲一般用C++，在手機上一般是小型的2D游戲，用JAVA,J2ME，網頁不怎麼清楚，一般用flash吧。做游戲的話要掌握一些數學知識（如三角函數）、物理知識（碰撞模擬等），要懂得進行圖形編程，向高級發展還要懂人工智慧（如有限狀態機，A*尋路演算法），如果做3D游戲的話還要懂一些計算機圖形學演算法（如空間變換，光照計算，插值演算法等），根據樓主現有的知識建議樓主做網頁游戲吧，用PHP+flex。樓主既然有興趣那就去做，下定決心，本人以前是做化工的，因為興趣自學轉了做程序員。只要相信自己就能成功。

⑹ 游戲中的常用的尋路演算法有哪些

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列表
?

⑺ 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*演算法

⑻ 游戲開發都會學什麼

游戲開發需要學習C語言系列、UE4這些常用游戲引擎，門檻很高。但游戲開發行業的整體收入水平，確實算是高薪了，學成後回報較高。

游戲開發所涉及的技能知識面較多，且難以把握學習難度，不建議自學。小白建議從UI做起，因為UI開發中簡單重復而瑣碎的工作相對比較多。

主要學的內容如下：

1.游戲程序設計：C++程序設計入門；基本數據類型和輸入輸出；流程式控制制語句；數組、指針和引用、函數；程序結構和書寫規；范結構體和聯合體、類；繼承與多態；異常處理與程序調試。

2.演算法與數據結構：演算法分析；數據結構；基本演算法；STL的概念與使用；靜態庫與動態庫；XML庫的使用。

3.Win32程序設計：Windows程序入門；Windows消息；GDI繪圖游戲工具與MFC；網路編程基礎。

4.游戲數學和智能應用：游戲中的坐標系；矢量、矩陣；幾何碰撞；物理模擬；人工智慧與尋路演算法。

5.2D游戲技術與應用：2D游戲技術概論；游戲地圖系統；GUI系統；戰斗系統設計；任務系統；優秀的聲音引擎BASS；Cocos2D-X引擎；Box2D物理引擎。

互聯網行業目前還是最熱門的行業之一，學習IT技能之後足夠優秀是有機會進入騰訊、阿里、網易等互聯網大廠高薪就業的，發展前景非常好，普通人也可以學習。

想要系統學習，你可以考察對比一下開設有相關專業的熱門學校，好的學校擁有根據當下企業需求自主研發課程的能力，能夠在校期間取得大專或本科學歷，中博軟體學院、南京課工場、南京北大青鳥等開設相關專業的學校都是不錯的，建議實地考察對比一下。

祝你學有所成，望採納。

⑼ 夢幻西遊自動尋路的尋路演算法怎麼算

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)的信息，即減小約束條件。但演算法的准確性就差了，這里就有一個平衡的問題。
}