算法翻譯 中文

1、算法翻譯計(jì)科 1501 孫旭輝 201526811019移動(dòng)一個(gè)簡(jiǎn)單的物體看起來是容易的。而路徑搜索是復(fù)雜的。為什么涉及到路徑搜索就產(chǎn)生 麻煩了？考慮以下情況：物體（unit）最初位于地圖的底端并且嘗試向頂部移動(dòng)。物體掃描的區(qū)域中（粉紅色部分） 沒有任何東西顯示它不能向上移動(dòng)，因此它持續(xù)向上移動(dòng)。在靠近頂部時(shí)，它探測(cè)到一個(gè)障 礙物然后改變移動(dòng)方向。然后它沿著U形障礙物找到它的紅色的路徑。相反的，一個(gè)路徑 搜索器（pathfinder）將會(huì)掃描一個(gè)更大的區(qū)域（淡藍(lán)色部分），但是它能做到不讓物體走 向凹形障礙物而找到一條更短的路徑（藍(lán)色路徑）。然而你可以擴(kuò)展一個(gè)運(yùn)動(dòng)算法，用于對(duì)付上圖所示的障礙物。

2、或者避免制造凹形障礙， 或者把凹形出口標(biāo)識(shí)為危險(xiǎn)的（只有當(dāng)目的地在里面時(shí)才進(jìn)去）：比起一直等到最后一刻才發(fā)現(xiàn)問題，路徑搜索器讓你提前作出計(jì)劃。不帶路徑搜索的運(yùn) 動(dòng)可以在很多種情形下工作，同時(shí)可以擴(kuò)展到更多的情形，但是路徑搜索是一種更常用的解 決更多問題的方法。1.1算法計(jì)算機(jī)科學(xué)教材中的路徑搜索算法在數(shù)學(xué)視角的圖上工作一一由邊聯(lián)結(jié)起來的結(jié)點(diǎn)的 集合。一個(gè)基于圖塊(tile)拼接的游戲地圖可以看成是一個(gè)圖，每個(gè)圖塊(tile)是一個(gè)結(jié)點(diǎn)，并 在每個(gè)圖塊之間畫一條邊：目前，我會(huì)假設(shè)我們使用二維網(wǎng)格。稍后我將討論如何在你的游戲之外建立其他類型的 圖。許多AI領(lǐng)域或算法研究領(lǐng)域中的路徑搜索算法是基于任

3、意的圖設(shè)計(jì)的，而不是基于網(wǎng) 格(grid-based)的圖。我們可以找到一些能使用網(wǎng)格地圖的特性的東西。有一些我們認(rèn)為是 常識(shí)，而算法并不理解。例如，我們知道一些和方向有關(guān)的東西：一般而言，如果兩個(gè)物體距離越遠(yuǎn)，那么把其中一個(gè)物體向另一個(gè)移動(dòng)將花越多的時(shí)間；并且我們知道地圖中沒有任 何秘密通道可以從一個(gè)地點(diǎn)通向另一個(gè)地點(diǎn)。（我假設(shè)沒有，如果有的話，將會(huì)很難找到一 條好的路徑，因?yàn)槟悴⒉恢酪獜暮翁庨_始。）1.2 Dijkstra算法與最佳優(yōu)先搜索Dijkstra算法從物體所在的初始點(diǎn)開始，訪問圖中的結(jié)點(diǎn)。它迭代檢查待檢查結(jié)點(diǎn)集中 的結(jié)點(diǎn)，并把和該結(jié)點(diǎn)最靠近的尚未檢查的結(jié)點(diǎn)加入待檢查結(jié)點(diǎn)集。該結(jié)

4、點(diǎn)集從初始結(jié)點(diǎn)向 外擴(kuò)展，直到到達(dá)目標(biāo)結(jié)點(diǎn)。Dijkstra算法保證能找到一條從初始點(diǎn)到目標(biāo)點(diǎn)的最短路徑， 只要所有的邊都有一個(gè)非負(fù)的代價(jià)值。（我說最短路徑”是因?yàn)榻?jīng)常會(huì)出現(xiàn)許多差不多短的 路徑。）在下圖中，粉紅色的結(jié)點(diǎn)是初始結(jié)點(diǎn)，藍(lán)色的是目標(biāo)點(diǎn)，而類菱形的有色區(qū)域（注： 原文是teal areas）則是Dijkstra算法掃描過的區(qū)域。顏色最淡的區(qū)域是那些離初始點(diǎn)最遠(yuǎn) 的，因而形成探測(cè)過程（exploration）的邊境（frontier）：最佳優(yōu)先搜索（BFS）算法按照類似的流程運(yùn)行，不同的是它能夠評(píng)估（稱為啟發(fā)式的） 任意結(jié)點(diǎn)到目標(biāo)點(diǎn)的代價(jià)。與選擇離初始結(jié)點(diǎn)最近的結(jié)點(diǎn)不同的是，它選擇離目

5、標(biāo)最近的結(jié) 點(diǎn)。BFS不能保證找到一條最短路徑。然而，它比Dijkstra算法快的多，因?yàn)樗昧艘粋€(gè)啟 發(fā)式函數(shù)（heuristic function）快速地導(dǎo)向目標(biāo)結(jié)點(diǎn)。例如，如果目標(biāo)位于出發(fā)點(diǎn)的南方， BFS將趨向于導(dǎo)向南方的路徑。在下面的圖中，越黃的結(jié)點(diǎn)代表越高的啟發(fā)式值（移動(dòng)到 目標(biāo)的代價(jià)高），而越黑的結(jié)點(diǎn)代表越低的啟發(fā)式值（移動(dòng)到目標(biāo)的代價(jià)低）。這表明了與 Dijkstra算法相比，BFS運(yùn)行得更快。然而，這兩個(gè)例子都僅僅是最簡(jiǎn)單的情況一一地圖中沒有障礙物，最短路徑是直線的。現(xiàn)在我們來考慮前邊描述的凹型障礙物。Dijkstra算法運(yùn)行得較慢，但確實(shí)能保證找到一條問題在于BFS是基于貪

6、心策略的，它試圖向目標(biāo)移動(dòng)盡管這不是正確的路徑。由于它 僅僅考慮到達(dá)目標(biāo)的代價(jià)，而忽略了當(dāng)前已花費(fèi)的代價(jià)，于是盡管路徑變得很長(zhǎng)，它仍然繼 續(xù)走下去。結(jié)合兩者的優(yōu)點(diǎn)不是更好嗎？ 1968年發(fā)明的A*算法就是把啟發(fā)式方法(heuristic approaches)如BFS，和常規(guī)方法如Dijsktra算法結(jié)合在一起的算法。有點(diǎn)不同的是，類 似BFS的啟發(fā)式方法經(jīng)常給出一個(gè)近似解而不是保證最佳解。然而，盡管入*基于無法保證 最佳解的啟發(fā)式方法，A*卻能保證找到一條最短路徑。1.3 A*算法我將集中討論A*算法。A*是路徑搜索中最受歡迎的選擇，因?yàn)樗喈?dāng)靈活，并且能用 于多種多樣的情形之中。和其它的圖

7、搜索算法一樣，A*潛在地搜索圖中一個(gè)很大的區(qū)域。和Dijkstra 一樣，A* 能用于搜索最短路徑。和BFS 一樣，A*能用啟發(fā)式函數(shù)(注：原文為heuristic)引導(dǎo)它自 己。在簡(jiǎn)單的情況中，它和BFS 一樣快。-|_1|_|_|_-在凹型障礙物的例子中.A*找到一條和Diikstra算洼一樣好的路徑.成功的秘決在于，它把Dijkstra算法(靠近初始點(diǎn)的結(jié)點(diǎn))和BFS算法(靠近目標(biāo)點(diǎn) 的結(jié)點(diǎn))的信息塊結(jié)合起來。在討論A*的標(biāo)準(zhǔn)術(shù)語中，g(n)表示從初始結(jié)點(diǎn)到任意結(jié)點(diǎn)n 的代價(jià)，h(n)表示從結(jié)點(diǎn)n到目標(biāo)點(diǎn)的啟發(fā)式評(píng)估代價(jià)(heuristic estimated cost)。在上 圖中，y

8、ellow(h)表示遠(yuǎn)離目標(biāo)的結(jié)點(diǎn)而teal(g)表示遠(yuǎn)離初始點(diǎn)的結(jié)點(diǎn)。當(dāng)從初始點(diǎn)向目標(biāo) 點(diǎn)移動(dòng)時(shí)，A*權(quán)衡這兩者。每次進(jìn)行主循環(huán)時(shí)，它檢查f(n)最小的結(jié)點(diǎn)n，其中f(n) = g(n) + h(n)。2啟發(fā)式算法啟發(fā)式函數(shù)h(n)告訴A*從任意結(jié)點(diǎn)n到目標(biāo)結(jié)點(diǎn)的最小代價(jià)評(píng)估值。選擇一個(gè)好的啟 發(fā)式函數(shù)是重要的。2.1 A*對(duì)啟發(fā)式函數(shù)的使用啟發(fā)式函數(shù)可以控制A*的行為： 一種極端情況，如果h(n)是 0，則只有g(shù)(n)起作用，此時(shí)A*演變成Dijkstra算法， 這保證能找到最短路徑。如果h(n)經(jīng)常都比從n移動(dòng)到目標(biāo)的實(shí)際代價(jià)小(或者相等)，貝9A*保證能找到一 條最短路徑。h(n)越小

9、，A*擴(kuò)展的結(jié)點(diǎn)越多，運(yùn)行就得越慢。如果h(n)精確地等于從n移動(dòng)到目標(biāo)的代價(jià)，則A*將會(huì)僅僅尋找最佳路徑而不擴(kuò)展 別的任何結(jié)點(diǎn)，這會(huì)運(yùn)行得非?？臁１M管這不可能在所有情況下發(fā)生，你仍可以在 一些特殊情況下讓它們精確地相等(譯者：指讓h(n)精確地等于實(shí)際值)。只要提 供完美的信息，A*會(huì)運(yùn)行得很完美，認(rèn)識(shí)這一點(diǎn)很好。如果h(n)有時(shí)比從n移動(dòng)到目標(biāo)的實(shí)際代價(jià)高，則A*不能保證找到一條最短路徑， 但它運(yùn)行得更快。另一種極端情況，如果h(n)比g(n)大很多，則只有h(n)起作用，A*演變成BFS算法。所以我們得到一個(gè)很有趣的情況，那就是我們可以決定我們想要從A*中獲得什么。理 想情況下(注：原文

10、為At exactly the right point)，我們想最快地得到最短路徑。如果我們 的目標(biāo)太低，我們?nèi)詴?huì)得到最短路徑，不過速度變慢了；如果我們的目標(biāo)太高，那我們就放 棄了最短路徑，但A*運(yùn)行得更快。在游戲中，A*的這個(gè)特性非常有用。例如，你會(huì)發(fā)現(xiàn)在某些情況下，你希望得到一條好的 路徑(good path)而不是一條完美的路徑(perfect path)。為了權(quán)衡g(n)和h(n)，你 可以修改任意一個(gè)。注:在學(xué)術(shù)上，如果啟發(fā)式函數(shù)值是對(duì)實(shí)際代價(jià)的低估，A*算法被稱為簡(jiǎn)單的A算法(原文 為simply A)。然而，我繼續(xù)稱之為A*，因?yàn)樵趯?shí)現(xiàn)上是一樣的，并且在游戲編程領(lǐng)域并 不區(qū)別A和

11、A*。2.2速度還是精確度？A*改變它自己行為的能力基于啟發(fā)式代價(jià)函數(shù)，啟發(fā)式函數(shù)在游戲中非常有用。在速 度和精確度之間取得折衷將會(huì)讓你的游戲運(yùn)行得更快。在很多游戲中，你并不真正需要得到 最好的路徑，僅需要近似的就足夠了。而你需要什么則取決于游戲中發(fā)生著什么，或者運(yùn)行 游戲的機(jī)器有多快。假設(shè)你的游戲有兩種地形，平原和山地，在平原中的移動(dòng)代價(jià)是1而在山地則是3。A* is going to search three times as far along flat land as it does along mountainous land.這 是因?yàn)橛锌赡苡幸粭l沿著平原到山地的路徑。把兩個(gè)鄰接點(diǎn)

12、之間的評(píng)估距離設(shè)為1.5可以加 速A*的搜索過程。然后A*會(huì)將3和1.5比較，這并不比把3和1比較差。It is not as dissatisfied with mountainous terrain, so it wont spend as much time trying to find a way around it. Alternatively, you can speed up up A*s search by decreasing the amount it searches for paths around mountainsjust tell A* that the move

13、ment cost on mountains is 2 instead of 3. Now it will search only twice as far along the flat terrain as along mountainous terrain. Either approach gives up ideal paths to get something quicker.速度和精確度之間的選擇前不是靜態(tài)的。你可以基于CPU的速度、用于路徑搜索的時(shí)間片 數(shù)、地圖上物體(units)的數(shù)量、物體的重要性、組(group)的大小、難度或者其他任何 因素來進(jìn)行動(dòng)態(tài)的選擇。取得動(dòng)態(tài)的折衷的

14、一個(gè)方法是，建立一個(gè)啟發(fā)式函數(shù)用于假定通過 一個(gè)網(wǎng)格空間的最小代價(jià)是1，然后建立一個(gè)代價(jià)函數(shù)(cost function)用于測(cè)量(scales):g(n) = 1 + alpha * ( g(n) - 1 )如果alpha是0，則改進(jìn)后的代價(jià)函數(shù)的值總是1。這種情況下，地形代價(jià)被完全忽略， A*工作變成簡(jiǎn)單地判斷一個(gè)網(wǎng)格可否通過。如果alpha是1,則最初的代價(jià)函數(shù)將起作用， 然后你得到了 A*的所有優(yōu)點(diǎn)。你可以設(shè)置alpha的值為0到1的任意值。你也可以考慮對(duì)啟發(fā)式函數(shù)的返回值做選擇：絕對(duì)最小代價(jià)或者期望最小代價(jià)。例如， 如果你的地圖大部分地形是代價(jià)為2的草地，其它一些地方是代價(jià)為1的道路

15、，那么你可 以考慮讓啟發(fā)式函數(shù)不考慮道路，而只返回2*距離。速度和精確度之間的選擇并不是全局的。在地圖上的某些區(qū)域，精確度是重要的，你可 以基于此進(jìn)行動(dòng)態(tài)選擇。例如，假設(shè)我們可能在某點(diǎn)停止重新計(jì)算路徑或者改變方向，則在 接近當(dāng)前位置的地方，選擇一條好的路徑則是更重要的，因此為何要對(duì)后續(xù)路徑的精確度感 到厭煩？或者，對(duì)于在地圖上的一個(gè)安全區(qū)域，最短路徑也許并不十分重要，但是當(dāng)從一個(gè) 敵人的村莊逃跑時(shí)，安全和速度是最重要的。(譯者注：譯者認(rèn)為這里指的是，在安全區(qū)域，i=j w可以考慮不尋找精確的最短路徑而取近似路徑，因此尋路快；但在危險(xiǎn)區(qū)域，逃跑的安全性 和逃跑速度是重要的，即路徑的精確度是重要的

16、，因此可以多花點(diǎn)時(shí)間用于尋找精確路徑。) 2.3測(cè)量單位A*計(jì)算f(n) = g(n) + h(n)。為了對(duì)這兩個(gè)值進(jìn)行相加，這兩個(gè)值必須使用相同的衡量單位。 如果g(n)用小時(shí)來衡量而h(n)用米來衡量，那么A*將會(huì)認(rèn)為g或者h(yuǎn)太大或者太小，因而 你將不能得到正確的路徑，同時(shí)你的A*算法將運(yùn)行得更慢。2.4精確的啟發(fā)式函數(shù)如果你的啟發(fā)式函數(shù)精確地等于實(shí)際最佳路徑(optimal path)，如下一部分的圖中所 示，你會(huì)看到此時(shí)A*擴(kuò)展的結(jié)點(diǎn)將非常少。A*算法內(nèi)部發(fā)生的事情是：在每一結(jié)點(diǎn)它都計(jì) 算f(n) = g(n) + h(n)。當(dāng)h(n)精確地和g(n)匹配(譯者注：原文為match)時(shí)

17、，f(n)的值在 沿著該路徑時(shí)將不會(huì)改變。不在正確路徑(right path)上的所有結(jié)點(diǎn)的f值均大于正確路徑 上的f值(譯者注：正確路徑在這里應(yīng)該是指最短路徑)。如果已經(jīng)有較低f值的結(jié)點(diǎn)，A* 將不考慮f值較高的結(jié)點(diǎn)，因此它肯定不會(huì)偏離最短路徑。2.4.1預(yù)計(jì)算的精確啟發(fā)式函數(shù)構(gòu)造精確啟發(fā)函數(shù)的一種方法是預(yù)先計(jì)算任意一對(duì)結(jié)點(diǎn)之間最短路徑的長(zhǎng)度。在許多游 戲的地圖中這并不可行。然后，有幾種方法可以近似模擬這種啟發(fā)函數(shù)：Fit a coarse grid on top of the fine grid. Precompute the shortest path between any pair

18、of coarse grid locations.Precompute the shortest path between any pair of waypoints. This is a generalization of the coarse grid approach.(譯者：此處不好翻譯，暫時(shí)保留原文)然后添加一個(gè)啟發(fā)函數(shù)用于評(píng)估從任意位置到達(dá)鄰近導(dǎo)航點(diǎn)(waypoints)的代價(jià)。(如 果愿意，后者也可以通過預(yù)計(jì)算得到。)最終的啟發(fā)式函數(shù)可以是：h(n) = h(n, w1) + distance(w1, w2), h(w2, goal)或者如果你希望一個(gè)更好但是更昂貴的啟發(fā)式函數(shù)，

19、則分別用靠近結(jié)點(diǎn)和目標(biāo)的所有的 w1,w2對(duì)對(duì)上式進(jìn)行求值。(譯者注：原文為or if you want a better but more expensive heuristic, evaluate the above with all pairs w1, w2 that are close to the node and the goal, respectively.)2.4.2線性精確啟發(fā)式算法在特殊情況下，你可以不通過預(yù)計(jì)算而讓啟發(fā)式函數(shù)很精確。如果你有一個(gè)不存在障礙 物和slow地形，那么從初始點(diǎn)到目標(biāo)的最短路徑應(yīng)該是一條直線。如果你正使用簡(jiǎn)單的啟發(fā)式函數(shù)(我們不知道地圖上的障礙物)

20、，則它應(yīng)該和精確的啟 發(fā)式函數(shù)相符合(譯者注：原文為match)。如果不是這樣，則你會(huì)遇到衡量單位的問題， 或者你所選擇的啟發(fā)函數(shù)類型的問題。2.5網(wǎng)格地圖中的啟發(fā)式算法在網(wǎng)格地圖中，有一些眾所周知的啟發(fā)式函數(shù)。2.5.1曼哈頓距離標(biāo)準(zhǔn)的啟發(fā)式函數(shù)是曼哈頓距離(Manhattan distance)?？紤]你的代價(jià)函數(shù)并找到從一個(gè) 位置移動(dòng)到鄰近位置的最小代價(jià)D。因此，我的游戲中的啟發(fā)式函數(shù)應(yīng)該是曼哈頓距離的D倍：H(n) = D * (abs ( n.x - goal.x ) + abs ( n.y - goal.y )(Note: the above image has a tie-brea

21、ker added to the heuristic.(譯者注：曼哈頓距離一兩點(diǎn)在南北方向上的距離加上在東西方向上的距離，即D(I, J) =|XI-XJ|+|YI-YJ|。對(duì)于一個(gè)具有正南正北、正東正西方向規(guī)則布局的城鎮(zhèn)街道，從一點(diǎn)到 達(dá)另一點(diǎn)的距離正是在南北方向上旅行的距離加上在東西方向上旅行的距離因此曼哈頓距 離又稱為出租車距離，曼哈頓距離不是距離不變量，當(dāng)坐標(biāo)軸變動(dòng)時(shí)，點(diǎn)間的距離就會(huì)不同 百度知道)2.5.2對(duì)角線距離如果在你的地圖中你允許對(duì)角運(yùn)動(dòng)那么你需要一個(gè)不同的啟發(fā)函數(shù)。(4 east, 4 north)的 曼哈頓距離將變成8*D。然而，你可以簡(jiǎn)單地移動(dòng)(4 northeast)

22、代替，所以啟發(fā)函數(shù)應(yīng)該 是4*D。這個(gè)函數(shù)使用對(duì)角線，假設(shè)直線和對(duì)角線的代價(jià)都是D：h_diagonal(n) = min(abs(n.x - goal.x), abs(n.y - goal.y) h_straight(n) = (abs(n.x - goal.x) + abs(n.y - goal.y)h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)這里，我們計(jì)算h_diagonal(n)：沿著斜線可以移動(dòng)的步數(shù)；h_straight(n)：曼哈頓距離；然 后合并這兩項(xiàng)，讓所有的斜線步都乘以D2,剩下的所有直線步

23、(注意這里是曼哈頓距離的步 數(shù)減去2倍的斜線步數(shù))都乘以D。2.5.3歐幾里得距離如果你的單位可以沿著任意角度移動(dòng)(而不是網(wǎng)格方向)，那么你也許應(yīng)該使用直線距離:h(n) = D * sqrt(n.x-goal.x)A2 + (n.y-goal.y)A2)然而，如果是這樣的話，直接使用A*時(shí)將會(huì)遇到麻煩，因?yàn)榇鷥r(jià)函數(shù)g不會(huì)match啟發(fā)函 數(shù)h。因?yàn)闅W幾里得距離比曼哈頓距離和對(duì)角線距離都短，你仍可以得到最短路徑，不過 A*將運(yùn)行得更久一些：-X _2.5.4平方后的歐幾里得距離我曾經(jīng)看到一些A*的網(wǎng)頁(yè)，其中提到讓你通過使用距離的平方而避免歐幾里得距離中昂貴 的平方根運(yùn)算：h(n) = D *

24、(n.x-goal.x)A2 + (n.y-goal.y)A2)不要這樣做！這明顯地導(dǎo)致衡量單位的問題。當(dāng)A*計(jì)算f(n) = g(n) + h(n),距離的平方將比 g的代價(jià)大很多，并且你會(huì)因?yàn)閱l(fā)式函數(shù)評(píng)估值過高而停止。對(duì)于更長(zhǎng)的距離，這樣做會(huì) 靠近g(n)的極端情況而不再計(jì)算任何東西，入*退化成BFS：2.5.5 決勝法(Breaking ties)為了解決這個(gè)問題，我們可以為啟發(fā)函數(shù)添加一個(gè)附加值（譯者注:原文為small tie breaker）。 附加值對(duì)于結(jié)點(diǎn)必須是確定性的（也就是說，不能是隨機(jī)的數(shù)），而且它必須讓f值體現(xiàn)區(qū) 別。因?yàn)锳*對(duì)f值排序，讓f值不同意味著只有一個(gè)equ

25、ivalent ”的f值會(huì)被檢測(cè)。一種添加附加值的方式是稍微改變（譯者注：原文為nudge）h的衡量單位。如果我們減少 衡量單位（譯者注：原文為scale it downwards），那么當(dāng)我們朝著目標(biāo)移動(dòng)的時(shí)候f將逐 漸增加。很不幸，這意味著A*傾向于擴(kuò)展到靠近初始點(diǎn)的結(jié)點(diǎn)，而不是靠近目標(biāo)的結(jié)點(diǎn)。我們可以增加衡量單位（譯者注：原文為scale it downwards scale h upwards slightly）（甚 至是0.1%），A*就會(huì)傾向于擴(kuò)展到靠近目標(biāo)的結(jié)點(diǎn)。heuristic *= （1.0 + p）選擇因子p使得p 移動(dòng)一步（step）的最小代價(jià)/期望的最長(zhǎng)路徑長(zhǎng)度。假設(shè)

26、你不希望你Tie-breaking scaling added to heuristic.當(dāng)存在障礙物時(shí)，當(dāng)然仍要在它們周圍尋找路徑，但要意識(shí)到，當(dāng)繞過障礙物以后，A*搜 索的區(qū)域非常少：Tie-breaking scaling added to heuristic, works nicely with obstacles.Steven van Dijk建議，一個(gè)更直截了當(dāng)?shù)姆椒ㄊ前裩傳遞到比較函數(shù)(comparison function)。 當(dāng)f值相等時(shí)，比較函數(shù)檢查h,然后添加附加值。一個(gè)不同的添加附加值的方法是，傾向于從初始點(diǎn)到目標(biāo)點(diǎn)的連線(直線)：dx1 = current.x - g

27、oal.xdy1 = current.y - goal.ydx2 = start.x - goal.xdy2 = start.y - goal.ycross = abs(dx1*dy2 - dx2*dy1)heuristic += cross*0.001這段代碼計(jì)算初始-目標(biāo)向量(start to goal vector)和當(dāng)前-目標(biāo)向量(current point to goal vector)的向量叉積(vector cross-product)。When these vectors dont line up, the cross product will be larger.結(jié)果是，這段

28、代碼選擇的路徑稍微傾向于從初始點(diǎn)到目標(biāo)點(diǎn)的直線。當(dāng)沒有障礙物時(shí)，A*不僅搜索很少的區(qū)域，而且它找到的路徑看起來非常棒：Tie-breaking cross-product added to heuristic, produces pretty paths.然而，因?yàn)檫@種附加值傾向于從初始點(diǎn)到目標(biāo)點(diǎn)的直線路徑，當(dāng)出現(xiàn)障礙物時(shí)將會(huì)出現(xiàn)奇怪 的結(jié)果（注意這條路徑仍是最佳的，只是看起來很奇怪）：Tie-breaking cross-product added to heuristic, less pretty with obstacles.為了交互地研究這種附加值方法的改進(jìn)，請(qǐng)參考James Macg

29、ill的A*確applet( HYPERLINK http:/www.ccg.leeds.ac.uk/james/aStar/)%5b%e5%a6%82%e6%9e%9c%e9%93%be%e6%8e%a5%e6%97%a0%e6%95%88%ef%bc%8c%e8%af%b7%e4%bd%bf%e7%94%a8%e8%bf%99%e4%b8%aa%e9%95%9c%e5%83%8f http:/www.ccg.leeds.ac.uk/james/aStar/)如果鏈接無效，請(qǐng)使用這個(gè)鏡像( HYPERLINK http:/www.vision.ee.ethz.ch/buc/astar/ASt

30、ar.html)%5d(%e8%af%91%e8%80%85%e6%b3%a8%ef%bc%9a%e4%b8%a4%e4%b8%aa%e9%93%be%e6%8e%a5%e5%9d%87%e6%97%a0%e6%95%88)%e3%80%82%e4%bd%bf http:/www.vision.ee.ethz.ch/buc/astar/AStar.html)(譯者注：兩個(gè)鏈接均無效)。使 用“Clear”以清除地圖，選擇地圖對(duì)角的兩個(gè)點(diǎn)。當(dāng)你使用“ Classic A*”方法，你會(huì)看到附加 值的效果。當(dāng)你使用“Fudge ”方法，你會(huì)看到上面給啟發(fā)函數(shù)添加叉積后的效果。然而另一種添加附加值的方

31、法是，小心地構(gòu)造你的A*優(yōu)先隊(duì)列，使新插入的具有特殊f值 的結(jié)點(diǎn)總是比那些以前插入的具有相同f值的舊結(jié)點(diǎn)要好一些。你也許也想看看能夠更靈活地(譯者注：原文為sophisticated)添加附加值的AlphA*算法( HYPERLINK http:/home1.stofanet.dk/breese/papers.html)%ef%bc%8c%e4%b8%8d%e8%bf%87%e7%94%a8%e8%bf%99%e7%a7%8d%e7%ae%97%e6%b3%95%e5%be%97%e5%88%b0%e7%9a%84%e8%b7%af%e5%be%84%e6%98%af%e5%90%a6%e8%

32、83%bd%e8%be%be%e5%88%b0 http:/home1.stofanet.dk/breese/papers.html)，不過用這種算法得到的路徑是否能達(dá)到 最佳仍在研究中。AlphA*具有較好的適應(yīng)性，而且可能比我在上面討論的附加值方法運(yùn)行 得都要好。然而，我所討論的附加值方法非常容易實(shí)現(xiàn)，所以從它們開始吧，如果你需要得 到更好的效果，再去嘗試AlphA*。2.5.6多重的搜索如果你想搜索鄰近目標(biāo)的任意不確定結(jié)點(diǎn)，而不是某個(gè)特定的結(jié)點(diǎn)，你應(yīng)該建立一個(gè)啟 發(fā)函數(shù)h(x)，使得h(x)為h1(x), h2(x), h3(x)。的最小值，而這些h1, h2, h3是鄰近結(jié) 點(diǎn)的啟發(fā)函

33、數(shù)。然而，一種更快的方法是讓A*僅搜索目標(biāo)區(qū)域的中心。一旦你從OPEN集 合中取得任意一個(gè)鄰近目標(biāo)的結(jié)點(diǎn)，你就可以停止搜索并建立一條路徑了。3人*算法的變種3.1集束搜索在A*的主循環(huán)中,OPEN集保存所有需要檢查的結(jié)點(diǎn)Beam Search是A*算法的一個(gè)變種， 這種算法限定了 OPEN集的尺寸。如果OPEN集變得過大，那些沒有機(jī)會(huì)通向一條好的路 徑的結(jié)點(diǎn)將被拋棄。缺點(diǎn)是你必須讓排序你的集合以實(shí)現(xiàn)這個(gè)，這限制了可供選擇的數(shù)據(jù)結(jié) 構(gòu)。3.2迭代深化迭代深化是一種在許多AI算法中使用的方法，這種方法從一個(gè)近似解開始，逐漸得到更精 確的解。該名稱來源于游戲樹搜索，需要查看前面幾步(比如在象棋里)，

34、通過查看前面更 多步來提高樹的深度。一旦你的解不再有更多的改變或者改善，就可以認(rèn)為你已經(jīng)得到足夠 好的解，當(dāng)你想要進(jìn)一步精確化時(shí)，它不會(huì)再有改善。在ID-A*中，深度是f值的一個(gè)cutoffo 當(dāng)f的值太大時(shí)，結(jié)點(diǎn)甚至將不被考慮(例如，它不會(huì)被加入OPEN集中)。第一次迭代 只處理很少的結(jié)點(diǎn)。此后每一次迭代，訪問的結(jié)點(diǎn)都將增加。如果你發(fā)現(xiàn)路徑有所改善，那 么就繼續(xù)增加cutoff，否則就可以停止了。更多的細(xì)節(jié)請(qǐng)參考這些關(guān)于ID-A*的資料： HYPERLINK /hall/AI-Programming/IDA-Star.htmlo /hall/AI-Programming/IDA-Star.h

35、tmlo我本人認(rèn)為在游戲地圖中沒有太大的必要使用ID-A*尋路。ID算法趨向于增加計(jì)算時(shí)間而減 少內(nèi)存需求。然而在地圖路徑搜索中，“結(jié)點(diǎn)”是很小的一它們僅僅是坐標(biāo)而已。我認(rèn)為不 保存這些結(jié)點(diǎn)以節(jié)省空間并不會(huì)帶來多大改進(jìn)。i=jI三m3.3動(dòng)態(tài)衡量在動(dòng)態(tài)衡量中，你假設(shè)在開始搜索時(shí)，最重要的是訊速移動(dòng)到任意位置；而在搜索接近結(jié)束 時(shí)，最重要的是移動(dòng)到目標(biāo)點(diǎn)。f(p) = g(p) + w(p) * h(p)啟發(fā)函數(shù)中帶有一個(gè)權(quán)值(weight)(w=1 )。當(dāng)你接近目標(biāo)時(shí)，你降低這個(gè)權(quán)值；這降 低了啟發(fā)函數(shù)的重要性，同時(shí)增加了路徑真實(shí)代價(jià)的相對(duì)重要性。3.4帶寬搜索帶寬搜索(Bandwidth S

36、earch)有兩個(gè)對(duì)有些人也許有用的特性。這個(gè)變種假設(shè)h是過高 估計(jì)的值，但不高于某個(gè)數(shù)e。如果這就是你遇到的情況，那么你得到的路徑的代價(jià)將不會(huì) 比最佳路徑的代價(jià)超過。重申一次，你的啟發(fā)函數(shù)設(shè)計(jì)的越好，最終效果就越好。另一個(gè)特性是，你可以丟棄OPEN集中的某些結(jié)點(diǎn)。當(dāng)h+d比路徑的真實(shí)代價(jià)高的時(shí)候(對(duì) 于某些d)，你可以丟棄那些f值比OPEN集中的最好結(jié)點(diǎn)的f值高至少e+d的結(jié)點(diǎn)。這是 一個(gè)奇怪的特性。對(duì)于好的f值你有一個(gè)“范圍”(band)，任何在這個(gè)范圍之外的結(jié)點(diǎn)都 可以被丟棄掉，因?yàn)檫@個(gè)結(jié)點(diǎn)肯定不會(huì)在最佳路徑上。好奇地(Curiously)，你可以對(duì)這兩種特性使用不同的啟發(fā)函數(shù)，而問題仍

37、然可以得到解 決。使用一個(gè)啟發(fā)函數(shù)以保證你得到的路徑不會(huì)太差，另一個(gè)用于檢查從OPEN集中去掉 哪些結(jié)點(diǎn)。3.5雙向搜索與從開始點(diǎn)向目標(biāo)點(diǎn)搜索不同的是，你也可以并行地進(jìn)行兩個(gè)搜索一一一個(gè)從開始點(diǎn)向目標(biāo) 點(diǎn)，另一個(gè)從目標(biāo)點(diǎn)向開始點(diǎn)。當(dāng)它們相遇時(shí)，你將得到一條好的路徑。這聽起來是個(gè)好主意，但我不會(huì)給你講很多內(nèi)容。雙向搜索的思想是，搜索過程生成了一棵 在地圖上散開的樹。一棵大樹比兩棵小樹差得多，所以最好是使用兩棵較小的搜索樹。然而 我的試驗(yàn)表明，在A*中你得不到一棵樹，而只是在搜索地圖中當(dāng)前位置附近的區(qū)域，但是 又不像Dijkstra算法那樣散開。事實(shí)上，這就是讓A*算法運(yùn)行得如此快的原因無論你 的

38、路徑有多長(zhǎng)，它并不進(jìn)行瘋狂的搜索，除非路徑是瘋狂的。它只嘗試搜索地圖上小范圍的 區(qū)域。如果你的地圖很復(fù)雜，雙向搜索會(huì)更有用。面對(duì)面的方法(The front-to-fr(vatriation)把這兩種搜索結(jié)合在一起。這種算法選擇一對(duì) 具有最好的g(start,x) + h(x,y) + g(y,goal)的結(jié)點(diǎn)，而不是選擇最好的前向搜索結(jié)點(diǎn) g(start,x) + h(x,goal)，或者最好的后向搜索結(jié)點(diǎn)g(y,goal) + h(start,y)。Retargeting方法不允許前向和后向搜索同時(shí)發(fā)生。它朝著某個(gè)最佳的中間結(jié)點(diǎn)運(yùn)行前向搜 索一段時(shí)間，然后再朝這個(gè)結(jié)點(diǎn)運(yùn)行后向搜索。然后選擇

39、一個(gè)后向最佳中間結(jié)點(diǎn)，從前向最 佳中間結(jié)點(diǎn)向后向最佳中間結(jié)點(diǎn)搜索。一直進(jìn)行這個(gè)過程，直到兩個(gè)中間結(jié)點(diǎn)碰到一塊。3.6動(dòng)態(tài)A*與終身計(jì)劃A*有一些A*的變種允許當(dāng)初始路徑計(jì)算出來之后，世界發(fā)生改變。D*用于當(dāng)你沒有全局所有 信息的時(shí)候。如果你沒有所有的信息，A*可能會(huì)出錯(cuò)；D*的貢獻(xiàn)在于，它能糾正那些錯(cuò)誤 而不用過多的時(shí)間。LPA*用于代價(jià)會(huì)改變的情況。在A*中，當(dāng)?shù)貓D發(fā)生改變時(shí)，路徑將變 得無效；LPA*可以重新使用之前A*的計(jì)算結(jié)果并產(chǎn)生新的路徑。然而，D*和LPA*都需要 很多內(nèi)存一用于運(yùn)行A*并保存它的內(nèi)部信息(OPEN和CLOSED集，路徑樹，g值)， 當(dāng)?shù)貓D發(fā)生改變時(shí)，D*或者LPA

40、*會(huì)告訴你，是否需要就地圖的改變對(duì)路徑作調(diào)整。在一個(gè) 有許多運(yùn)動(dòng)著的物體的游戲中，你經(jīng)常不希望保存所有這些信息，所以D*和LPA*在這里并 不適用。它們是為機(jī)器人技術(shù)而設(shè)計(jì)的，這種情況下只有一個(gè)機(jī)器人一你不需要為別的機(jī) 器人尋路而重用內(nèi)存。如果你的游戲只有一個(gè)或者少數(shù)幾個(gè)物體，你可以研究一下D*或者 LPA*。Overview of D*( HYPERLINK /axs/dynamic_plan.html /axs/dynamic_plan.html)D* Paper 1 (http:/ HYPERLINK /axs/doc/icra94.ps /axs/doc/icra94.ps)D* Pa

41、per 2(http:/ HYPERLINK /axs/doc/ijcai95.ps /axs/doc/ijcai95.ps)Lifelong planning overview( HYPERLINK /project-a.html /project-a.html)Lifelong planning paper (PDF)( HYPERLINK /UMMCsciwiki/pub/ /UMMCsciwiki/pub/ Csci3903s03/KellysPaper/seminar.pdf) Lifelong planning A* applet ( HYPERLINK /applet.html

42、/applet.html)4預(yù)計(jì)算路徑的空間代價(jià)有時(shí)，路徑計(jì)算的限制因素不是時(shí)間，而是用于數(shù)以百計(jì)的物體的存儲(chǔ)空間。路徑搜索器需 要空間以運(yùn)行算法和保存路徑。算法運(yùn)行所需的臨時(shí)空間（在A*中是OPEN和CLOSED 集）通常比保存結(jié)果路徑的空間大許多。通過限制在一定的時(shí)間計(jì)算一條路徑，可以把臨時(shí) 空間數(shù)量最小化。另外，為OPEN和CLOSED集所選擇的數(shù)據(jù)結(jié)構(gòu)的不同，最小化臨時(shí)空 間的程度也有很大的不同。這一部分聚集于優(yōu)化用于計(jì)算路徑的空間代價(jià)。4.1位置VS方向一條路徑可以用位置或者方向來表示。位置需要更多的空間，但是有一個(gè)優(yōu)點(diǎn)，易于查詢路 徑中的任意位置或者方向而不用沿著路徑移動(dòng)。當(dāng)保存方

43、向時(shí)，只有方向容易被查詢；只有 沿著整個(gè)路徑移動(dòng)才能查詢位置。在一個(gè)典形的網(wǎng)格地圖中，位置可以被保存為兩個(gè)16位 整數(shù)，每走一步是32位。而方向是很少的，因此用極少的空間就夠了。如果物體只能沿著 四個(gè)方向移動(dòng)，每一步用兩位就夠了；如果物體能沿著6個(gè)或者8個(gè)方向移動(dòng)，每一步也 只需要三位。這些對(duì)于保存路徑中的位置都有明顯的空間節(jié)省。HannuKankaanpaa指出可 以進(jìn)一步減少空間需求，那就是保存相對(duì)方向（右旋60度）而不是絕對(duì)方向（朝北走）。 有些相對(duì)方向?qū)δ承┪矬w來說意義不大。比如，如果你的物體朝北移動(dòng)，那么下一步朝南移 動(dòng)的可能性很小。在只有六種方向的游戲中，你只有五個(gè)有意義的方向。在某些地圖中，也 許只有三個(gè)方向（直走，左旋60度，右旋60度）有意義，而其它地圖中，右旋120度是 有效的（比如，沿著陡峭的山坡走之字形的路徑時(shí)）。4.2路徑壓縮一旦找到一條路徑，可以對(duì)它進(jìn)行壓縮?？梢杂靡粋€(gè)普通的壓縮算法，但這里不進(jìn)行討論。使用特定的壓縮算法可以縮小路徑的存儲(chǔ)，無論它是基于位置的還是基于方向的。在做決定 之前，考察你的游戲中的路徑以確定哪種壓縮效果最好。另外還要考慮實(shí)現(xiàn)和調(diào)試，代碼量， and whether it really matters如果你有300個(gè)物體并且在同一時(shí)刻只有50個(gè)在移動(dòng)，同時(shí) 路徑比較短（100步），內(nèi)存總需求大概只有不到50k，總之，沒