A*路徑搜尋初探 GameDev.net

「路徑搜尋（pathfinding）」是角色扮演（RPG）類型和其他電玩遊戲中，常見的基本人工智慧程式。當玩家點選地圖上的某一點，螢幕上的角色就會自動越過障礙物，抵達目的地，這就是「路徑搜尋」演算法的用途，而本文介紹的A*則是知名的路徑搜尋演算法之一。當然，車用GPS衛星導航軟體，以及會走迷宮的電腦鼠（micromouse），也需要用到不同形式的「路徑搜尋」演算法。

最近在Patrick Lester先生的網站看到，他的大作已經被Panic先生翻譯成簡體中文。在取得Panic的同意後，筆者將他的譯槁加以編輯，並做了部分改寫成正體中文版，希望對有興趣的讀者有所幫助。

原文作者：Patrick Lester
簡體中文版譯者：Panic 2005年3月18日（第一版）
2005年7月19日（第二版，應原作者要求，對文中的某些演算法細節做了修改。）
正體中文版編輯：趙英傑

譯者序：很久以前就知道了A*演算法，但是從未認真讀過相關的文章，也沒有看過程式碼，只是腦子裡有個模糊的概念。這次決定從頭開始，研究一下這個被人推崇備至的簡單方法，作為學習人工智慧的開始。

這篇文章非常知名，國內應該有不少人翻譯過它，我沒有搜尋過，覺得翻譯本身也是對自身英文水平的鍛煉。經過努力，終於完成了本文，也明白的A*演算法的原理。毫無疑問，作者用形象的描述、簡潔詼諧的語言由淺入深的講述了這一神奇的演算法，相信每個讀過的人都會對此有所認識（如果沒有，那就是偶的翻譯太差了 :wink:）。

原文連結：http://www.gamedev.net/reference/articles/article2003.asp
原作者文章連結：http://www.policyalmanac.org/games/aStarTutorial.htm
簡體中文版連結：http://blog.vckbase.com/panic/archive/2005/03/20/3778.html

以下是翻譯的正文。

A*（唸作A star）演算法對初學者來說的確有些難度。這篇文章並不試圖對這個話題作權威性地陳述。取而代之的是，本文只是描述演算法的原理，讓你可以在進一步的閱讀中理解其他相關的資料。

最後，這篇文章不包含程式實作的細節。你可以用任意的電腦程式語言實作它。如你所願，我在文章的末尾包含了一個範例程式碼的連結。該壓縮檔中包括C++和Blitz Basic兩個語言的版本，如果你只是想看看它的執行效果，裡面還包含了可執行檔。

準備超越自己，讓我們從頭開始…

序：搜尋區域

假設有人想從A點移動到一牆之隔的B點，如下圖，綠色的是起點A，紅色是終點B，藍色方塊是中間的牆。

【圖1】

你首先將注意到，搜尋區域被我們劃分成了方形網格。像這樣，簡化搜尋區域，是路徑搜尋的第一步。這一方法把搜尋區域簡化成了一個二維陣列。陣列的每一個元素是網格的一個方塊，方塊被標記為可通過的和不可通過的。路徑被描述為從A到B我們經過的方塊的集合。一旦找到路徑，我們的人就從一個方格的中心走向另一個，直到抵達目的地。

這些中點被稱為「節點」。當你閱讀其他的路徑搜尋資料時，你將經常會看到人們討論節點。為什麼不把他們描述為方格呢？因為有可能你的路徑被分割成其他不是方格的結構。他們完全可以是矩形、六角形、或其他任意形狀。節點能夠被放置在形狀的任意位置－－可以在中心、或者沿著邊界、或其他位置。我們使用這種系統，因為它是最簡單的。

開始搜尋

正如我們處理上圖網格的方法，一旦搜尋區域被轉化為容易處理的節點，下一步就是去引導一次找到最短路徑的搜尋。在A*路徑搜尋演算法中，我們透過從點A開始，檢查相鄰方格的方式，向外擴展直到找到目標。

我們透過以下操作開始搜尋：

1. 從點A開始，並且把它作為待處理點存入一個「開啟列表（open list）」。開啟列表就像一張購物清單。儘管現在列表裡只有一個元素，但以後就會逐漸增多。你的路徑可能會通過它包含的方格，也可能不會。基本上，這是一個待檢查方格的列表。
2. 尋找起點周圍所有可到達或者可通過的方格，跳過有牆壁、湖水、或其他無法通過地形的方格。也把他們加入開啟列表。把點A當成這些方格的「父方格」儲存下來。當我們想描述路徑的時候，父方格的資料是十分重要的。後面會解釋它的實際用途。
3. 從開啟列表中刪除點A，把它加入到一個「關閉列表（closed list）」，此列表將儲存所有不需要再次檢查的方格。

此時，你應該能想像出如圖下的結構。在【圖2】中，深綠色方格是起始方格的中心。它附帶了淺藍色描邊，代表這一格已經被加入「關閉列表」中了。所有相鄰格現在都存在「開啟列表」中，它們都有淺綠色描邊。每個相鄰方格都有一個灰色指標，指向它們的父方格，也就是起始的方格。

【圖2】

接著，我們將大致重複上述的步驟，選擇開啟列表中的臨近方格，如下所述。但是，我們該選擇哪個方格呢？就是F值最低的那一個。

路徑評估（Path Scoring）

選擇經過哪些方格的關鍵是底下這個等式：

F = G + H

其中：

G：代表從起點A，沿著產生的路徑，移動到網格上指定方格的移動代價（movement cost）。   

H：從網格上那個方格移動到終點B的預估移動代價。這個經常被稱為「錯誤嘗試（heuristic）」的作法，可能會讓你感到有些困惑。這樣叫的原因是因為它只是個猜測。我們沒辦法事先知道路徑的長度，因為路上可能包含各種障礙物（牆壁、湖水…等等）。雖然本文只提供了一種計算H的方法，但是你可以在網路上找到很多其他方法。

我們的路徑是透過反覆遍覽「開啟列表」並且選擇具有最低F值的方格產生的。本文將詳細描述這個過程。首先，我們深入地看看如何計算這個方程式。

正如上面所說，G代表沿路徑從起點到當前點的移動代價。在這個例子裡，我們令水平或者垂直移動的代價為10，對角線方向代價為14。我們取這些值是因為沿對角線的距離是沿水平或垂直移動代價的的開根號2（別怕），或者約1.414倍。為了簡化，我們取用10和14的近似值。這個比例基本上正確，同時也免除了開根號和小數值的運算。這不是只因為我們怕麻煩或者不喜歡數學。使用這樣的整數也能讓電腦算得更快。你不久就會發現，如果你不使用這些簡化的算法，路徑搜尋會變得很慢。

既然我們在計算沿特定路徑通往某個方格的G值，求值的方法就是取它父節點的G值，然後依照它相對父節點是對角線方向或者直角方向（非對角線），分別增加14和10。範例中這個方法的需求會變得更多，因為我們從起點方格以外不止獲取一個方格。

H值可以用不同的方法估算。這裡使用的方法被稱為「曼哈頓方法（Manhattan method）」，它計算從當前格到目的格之間，水平和垂直的方格的數量總和，忽略對角線方向，然後把結果乘以10。稱之為「曼哈頓方法」是因為它看起來像計算城市中，從一個地方到另外一個地方的街區數，在此，你無法沿對角線方向穿過街區。很重要的一點，我們忽略了一切障礙物。這是對剩餘距離的一個估算，而非實際值，這也是這一方法被稱為「錯誤嘗試」的原因。想知道更多？你可以在這篇文章找到方程式和額外的註解。

F的值是G和H的和。第一步搜尋的結果可以在【圖三】看到。F, G和H的評估（scores）寫在每個方格中。正如緊鄰在起始格右側的方格所示，F值列在左上方、G在左下角、H則在右下角。

【圖3】

現在我們來看看這些方格。在包含字母的方格裡面（也就是中間右側那一個），G = 10。這是因為它只在水平方向偏離「起始格」一個格距。緊鄰起始格的上方、下方和左邊的方格的G值都等於10。對角線方向的G值是14。

H值透過求解到紅色目標格的「曼哈頓距離」得到，其中只在水平和垂直方向移動，並且忽略中間的牆壁。用這種方法，緊靠在起點右側的方格，離紅色方格有3格距離，H值就是30。這塊方格上面的方格有4格距離（記住，只能往水平和垂直方向移動），H值是40。到此，你應該大致知道如何計算其他方格的H值了～

每一格的F值，仍是簡單地由G和H相加得到。

繼續搜尋

為了繼續搜尋，我們簡單地從開啟列表中選擇F值最低的方格。然後，對選中的方格做如下處理：

4. 把它從開啟列表中刪除，然後添加到關閉列表中。
5. 檢查所有相鄰格子。跳過那些已經在關閉列表中，或者不可通過的（有牆和水，或其他無法通過的地形），把他們加入開啟列表，如果他們還不在裡面的話。把選中的方格當成新的方格的父節點。
6. 如果某個相鄰格已經在開啟列表裡了，檢查現在的這條路徑是否更好。換句話說，檢查如果我們用新的路徑到達它的話，G值是否會更低一些。如果不會，那就什麼都不做。

另一方面，如果新的G值更低，那就把相鄰方格的父節點改為目前選中的方格（在上面的圖表中，把箭頭的方向改為指向這個方格）。最後，重新計算F和G的值。如果這樣的說明不夠清晰明瞭，你可以參考底下的【圖4】。

好了，讓我們看看它的運作方式。我們最初的9格方格中，在「起始格」被存入關閉列表裡面之後，還剩8格留在開啟列表中。這當中，F值最低的是緊鄰在起始格右側的格子，它的F值是40。因此我們選擇這一格作為下一個要處理的方格。在底下的【圖4】中，這一格用藍色邊框標示。

【圖4】

首先，我們把它從開啟列表中取出，放入關閉列表（這就是它被用藍色邊框標示的原因）。然後我們檢查相鄰的格子。哦，右側的格子是牆，所以我們略過。左側的格子是起始格。它在「關閉列表」裡，所以我們也跳過它。

其他4格已經在開啟列表當中了，於是我們檢查G值來判定，如果通過這一格到達那裡，路徑是否更好。我們來看選中格子下面的方格。它的G值是14。如果我們從當前格移動到那裡，G值就會等於20（到達當前格的G值是10，移動到上面的格子將使得G值增加10）。因為G值20大於14，所以這不是更好的路徑。看看圖4，就能理解。與其通過先水平移動一格，再垂直移動一格，還不如直接沿對角線方向移動一格來得簡單。

當我們對已經存在於開啟列表中的4個臨近格重複此一過程的時候，我們發現沒有一條路徑可以透過使用當前格子得到改善，所以我們不做任何改變。既然我們已經檢查過了所有鄰近格，那麼就可以移動到下一格了。

於是我們檢索開啟列表，現在裡面只有7格了，我們仍然選擇其中F值最低的。有趣的是，這次，有兩個格子的數值都是54。我們如何選擇？這並不麻煩。從速度上考慮，選擇最後加入列表的格子會更快捷。這種導致了路徑搜尋過程中，在靠近目標的時候，優先使用新找到的格子的偏好。但這無關緊要（對相同數值的不同對待，導致不同版本的A*演算法找到等長的不同路徑。）
那我們就選擇起始格右下方的格子，如【圖5】。

【圖5】

這次，當我們檢查相鄰格的時候，發現右側是牆壁，於是略過。上面一格也被略過。我們也略過了牆壁底下的格子。為什麼呢？因為你不能在不穿越牆角的情況下，直接到達那個格子。你的確需要先往下走然後到達那一格，按部就班的走過那個拐角（註解：穿越拐角的規則是選擇性的，取決於你如何放置節點）。

這樣一來，就剩下了其他5格。目前格子之下的另外兩個格子現在不在開啟列表中，於是我們加入他們，並且把當前格指定為他們的父節點。其餘3格，兩個已 經在關閉列表中（起始格，和當前格上方的格子，在網格中用藍色邊框標示），於是我們略過它們。最後一格，在當前格的左側，將被檢查通過這條路徑，G值是否更低。不必擔心，我們已經準備好檢查開啟列表中的下一格了。

我們重複這個過程，直到目標格被加入關閉列表（參閱下文的註解），如【圖6】所示。

【圖6】

注意，「起始格」下方格子的父節點已經和前面的不同。之前它的G值是28，並且指向右上方的格子。現在它的G值是20，指向它上方的格子。這在路徑搜尋過程中的某處發生，當套用新路徑時，G值經過檢查變得低了－－於是父節點被重新指定，G和F值被重新計算。儘管這一變化在這個例子中並不重要，在很多場合，這種變化會導致路徑搜尋結果的巨大變化。

那麼，我們怎麼確定這條路徑呢？很簡單，從紅色的目標格開始，按箭頭的方向朝父節點移動。這最終會引導你回到起始格，這就是你的路徑！看起來應該像圖中那樣。從起始格A移動到目標格B只是簡單的從每個格子（節點）的中點沿路徑移動到下一個，直到你到達目標點。就這麼簡單。

【圖7】

A*方法總結

好，現在你已經看完了整個說明，讓我們把每一步的操作寫在一起：

1. 把起始格加入「開啟列表」。
2. 重複如下的工作：
   1. 尋找開啟列表中F值最低的格子。我們稱它為「當前格」。
   2. 把它存入「關閉列表」。
   3. 對相鄰的8格中的每一格：
      • 如果它不可通過或者已經在關閉列表中，略過它。反之如下：
      • 如果它不在開啟列表中，把它添加進去。把當前格作為這一格的父節點。記錄這一格的F, G和H值。
      • 如果它已經在開啟列表中，拿G值當作參考，檢查新的路徑是否更好。更低的G值意味著更好的路徑。如果是這樣，就把這一格的父節點改成當前格，並且重新計算這一格的G和F值。如果你想讓開啟列表按F值排序，你可能需要在此步驟之後，重新對開啟列表排序。
   4. 停止，當你：
      • 把目標格加入關閉列表（參閱下文的註解），代表找到路徑了，或者：
      • 沒有找到目標格，開啟列表已經空了。這時候，路徑不存在。
3. 儲存路徑。從目標格開始，沿著每一格的父節點移動直到回到起始格。這就是你的路徑。
   （註解：在本文的較早版本中，建議的做法是當目標格（或節點）被加入到開啟列表，而不是關閉列表的時候停止路徑搜尋。這麼做會更迅速，而且幾乎總是能找到最短的路徑，但不是絕對的。當從倒數第二個節點到最後一個（目標節點）之間的移動代價懸殊很大時－－例如剛好有一條河穿越兩個節點中間，這時候舊的做法和新的做法就會有顯著不同。）

題外話

離題一下，請見諒，值得一提的是，當你在網路上或者相關論壇看到關於A*的不同的探討，你有時會看到一些被當作A*演算法的程式碼而實際上它們不是。要使用 A*，你必須包含上面討論的所有元素－－特定的開啟和關閉列表，用F, G和H當作路徑評價。有很多其他的路徑搜尋演算法，但他們並不是A*，A*被認為是他們當中最好的。Bryan Stout在這篇文章後面的參考文件中論述了一部分，包括它們的一些優點和缺點。在某些特定的場合，其他演算法比較好，但你必須很明確知道你在做什麼。好了，回到文章。

實作的註解

現在你已經明白了基本原理，寫程式的時候還得考慮一些額外的東西。下面這些內容中的一些，引用了我用C++和Blitz Basic寫的程式，但對其他語言寫的程式碼同樣有效。

1. 其他元素（unit，避免碰撞）：如果你恰好看了我的範例程式碼，你會發現它完全忽略了其他元素。我的路徑搜尋程式事實上可以相互穿越。取決於實際的遊戲，這也許可以，也許不行。如果你打算考慮其他元素，希望他們能互相繞過，我建議你只考慮靜止或那些在計算路徑時臨近當前元素的元素，把它們當前的位置標誌為可通過的。對於臨近的運動中的元素，你可以藉由「懲罰」它們各自路徑上的節點，來鼓勵這些路徑搜尋程式找到不同的路徑（更多的說明請參閱#2）。

   如果你選擇了把其他正在移動，並且遠離當前路徑搜尋元素的那些元素考慮在內，你將需要實作一種方法，及時預測在何時何地可能會發生碰撞，以便適時避免。否則你極有可能得到一條怪異的路徑，元素突然轉彎試圖避免和一個已經不存在的元素發生碰撞。
   當然，你也需要寫一些碰撞檢測的程式碼，因為無論計算的時候路徑有多完美，它也會因時間而改變。當碰撞發生時，一個元素必須尋找一條新路徑，或者，如果另一個元素正在移動並且不是正面碰撞，在繼續沿當前路徑移動之前，等待那個元素離開。

   這些提示大概足以讓你著手撰寫程式了。如果你想瞭解更多，這裡有些你可能會覺得有用的連結：

   • Steering Behavior for Autonomous Characters（自動角色的操控行為）：Craig Reynold在操控上的研究和路徑搜尋有些不同，但是它可以和路徑搜尋整合從而形成更完整的移動和碰撞檢測系統。
   • The Long and Short of Steering in Computer Games（電腦遊戲中的長短距操控）：有關操控和路徑搜尋著作上的一個有趣的調查。這是一個pdf檔。
   • Coordinated Unit Movement（協同元素移動）：這是兩部分系列文章的第一篇，內容是關於編隊和基於分組的移動，作者是「帝國時代（Age of Empires）」遊戲的設計者Dave Pottinger。
   • Implementing Coordinated Movement（實作協同移動）：Dave Pottinger文章系列的第二篇。

2. 不同的地形損耗：在這個教程和我附帶的程式中，地形只能是二者之一：可通過和不可通過的。你可能會需要一些可通過的地形，但是移動代價更高－－沼澤、小山、地牢的樓梯…等等。這些都是可通過，但是比「平坦的開闊地形」移動代價更高的地形。同樣地，道路應該比自然地形所需的移動代價更低。

   這個問題很容易解決，只要在計算任何地形的G值時，增加地形損耗就可以了。簡單地替它增加一些額外的損耗就可以了。由於A*演算法已經按照尋找最低代價的路徑來設計，所以很容易處理這種情況。在我提供的這個簡單的範例中，地形只有可通過和不可通過兩種，A*會找到最短、最直接的路徑。但是在地形代價不同的場合，代價最低的路徑也許會包含很長的移動距離－－就像沿著路繞過沼澤而不是直接穿過它。

   一種需額外考慮的情況是被專家稱之為"influence mapping"的東西（暫譯為「影響映射圖」）。就像上面描述的不同地形代價一樣，你可以建立一個額外的分數系統，並把它套用到路徑搜尋的AI中。假設你有一張包含大批路徑搜尋程式的地圖，他們都要通過某個山區。每次電腦產生一條通過那個關口的路徑，它就會變得更擁擠。如果你願意，你可以建立一個影響映射圖，對有大量屠殺事件的格子施以不利影響。這會讓電腦更傾向比較安全的路徑，並且幫助它避免總是僅僅因為路徑短（但可能更危險），而持續把隊伍和路徑搜尋程式送到某一特定路徑。

   另一個可能的應用是懲罰周圍移動元素路徑上的節點。A*的一個底限是，當一群元素同時嘗試路徑搜尋到接近的地點時，通常會導致路徑重疊。因為一個或者多個元素都試圖走相同或者近似的路徑到達目的地。對其他元素已經「認領」了的節點增加一些懲罰，會有助於你在一定程度上分離路徑，降低碰撞的可能性。然而，如果有必要，不要把那些節點看成不可通過的，因為你仍然希望多個元素能夠一字縱隊通過擁擠的出口。同時，你只能懲罰那些臨近元素的路徑，而不是所有路徑，否則你就會得到奇怪的躲避行為。例如，元素躲避路徑上其他已經不在那裡的元素。 還有，你應該只懲罰路徑當前節點和隨後的節點，而不應處理已經走過並甩在身後的節點。

3. 處理未知區域：你是否玩過這樣的PC遊戲，電腦總是知道哪條路是正確的，即使它還沒有偵察過地圖？對於遊戲，路徑搜尋太好會顯得不真實。幸運的是，這是一個可以輕易解決的問題。

   答案就是為每個不同的玩家和電腦（每個玩家，而不是每個元素－－那樣的話會代價大量的記憶體）建立一個獨立的"knownWalkability"陣列，每個陣列包含玩家已經探索過的區域，以及被當作可通過區域的其他區域，直到被證實。用這種方法，元素會在死路徘徊並且導致錯誤的選擇，直到他們在周圍找到路。一旦地圖被探索了，路徑搜尋就像往常那樣進行。

4. 平滑路徑：儘管A*提供了最短、最低代價的路徑，它無法自動提供看起來平滑的路徑。看一下我們的範例最終形成的路徑（圖7）。最初的一步是起始格的右下方，如果這一步是直接往下的話，路徑不是會更平滑一些嗎？

   有幾種方法來解決這個問題。當計算路徑的時候可以對改變方向的格子施加不利影響，對G值增加額外的數值。也可以換種方法，你可以在路徑計算完之後沿著它跑一遍，找那些用相鄰格替換會讓路徑看起來更平滑的地方。想知道完整的結果，請參考Marco Pinter發表在Gamasutra.com的Toward More Realistic Pathfinding文章（免費，但是需要註冊）。

5. 非方形搜尋區域：在我們的範例裡，我們使用簡單的2D方形圖。你可以不使用這種方式。你可以使用不規則形狀的區域。想想棋類冒險遊戲，及遊戲中的那些國家。你可以設計一個像那樣的路徑搜尋關卡。為此，你可能需要建立一個國家相鄰關係的表格，和從一個國家移動到另一個的G值。你也需要估算H值的方法。其他的事情就 和範例中完全一樣了。當你需要在開啟列表中新增元素時，不需使用相鄰的格子，取而代之的是從表格中尋找相鄰的國家。

   同樣地，你可以為一張確定的地形圖建立路徑點系統，路徑點一般是路上，或者地牢通道的轉捩點。作為遊戲設計者，你可以預設這些路徑點。兩個路徑點被認為是相鄰的，如果他們之間的直線上沒有障礙的話。在棋類冒險遊戲的範例中，你可以在某個表格中儲存這些相鄰資訊，以便需要在「開啟列表」中新增元素的時候使用它。然後，你就可以記錄關聯的G值（可能使用兩點間的直線距離），H值（可以使用到目標點的直線距離），其他都按原先的做就可以了。

   Amit Patel 寫了其他方法的摘要。另一個在非方形區域搜尋RPG地圖的例子，請參考我的文章Two-Tiered A* Pathfinding（譯者註：譯文： A*分層路徑搜尋）

6. 一些速度方面的提示：當你開發自己的A*程式，或者改寫我的，你會發現路徑搜尋佔據了大量的CPU時間，尤其是在大地圖上有大量物件在執行路徑搜尋的時候。如果你閱讀過網路上的其他文件，你會明白，即使是開發了「星際爭霸」或「帝國時代」的專家，這也無可奈何。如果你覺得路徑搜尋太過緩慢，這裡有一些建議也許有效：
   • 使用小一點的地圖，或者減少使用路徑搜尋程式的元素。
   • 不要同時讓多個物件執行路徑搜尋。取而代之的是，將他們加入一個佇列，把路徑搜尋過程分散在幾個遊戲週期中。如果你的遊戲以每秒40週期的速度執行，沒人能察覺。但是當大量路徑搜尋程式計算自己路徑的時候，玩家會發覺遊戲速度突然變慢了。
   • 儘量使用大一點的地圖方格（或者任何形狀的格子）。此舉能降低路徑搜尋中，搜尋的總網格數。你可以取決於路徑的長度，設計兩種或者更多不同的路徑搜尋系統，以便使用在不同場合。這也正是專業人士的做法，用大區域計算比較長的路徑，然後在接近目標的時候，切換到使用小格子∕區域的精細路徑搜尋。如果你對這個觀點感興趣，請參閱我的文章Two-Tiered A* Pathfinding（譯者注：譯文：A*分層路徑搜尋）。
   • 對於比較長的路徑，可以預先計算好並植入（hardwired）遊戲裡面。
   • 預先處理地圖，標示地圖中哪些區域是無法到達的。我把這些區域稱作「孤島」。事實上，他們可以是島嶼或其他被牆壁包圍等無法到達的任意區域。A*的缺點是，當你告訴它要找出通過那些區域的路徑時，它會搜尋整個地圖，只有在每個可連通的方格∕節點都經由「開啟列表」和「關閉列表」處理過，才會停下來。這可能會浪費大量的CPU時間。可以透過預先確定這些區域（比如flood-fill或類似的方法）來避免這種情況的發生，用某些種類的陣列記錄這些資訊，在開始路徑搜尋前檢查它。
   • 在一個擁擠的類似迷宮的場合，把不能連通的節點看作死路。這些區域可以在地圖編輯器中預先手動指定，或者如果你有雄心壯志，開發一個自動識別這些區域的演算法。設定成死路的所有節點，可以被賦予一個唯一的標識數字。然後你就可以在路徑搜尋過程中安全地忽略所有死路，只有當起點或者終點恰好在死路的某個節點的時候，才需要考慮它們。

7. 維護開啟列表：這是A*路徑搜尋演算法最重要的組成部分。每當你存取開啟列表，你都需要尋找F值最低的方格。實作這項功能的方法有幾種。你可以把路徑元素隨意保存，當需要尋找F值最低的元素的時候，遍覽開啟列表。這很簡單，但是太慢了，尤其是對長路徑來說。這可以藉由維護一個排序好的列表來改善，每次尋找F值最低的方格，只需要選取列表的第一個元素。當我實作程式的時候，這種方法是我的首選。

   在小地圖上，這種方法可以良好地運作，但它並不是最快的解決方案。對速度更苛求的A*程式設計師使用叫做"binary heap"的方法，這也是我在程式碼中使用的方法。憑我的經驗，這種方法在大多數場合會快2～3倍，並且在長路徑上速度呈幾何級數提升（10倍以上速度）。如果你想瞭解更多關於"binary heap"的內容，請參閱我的文章，Using Binary Heaps in A* Pathfinding（譯者注：譯文：在A*路徑搜尋中使用Binary Heap）。
   另一個可能的瓶頸，是在多次路徑搜尋之間清除和保存資料結構的方法。我個人更傾向把所有東西都儲存在陣列裡面。雖然節點可以以物件導向的風格被動態 地產生、記錄和保存，我發現建立和刪除物件所增加的大量時間，以及多餘的管理層次將減慢整個過程的速度。但是，如果你使用陣列，你需要在呼叫之間清理資料。這種情形下，你想做的最後一件事就是在路徑搜尋呼叫之後，花點時間把一切歸零，尤其是你的地圖很大的時候。

   我透過使用一個叫做whichList(x,y)的二維陣列避免這種開銷，陣列的每個元素表明了節點是位於開啟列表還是在關閉列表中。嘗試路徑搜尋之後，我沒有清除這個陣列。取而代之的是，我在新的路徑搜尋中重置onClosedList和onOpenList的數值，每次路徑搜尋兩個都+5或者其他類似的數值。藉由這種方式，演算法可以安全地跳過前面路徑搜尋留下的冗餘資料。我還在陣列中儲存了諸如F, G和H的值。這樣一來，我只需簡單地重寫任何已經存在的值，而無需被清除陣列的操作干擾。將資料儲存在多維陣列中需要更多記憶體，所以這裡需要權衡利弊。最後，你應該使用你最得心應手的方法。

8. Dijkstra的演算法：儘管A*被認為是通常最好的路徑搜尋演算法（參閱上文的「題外話」），還是外一種演算法有它的可取之處，稱為：Dijkstra演算法。 Dijkstra演算法和A*本質是相同的，只有一點不同，就是Dijkstra演算法沒有錯誤嘗試（H值總是0）。由於沒有錯誤嘗試，它會在各個方向上平均搜尋。正如你所預料，由於Dijkstra演算法在找到目標前通常會探索更大的區域，所以一般會比A*更慢一些。
   那麼為什麼要使用這種演算法呢？因為有時候我們並不知道目標的位置。比如說你有一個資源採集元素，需要獲取某種類型的資源若干。它可能知道幾個資源區 域，但是它想去最近的那個。這種情況，Dijkstra演算法就比A*更適合，因為我們不知道哪個更近。用A*，我們唯一的選擇是依次對每個目標許路並計算距離，然後選擇最近的路徑。我們尋找的目標可能會有不計其數的位置，我們只想找其中最近的，而我們並不知道它在哪里，或者不知道哪個是最近的。

延伸閱讀

好，現在你對這些進一步的觀點有了初步認識。我建議你研究我的原始程式碼。壓縮檔裡面包含兩個版本，一個是用C++寫的，另一個用Blitz Basic。附帶一題，兩個版本都有詳盡的註解，容易閱讀，壓縮檔的連結如下。

• 範例程式碼： A* Pathfinder (2D) Version 1.9

如果你既不用C++也不用Blitz Basic，在C++版本裡有兩個小的可執行檔。Blitz Basic能在從Blitz Basic網站免費下載的Blitz Basic 3D（不是Blitz Plus）試用版上執行。Ben O’Neill提供一個連線範例可以在這裡找到。

你也該看看以下的網頁。閱讀這篇教學文件之後，他們應該變得容易理解多了。

• Amit的 A* 網頁：這是由Amit Patel撰寫，被廣泛引用的網頁，如果你事先未曾閱讀過本文，可能會有點難以理解。值得一看。尤其要看Amit對於這個問題所提出的自己的看法。
• Smart Moves：智慧型路徑搜尋：Bryan Stout發表在Gamasutra.com的這篇文章需要註冊才能閱讀。註冊是免費的而且比起這篇文章和網站的其他資源，是非常物有所值的。Bryan用Delphi寫的程式幫助我學習A*，也是我的A*程式碼的靈感來源。它還描述了A*的幾種變型。
• 地形分析：這是一個高階，但是有趣的話題，由Ensemble Studios的專家Dave Pottinge所撰寫。這傢伙參與了「帝國時代」和「君王時代（Age of Kings）」的開發。別指望看懂這裡的所有東西，但是這是篇有趣的文章，也許會讓你產生自己的想法。它包含一些對 mip-mapping, influence mapping以及其他一些進階AI路徑搜尋觀點。對"flood filling"的討論讓我有了我自己的「死路」和「孤島」程式碼的靈感，這些包含在我Blitz版本的程式碼中。

其他一些值得一看的網站：

• aiGuru: Pathfinding
• Game AI Resource: Pathfinding
• GameDev.net: Pathfinding

我同樣高度推薦下面這幾本書，裡面有很多關於路徑搜尋和其他AI話題的文章。 它們也附帶了實例程式碼的CD。這些書我都買了。另外，如果你透過底下的連結購買了這些書，我會從Amazon得到幾個美分 🙂

好了，這就是全部。如果你剛好寫了一個運用這些觀點的程式，我想拜讀一下。您可以透過底下的e-mail和我聯繫：

祝您好運！

譯者參考文獻：
 在A*路徑搜尋中使用Binary Heap
A*分層路徑搜尋