定向搜索

在A*算法的循環(huán)中，OPEN集合用來保存所有用于尋找路徑的被搜索節(jié)點。定向搜索是在A*算法基礎(chǔ)上，通過對OPEN集合大小設(shè)置約束條件而得到的變體算法。當(dāng)集合太大的時候，最不可能出現(xiàn)在最優(yōu)路徑上的節(jié)點將會被剔除。這樣做會帶來一個缺點：由于必須得保持這樣的篩選，所以可選擇的數(shù)據(jù)結(jié)構(gòu)類型會受到限制。

迭代深化（Iterative deepening）

迭代深化是一種很多AI算法采用的方法，開始的時候給一個估計值，然后通過迭代使它越來越精確。這個名字來源于游戲樹搜索中對接下來幾次操作的提前預(yù)判（例如，在象棋游戲中）。你可以通過向前預(yù)判更多的操作來深化游戲樹。一旦當(dāng)你的結(jié)果不發(fā)生變化或提高很多，就可以認(rèn)為你已經(jīng)得到了一個非常好的結(jié)果，即使讓它更精確，結(jié)果也不會再改善。在迭代深化A*(IDA*)算法中，“深度”是 f 值當(dāng)前的一個截斷值。當(dāng) f 值太大的時候，節(jié)點不會被考慮（也就是說，不會被加入到OPEN集中）。第一次循環(huán)時，只需要處理非常少的節(jié)點。隨后的每次循環(huán)，都會增加訪問的節(jié)點數(shù)。如果發(fā)現(xiàn)路徑得到優(yōu)化，就繼續(xù)增加當(dāng)前的截斷值，否則結(jié)束。更多細(xì)節(jié)，參見鏈接。

我個人并不看好IDA*算法在游戲地圖尋路中的應(yīng)用。迭代深化的算法往往增加了計算時間，同時降低了內(nèi)存需求。然而，在地圖尋路的場景中，節(jié)點僅僅包含坐標(biāo)信息，所需要的內(nèi)存非常小。所以減少這部分內(nèi)存開銷并不會帶來什么優(yōu)勢。

動態(tài)加權(quán)

在動態(tài)加權(quán)算法中，你假定在搜索開始時快速達(dá)到(任意)一個位置更為重要，在搜索結(jié)束時到達(dá)目標(biāo)位置更為重要。

f(p) = g(p) + w(p) * h(p)

有一個權(quán)值(w >=  1 )和該啟發(fā)式關(guān)聯(lián)。當(dāng)不斷接近目標(biāo)位置的時候，權(quán)重值也不斷降低。這樣降低了啟發(fā)式函數(shù)的重要性，并增加了路徑實際代價的相對重要性。

帶寬搜索

帶寬搜索有兩個被認(rèn)為非常有用的特性。這個算法變體假設(shè) h 是一個估計過高的值，但它的估計誤差不會超過 e。那么在這樣的條件下，搜索到的路徑代價與最優(yōu)路徑代價的誤差不會超過 e。這里需要再一次強(qiáng)調(diào)，啟發(fā)值設(shè)置得越好，那么得到的結(jié)果也將越好。

另外一個特性是用來判斷你是否可以刪掉OPEN集合中的某些節(jié)點。只要 h+d 大于路徑真實代價（對于一些 d），那么你可以丟掉任意滿足其 f 值比OPEN集合中最優(yōu)節(jié)點 f 值至少大 e+d 的節(jié)點。這是一個很奇異的特性。你相當(dāng)于得到了一個 f 值的帶寬；所有在這個帶寬意外的節(jié)點都可以被丟棄掉，因為他們被保證一定不會出現(xiàn)在最優(yōu)路徑中。

有意思地是，對于這兩種特性分別使用不同的啟發(fā)值，仍然可以計算得到結(jié)果。你可以使用一個啟發(fā)值來保證路徑代價不會太大，另外一個啟發(fā)值來決定丟棄掉OPEN集中的哪些節(jié)點。

雙向搜索

與從頭到尾的搜索不同，你也可以并行地同時進(jìn)行兩個搜索，一個從開始到結(jié)束，一個從結(jié)束到開始。當(dāng)它們相遇的時候，你就會得到一個最優(yōu)路徑。

這個想法在一些情況下非常有用。雙向搜索的主要思想是：搜索結(jié)果會形成一個在地圖上呈扇形展開的樹。而一個大的樹遠(yuǎn)不如兩個小的樹，所以使用兩個小的搜索樹更好。

面對面的變體將兩個搜索結(jié)果鏈接到一起。該算法選擇滿足最佳 g(start,x) + h(x,y) + g(y,goal) 的一對節(jié)點，而不是選擇最佳前向搜索節(jié)點 g(start,x) + h(x,goal) 或者最佳后向搜索節(jié)點 g(y,goal) + h(start,y)。

重定向算法放棄同時前向和后向的搜索方法。該算法首先進(jìn)行一個短暫的前向搜索，并選出一個最佳的前向候選節(jié)點。接著進(jìn)行后向搜索。此時，后向搜索不是朝向開始節(jié)點，而是朝向剛剛得到的前向候選節(jié)點。后向搜索也會選出一個最佳后向搜索節(jié)點。然后下一步，再運(yùn)行前向搜索，從當(dāng)前的前向候選節(jié)點到后向候選節(jié)點。這個過程將會不斷重復(fù)，直到兩個后選節(jié)點重合。

動態(tài)A*與終身規(guī)劃A*

有一些A*的變體算法允許初始路徑計算之后地圖發(fā)生改變。動態(tài)A*可以用于在不知道全部地圖信息的情況進(jìn)行尋路。如果沒有全部信息，那么A*算法的計算可能會出現(xiàn)錯誤，動態(tài)A*的優(yōu)勢在于可以快速改正那些錯誤而不會花費(fèi)很多時間。終身規(guī)劃A*算法可以用于代價發(fā)生改變的情況。當(dāng)?shù)貓D發(fā)生改變的時候，A*計算得到路徑可能會失效；終身規(guī)劃A*可以重復(fù)利用以前的A*計算來產(chǎn)生新的路徑。

然而，動態(tài)A*與終身規(guī)劃A*都要求大量的空間——運(yùn)行A*算法時需要保持它的內(nèi)部信息（OPEN/CLOSED集合，路徑樹，g值）。當(dāng)路徑發(fā)生改變的時候，動態(tài)A*或終身規(guī)劃A*算法會告訴你是否需要根據(jù)地圖的變化調(diào)整你的路徑。

對于一個有大量運(yùn)動單元的游戲，通常不會想要保存所有的信息，所以動態(tài)D*和終身規(guī)劃A*可能不適用。這兩種算法主要為機(jī)器人而設(shè)計。當(dāng)只有一個機(jī)器人的時候，你不需要為了其他機(jī)器人的路徑來重復(fù)使用內(nèi)存。如果你的游戲只有一個或比較少的單元，你能會想要研究一下動態(tài)A*或者終身規(guī)劃A*算法。

D*算法概述

D*文章1

D*文章2

終身規(guī)劃算法概述

終身規(guī)劃算法論文(PDF)

終身規(guī)劃 A*算法 applet

跳躍點搜索

提高A*算法計算速度的大多數(shù)技術(shù)都是采取減少節(jié)點數(shù)量的策略。在統(tǒng)一代價的方格網(wǎng)絡(luò)中，每次單獨(dú)搜索一個獨(dú)立格空間是非常浪費(fèi)的。一個解決辦法是對其中關(guān)鍵節(jié)點（例如拐角）建立一個用來進(jìn)行尋路的圖。但是，沒有人愿意預(yù)先計算出一個路標(biāo)圖，那就來看看可以在網(wǎng)格圖上向前跳躍的A*變體算法，跳躍點搜索。 考慮到當(dāng)前節(jié)點的孩子節(jié)點有可能會出現(xiàn)在OPEN集合中，跳躍點搜索直接跳躍到從當(dāng)前點可看到的遙遠(yuǎn)的節(jié)點。隨著OPEN集合中節(jié)點的不斷減少，每一步的代價都會越來越高雖然都很高，但是步數(shù)也會越來越少。相關(guān)細(xì)節(jié)，可以參考鏈接；這篇博客中有很好的可視化解釋；還有，reddit上對優(yōu)缺點的討論可點擊這個鏈接。

此外，在矩形對稱消減中，有對地圖進(jìn)行分析和圖中嵌入跳躍。這兩種技術(shù)都是應(yīng)用于方格網(wǎng)絡(luò)圖中的。

Theta*

有時網(wǎng)格會用來尋路是因為地圖是用網(wǎng)格來生成，而不是因為真的要在網(wǎng)格上移動。如果給定一個關(guān)鍵點的圖（例如拐角）而不是網(wǎng)格的話，A*算法可以運(yùn)行得更快并得到更優(yōu)的路徑。但是，如果你不想預(yù)先計算那些圖的拐角，你可以通過A*算法的變體Theta*在方格網(wǎng)絡(luò)上進(jìn)行尋路而不必嚴(yán)格遵循那些方格。當(dāng)構(gòu)建父親指針的時候，如果有一個祖先與該節(jié)點間存在邊，那么Theta*算法會直接將該指針指向該祖先而忽略所有的中間節(jié)點。不像路徑光滑那樣將A*找到的路徑變?yōu)橹本€，Theta*可以把那些路徑的分析作為A*算法過程的一部分。這樣的做法可以比后處理方格路徑使之成為任意傾角的路徑的方式，可以得到更短的路徑。這篇文章的是對算法的一個比較合理的介紹，另外可參考懶惰Theta*。

Theta*的思路也可能被應(yīng)用于導(dǎo)航網(wǎng)格。

更多信息請查看IT技術(shù)專欄