在看下面這篇文章之前，先介紹幾個理論知識，有助于了解A*算法。
啟發式搜尋：啟發式搜尋就是在狀态空間中的搜尋對每一個搜尋的位置進行評估，得到最好的位置，再從這個位置進行搜尋直到目标。這樣可以省略大量無畏的搜尋路徑，提到了效率。在啟發式搜尋中，對位置的估價是十分重要的。采用了不同的估價可以有不同的效果。
估價函數：從目前節點移動到目标節點的預估費用；這個估計就是啟發式的。在尋路問題和迷宮問題中，我們通常用曼哈頓（manhattan）估價函數（下文有介紹）預估費用。
A*算法與BFS：可以這樣說，BFS是A*算法的一個特例。對于一個BFS算法，從目前節點擴充出來的每一個節點（如果沒有被通路過的話）都要放進隊列進行進一步擴充。也就是說BFS的估計函數h永遠等于0，沒有一點啟發式的資訊，可以認為BFS是“最爛的”A*算法。
選取最小估價：如果學過資料結構的話，應該可以知道，對于每次都要選取最小估價的節點，應該用到最小優先級隊列（也叫最小二叉堆）。在C++的STL裡有現成的資料結構priority_queue，可以直接使用。當然不要忘了重載自定義節點的比較操作符。
A*算法的特點：A*算法在理論上是時間最優的，但是也有缺點：它的空間增長是指數級别的。
IDA*算法：這種算法被稱為疊代加深A*算法，可以有效的解決A*空間增長帶來的問題，甚至可以不用到優先級隊列。如果要知道詳細：google一下。
A*尋路初探
作者：Patrick Lester
譯者：Panic2005年
譯者序：很久以前就知道了A*算法，但是從未認真讀過相關的文章，也沒有看過代碼，隻是腦子裡有個模糊的概念。這次決定從頭開始，研究一下這個被人推崇備至的簡單方法，作為學習人工智能的開始。
這篇文章非常知名，國内應該有不少人翻譯過它，我沒有查找，覺得翻譯本身也是對自身英文水準的鍛煉。經過努力，終于完成了文檔，也明白的A*算法的原理。毫無疑問，作者用形象的描述，簡潔诙諧的語言由淺入深的講述了這一神奇的算法，相信每個讀過的人都會對此有所認識（如果沒有，那就是偶的翻譯太差了--b）。
現在是年月日的版本，應原作者要求，對文中的某些算法細節做了修改。
原文連結：http://www.gamedev.net/reference/articles/article2003.asp
原作者文章連結：http://www.policyalmanac.org/games/aStarTutorial.htm
以下是翻譯的正文
會者不難，A*(念作A星)算法對初學者來說的确有些難度。這篇文章并不試圖對這個話題作權威的陳述。取而代之的是，它隻是描述算法的原理，使你可以在進一步的閱讀中了解其他相關的資料。最後，這篇文章沒有程式細節。你盡可以用任意的計算機程式語言實作它。如你所願，我在文章的末尾包含了一個指向例子程式的連結。壓縮包包括C++和Blitz Basic兩個語言的版本，如果你隻是想看看它的運作效果，裡面還包含了可執行檔案。我們正在提高自己。讓我們從頭開始。。。
序：搜尋區域
假設有人想從A點移動到一牆之隔的B點，如下圖，綠色的是起點A，紅色是終點B，藍色方塊是中間的牆。
[圖-1]
你首先注意到，搜尋區域被我們劃分成了方形網格。像這樣，簡化搜尋區域，是尋路的第一步。這一方法把搜尋區域簡化成了一個二維數組。數組的每一個元素是網格的一個方塊，方塊被标記為可通過的和不可通過的。路徑被描述為從A到B我們經過的方塊的集合。一旦路徑被找到，我們的人就從一個方格的中心走向另一個，直到到達目的地。
這些中點被稱為“節點”。當你閱讀其他的尋路資料時，你将經常會看到人們讨論節點。為什麼不把他們描述為方格呢？因為有可能你的路徑被分割成其他不是方格的結構。他們完全可以是矩形，六角形，或者其他任意形狀。節點能夠被放置在形狀的任意位置－可以在中心，或者沿着邊界，或其他什麼地方。我們使用這種系統，無論如何，因為它是最簡單的。
開始搜尋
正如我們處理上圖網格的方法，一旦搜尋區域被轉化為容易處理的節點，下一步就是去引導一次找到最短路徑的搜尋。在A*尋路算法中，我們通過從點A開始，檢查相鄰方格的方式，向外擴充直到找到目标。
我們做如下操作開始搜尋：
1，從點A開始，并且把它作為待處理點存入一個“開啟清單”。開啟清單就像一張購物清單。盡管現在清單裡隻有一個元素，但以後就會多起來。你的路徑可能會通過它包含的方格，也可能不會。基本上，這是一個待檢查方格的清單。
2，尋找起點周圍所有可到達或者可通過的方格，跳過有牆，水，或其他無法通過地形的方格。也把他們加入開啟清單。為所有這些方格儲存點A作為“父方格”。當我們想描述路徑的時候，父方格的資料是十分重要的。後面會解釋它的具體用途。
3，從開啟清單中删除點A，把它加入到一個“關閉清單”，清單中儲存所有不需要再次檢查的方格。在這一點，你應該形成如圖的結構。在圖中，暗綠色方格是你起始方格的中心。它被用淺藍色描邊，以表示它被加入到關閉清單中了。所有的相鄰格現在都在開啟清單中，它們被用淺綠色描邊。每個方格都有一個灰色指針反指他們的父方格，也就是開始的方格。
[圖-2]
接着，我們選擇開啟清單中的臨近方格，大緻重複前面的過程，如下。但是，哪個方格是我們要選擇的呢？是那個F值最低的。
路徑評分
選擇路徑中經過哪個方格的關鍵是下面這個等式：F = G + H
這裡：
* G = 從起點A，沿着産生的路徑，移動到網格上指定方格的移動耗費。
* H = 從網格上那個方格移動到終點B的預估移動耗費。這經常被稱為啟發式的，可能會讓你有點迷惑。這樣叫的原因是因為它隻是個猜測。我們沒辦法事先知道路徑的長度，因為路上可能存在各種障礙(牆，水，等等)。雖然本文隻提供了一種計算H的方法，但是你可以在網上找到很多其他的方法。
我們的路徑是通過反複周遊開啟清單并且選擇具有最低F值的方格來生成的。文章将對這個過程做更詳細的描述。首先，我們更深入的看看如何計算這個方程。
正如上面所說，G表示沿路徑從起點到目前點的移動耗費。在這個例子裡，我們令水準或者垂直移動的耗費為，對角線方向耗費為。我們取這些值是因為沿對角線的距離是沿水準或垂直移動耗費的的根号（别怕），或者約.414倍。為了簡化，我們用和近似。比例基本正确，同時我們避免了求根運算和小數。這不是隻因為我們怕麻煩或者不喜歡數學。使用這樣的整數對計算機來說也更快捷。你不就就會發現，如果你不使用這些簡化方法，尋路會變得很慢。
既然我們在計算沿特定路徑通往某個方格的G值，求值的方法就是取它父節點的G值，然後依照它相對父節點是對角線方向或者直角方向(非對角線)，分别增加和。例子中這個方法的需求會變得更多，因為我們從起點方格以外擷取了不止一個方格。
H值可以用不同的方法估算。我們這裡使用的方法被稱為曼哈頓方法，它計算從目前格到目的格之間水準和垂直的方格的數量總和，忽略對角線方向，然後把結果乘以10。這被稱為曼哈頓方法是因為它看起來像計算城市中從一個地方到另外一個地方的街區數，在那裡你不能沿對角線方向穿過街區。很重要的一點，我們忽略了一切障礙物。這是對剩餘距離的一個估算，而非實際值，這也是這一方法被稱為啟發式的原因。想知道更多？你可以在這裡找到方程和額外的注解。
F的值是G和H的和。第一步搜尋的結果可以在下面的圖表中看到。F,G和H的評分被寫在每個方格裡。正如在緊挨起始格右側的方格所表示的，F被列印在左上角，G在左下角，H則在右下角。
[圖-3]
現在我們來看看這些方格。寫字母的方格裡，G = 10。這是因為它隻在水準方向偏離起始格一個格距。緊鄰起始格的上方，下方和左邊的方格的G值都等于。對角線方向的G值是。
H值通過求解到紅色目标格的曼哈頓距離得到，其中隻在水準和垂直方向移動，并且忽略中間的牆。用這種方法，起點右側緊鄰的方格離紅色方格有格距離，H值就是。這塊方格上方的方格有格距離(記住，隻能在水準和垂直方向移動)，H值是。你大緻應該知道如何計算其他方格的H值了～。每個格子的F值，還是簡單的由G和H相加得到
繼續搜尋
為了繼續搜尋，我們簡單的從開啟清單中選擇F值最低的方格。然後，對選中的方格做如下處理：
4，把它從開啟清單中删除，然後添加到關閉清單中。
5，檢查所有相鄰格子。跳過那些已經在關閉清單中的或者不可通過的(有牆，水的地形，或者其他無法通過的地形)，把他們添加進開啟清單，如果他們還不在裡面的話。把選中的方格作為新的方格的父節點。
6，如果某個相鄰格已經在開啟清單裡了，檢查現在的這條路徑是否更好。換句話說，檢查如果我們用新的路徑到達它的話，G值是否會更低一些。如果不是，那就什麼都不做。
另一方面，如果新的G值更低，那就把相鄰方格的父節點改為目前選中的方格（在上面的圖表中，把箭頭的方向改為指向這個方格）。最後，重新計算F和G的值。如果這看起來不夠清晰，你可以看下面的圖示。
好了，讓我們看看它是怎麼運作的。我們最初的格方格中，在起點被切換到關閉清單中後，還剩格留在開啟清單中。這裡面，F值最低的那個是起始格右側緊鄰的格子，它的F值是。是以我們選擇這一格作為下一個要處理的方格。在緊随的圖中，它被用藍色突出顯示。
[圖-4]
首先，我們把它從開啟清單中取出，放入關閉清單(這就是他被藍色突出顯示的原因)。然後我們檢查相鄰的格子。哦，右側的格子是牆，是以我們略過。左側的格子是起始格。它在關閉清單裡，是以我們也跳過它。
其他格已經在開啟清單裡了，于是我們檢查G值來判定，如果通過這一格到達那裡，路徑是否更好。我們來看選中格子下面的方格。它的G值是。如果我們從目前格移動到那裡，G值就會等于(到達目前格的G值是，移動到上面的格子将使得G值增加)。因為G值大于，是以這不是更好的路徑。如果你看圖，就能了解。與其通過先水準移動一格，再垂直移動一格，還不如直接沿對角線方向移動一格來得簡單。
當我們對已經存在于開啟清單中的個臨近格重複這一過程的時候，我們發現沒有一條路徑可以通過使用目前格子得到改善，是以我們不做任何改變。既然我們已經檢查過了所有鄰近格，那麼就可以移動到下一格了。
于是我們檢索開啟清單，現在裡面隻有7格了，我們仍然選擇其中F值最低的。有趣的是，這次，有兩個格子的數值都是。我們如何選擇？這并不麻煩。從速度上考慮，選擇最後添加進清單的格子會更快捷。這種導緻了尋路過程中，在靠近目标的時候，優先使用新找到的格子的偏好。但這無關緊要。（對相同數值的不同對待，導緻不同版本的A*算法找到等長的不同路徑）那我們就選擇起始格右下方的格子，如圖：
[圖-5]
這次，當我們檢查相鄰格的時候，發現右側是牆，于是略過。上面一格也被略過。我們也略過了牆下面的格子。為什麼呢？因為你不能在不穿越牆角的情況下直接到達那個格子。你的确需要先往下走然後到達那一格，按部就班的走過那個拐角。(注解：穿越拐角的規則是可選的。它取決于你的節點是如何放置的。)
這樣一來，就剩下了其他格。目前格下面的另外兩個格子目前不在開啟清單中，于是我們添加他們，并且把目前格指定為他們的父節點。其餘格，兩個已經在關閉清單中（起始格，和目前格上方的格子，在表格中藍色高亮顯示),于是我們略過它們。最後一格，在目前格的左側，将被檢查通過這條路徑，G值是否更低。不必擔心，我們已經準備好檢查開啟清單中的下一格了。
我們重複這個過程，直到目标格被添加進關閉清單(注解)，就如在下面的圖中所看到的。
[圖-6]
注意，起始格下方格子的父節點已經和前面不同的。之前它的G值是，并且指向右上方的格子。現在它的G值是，指向它上方的格子。這在尋路過程中的某處發生，當應用新路徑時，G值經過檢查變得低了－于是父節點被重新指定，G和F值被重新計算。盡管這一變化在這個例子中并不重要，在很多場合，這種變化會導緻尋路結果的巨大變化。
那麼，我們怎麼确定這條路徑呢？很簡單，從紅色的目标格開始，按箭頭的方向朝父節點移動。這最終會引導你回到起始格，這就是你的路徑！看起來應該像圖中那樣。從起始格A移動到目标格B隻是簡單的從每個格子（節點）的中點沿路徑移動到下一個，直到你到達目标點。就這麼簡單。
[圖-7]
A*方法總結
好，現在你已經看完了整個說明，讓我們把每一步的操作寫在一起：
1，把起始格添加到開啟清單。
2，重複如下的工作：
a) 尋找開啟清單中F值最低的格子。我們稱它為目前格。
b) 把它切換到關閉清單。
c) 對相鄰的格中的每一個？
* 如果它不可通過或者已經在關閉清單中，略過它。反之如下。
* 如果它不在開啟清單中，把它添加進去。把目前格作為這一格的父節點。記錄這一格的F,G,和H值。
* 如果它已經在開啟清單中，用G值為參考檢查新的路徑是否更好。更低的G值意味着更好的路徑。如果是這樣，就把這一格的父節點改成目前格，并且重新計算這一格的G和F值。如果你保持你的開啟清單按F值排序，改變之後你可能需要重新對開啟清單排序。
d) 停止，當你
* 把目标格添加進了關閉清單(注解)，這時候路徑被找到，或者
* 沒有找到目标格，開啟清單已經空了。這時候，路徑不存在。
3.儲存路徑。從目标格開始，沿着每一格的父節點移動直到回到起始格。這就是你的路徑。
(注解:在這篇文章的較早版本中，建議的做法是當目标格（或節點）被加入到開啟清單，而不是關閉清單的時候停止尋路。這麼做會更迅速，而且幾乎總是能找到最短的路徑，但不是絕對的。當從倒數第二個節點到最後一個（目标節點）之間的移動耗費懸殊很大時－例如剛好有一條河穿越兩個節點中間，這時候舊的做法和新的做法就會有顯著不同。)
題外話
離題一下，見諒，值得一提的是，當你在網上或者相關論壇看到關于A*的不同的探讨，你有時會看到一些被當作A*算法的代碼而實際上他們不是。要使用A*，你必須包含上面讨論的所有元素－－特定的開啟和關閉清單，用F,G和H作路徑評價。有很多其他的尋路算法，但他們并不是A*，A*被認為是他們當中最好的。Bryan Stout在這篇文章後面的參考文檔中論述了一部分，包括他們的一些優點和缺點。有時候特定的場合其他算法會更好，但你必須很明确你在作什麼。好了，夠多的了。回到文章。
實作的注解
現在你已經明白了基本原理，寫你的程式的時候還得考慮一些額外的東西。下面這些材料中的一些引用了我用C++和Blitz Basic寫的程式，但對其他語言寫的代碼同樣有效。
1.其他機關(避免碰撞)：如果你恰好看了我的例子代碼，你會發現它完全忽略了其他機關。我的尋路者事實上可以互相穿越。取決于具體的遊戲，這也許可以，也許不行。如果你打算考慮其他機關，希望他們能互相繞過，我建議你隻考慮靜止或那些在計算路徑時臨近目前機關的機關，把它們目前的位置标志為可通過的。對于臨近的運動着的機關，你可以通過懲罰它們各自路徑上的節點，來鼓勵這些尋路者找到不同的路徑(更多的描述見#2).
如果你選擇了把其他正在移動并且遠離目前尋路機關的那些機關考慮在内，你将需要實作一種方法及時預測在何時何地碰撞可能會發生，以便恰當的避免。否則你極有可能得到一條怪異的路徑，機關突然轉彎試圖避免和一個已經不存在的機關發生碰撞。
當然，你也需要寫一些碰撞檢測的代碼，因為無論計算的時候路徑有多完美，它也會因時間而改變。當碰撞發生時，一個機關必須尋找一條新路徑，或者，如果另一個機關正在移動并且不是正面碰撞，在繼續沿目前路徑移動之前，等待那個機關離開。
這些提示大概可以讓你開始了。如果你想了解更多，這裡有些你可能會覺得有用的連結：
*自治角色的指導行為：Craig Reynold在指導能力上的工作和尋路有些不同，但是它可以和尋路整合進而形成更完整的移動和碰撞檢測系統。
*電腦遊戲中的長短距指導：指導和尋路方面著作的一個有趣的考察。這是一個pdf檔案。
*協同機關移動：一個兩部分系列文章的第一篇，内容是關于編隊和基于分組的移動，作者是帝國時代(Age of Empires)的設計者Dave Pottinger.
*實作協同移動：Dave Pottinger文章系列的第二篇。
2. 不同的地形損耗：在這個教程和我附帶的程式中，地形隻能是二者之－可通過的和不可通過的。但是你可能會需要一些可通過的地形，但是移動耗費更高－沼澤，小山，地牢的樓梯，等等。這些都是可通過但是比平坦的開闊地移動耗費更高的地形。類似的，道路應該比自然地形移動耗費更低。
這個問題很容易解決，隻要在計算任何地形的G值的時候增加地形損耗就可以了。簡單的給它增加一些額外的損耗就可以了。由于A*算法已經按照尋找最低耗費的路徑來設計，是以很容易處理這種情況。在我提供的這個簡單的例子裡，地形隻有可通過和不可通過兩種，A*會找到最短，最直接的路徑。但是在地形耗費不同的場合，耗費最低的路徑也許會包含很長的移動距離－就像沿着路繞過沼澤而不是直接穿過它。
一種需額外考慮的情況是被專家稱之為“influence mapping”的東西（暫譯為影響映射圖）。就像上面描述的不同地形耗費一樣，你可以建立一格額外的分數系統，并把它應用到尋路的AI中。假設你有一張有大批尋路者的地圖，他們都要通過某個山區。每次電腦生成一條通過那個關口的路徑，它就會變得更擁擠。如果你願意，你可以建立一個影響映射圖對有大量屠殺事件的格子施以不利影響。這會讓計算機更傾向安全些的路徑，并且幫助它避免總是僅僅因為路徑短(但可能更危險)而持續把隊伍和尋路者送到某一特定路徑。
另一個可能得應用是懲罰周圍移動機關路徑上得節點。A*的一個底限是，當一群機關同時試圖尋路到接近的地點，這通常會導緻路徑交疊。以為一個或者多個機關都試圖走相同或者近似的路徑到達目的地。對其他機關已經“認領”了的節點增加一些懲罰會有助于你在一定程度上分離路徑，降低碰撞的可能性。然而，如果有必要，不要把那些節點看成不可通過的，因為你仍然希望多個機關能夠一字縱隊通過擁擠的出口。同時，你隻能懲罰那些臨近機關的路徑，而不是所有路徑，否則你就會得到奇怪的躲避行為例如機關躲避路徑上其他已經不在那裡的機關。還有，你應該隻懲罰路徑目前節點和随後的節點，而不應處理已經走過并甩在身後的節點。
3. 處理未知區域：你是否玩過這樣的PC遊戲，電腦總是知道哪條路是正确的，即使它還沒有偵察過地圖？對于遊戲，尋路太好會顯得不真實。幸運的是，這是一格可以輕易解決的問題。
答案就是為每個不同的玩家和電腦（每個玩家，而不是每個機關－－那樣的話會耗費大量的記憶體）建立一個獨立的“knownWalkability”數組，每個數組包含玩家已經探索過的區域，以及被當作可通過區域的其他區域，直到被證明。用這種方法，機關會在路的死端徘徊并且導緻錯誤的選擇直到他們在周圍找到路。一旦地圖被探索了，尋路就像往常那樣進行。
4. 平滑路徑：盡管A*提供了最短，最低代價的路徑，它無法自動提供看起來平滑的路徑。看一下我們的例子最終形成的路徑（在圖）。最初的一步是起始格的右下方，如果這一步是直接往下的話，路徑不是會更平滑一些嗎？有幾種方法來解決這個問題。當計算路徑的時候可以對改變方向的格子施加不利影響，對G值增加額外的數值。也可以換種方法，你可以在路徑計算完之後沿着它跑一遍，找那些用相鄰格替換會讓路徑看起來更平滑的地方。想知道完整的結果，檢視Toward More Realistic Pathfinding，一篇(免費，但是需要注冊)Marco Pinter發表在Gamasutra.com的文章
5. 非方形搜尋區域：在我們的例子裡，我們使用簡單的D方形圖。你可以不使用這種方式。你可以使用不規則形狀的區域。想想冒險棋的遊戲，和遊戲中那些國家。你可以設計一個像那樣的尋路關卡。為此，你可能需要建立一個國家相鄰關系的表格，和從一個國家移動到另一個的G值。你也需要估算H值的方法。其他的事情就和例子中完全一樣了。當你需要向開啟清單中添加新元素的時候，不需使用相鄰的格子，取而代之的是從表格中尋找相鄰的國家。
類似的，你可以為一張确定的地形圖建立路徑點系統，路徑點一般是路上，或者地牢通道的轉折點。作為遊戲設計者，你可以預設這些路徑點。兩個路徑點被認為是相鄰的如果他們之間的直線上沒有障礙的話。在冒險棋的例子裡，你可以儲存這些相鄰資訊在某個表格裡，當需要在開啟清單中添加元素的時候使用它。然後你就可以記錄關聯的G值（可能使用兩點間的直線距離），H值（可以使用到目标點的直線距離），其他都按原先的做就可以了。Amit Patel 寫了其他方法的摘要。另一個在非方形區域搜尋RPG地圖的例子，檢視我的文章Two-Tiered A* Pathfinding。(譯者注：譯文： A*分層尋路)
6. 一些速度方面的提示：當你開發你自己的A*程式，或者改寫我的，你會發現尋路占據了大量的CPU時間，尤其是在大地圖上有大量對象在尋路的時候。如果你閱讀過網上的其他材料，你會明白，即使是開發了星際争霸或帝國時代的專家，這也無可奈何。如果你覺得尋路太過緩慢，這裡有一些建議也許有效：
* 使用更小的地圖或者更少的尋路者。
* 不要同時給多個對象尋路。取而代之的是把他們加入一個隊列，把尋路過程分散在幾個遊戲周期中。如果你的遊戲以周期每秒的速度運作，沒人能察覺。但是當大量尋路者計算自己路徑的時候,他們會發覺遊戲速度突然變慢。
* 盡量使用更大的地圖網格。這降低了尋路中搜尋的總網格數。如果你有志氣，你可以設計兩個或者更多尋路系統以便使用在不同場合，取決于路徑的長度。這也正是專業人士的做法，用大的區域計算長的路徑，然後在接近目标的時候切換到使用小格子/區域的精細尋路。如果你對這個觀點感興趣，查閱我的文章Two-Tiered A* Pathfinding。(譯者注：譯文:A*分層尋路)
* 使用路徑點系統計算長路徑，或者預先計算好路徑并加入到遊戲中。
* 預處理你的地圖，表明地圖中哪些區域是不可到達的。我把這些區域稱作“孤島”。事實上，他們可以是島嶼或其他被牆壁包圍等無法到達的任意區域。A*的下限是，當你告訴它要尋找通往那些區域的路徑時，它會搜尋整個地圖，直到所有可到達的方格/節點都被通過開啟清單和關閉清單的計算。這會浪費大量的CPU時間。可以通過預先确定這些區域（比如通過flood-fill或類似的方法)來避免這種情況的發生,用某些種類的數組記錄這些資訊，在開始尋路前檢查它。
* 在一個擁擠的類似迷宮的場合，把不能連通的節點看作死端。這些區域可以在地圖編輯器中預先手動指定，或者如果你有雄心壯志，開發一個自動識别這些區域的算法。給定死端的所有節點可以被賦予一個唯一的标志數字。然後你就可以在尋路過程中安全的忽略所有死端，隻有當起點或者終點恰好在死端的某個節點的時候才需要考慮它們。
7. 維護開啟清單：這是A*尋路算法最重要的組成部分。每次你通路開啟清單，你都需要尋找F值最低的方格。有幾種不同的方法實作這一點。你可以把路徑元素随意儲存，當需要尋找F值最低的元素的時候，周遊開啟清單。這很簡單，但是太慢了，尤其是對長路徑來說。這可以通過維護一格排好序的清單來改善，每次尋找F值最低的方格隻需要選取清單的首元素。當我自己實作的時候，這種方法是我的首選。
在小地圖。這種方法工作的很好，但它并不是最快的解決方案。更苛求速度的A*程式員使用叫做二叉堆的方法，這也是我在代碼中使用的方法。憑我的經驗，這種方法在大多數場合會快～倍，并且在長路經上速度呈幾何級數提升(10倍以上速度)。如果你想了解更多關于二叉堆的内容，查閱我的文章，Using Binary Heaps in A* Pathfinding。(譯者注：譯文：在A*尋路中使用二叉堆)
另一個可能的瓶頸是你在多次尋路之間清除和儲存你的資料結構的方法。我個人更傾向把所有東西都存儲在數組裡面。雖然節點可以以面向對象的風格被動态的産生，記錄和儲存，我發現建立和删除對象所增加的大量時間，以及多餘的管理層次減慢的整個過程的速度。但是，如果你使用數組，你需要在調用之間清理資料。這中情形你想做的最後一件事就是在尋路調用之後花點時間把一切歸零，尤其是你的地圖很大的時候。
我通過使用一個叫做whichList(x,y)的二維數組避免這種開銷，數組的每個元素表明了節點在開啟清單還是在關閉清單中。嘗試尋路之後，我沒有清零這個數組。取而代之的是，我在新的尋路中重置onClosedList和onOpenList的數值，每次尋路兩個都+5或者類似其他數值。這種方法，算法可以安全的跳過前面尋路留下的髒資料。我還在數組中儲存了諸如F,G和H的值。這樣一來，我隻需簡單的重寫任何已經存在的值而無需被清除數組的操作幹擾。将資料存儲在多元數組中需要更多記憶體，是以這裡需要權衡利弊。最後，你應該使用你最得心應手的方法。
8. Dijkstra的算法：盡管A*被認為是通常最好的尋路算法(看前面的“題外話”),還是有一種另外的算法有它的可取之處-Dijkstra算法。Dijkstra算法和A*本質是相同的，隻有一點不同，就是Dijkstra算法沒有啟發式(H值總是)。由于沒有啟發式，它在各個方向上平均搜尋。正如你所預料，由于Dijkstra算法在找到目标前通常會探索更大的區域，是以一般會比A*更慢一些。
那麼為什麼要使用這種算法呢？因為有時候我們并不知道目标的位置。比如說你有一個資源采集機關，需要擷取某種類型的資源若幹。它可能知道幾個資源區域，但是它想去最近的那個。這種情況，Dijkstra算法就比A*更适合，因為我們不知道哪個更近。用A*，我們唯一的選擇是依次對每個目标許路并計算距離，然後選擇最近的路徑。我們尋找的目标可能會有不計其數的位置，我們隻想找其中最近的，而我們并不知道它在哪裡，或者不知道哪個是最近的。
看完上面的介紹，再來看一個比較經典的題目:knight moves。貌似也叫漢密爾頓路徑，具體的我也不記得了。對這個問題我用A*算法來求解，正所謂光說不練是沒有用的
http://acm.pku.edu.cn/JudgeOnline/problem?id=2243
problem statement
A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.
Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.
Input Specification
The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.
Output Specification
For each test case, print one line saying "To get from xx to yy takes n knight moves.".
Sample Input
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
Sample Output
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
題目的意思大概是說：在國際象棋的棋盤上，一匹馬共有8個可能的跳躍方向，求從起點到目标點之間的最少跳躍次數。
A* code:
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4
5 struct knight{
6 int x,y,step;
7 int g,h,f;
8 bool operator < (const knight & k) const{ //重載比較運算符
9 return f > k.f;
10 }
11 }k;
12 bool visited[8][8]; //已通路标記(關閉清單)
13 int x1,y1,x2,y2,ans; //起點(x1,y1),終點(x2,y2),最少移動次數ans
14 int dirs[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};//8個移動方向
15 priority_queue<knight> que; //最小優先級隊列(開啟清單)
16
17 bool in(const knight & a){ //判斷knight是否在棋盤内
18 if(a.x<0 || a.y<0 || a.x>=8 || a.y>=8)
19 return false;
20 return true;
21 }
22 int Heuristic(const knight &a){ //manhattan估價函數
23 return (abs(a.x-x2)+abs(a.y-y2))*10;
24 }
25 void Astar(){ //A*算法
26 knight t,s;
27 while(!que.empty()){
28 t=que.top(),que.pop(),visited[t.x][t.y]=true;
29 if(t.x==x2 && t.y==y2){
30 ans=t.step;
31 break;
32 }
33 for(int i=0;i<8;i++){
34 s.x=t.x+dirs[i][0],s.y=t.y+dirs[i][1];
35 if(in(s) && !visited[s.x][s.y]){
36 s.g = t.g + 23; //23表示根号5乘以10再取其ceil
37 s.h = Heuristic(s);
38 s.f = s.g + s.h;
39 s.step = t.step + 1;
40 que.push(s);
41 }
42 }
43 }
44 }
45 int main(){
46 char line[5];
47 while(gets(line)){
48 x1=line[0]-'a',y1=line[1]-'1',x2=line[3]-'a',y2=line[4]-'1';
49 memset(visited,false,sizeof(visited));
50 k.x=x1,k.y=y1,k.g=k.step=0,k.h=Heuristic(k),k.f=k.g+k.h;
51 while(!que.empty()) que.pop();
52 que.push(k);
53 Astar();
54 printf("To get from %c%c to %c%c takes %d knight moves.\n",line[0],line[1],line[3],line[4],ans);
55 }
56 return 0;
57 }
58
posted
==========================================================================================================
原文位址： http://www.gamedev.net/reference/articles/article2003.asp
概述
雖然掌握了 A* 算法的人認為它容易，但是對于初學者來說， A* 算法還是很複雜的。
搜尋區域(The Search Area)
我們假設某人要從 A 點移動到 B 點，但是這兩點之間被一堵牆隔開。如圖 1 ，綠色是 A ，紅色是 B ，中間藍色是牆。
圖 1
你應該注意到了，我們把要搜尋的區域劃分成了正方形的格子。這是尋路的第一步，簡化搜尋區域，就像我們這裡做的一樣。這個特殊的方法把我們的搜尋區域簡化為了 2 維數組。數組的每一項代表一個格子，它的狀态就是可走 (walkalbe) 和不可走 (unwalkable) 。通過計算出從 A 到 B 需要走過哪些方格，就找到了路徑。一旦路徑找到了，人物便從一個方格的中心移動到另一個方格的中心，直至到達目的地。
方格的中心點我們成為“節點 (nodes) ”。如果你讀過其他關于 A* 尋路算法的文章，你會發現人們常常都在讨論節點。為什麼不直接描述為方格呢？因為我們有可能把搜尋區域劃為為其他多變形而不是正方形，例如可以是六邊形，矩形，甚至可以是任意多變形。而節點可以放在任意多邊形裡面，可以放在多變形的中心，也可以放在多邊形的邊上。我們使用這個系統，因為它最簡單。
開始搜尋(Starting the Search)
一旦我們把搜尋區域簡化為一組可以量化的節點後，就像上面做的一樣，我們下一步要做的便是查找最短路徑。在 A* 中，我們從起點開始，檢查其相鄰的方格，然後向四周擴充，直至找到目标。
我們這樣開始我們的尋路旅途：
1. 從起點 A 開始，并把它就加入到一個由方格組成的 open list( 開放清單 ) 中。這個 open list 有點像是一個購物單。當然現在 open list 裡隻有一項，它就是起點 A ，後面會慢慢加入更多的項。 Open list 裡的格子是路徑可能會是沿途經過的，也有可能不經過。基本上 open list 是一個待檢查的方格清單。
2. 檢視與起點 A 相鄰的方格 ( 忽略其中牆壁所占領的方格，河流所占領的方格及其他非法地形占領的方格 ) ，把其中可走的 (walkable) 或可到達的(reachable) 方格也加入到 open list 中。把起點 A 設定為這些方格的父親 (parent node 或 parent square) 。當我們在追蹤路徑時，這些父節點的内容是很重要的。稍後解釋。
3. 把 A 從 open list 中移除，加入到 close list( 封閉清單 ) 中， close list 中的每個方格都是現在不需要再關注的。
如下圖所示，深綠色的方格為起點，它的外框是亮藍色，表示該方格被加入到了 close list 。與它相鄰的黑色方格是需要被檢查的，他們的外框是亮綠色。每個黑方格都有一個灰色的指針指向他們的父節點，這裡是起點 A 。
圖 2 。
下一步，我們需要從 open list 中選一個與起點 A 相鄰的方格，按下面描述的一樣或多或少的重複前面的步驟。但是到底選擇哪個方格好呢？具有最小F 值的那個。
路徑排序(Path Sorting)
計算出組成路徑的方格的關鍵是下面這個等式：
F = G + H
這裡，
G = 從起點 A 移動到指定方格的移動代價，沿着到達該方格而生成的路徑。
H = 從指定的方格移動到終點 B 的估算成本。這個通常被稱為試探法，有點讓人混淆。為什麼這麼叫呢，因為這是個猜測。直到我們找到了路徑我們才會知道真正的距離，因為途中有各種各樣的東西 ( 比如牆壁，水等 ) 。本教程将教你一種計算 H 的方法，你也可以在網上找到其他方法。
我們的路徑是這麼産生的：反複周遊 open list ，選擇 F 值最小的方格。這個過程稍後較長的描述。我們還是先看看怎麼去計算上面的等式。
如上所述， G 是從起點Ａ移動到指定方格的移動代價。在本例中，橫向和縱向的移動代價為 10 ，對角線的移動代價為 14 。之是以使用這些資料，是因為實際的對角移動距離是 2 的平方根，或者是近似的 1.414 倍的橫向或縱向移動代價。使用 10 和 14 就是為了簡單起見。比例是對的，我們避免了開放和小數的計算。這并不是我們沒有這個能力或是不喜歡數學。使用這些數字也可以使計算機更快。稍後你便會發現，如果不使用這些技巧，尋路算法将很慢。
既然我們是沿着到達指定方格的路徑來計算 G 值，那麼計算出該方格的 G 值的方法就是找出其父親的 G 值，然後按父親是直線方向還是斜線方向加上10 或 14 。随着我們離開起點而得到更多的方格，這個方法會變得更加明朗。
有很多方法可以估算 H 值。這裡我們使用 Manhattan 方法，計算從目前方格橫向或縱向移動到達目标所經過的方格數，忽略對角移動，然後把總數乘以 10 。之是以叫做 Manhattan 方法，是因為這很像統計從一個地點到另一個地點所穿過的街區數，而你不能斜向穿過街區。重要的是，計算 H 是，要忽略路徑中的障礙物。這是對剩餘距離的估算值，而不是實際值，是以才稱為試探法。
把 G 和 H 相加便得到 F 。我們第一步的結果如下圖所示。每個方格都标上了 F ， G ， H 的值，就像起點右邊的方格那樣，左上角是 F ，左下角是 G，右下角是 H 。
圖 3
好，現在讓我們看看其中的一些方格。在标有字母的方格， G = 10 。這是因為水準方向從起點到那裡隻有一個方格的距離。與起點直接相鄰的上方，下方，左方的方格的 G 值都是 10 ，對角線的方格 G 值都是 14 。
H 值通過估算起點于終點 ( 紅色方格 ) 的 Manhattan 距離得到，僅作橫向和縱向移動，并且忽略沿途的牆壁。使用這種方式，起點右邊的方格到終點有3 個方格的距離，是以 H = 30 。這個方格上方的方格到終點有 4 個方格的距離 ( 注意隻計算橫向和縱向距離 ) ，是以 H = 40 。對于其他的方格，你可以用同樣的方法知道 H 值是如何得來的。
每個方格的 F 值，再說一次，直接把 G 值和 H 值相加就可以了。
繼續搜尋(Continuing the Search)
為了繼續搜尋，我們從 open list 中選擇 F 值最小的 ( 方格 ) 節點，然後對所選擇的方格作如下操作：
4. 把它從 open list 裡取出，放到 close list 中。
5. 檢查所有與它相鄰的方格，忽略其中在 close list 中或是不可走 (unwalkable) 的方格 ( 比如牆，水，或是其他非法地形 ) ，如果方格不在 open lsit中，則把它們加入到 open list 中。
把我們標明的方格設定為這些新加入的方格的父親。
6. 如果某個相鄰的方格已經在 open list 中，則檢查這條路徑是否更優，也就是說經由目前方格 ( 我們選中的方格 ) 到達那個方格是否具有更小的 G值。如果沒有，不做任何操作。
相反，如果 G 值更小，則把那個方格的父親設為目前方格 ( 我們選中的方格 ) ，然後重新計算那個方格的 F 值和 G 值。如果你還是很混淆，請參考下圖。
圖 4
Ok ，讓我們看看它是怎麼工作的。在我們最初的 9 個方格中，還有 8 個在 open list 中，起點被放入了 close list 中。在這些方格中，起點右邊的格子的 F 值 40 最小，是以我們選擇這個方格作為下一個要處理的方格。它的外框用藍線打亮。
首先，我們把它從 open list 移到 close list 中 ( 這就是為什麼用藍線打亮的原因了 ) 。然後我們檢查與它相鄰的方格。它右邊的方格是牆壁，我們忽略。它左邊的方格是起點，在 close list 中，我們也忽略。其他 4 個相鄰的方格均在 open list 中，我們需要檢查經由這個方格到達那裡的路徑是否更好，使用 G 值來判定。讓我們看看上面的方格。它現在的 G 值為 14 。如果我們經由目前方格到達那裡， G 值将會為 20( 其中 10 為到達目前方格的 G 值，此外還要加上從目前方格縱向移動到上面方格的 G 值 10) 。顯然 20 比 14 大，是以這不是最優的路徑。如果你看圖你就會明白。直接從起點沿對角線移動到那個方格比先橫向移動再縱向移動要好。
當把 4 個已經在 open list 中的相鄰方格都檢查後，沒有發現經由目前方格的更好路徑，是以我們不做任何改變。現在我們已經檢查了目前方格的所有相鄰的方格，并也對他們作了處理，是時候選擇下一個待處理的方格了。
是以再次周遊我們的 open list ，現在它隻有 7 個方格了，我們需要選擇 F 值最小的那個。有趣的是，這次有兩個方格的 F 值都 54 ，選哪個呢？沒什麼關系。從速度上考慮，選擇最後加入 open list 的方格更快。這導緻了在尋路過程中，當靠近目标時，優先使用新找到的方格的偏好。但是這并不重要。 ( 對相同資料的不同對待，導緻兩中版本的 A* 找到等長的不同路徑 ) 。
我們選擇起點右下方的方格，如下圖所示。
圖 5
這次，當我們檢查相鄰的方格時，我們發現它右邊的方格是牆，忽略之。上面的也一樣。
我們把牆下面的一格也忽略掉。為什麼？因為如果不穿越牆角的話，你不能直接從目前方格移動到那個方格。你需要先往下走，然後再移動到那個方格，這樣來繞過牆角。 ( 注意：穿越牆角的規則是可選的，依賴于你的節點是怎麼放置的 )
這樣還剩下 5 個相鄰的方格。目前方格下面的 2 個方格還沒有加入 open list ，是以把它們加入，同時把目前方格設為他們的父親。在剩下的 3 個方格中，有 2 個已經在 close list 中 ( 一個是起點，一個是目前方格上面的方格，外框被加亮的 ) ，我們忽略它們。最後一個方格，也就是目前方格左邊的方格，我們檢查經由目前方格到達那裡是否具有更小的 G 值。沒有。是以我們準備從 open list 中選擇下一個待處理的方格。
不斷重複這個過程，直到把終點也加入到了 open list 中，此時如下圖所示。
圖 6
注意，在起點下面 2 格的方格的父親已經與前面不同了。之前它的 G 值是 28 并且指向它右上方的方格。現在它的 G 值為 20 ，并且指向它正上方的方格。這在尋路過程中的某處發生，使用新路徑時 G 值經過檢查并且變得更低，是以父節點被重新設定， G 和 F 值被重新計算。盡管這一變化在本例中并不重要，但是在很多場合中，這種變化會導緻尋路結果的巨大變化。
那麼我們怎麼樣去确定實際路徑呢？很簡單，從終點開始，按着箭頭向父節點移動，這樣你就被帶回到了起點，這就是你的路徑。如下圖所示。從起點 A 移動到終點 B 就是簡單從路徑上的一個方格的中心移動到另一個方格的中心，直至目标。就是這麼簡單！
圖 7
A*算法總結(Summary of the A* Method)
Ok ，現在你已經看完了整個的介紹，現在我們把所有步驟放在一起：
1. 把起點加入 open list 。
2. 重複如下過程：
a. 周遊 open list ，查找 F 值最小的節點，把它作為目前要處理的節點。
b. 把這個節點移到 close list 。
c. 對目前方格的 8 個相鄰方格的每一個方格？
◆ 如果它是不可抵達的或者它在 close list 中，忽略它。否則，做如下操作。
◆ 如果它不在 open list 中，把它加入 open list ，并且把目前方格設定為它的父親，記錄該方格的 F ， G 和 H 值。
◆ 如果它已經在 open list 中，檢查這條路徑 ( 即經由目前方格到達它那裡 ) 是否更好，用 G 值作參考。更小的 G 值表示這是更好的路徑。如果是這樣，把它的父親設定為目前方格，并重新計算它的 G 和 F 值。如果你的 open list 是按 F 值排序的話，改變後你可能需要重新排序。
d. 停止，當你
◆ 把終點加入到了 open list 中，此時路徑已經找到了，或者
◆ 查找終點失敗，并且 open list 是空的，此時沒有路徑。
3. 儲存路徑。從終點開始，每個方格沿着父節點移動直至起點，這就是你的路徑。
題外話(Small Rant)
請原諒我的離題，當你在網上或論壇上看到各種關于 A* 算法的讨論時，你偶爾會發現一些 A* 的代碼，實際上他們不是。要使用 A* ，你必須包含上面讨論的所有元素 ---- 尤其是 open list ， close list 和路徑代價 G ， H 和 F 。也有很多其他的尋路算法，這些算法并不是 A* 算法， A* 被認為是最好的。在本文末尾引用的一些文章中 Bryan Stout 讨論了他們的一部分，包括他們的優缺點。在某些時候你可以二中擇一，但你必須明白自己在做什麼。Ok ，不廢話了。回到文章。
實作的注解(Notes on Implemetation)
現在你已經明白了基本方法，這裡是你在寫自己的程式是需要考慮的一些額外的東西。下面的材料引用了一些我用 C++ 和 Basic 寫的程式，但是對其他語言同樣有效。
1. 維護 Open List ：這是 A* 中最重要的部分。每次你通路 Open list ，你都要找出具有最小 F 值的方格。有幾種做法可以做到這個。你可以随意儲存路徑元素，當你需要找到具 有最小 F 值的方格時，周遊整個 open list 。這個很簡單，但對于很長的路徑會很慢。這個方法可以通過維護一個排好序的表來改進，每次當你需要找到具有最小 F 值的方格時，僅取出表的第一項即可。我寫程式時，這是我用的第一個方法。
對于小地圖，這可以很好的工作，但這不是最快的方案。追求速度的 A* 程式員使用了叫做二叉堆的東西，我的程式裡也用了這個。以我的經驗，這種方法在多數場合下會快 2—3 倍，對于更長的路徑速度成幾何級數增長 (10 倍甚至更快 ) 。如果你想更多的了解二叉堆，請閱讀 Using Binary Heaps in A* Pathfinding 。
2. 其他機關：如果你碰巧很仔細的看了我的程式，你會注意到我完全忽略了其他機關。我的尋路者實際上可以互相穿越。這取決于遊戲，也許可以，也許不可以。如果你想考慮其他機關，并想使他們移動時繞過彼此，我建議你的尋路程式忽略它們，再寫一些新的程式來判斷兩個機關是否會發生碰撞。如果發生碰撞，你可以産生一個新的路徑，或者是使用一些标準的運動法則（比如永遠向右移動，等等）直至障礙物不在途中，然後産生一個新的路徑。為什麼在計算初始路徑是不包括其他機關呢？因為其他機關是可以動的，當你到達的時候它們可能不在自己的位置上。這可以産生一些怪異的結果，一個機關突然轉向來避免和一個已不存在的機關碰撞，在它的路徑計算出來後和穿越它路徑的那些機關碰撞了。
在尋路代碼中忽略其他機關，意味着你必須寫另一份代碼來處理碰撞。這是遊戲的細節，是以我把解決方案留給你。本文末尾引用的 Bryan Stout's的文章中的幾種解決方案非常值得了解。
3. 一些速度方面的提示：如果你在開發自己的 A* 程式或者是改編我寫的程式，最後你會發現尋路占用了大量的 CPU 時間，尤其是當你有相當多的尋路者和一塊很大的地圖時。如果你閱讀過網上的資料，你會發現就算是開發星際争霸，帝國時代的專家也是這樣。如果你發現事情由于尋路而變慢了，這裡有些主意很不錯：
◆ 使用小地圖或者更少的尋路者。
◆ 千萬不要同時給多個尋路者尋路。取而代之的是把它們放入隊列中，分散到幾個遊戲周期中。如果你的遊戲以每秒 40 周期的速度運作，沒人能察覺到。但是如果同時有大量的尋路者在尋路的話，他們會馬上就發現遊戲慢下來了。
◆ 考慮在地圖中使用更大的方格。這減少了尋路時需要搜尋的方格數量。如果你是有雄心的話，你可以設計多套尋路方案，根據路徑的長度而使用在不同場合。這也是專業人士的做法，對長路徑使用大方格，當你接近目标時使用小方格。如果你對這個有興趣，請看 Two-Tiered A* Pathfinding 。
◆ 對于很長的路徑，考慮使用路徑點系統，或者可以預先計算路徑并加入遊戲中。
◆ 預先處理你的地圖，指出哪些區域是不可到達的。這些區域稱為“孤島”。實際上，他們可以是島嶼，或者是被牆壁等包圍而不可到達的任意區域。 A* 的下限是，你告訴他搜尋通往哪些區域的路徑時，他會搜尋整個地圖，直到所有可以抵達的方格都通過 open list 或 close list 得到了處理。這會浪費大量的 CPU 時間。這可以通過預先設定不可到達的區域來解決。在某種數組中記錄這些資訊，在尋路前檢查它。在我的 Blitz版程式中，我寫了個地圖預處理程式來完成這個。它可以提前識别尋路算法會忽略的死路徑，這又進一步提高了速度。
4. 不同的地形損耗：在這個教程和我的程式中，地形隻有 2 種：可抵達的和不可抵達 的。但是如果你有些可抵達的地形，移動代價會更高些，沼澤，山丘，地牢的樓梯
等都是可抵達的地形，但是移動代價比平地就要高。類似的，道路的移動代價就比 它周圍的地形低。
在你計算給定方格的 G 值時加上地形的代價就很容易解決了這個問題。簡單的給這些方格加上一些額外的代價就可以了。 A* 算法用來查找代價最低的路徑，應該很容易處理這些。在我的簡單例子中，地形隻有可達和不可達兩種， A* 會搜尋最短和最直接的路徑。但是在有地形代價的環境中，代價最低的的路徑可能會很長。
就像沿着公路繞過沼澤而不是直接穿越它。
另一個需要考慮的是專家所謂的“ influence Mapping ”，就像上面描述的可變成本地形一樣，你可以建立一個額外的計分系統，把它應用到尋路的 AI 中。假設你有這樣一張地圖，地圖上由個通道穿過山丘，有大批的尋路者要通過這個通道，電腦每次産生一個通過那個通道的路徑都會變得很擁擠。如果需要，你可以産生一個 influence map ，它懲罰那些會發生大屠殺的方格。這會讓電腦選擇更安全的路徑，也可以幫助它避免因為路徑短（當然也更危險）而持續把隊伍或尋路者送往某一特定路徑。
5. 維護未探測的區域：你玩 PC 遊戲的時候是否發現電腦總是能精确的選擇路徑，甚至地圖都未被探測。對于遊戲來說，尋路過于精确反而不真實。幸運的是，這個問題很容易修正。答案就是為每個玩家和電腦（每個玩家，不是每個機關 --- 那會浪費很多記憶體）建立一個獨立的knownWalkability 數組。每個數組包含了玩家已經探測的區域的資訊，和假設是可到達的其他區域，直到被證明。使用這種方法，機關會在路的死端徘徊，并會做出錯誤的選擇，直到在它周圍找到了路徑。地圖一旦被探測了，尋路又向平常一樣工作。
6. 平滑路徑： A* 自動給你花費最小的，最短的路徑，但它不會自動給你最平滑的路徑。看看我們的例子所找到的路徑（圖 7 ）。在這條路徑上，第一步在起點的右下方，如果第一步在起點的正下方是不是路徑會更平滑呢？
有幾個方法解決這個問題。在你計算路徑時，你可以懲罰那些改變方向的方格，把它的 G 值增加一個額外的開銷。另一種選擇是，你可以周遊你生成的路徑，查找那些用相鄰的方格替代會使路徑更平滑的地方。要了解更多，請看 Toward More Realistic Pathfinding 。
7. 非方形搜尋區域：在我們的例子中，我們使用都是 2D 的方形的區域。你可以使用不規則的區域。想想冒險遊戲中的那些國家，你可以設計一個像那樣的尋路關卡。你需要建立一張表格來儲存國家相鄰關系，以及從一個國家移動到另一個國家的 G 值。你還需要一個方法了估算 H值。其他的都可以向上面的例子一樣處理。當你向 open list 添加新項時，不是使用相鄰的方格，而是檢視表裡相鄰的國家。
類似的，你可以為一張固定地形的地圖的路徑建立路徑點系統。路徑點通常是道路或地牢通道的轉折點。作為遊戲設計者，你可以預先設定路徑點。如果兩個路徑點的連線沒有障礙物的話它們被視為相鄰的。在冒險遊戲的例子中，你可以儲存這些相鄰資訊在某種表中，當 open list 增加新項時使用。然後記錄 G 值（可能用兩個結點間的直線距離）和 H 值（可能使用從節點到目标的直線距離）。其它的都想往常一樣處理。
進一步閱讀(Further Reading)
Ok ，現在你已經對 A* 有了個基本的了解，同時也認識了一些進階的主題。我強烈建議你看看我的代碼，壓縮包裡包含了 2 個版本的實作，一個是C++ ，另一個是 Blitz Basic 。 2 個版本都有注釋，你以該可以很容易就看懂。下面是連結：
Sample Code: A* Pathfinder (2D) Version 1.71 。
如果你不會使用 C++ 或是 BlitzBasic ，在 C++ 版本下你可以找到兩個 exe 檔案。 BlitzBasic 版本必須去網站 Blitz Basic 下載下傳 BlitzBasic 3D 的免費Demo 才能運作。 在這裡 here 你可以看到一個 Ben O'Neill 的 A* 線上驗證執行個體。
你應該閱讀下面這幾個站點的文章。在你讀完本教程後你可以更容易了解他們。
Amit's A* Pages ： Amit Patel 的這篇文章被廣泛引用，但是如果你沒有閱讀本教程的話，你可能會感到很迷惑。尤其是你可以看到 Amit Patel 自己的一些想法。
Smart Moves: Intelligent Path Finding ： Bryan Stout 的這篇需要去 Gamasutra.com 注冊才能閱讀。 Bryan 用 Delphi 寫的程式幫助我學習了 A* ，同時給了我一些我的程式中的一些靈感。他也闡述了 A* 的其他選擇。
Terrain Analysis ： Dave Pottinger 一篇非常高階的，有吸引力的文章。他是 Ensemble Studios 的一名專家。這個家夥調整了遊戲帝國時代和王者時代。不要期望能夠讀懂這裡的每一樣東西，但是這是一篇能給你一些不錯的主意的很有吸引力的文章。它讨論了包 mip-mapping ，
influence mapping ，和其他高階 AI 尋路主題。他的 flood filling 給了我在處理死路徑 ”dead ends” 和孤島 ”island” 時的靈感。這包含在我的 Blitz 版本的程式裡。
下面的一些站點也值得去看看：
· aiGuru: Pathfinding
· Game AI Resource: Pathfinding
· GameDev.net: Pathfinding
謝謝。