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

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

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

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

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

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

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

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

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

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

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

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