從人類的思維方式中尋找啟示宏觀～微觀尋徑算法（1）

1、從人類的思維方式中尋找啟示宏觀微觀尋徑算法1尋找路徑是游戲中人工智能的一個重要的主題。 特別是即時戰(zhàn)略游戲隨著游戲場景的增大，游戲場景的維數(shù)的擴充，游戲中參加尋徑的智能體數(shù)目的增多，尋徑的時間和空間開銷都將會成為影響游戲性能重要因素。本文提出一種新的尋徑算法思路：宏觀微觀(MacToMic)尋徑算法。這種尋徑算法思路相對于傳統(tǒng)的尋徑算法思路來說，更加類似于人human-like的思維模式。它結(jié)合了人類宏觀啟發(fā)式思維的優(yōu)勢和計算機微觀處理的速度優(yōu)勢而產(chǎn)生的高效的尋徑算法。傳統(tǒng)的尋徑算法及其弊端傳統(tǒng)的尋徑算法及其弊端傳統(tǒng)的尋徑算法比方廣度優(yōu)先算法和 AStar 算法都是基于單個節(jié)點進行尋徑的。這種

2、算法模式具有明顯的局限性尋徑的效率時間和空間開銷受制于尋徑場景的節(jié)點數(shù)目，更進一步說就是受制于場景的精細程度而不是地圖的復(fù)雜程度。雖然從地圖的結(jié)構(gòu)來說，圖 1 和圖 2 是完全一樣的。 圖 1 圖 2但是對于基于節(jié)點搜索的廣度優(yōu)先算法和 AStar 算法來說它們并不會等同看待，而是在圖 1 中所付出的尋徑代價遠高于圖 2。當(dāng)然在這個 1010 的地圖上面問題的嚴(yán)重性并不明顯，但如果是在一個 10001000 的地圖涉及到 1000000 個節(jié)點的時候呢？更別說在一個100010001000 涉及到 1000000000 個節(jié)點的三維場景中了，這簡直是一場惡夢！從人類的思維方式中尋求啟示從人類的

3、思維方式中尋求啟示對于同樣的任務(wù)，人類的方法就高明得多了。人類壓根兒不受網(wǎng)格的“束縛。在人類的眼中地圖就如下所示：當(dāng)然，讓計算機超越“網(wǎng)格還不是那么容易的事情，因為對于計算機來說矩形實在太“優(yōu)美了！讀者可以嘗試在上面的地圖上面尋找兩輛轎車之間的路徑最好嘗試把這條路徑畫出來 ，體會一下你自己是怎么尋找路徑的。如果我估計得不錯，我想你先觀望一下兩輛車各自的位置，然后大致上找到一條可通行的路徑，最后在你畫出路徑的時候，你會按照你先前大致找到的路徑的方向畫出一條繞開所有障礙的路徑?？偨Y(jié)來說人類尋徑的速度跟一張地圖的復(fù)雜度，而不是一張地圖的網(wǎng)格多少有關(guān)，而這些傳統(tǒng)的尋徑算法明顯跟后者的關(guān)系大一些。較前沿

4、的尋徑算法研究其實也正朝著這個方向，比方導(dǎo)航點法，還有分解矩形法等，讓搜索節(jié)點數(shù)大大減小。但這些算法，都存在一些問題，比方導(dǎo)航點需要人為地設(shè)置，分解矩形法并沒有很好地減小搜索的節(jié)點數(shù)。下面是從 PaulTozour 的尋徑算法演示平臺里面得到的一些圖片。 導(dǎo)航點法 分解矩形法為了設(shè)計一種具有人這種能夠從“宏觀上尋徑的計算機算法，我們回憶一下自己在一張地圖上面尋找兩點之間的較短路徑的時候所做的工作流程，我首先會大致地掃描一下地圖，大體地找到最短路徑的“輪廓或許這樣說缺乏準(zhǔn)確，但是我想你能理解。 然后接下來在細致地“區(qū)分出最短路徑。其實這個過程對一個人來說是非常自然的，但是我們怎么能用計算機算法來

5、實現(xiàn)這樣“模糊“的概念呢？人和計算機畢竟有不同，我們不能像劃分圖多邊形那樣處理，因為經(jīng)過那樣的處理后，對于計算機來說依然很“模糊。最后我決定讓地圖分成很多較大的格子并通過預(yù)計算來處理這些格子之間的連通關(guān)系，然后在后續(xù)的尋徑過程中可以大大地減少所需要搜索點的數(shù)目，事實上在某些情況下，還可以用最簡單的試探式尋徑從而更加減少廣度優(yōu)先搜索的開銷，或 AStar 算法估值的開銷，而且搜索出來的路徑還特別自然！計算機和人不同，計算機總是認(rèn)為正立的矩形相對于其它多邊形更加親切一些，這跟我們建立的笛卡兒坐標(biāo)系有關(guān) 。宏觀微觀宏觀微觀(MacToMic)(MacToMic)尋徑算法尋徑算法簡化的宏觀微觀尋徑算法

6、簡化的宏觀微觀尋徑算法1 1預(yù)處理過程預(yù)處理過程遵照人類的思維方式，第一步是宏觀地觀察觀察地圖，所以在這個算法的第一步就是把地圖分塊，但并不像前面提到的那些尋徑算法的分塊方式通過很復(fù)雜的算法把地圖分成大小不等而雜亂的很多塊，而是簡單地把地圖分成大小相等的很多個小長方形，為了方便陳述，我舉個例子，比方現(xiàn)在我們在一個 2525 象素的正方形地圖上面尋徑，我們可以把整個地圖分塊成 25 個 55 的正方形。第二個步驟是在每一個正方形小塊的非障礙物點上面使用廣度優(yōu)先算法。當(dāng)然，這個廣度優(yōu)先算法只有起始點而沒有目標(biāo)點，目的是得到該正方形小塊與其上下左右四塊小正方形小塊的連通性就是說是否存在一條路徑使到兩

7、個正方形小塊直接連通，注意是直接，就是說邊界上是否有連通點，當(dāng)然使用廣度優(yōu)先而不是簡單的判斷邊界還有另外的目的，就是測試出本來的正方形小塊本身是否是連通的，如果沒有連通需要特殊處理，這里先不要考慮這種情況，方便理解算法。 如果，0 代表障礙，1 代表可行的話，那么下面的是 4個分塊之間的連通關(guān)系：左上與右上連通，左上與左下不連通，右上與右下不連通，左下與右下連通。當(dāng)我們完成對每一個小塊進行上面的處理后，我們將得到一個表：每一個小塊為搜索關(guān)鍵字，能夠得到與該小塊直接連通的小塊的搜索關(guān)鍵字。 更抽象層次來說，其實這個表描述的就是一個關(guān)于節(jié)點之間是否相連的無向圖。 一二步驟就完成了簡化情況下的預(yù)處理

8、過程。 一旦完成預(yù)處理過程，對于同一幅地圖就不需要重復(fù)預(yù)處理了，就是說后續(xù)的尋徑過程都是基于這個預(yù)處理結(jié)果的。 2 2尋徑過程尋徑過程預(yù)處理完成后，可以開始尋找路徑了。先判斷待搜索的點分別屬于哪兩個正方形小塊當(dāng)然也許是處于同一個小塊，這樣的時候就用傳統(tǒng)的算法處理 ，然后通過 Astar 或者干脆用廣度優(yōu)先算法搜索出這兩個正方小塊之間的最短路徑這個路徑當(dāng)然是由小正方塊為單位構(gòu)成的，如果你還記得的話，每個小正方塊是 55 的 。到了這步，我們就減少了很多需要搜索的點的數(shù)目，我們自然可以使用 Astar 算法或者廣度優(yōu)先算法在剩下的正方形小塊里面以一個象素為搜索節(jié)點單位來搜索出始末點之間的最短路徑。

9、不過，更簡單快捷地我們可以試探法來得到一條看起來更自然的路徑?？梢韵胂蟪?，我們現(xiàn)在得到的搜索空間是一條寬為 5 的帶子形區(qū)域最短路徑就存在于這個帶子范圍里面。 ，我們可以從起始點開始，以接下來一個相鄰的正方形小塊的中點為目標(biāo)走過去這個過程具體是判斷當(dāng)前點和下一個相鄰正方形小塊的中點的坐標(biāo)關(guān)系，比方，如果橫坐標(biāo)大一些，就向著減小的方向走，縱坐標(biāo)大些，向著減小的走，如果兩個都小了，就斜走。 當(dāng)當(dāng)前點一旦踏入下一個正方形小塊，就立即把參考點改為再下面一個正方形小塊的中點，一直下去，如果順利的話，就能夠很便捷地找到看起來比擬自然的路徑，如果不順利，一般是因為走進死胡同了，那么就走出來，再向沒走過的方向

10、走，肯定能走到終點。 尋徑的過程是這個算法的重要步驟，如果文字的說明大家不能很好地理解，那么請大家運行我做的算法演示程序，從那個程序的演示功能會讓大家很容易地把握算法的搜索過程。 宏觀微觀算法在大格子里面的搜索演示宏觀微觀算法在小格子里面的搜索演示到了這里這個算法的簡化版就算結(jié)束了。完整的宏觀微觀尋徑算法完整的宏觀微觀尋徑算法當(dāng)然，僅僅像上面那樣做的話，算法速度的提高還不算很多，比方搜索一個 125125的地圖的時候，我們把地圖分成 625 塊 55 的小塊，這樣的話我們還得在一個有 625 塊節(jié)點的地圖上面搜索。但是應(yīng)用上面算法的思想與及迭代的思想迭代的思想相結(jié)合把小塊本身看成是一個尋徑的單

11、位，對于這些小塊組成的地圖再進行一次“宏觀的處理把 55 塊55 的小塊看成是一個大塊。所以對于 125125 的地圖我們第一步是把這個地圖分成55 塊正方形，每塊正方形的大小是 2525，然后列出這些正方形的鄰接表。接著把125125 的地圖分成 2525 塊 55 的正方形塊，然后再列出這些小塊之間的鄰接表。讀者最好按照這個例子粗略畫出一個草圖，那樣更容易理解這個迭代過程搜索的時候第一步就是判斷兩個正方形處于哪兩個大正方形2525上，然后就用Astar 或者廣度優(yōu)先找出最短路徑，路徑單位是大正方形，然后再判斷這兩個點在哪兩個小正方形55里面，然后以上一個步驟所得到的大塊為單位的路徑作為搜索空間，以小塊為搜索節(jié)點，用 Astar 或者廣度優(yōu)先算法找出最短路徑，最后用同簡化版同樣的算法得到真正的，以象素為根本節(jié)點的最短路徑。這就是整個算法大致上的過程。這個算法通過對一個根本不變的地圖做預(yù)處理，犧牲一些儲存空間，從而大大提高后續(xù)每次尋徑所需要的時間并且減小每次搜索所需要的空間。這種算法特別適合使用在那種地圖精度高，但是復(fù)雜度比擬小的時候。 即時戰(zhàn)略游戲地圖大多屬于這種類型。 根據(jù)一些統(tǒng)計數(shù)據(jù)，該算法在 1000 1000 的地圖上面，速度是廣度優(yōu)先，AStar 等算法的 100 倍。思維慎密的讀者會發(fā)現(xiàn)上面所描述的算法是不