與心靈對話

游戲算法整理 算法一：A*尋路初探

作者： Patrick Lester
譯者：Panic 2005年3月18日

譯者序：很久以前就知道了A*算法，但是從未認真讀過相關的文章，也沒有看過代碼，只是腦子里有個模糊的概念。這次決定從頭開始，研究一下這個被人推崇備至的簡單方法，作為學習人工智能的開始。
這篇文章非常知名，國內應該有不少人翻譯過它，我沒有查找，覺得翻譯本身也是對自身英文水平的鍛煉。經過努力，終于完成了文檔，也明白的A*算法的原理。毫無疑問，作者用形象的描述，簡潔詼諧的語言由淺入深的講述了這一神奇的算法，相信每個讀過的人都會對此有所認識（如果沒有，那就是偶的翻譯太差了 --b）。
現在是2005年7月19日的版本，應原作者要求，對文中的某些算法細節做了修改。
原文鏈接：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表示沿路徑從起點到當前點的移動耗費。在這個例子里，我們令水平或者垂直移動的耗費為10，對角線方向耗費為14。我們取這些值是因為沿對角線的距離是沿水平或垂直移動耗費的的根號2（別怕），或者約1.414倍。為了簡化，我們用10和14近似。比例基本正確，同時我們避免了求根運算和小數。這不是只因為我們怕麻煩或者不喜歡數學。使用這樣的整數對計算機來說也更快捷。你不就就會發現，如果你不使用這些簡化方法，尋路會變得很慢。

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

H值可以用不同的方法估算。我們這里使用的方法被稱為曼哈頓方法，它計算從當前格到目的格之間水平和垂直的方格的數量總和，忽略對角線方向。然后把結果乘以10。這被成為曼哈頓方法是因為它看起來像計算城市中從一個地方到另外一個地方的街區數，在那里你不能沿對角線方向穿過街區。很重要的一點，我們忽略了一切障礙物。這是對剩余距離的一個估算，而非實際值，這也是這一方法被稱為啟發式的原因。想知道更多？你可以在這里找到方程和額外的注解。

F的值是G和H的和。第一步搜索的結果可以在下面的圖表中看到。F,G和H的評分被寫在每個方格里。正如在緊挨起始格右側的方格所表示的，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的值。如果這看起來不夠清晰，你可以看下面的圖示。

好了，讓我們看看它是怎么運作的。我們最初的9格方格中，在起點被切換到關閉列表中后，還剩8格留在開啟列表中。這里面，F值最低的那個是起始格右側緊鄰的格子，它的F值是40。因此我們選擇這一格作為下一個要處理的方格。在緊隨的圖中，它被用藍色突出顯示。

[圖4]

首先，我們把它從開啟列表中取出，放入關閉列表(這就是他被藍色突出顯示的原因)。然后我們檢查相鄰的格子。哦，右側的格子是墻，所以我們略過。左側的格子是起始格。它在關閉列表里，所以我們也跳過它。

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

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

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

那我們就選擇起始格右下方的格子，如圖。

[圖5]

這次，當我們檢查相鄰格的時候，發現右側是墻，于是略過。上面一格也被略過。我們也略過了墻下面的格子。為什么呢？因為你不能在不穿越墻角的情況下直接到達那個格子。你的確需要先往下走然后到達那一格，按部就班的走過那個拐角。(注解：穿越拐角的規則是可選的。它取決于你的節點是如何放置的。)

這樣一來，就剩下了其他5格。當前格下面的另外兩個格子目前不在開啟列表中，于是我們添加他們，并且把當前格指定為他們的父節點。其余3格，兩個已經在關閉列表中（起始格，和當前格上方的格子，在表格中藍色高亮顯示),于是我們略過它們。最后一格，在當前格的左側，將被檢查通過這條路徑，G值是否更低。不必擔心，我們已經準備好檢查開啟列表中的下一格了。

我們重復這個過程，直到目標格被添加進關閉列表(注解)，就如在下面的圖中所看到的。

[圖6]

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

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

[圖7]

A*方法總結

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

   1，把起始格添加到開啟列表。
   2，重復如下的工作：
      a) 尋找開啟列表中F值最低的格子。我們稱它為當前格。
      b) 把它切換到關閉列表。
      c) 對相鄰的8格中的每一個？
          * 如果它不可通過或者已經在關閉列表中，略過它。反之如下。
          * 如果它不在開啟列表中，把它添加進去。把當前格作為這一格的父節點。記錄這一格的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*提供了最短，最低代價的路徑，它無法自動提供看起來平滑的路徑。看一下我們的例子最終形成的路徑（在圖7）。最初的一步是起始格的右下方，如果這一步是直接往下的話，路徑不是會更平滑一些嗎？

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

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

類似的，你可以為一張確定的地形圖創建路徑點系統，路徑點一般是路上，或者地牢通道的轉折點。作為游戲設計者，你可以預設這些路徑點。兩個路徑點被認為是相鄰的如果他們之間的直線上沒有障礙的話。在冒險棋的例子里，你可以保存這些相鄰信息在某個表格里，當需要在開啟列表中添加元素的時候使用它。然后你就可以記錄關聯的G值（可能使用兩點間的直線距離），H值（可以使用到目標點的直線距離），其他都按原先的做就可以了。

Amit Patel 寫了其他方法的摘要。另一個在非方形區域搜索RPG地圖的例子，查看我的文章Two-Tiered A* Pathfinding。(譯者注：譯文：  A*分層尋路)

6. 一些速度方面的提示：當你開發你自己的A*程序，或者改寫我的，你會發現尋路占據了大量的CPU時間，尤其是在大地圖上有大量對象在尋路的時候。如果你閱讀過網上的其他材料，你會明白，即使是開發了星際爭霸或帝國時代的專家，這也無可奈何。如果你覺得尋路太過緩慢，這里有一些建議也許有效：

    * 使用更小的地圖或者更少的尋路者。

    * 不要同時給多個對象尋路。取而代之的是把他們加入一個隊列，把尋路過程分散在幾個游戲周期中。如果你的游戲以40周期每秒的速度運行，沒人能察覺。但是當大量尋路者計算自己路徑的時候,他們會發覺游戲速度突然變慢。

    * 盡量使用更大的地圖網格。這降低了尋路中搜索的總網格數。如果你有志氣，你可以設計兩個或者更多尋路系統以便使用在不同場合，取決于路徑的長度。這也正是專業人士的做法，用大的區域計算長的路徑，然后在接近目標的時候切換到使用小格子/區域的精細尋路。如果你對這個觀點感興趣，查閱我的文章Two-Tiered A* Pathfinding。(譯者注：譯文 :A*分層尋路)

    * 使用路徑點系統計算長路徑，或者預先計算好路徑并加入到游戲中。
   
    * 預處理你的地圖，表明地圖中哪些區域是不可到達的。我把這些區域稱作“孤島”。事實上，他們可以是島嶼或其他被墻壁包圍等無法到達的任意區域。A*的下限是，當你告訴它要尋找通往那些區域的路徑時，它會搜索整個地圖，直到所有可到達的方格/節點都被通過開啟列表和關閉列表的計算。這會浪費大量的CPU時間。可以通過預先確定這些區域（比如通過flood-fill或類似的方法)來避免這種情況的發生,用某些種類的數組記錄這些信息，在開始尋路前檢查它。
   
    * 在一個擁擠的類似迷宮的場合，把不能連通的節點看作死端。這些區域可以在地圖編輯器中預先手動指定，或者如果你有雄心壯志，開發一個自動識別這些區域的算法。給定死端的所有節點可以被賦予一個唯一的標志數字。然后你就可以在尋路過程中安全的忽略所有死端，只有當起點或者終點恰好在死端的某個節點的時候才需要考慮它們。

7. 維護開啟列表：這是A*尋路算法最重要的組成部分。每次你訪問開啟列表，你都需要尋找F值最低的方格。有幾種不同的方法實現這一點。你可以把路徑元素隨意保存，當需要尋找F值最低的元素的時候，遍歷開啟列表。這很簡單，但是太慢了，尤其是對長路徑來說。這可以通過維護一格排好序的列表來改善，每次尋找F值最低的方格只需要選取列表的首元素。當我自己實現的時候，這種方法是我的首選。

在小地圖。這種方法工作的很好，但它并不是最快的解決方案。更苛求速度的A*程序員使用叫做二叉堆的方法，這也是我在代碼中使用的方法。憑我的經驗，這種方法在大多數場合會快2～3倍，并且在長路經上速度呈幾何級數提升(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值總是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*的幾種變化。
    * 地形分析：這是一格高階，但是有趣的話題，Dave Pottinge撰寫，Ensemble Studios的專家。這家伙參與了帝國時代和君王時代的開發。別指望看懂這里所有的東西，但是這是篇有趣的文章也許會讓你產生自己的想法。它包含一些對 mip-mapping，influence mapping以及其他一些高級AI/尋路觀點。對"flood filling"的討論使我有了我自己的“死端”和“孤島”的代碼的靈感，這些包含在我Blitz版本的代碼中。

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

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

我同樣高度推薦下面這幾本書, 里面有很多關于尋路和其他AI話題的文章。 它們也附帶了實例代碼的CD。這些書我都買了。另外，如果你通過下面的鏈接購買了它們，我會從Amazon得到幾個美分。:)

A*分層尋

游戲算法整理 算法二：碰撞

游戲算法整理 算法四：戰略游戲中的戰爭模型算法的初步探討

游戲算法整理 算法五：飛行射擊游戲中的碰撞檢測

　　在游戲中物體的碰撞是經常發生的，怎樣檢測物體的碰撞是一個很關鍵的技術問題。在RPG游戲中，一般都將場景分為許多矩形的單元，碰撞的問題被大大的簡化了，只要判斷精靈所在的單元是不是有其它的東西就可以了。而在飛行射擊游戲（包括象荒野大鏢客這樣的射擊游戲）中，碰撞卻是最關鍵的技術，如果不能很好的解決，會影響玩游戲者的興趣。因為飛行射擊游戲說白了就是碰撞的游戲——躲避敵人的子彈或飛機，同時用自己的子彈去碰撞敵人。

　　碰撞，這很簡單嘛，只要兩個物體的中心點距離小于它們的半徑之和就可以了。確實，而且我也看到很多人是這樣做的，但是，這只適合圓形的物體——圓形的半徑處處相等。如果我們要碰撞的物體是兩艘威力巨大的太空飛船，它是三角形或矩形或其他的什么形狀，就會出現讓人尷尬的情景：兩艘飛船眼看就要擦肩而過，卻出人意料的發生了爆炸；或者敵人的子彈穿透了你的飛船的右弦，你卻安然無恙，這不是我們希望發生的。于是，我們需要一種精確的檢測方法。

　　那么，怎樣才能達到我們的要求呢？其實我們的前輩們已經總結了許多這方面的經驗，如上所述的半徑檢測法，三維中的標準平臺方程法，邊界框法等等。大多數游戲程序員都喜歡用邊界框法，這也是我采用的方法。邊界框是在編程中加進去的不可見的邊界。邊界框法，顧名思義，就是用邊界框來檢測物體是否發生了碰撞，如果兩個物體的邊界框相互干擾，則發生了碰撞。用什么樣的邊界框要視不同情況而定，用最近似的幾何形狀。當然，你可以用物體的準確幾何形狀作邊界框，但出于效率的考慮，我不贊成這樣做，因為游戲中的物體一般都很復雜，用復雜的邊界框將增加大量的計算，尤其是浮點計算，而這正是我們想盡量避免的。但邊界框也不能與準確幾何形狀有太大的出入，否則就象用半徑法一樣出現奇怪的現象。

　　在飛行射擊游戲中，我們的飛機大多都是三角形的，我們可以用三角形作近似的邊界框。現在我們假設飛機是一個正三角形（或等要三角形，我想如果誰把飛機設計成左右不對稱的怪物，那他的審美觀一定有問題），我的飛機是正著的、向上飛的三角形，敵人的飛機是倒著的、向下飛的三角形，且飛機不會旋轉（大部分游戲中都是這樣的）。我們可以這樣定義飛機：中心點O(Xo,Yo),三個頂點P0(X0,Y0)、P1(X1,Y1)、P2(X2,Y2)。中心點為正三角形的中心點，即中心點到三個頂點的距離相等。接下來的問題是怎樣確定兩個三角形互相干擾了呢？嗯，現在我們接觸到問題的實質了。如果你學過平面解析幾何，我相信你可以想出許多方法解決這個問題。判斷一個三角形的各個頂點是否在另一個三角形里面，看起來是個不錯的方法，你可以這樣做，但我卻發現一個小問題：一個三角形的頂點沒有在另一個三角形的里面，卻可能發生了碰撞，因為另一個三角形的頂點在這個三角形的里面，所以要判斷兩次，這很麻煩。有沒有一次判斷就可以的方法？我們把三角形放到極坐標平面中，中心點為原點，水平線即X軸為零度角。我們發現三角形成了這個樣子：在每個角度我們都可以找到一個距離，用以描述三角形的邊。既然我們找到了邊到中心點的距離，那就可以用這個距離來檢測碰撞。如圖一，兩個三角形中心點坐標分別為（Xo,Yo）和 (Xo1,Yo1),由這兩個點的坐標求出兩點的距離及兩點連線和X軸的夾角θ，再由θ求出中心點連線與三角形邊的交點到中心點的距離，用這個距離與兩中心點距離比較，從而判斷兩三角形是否碰撞。因為三角形左右對稱，所以θ取-90～90度區間就可以了。哈，現在問題有趣多了，-90～90度區間正是正切函數的定義域，求出θ之后再找對應的邊到中心點的距離就容易多了，利用幾何知識，如圖二，將三角形的邊分為三部分,即圖2中紅綠藍三部分，根據θ在那一部分而分別對待。用正弦定理求出邊到中心點的距離，即圖2中淺綠色線段的長度。但是，如果飛機每次移動都這樣判斷一次，效率仍然很低。我們可以結合半徑法來解決，先用半徑法判斷是否可能發生碰撞，如果可能發生碰撞，再用上面的方法精確判斷是不是真的發生了碰撞，這樣基本就可以了。如果飛機旋轉了怎么辦呢，例如，如圖三所示飛機旋轉了一個角度α，仔細觀察圖三會發現，用（θ-α）就可以求出邊到中心點的距離，這時你要注意邊界情況，即（θ-α）可能大于90度或小于-90度。啰羅嗦嗦說了這么多，不知道大家明白了沒有。我編寫了一個簡單的例程，用于說明我的意圖。在例子中假設所有飛機的大小都一樣，并且沒有旋轉。

/////////////////////////////////////////////////////////////////////
            //example.cpp
            //碰撞檢測演示
            //作者 李韜
            /////////////////////////////////////////////////////////////////////
            //限于篇幅，這里只給出了碰撞檢測的函數
            //define/////////////////////////////////////////////////////////////
            #define NUM_VERTICES 3
            #define ang_30 -0.5236
            #define ang60    1.0472
            #define ang120 2.0944
            //deftype////////////////////////////////////////////////////////////
            struct object
            {
            float xo, yo;
            float radio;
            float x_vel, y_vel;
            float vertices[NUM_VERTICES][2];
            }
             
            //faction/////////////////////////////////////////////////////////////
            //根據角度求距離
            float AngToDis(struct object obj, float angle)
            {
            float dis, R;
            R = obj.radius;
            if (angle <= ang_30)
            dis = R / (2 * sin(-angle));
            else if (angle >= 0)
            dis = R / (2 * sin(angle + ang60));
            else dis = R / (2 * sin(ang120 - angle));
            return dis;
            }
             
            //碰撞檢測
            int CheckHit(struct object obj1, struct object obj2)
            {
            float deltaX, deltaY, angle, distance, bumpdis;
            deltaX = abs(obj1.xo - obj2.xo);
            deltaY = obj1.yo - obj2.yo;
            distance = sqrt(deltaX * deltaX + deltaY * deltaY);
            if (distance <= obj.radio)
            {
            angle = atan2(deltaY, deltaX);
            bumpdis1 = AngToDis(obj1, angle);
            return (distance <= 2 * bumpdis);
            }
            ruturn 0;
            }
            //End//////////////////////////////////////////////////////////////

游戲算法整理 算法六：關于SLG中人物可到達范圍計算的想法

下面的沒有經過實踐，因此很可能是錯誤的，覺得有用的初學朋友讀一讀吧：）
希望高人指點一二 :)

簡介：
在標準的SLG游戲中，當在一個人物處按下鼠標時，會以人物為中心，向四周生成一個菱形的可移動區范圍，如下：

    0
  000
00s00
  000
   0

這個圖形在剛開始學習PASCAL時就應該寫過一個畫圖的程序（是否有人懷念？）。那個圖形和SLG的擴展路徑一樣。

一、如何生成路徑：
從人物所在的位置開始，向四周的四個方向擴展，之后的點再進行擴展。即從人物所在的位置從近到遠進行擴展（類似廣寬優先）。

二、擴展時會遇到的問題：
1、當擴展到一個點時，人物的移動力沒有了。
2、當擴展的時候遇到了一個障礙點。
3、當擴展的時候這個結點出了地圖。
4、擴展的時候遇到了一個人物正好站在這個點（與2同？）。
5、擴展的點已經被擴展過了。當擴展節點的時候，每個節點都是向四周擴展，因此會產生重復的節點。

當遇到這些問題的時候，我們就不對這些節點處理了。在程序中使用ALLPATH[]數組記錄下每一個等擴展的節點，不處理這些問題節點的意思就是不把它們加入到ALLPATH[]數組中。我們如何去擴展一個結點周圍的四個結點，使用這個結點的坐標加上一個偏移量就可以了，方向如下：

   3
   0 2
   1

偏移量定義如下：
int offx[4] = { -1, 0, 1, 0 };
int offy[4] = { 0, 1, 0, -1 };

擴展一個節點的相鄰的四個節點的坐標為：
for(int i=0; i<4; i )
{
     temp.x = temp1.x offx[i];
     temp.y = temp1.y offy[i];
}

三、關于地圖的結構：
1、地圖的二維坐標，用于確定每個圖塊在地圖中的位置。
2、SLG中還要引入一個變量decrease表示人物經過這個圖塊后他的移動力的減少值。例如，一個人物現在的移動力為CurMP=5，與之相領的圖塊的decrease=2；這時，如果人物移動到這里，那它的移動力變成CurMP-decrease。
3、Flag域：寬度優先中好像都有這個變量，有了它，每一個點保證只被擴展一次。防止一個點被擴展多次。（一個點只被擴展一次真的能得到正確的結果嗎？）
4、一個地圖上的圖塊是否可以通過，我們使用了一個Block代表。1---不可以通過；0---可以通過。

這樣，我們可以定義一個簡單的地圖結構數組了：

#define MAP_MAX_WIDTH 50
#define MAP_MAX_HEIGHT 50
typedef struct tagTILE{
     int x,y,decrease,flag,block;
}TILE,*LPTILE;
TILE pMap[MAP_MAX_WIDTH][MAP_MAX_HEIGHT];

以上是順序數組，是否使用動態的分配更好些？畢竟不能事先知道一個地圖的寬、高。

四、關于路徑：
SLG游戲中的擴展路徑是一片區域（以人物為中心向四周擴展，當然，當人物移動時路徑只有一個）。這些擴展的路徑必須要存儲起來，所有要有一個好的結構。我定義了一個結構，不是很好：

typedef struct tagNODE{
     int x,y;   //擴展路徑中的一個點在地圖中的坐標。
     int curmp; //人物到了這個點以后的當前的移動力。
}NODE,*LPNODE;

上面的結構是定義擴展路徑中的一個點的結構。擴展路徑是點的集合，因此用如下的數組進行定義：

NODE AllPath[PATH_MAX_LENGTH];

其中的PATH_MAX_LENGTH代表擴展路徑的點的個數，我們不知道這個擴展的路徑中包含多少個點，因此定義一個大一點的數字使這個數組不會產生溢出：

#define PATH_MAX_LENGTH 200

上面的這個數組很有用處，以后的擴展就靠它來實現，它應該帶有兩個變量nodecount 代表當前的數組中有多少個點。當然，數組中的點分成兩大部分，一部分是已經擴展的結點，存放在數組的前面；另一部分是等擴展的節點，放在數組的后面為什么會出現已擴展節點和待擴展節點？如下例子：

當前的人物坐標為x,y；移動力為mp。將它存放到AllPath數組中，這時的起始節點為等擴展的節點。這時我們擴展它的四個方向，對于合法的節點（如沒有出地圖，也沒有障礙......），我們將它們存放入AllPath數組中，這時的新加入的節點（起始節點的子節點）就是等擴展結點，而起始節點就成了已擴展節點了。下一次再擴展節點的時候，我們不能再擴展起始節點，因為它是已經擴展的節點了。我們只擴展那幾個新加入的節點（待擴展節點），之后的情況以此類推。那么我們如何知道哪些是已經擴展的結點，哪些是等擴展的節點？我們使用另一個變量cutflag，在這個變量所代表的下標以前的結點是已擴展節點，在它及它之后是待擴展結點。

五、下面是基本框架（只擴展一個人物的可達范圍）：

int nodecount = 0; //AllPath數組中的點的個數（包含待擴展節點和已經擴展的節點
            int cutflag = 0; //用于劃分已經擴展的節點和待擴展節點
            NODE temp; //路徑中的一個點（臨時）
            temp.x = pRole[cur] - >x; //假設有一個關于人物的類，代表當前的人物
            temp.y = pRole[cur] - >y;
            temp.curmp = pRole[cur] - >MP; //人物的最大MP
            AllPath[nodecount] = temp; //起始點入AllPath，此時的起始點為等擴展的節點
             
            while (curflag < nodecount) { //數組中還有待擴展的節點
            int n = nodecount; //記錄下當前的數組節點的個數。
            for (int i = cutflag; i < nodecount; i) { //遍歷待擴展節點
            for (int j = 0; j < 4; j) { //向待擴展節點的四周各走一步
            //取得相鄰點的數據
            temp.x = AllPath[i].x offx[j];
            temp.y = AllPath[i].y offy[j];
            temp.curmp = AllPath[i].curmp -
            pMap[AllPath[i].x][AllPath[i].y].decrease;
            //以下為檢測是否為問題點的過程，如果是問題點，不加入AllPath數組，繼續處理其它的點
            if (pMap[temp.x][temp.y].block) {
            continue; //有障礙，處理下一個節點
            }
            if (temp.curmp < 0) {
            continue; //沒有移動力了
            }
            if (temp.x < 0 || temp.x >= MAP_MAX_WIDTH || temp.y < 0 ||
            temp.y >= MAP_MAX_HEIGHT) {
            continue; //出了地圖的范圍
            }
            if (pMap[temp.x][temp.y].flag) {
            continue; //已經擴展了的結點
            }
            //經過了上面幾層的檢測，沒有問題的節點過濾出來，可以加入AllPath
            AllPath[nodecount] = temp;
            }
            pMap[AllPath[i].x][AllPath[i].y].flag = 1; //將已經擴展的節點標記為已擴展節點
            }
            cutflag = n; //將已擴展節點和待擴展節點的分界線下標值移動到新的分界線
            }
            for (int i = 0; i < nodecount; i) {
            pMap[AllPath[i].x][AllPath[i].y].bFlag = 0; //標記為已擴展節點的標記設回為待擴展節點。
            }

游戲算法整理 算法七 無限大地圖的實現

這已經不是什么新鮮的東西了，不過現在實在想不到什么好寫，而且版面上又異常冷清，我再不說幾句就想要倒閉了一樣。只好暫且拿這個東西來湊數吧。
無限大的地圖，聽上去非常吸引人。本來人生活的空間就是十分廣闊的，人在這么廣闊的空間里活動才有一種自由的感覺。游戲中的虛擬世界由于受到計算機存儲空間的限制，要真實地反映這個無限的空間是不可能的。而對這個限制最大的，就是內存的容量了。所以在游戲的空間里，我們一般只能在一個狹小的范圍里活動，在一般的RPG中，從一個場景走到另一個場景，即使兩個地方是緊緊相連的，也要有一個場景的切換過程，一般的表現就是畫面的淡入淡出。

這樣的場景切換給人一種不連續的感覺（我不知道可不可以把這種稱作“蒙太奇”:o)），從城內走到城外還有情可緣，因為有道城墻嘛，但是兩個地方明明沒有界限，卻偏偏在這一邊看不到另外一邊，就有點不現實了。當然這并不是毛病，一直以來的RPG都是遵循這個原則，我們（至少是我）已經習慣了這種走路的方式。我在這里說的僅僅是另外一種看起來更自然一點的走路方式，僅此而已。

當然要把整個城市的地圖一下子裝進內存，現在的確是不現實的，每一次只能放一部分，那么應該怎么放才是我們要討論的問題。

我們在以前提到Tile方法構造地圖時就談到過Tile的好處之一就是節省內存，這里仍然可以借鑒Tile的思想。我們把整個大地圖分成幾塊，把每一塊稱作一個區域，在同一時間里，內存中只保存相鄰的四塊區域。這里每個區域的劃分都有一定的要求：每個區域大小應該相等這是一定的了，不然判斷當前屏幕在哪個區域中就成了一個非常令人撓頭的事；另外每個區域的大小都要大于屏幕的大小，也只有這樣才能保證屏幕（就是圖中那塊半透明的藍色矩形）在地圖上蕩來蕩去的時候，最多同時只能覆蓋四個區域（象左圖中所表示的），內存里也只要保存四個區域就足夠了；還有一點要注意的，就是地圖上的建筑物（也包括樹啦，大石頭啦什么的）必須在一個區域內，這樣也是為了畫起來方便，當然墻壁——就是那種連續的圍墻可以除外，因為墻壁本來就是一段一段拼起來的。

我們在程序中可以設定4個指針來分別指向這4個區域，當每次主角移動時，就判斷當前滾動的屏幕是否移出了這四個區域，如果移出了這四個區域，那么就廢棄兩個（或三個）已經在目前的四個相鄰區域中被滾出去的區域（說得很別扭，各位見諒），讀入兩個（或三個）新滾進來的區域，并重新組織指針。這里并不涉及內存區域的拷貝。

這樣的區域劃分方法剛好適合我們以前提到的Tile排列方法，只要每個區域橫向Tile的個數是個偶數就行了，這樣相鄰的兩個區域拼接起來剛好嚴絲合縫，而且每個區域塊的結構完全一致，沒有那些需要重復保存的Tile（這個我想我不需要再畫圖說明了，大家自己隨便畫個草圖就看得出來了）。在文件中的保存方法就是按一個個區域分別保存，這樣在讀取區域數據時就可以直接作為一整塊讀入，也簡化了程序。另外還有個細節就是，我們的整個地圖可能不是一個規則的矩形，可能有些地方是無法達到的，如右圖所示，背景是黑色的部分代表人物不能達到的地方。那么在整個地圖中，這一部分區域（在圖中藍色的3號區域）就可以省略，表現在文件存儲上就是實際上不存儲這一部分區域，這樣可以節省下不少存儲空間。對于這種地圖可以用一個稀疏矩陣來存儲，大家也可以發揮自己的才智用其他對于編程來說更方便的形式來存儲地圖。  

這就是對無限大地圖實現的一種方法，歡迎大家提出更好的方法。也希望整個版面能夠活躍一點。