柯 健，李 帥，郝沅君，張倩倩

(蘇州市職業(yè)大學(xué) 計(jì)算機(jī)工程系，江蘇 蘇州 215104)

虛擬場景中路徑搜索技術(shù)的研究

柯 健，李 帥，郝沅君，張倩倩

(蘇州市職業(yè)大學(xué) 計(jì)算機(jī)工程系，江蘇 蘇州 215104)

路徑搜索系統(tǒng)一般是游戲或虛擬現(xiàn)實(shí)中常用的人工智能的一部分.分析討論路徑搜索系統(tǒng)中幾種常用的路徑搜索算法，對(duì)啟發(fā)式路徑搜索方法A*算法和IDA*算法進(jìn)行了改進(jìn)，在存儲(chǔ)空間和運(yùn)行時(shí)間上取得了較為平衡的效果.討論搜索空間的幾種劃分方法，在導(dǎo)航網(wǎng)格的基礎(chǔ)上實(shí)現(xiàn)了路徑的搜索.

路徑搜索;A*算法;導(dǎo)航網(wǎng)格

Abstract:The path finding system is a part of the artificial intelligence which is often used in games or virtual reality.A few path finding algorithms often used in path finding system are discussed，heuristic path finding algorithm such as A*and IDA*are improved，which obtains balanced result in storage space and running time.A few methods which dividing searching space are discussed，and path finding is implemented based on navigation mesh.

Key words:path finding;A*algorithm;navigation mesh

目前，大部分游戲或虛擬現(xiàn)實(shí)都使用了人工智能(AI)，而路徑搜索系統(tǒng)一般都是這些AI模塊中的一個(gè)組成部分.路徑搜索就是在虛擬世界中規(guī)劃出一條路徑，使其從一個(gè)初始地點(diǎn)到達(dá)另一個(gè)目的地點(diǎn).

1 路徑搜索算法

路徑搜索系統(tǒng)主要由路徑搜索算法和搜索空間劃分兩部分組成，A*算法［1－2］是比較流行的啟發(fā)式搜索算法之一，常用于路徑搜索.A*算法從一個(gè)起始位置開始，先進(jìn)行廣度優(yōu)先搜索，再進(jìn)行啟發(fā)式搜索，利用評(píng)估函數(shù)對(duì)當(dāng)前節(jié)點(diǎn)的鄰近節(jié)點(diǎn)進(jìn)行評(píng)估，選出最好的節(jié)點(diǎn)，再從這個(gè)最好的節(jié)點(diǎn)開始進(jìn)行下一輪搜索直到搜索到目標(biāo)節(jié)點(diǎn)為止.A*算法的評(píng)估函數(shù)為f(n)=g(n)+h(n)，其中g(shù)(n)表示從起點(diǎn)到節(jié)點(diǎn)n所需要的移動(dòng)開銷，這是Dijkstra算法所考慮的，其移動(dòng)開銷是確定的;h(n)表示從節(jié)點(diǎn)到目的點(diǎn)的移動(dòng)開銷，是通過啟發(fā)式方法預(yù)估出來的.A*算法需要維護(hù)兩個(gè)表:open表和closed表，open表由未考察的節(jié)點(diǎn)組成，closed表由已考察的節(jié)點(diǎn)組成，當(dāng)某個(gè)節(jié)點(diǎn)的所有下一級(jí)節(jié)點(diǎn)被評(píng)估，并放入到open表中，則該節(jié)點(diǎn)為已考察的.

A*算法是目前尋找最小開銷路徑的最快算法，能夠很好地解決基本的尋路問題.但是A*算法也有局限性，就是隨著搜索空間的增大，算法的性能會(huì)驟然下降，而且對(duì)CPU和內(nèi)存資源的需求也會(huì)急劇上升，A*算法弱點(diǎn)在于open表和closed表的維護(hù)，open表必須保持是已排序的，列表頂部是最低開銷的節(jié)點(diǎn)，open表和closed表會(huì)被不斷輪詢來判斷一個(gè)節(jié)點(diǎn)是否已經(jīng)被評(píng)價(jià)，這會(huì)帶來很高的計(jì)算負(fù)擔(dān)，使得它無法解決那些搜索空間較大的問題.

A*算法的一種擴(kuò)展是迭代延伸A*算法(IDA*)［3］，這個(gè)算法去掉了open表和closed表，但可以通過適當(dāng)構(gòu)建節(jié)點(diǎn)擴(kuò)展的方式來適應(yīng)特定的順序、防止回溯等.在IDA*中，為f建立了一個(gè)開銷閾值，定義了節(jié)點(diǎn)可以被評(píng)估的最大允許開銷，所有的節(jié)點(diǎn)都在這個(gè)閾值下擴(kuò)展，如果目的節(jié)點(diǎn)沒有找到，閾值會(huì)增加.因?yàn)闆]有維護(hù)搜索歷史，必須從起始點(diǎn)重新開始搜索，并用給予的閾值擴(kuò)展所有允許的節(jié)點(diǎn)，雖然可能會(huì)重復(fù)評(píng)價(jià)以前的非目的節(jié)點(diǎn)，但是擴(kuò)展和評(píng)價(jià)節(jié)點(diǎn)的開銷遠(yuǎn)遠(yuǎn)低于維護(hù)open表和closed表，最終的結(jié)果是以搜索時(shí)間開銷為代價(jià)，而獲得內(nèi)存上的最小開銷.

A*算法一般比IDA*算法速度快一些，但I(xiàn)DA*算法比A*算法使用較少的內(nèi)存，為此需要對(duì)A*和IDA*算法進(jìn)行改進(jìn)，綜合兩者的優(yōu)點(diǎn)，使得搜索速度和內(nèi)存開銷相對(duì)平衡，改進(jìn)后的算法如下open表為當(dāng)前搜索節(jié)點(diǎn)列表，按估計(jì)值排序.closed表為待搜索節(jié)點(diǎn)表:

①設(shè)置當(dāng)前節(jié)點(diǎn)為起始節(jié)點(diǎn);②設(shè)置閾值為當(dāng)前節(jié)點(diǎn)的g值;③把當(dāng)前節(jié)點(diǎn)放到open表中;④當(dāng)open表不為空時(shí);⑤取得open表中的一個(gè)節(jié)點(diǎn);⑥如果節(jié)點(diǎn)就是目的節(jié)點(diǎn)，則路徑找到，停止搜索;⑦如果節(jié)點(diǎn)的f值大于閾值，則把節(jié)點(diǎn)放到closed表的末尾，否則把節(jié)點(diǎn)的子節(jié)點(diǎn)放到open表中該節(jié)點(diǎn)的后面;⑧把節(jié)點(diǎn)從open表中刪除;⑨繼續(xù)取open表的下一個(gè)節(jié)點(diǎn)，重復(fù)⑥～⑧;⑩把closed表轉(zhuǎn)換為open表，清空closed表;?設(shè)置閾值為比當(dāng)前閾值高的最小g值，跳到⑤.

改進(jìn)后的算法中節(jié)點(diǎn)會(huì)像IDA*一樣給予一個(gè)開銷閾值來擴(kuò)展，但是這里的邊緣節(jié)點(diǎn)不會(huì)丟失，邊緣節(jié)點(diǎn)在open和closed表中進(jìn)行維護(hù)，首先評(píng)估open表中頂部的節(jié)點(diǎn)，如果它的f值比閾值大，會(huì)被移到closed表中，如果它的f值比閾值小，則擴(kuò)展該節(jié)點(diǎn)的子節(jié)點(diǎn)，同時(shí)丟棄該節(jié)點(diǎn)，新擴(kuò)展的子節(jié)點(diǎn)被添加到open表的頂部，準(zhǔn)備做下一次評(píng)估.如果完成一次遍歷open表還沒有找到目的節(jié)點(diǎn)，閾值就會(huì)像在IDA*中一樣增加.closed表轉(zhuǎn)換為open表，搜索從open表的頂部重新開始，雖然該搜索過程需要維護(hù)open表和closed表，但是沒有排序的開銷，而且這兩個(gè)表的內(nèi)存開銷也比A*算法要小，因?yàn)椴恍枰鎯?chǔ)所有以前評(píng)估過的節(jié)點(diǎn)，也不會(huì)在迭代重復(fù)搜索過程中花費(fèi)太多時(shí)間，使得它在A*和IDA*算法之間取得了相對(duì)平衡的效率.

2 搜索空間的劃分

虛擬角色在虛擬世界中的尋路行為的基礎(chǔ)是對(duì)所處環(huán)境的感知，需要對(duì)虛擬環(huán)境進(jìn)行分析處理，提取地形特征、實(shí)體的空間位置等形成尋路使用的導(dǎo)航圖.空間劃分方案決定了導(dǎo)航圖的復(fù)雜度，導(dǎo)航圖越簡單，搜索路徑的耗費(fèi)就越小，合理的劃分方法要能較好地匹配場景中的地理特征，使路徑搜索和游戲角色的移動(dòng)更加自然真實(shí).搜索空間的構(gòu)建方法有柵格法、四叉樹分割法、可見點(diǎn)法、導(dǎo)航網(wǎng)格等［4－5］.

1)柵格法是將搜索空間分割為規(guī)則的正方形柵格，柵格的劃分粒度決定著地形描述的準(zhǔn)確程度.柵格中的每個(gè)單元代表一個(gè)點(diǎn)，柵格中的鄰近邊表示相鄰兩點(diǎn)互相可達(dá).柵格法的優(yōu)點(diǎn)是空間表示簡單，比較適合二維游戲的空間劃分，缺點(diǎn)是需要大量節(jié)點(diǎn)來表示空間，尋路的效率比較低.

2)四叉樹分割法是將空間遞歸地劃分為四個(gè)更小的正方形，直到每個(gè)正方形都包含基本一致的地形.它的缺點(diǎn)是搜索算法產(chǎn)生的路徑軌跡不真實(shí)，需要進(jìn)一步平滑處理.

3)可見點(diǎn)法，這種方法是把搜索空間抽象成一些點(diǎn)構(gòu)成的一個(gè)圖，這個(gè)圖上的點(diǎn)代表了凸多邊形形狀的障礙物的角，兩個(gè)能互相可見的點(diǎn)就用一條邊連接起來，這種方法提供了高質(zhì)量的解決方案，在障礙物相對(duì)較小并且具有凸多邊形形狀的時(shí)候尤其有用，而在障礙物不是凸多邊形的情況下，效率會(huì)降低，這種方法還需要手工設(shè)置可見點(diǎn)和連通圖，工作量較大.

4)導(dǎo)航網(wǎng)格是一個(gè)凸多邊形的集合，將三維空間表示為由相連的多邊形構(gòu)成的網(wǎng)格.使用導(dǎo)航網(wǎng)格要滿足幾個(gè)條件才能正常工作，首先全部多邊形必須是相鄰的，其次所有相鄰的凸多邊形共享兩個(gè)頂點(diǎn)和一條邊，最后，在同一個(gè)平面內(nèi)，沒有多個(gè)多邊形重疊.

導(dǎo)航網(wǎng)格的一個(gè)優(yōu)點(diǎn)是使用較少的節(jié)點(diǎn)表示三維空間，減少了搜索空間的空間復(fù)雜度，從而提高路徑搜索系統(tǒng)的性能.另外導(dǎo)航網(wǎng)格是從三維場景中提取出來并經(jīng)過優(yōu)化處理的，這些工作可以事先預(yù)處理完成，不會(huì)占有路徑搜索運(yùn)行時(shí)間，從而縮短了路徑搜索系統(tǒng)運(yùn)行時(shí)間.

3 導(dǎo)航網(wǎng)格路徑搜索

圖1為原始的場景地圖，生成的導(dǎo)航網(wǎng)格如圖2所示，場景中的不可行走區(qū)域已從導(dǎo)航網(wǎng)格中移除.

圖1 場景地圖

圖2 導(dǎo)航網(wǎng)格

所有導(dǎo)航網(wǎng)格中多邊形的頂點(diǎn)都按逆時(shí)針方向存儲(chǔ).要求計(jì)算從起始點(diǎn)A到目的點(diǎn)B的路徑，根據(jù)改進(jìn)的A*算法可以得到從起始點(diǎn)A到目的點(diǎn)B所經(jīng)過的多邊形為P1、P2、P3、P6、P7、P9，每兩個(gè)多邊形相鄰的邊為E1、E2、E3、E4、E5，這些相鄰邊也是從起始點(diǎn)到目的點(diǎn)所經(jīng)過的多邊形的穿出邊，其網(wǎng)格路徑見圖3.在網(wǎng)格路徑基礎(chǔ)上生成路徑點(diǎn)的過程，如圖4所示.

圖3 網(wǎng)格路徑

圖4 搜索路徑

在網(wǎng)格路徑基礎(chǔ)上生成路徑點(diǎn)的過程為:

1)從起始點(diǎn)A連接第一條穿出邊E1的兩個(gè)端點(diǎn)a1和a2，形成兩條線段左線段和右線段;

2)繼續(xù)下一條穿出邊的兩個(gè)端點(diǎn)a3和a4，判斷新的左點(diǎn)a3在左線段和右線段范圍之內(nèi)，則更新左線段為起始點(diǎn)到新的左點(diǎn)a3的線段，同理判斷新的右點(diǎn)a4在左線段和右線段范圍之內(nèi)，則更新右線段為起始點(diǎn)到新的右點(diǎn)a4的線段;

3)繼續(xù)下一條穿出邊的兩個(gè)端點(diǎn)a5和a6，判斷新的左點(diǎn)a5在左線段和右線段范圍之內(nèi)，則更新左線段為起始點(diǎn)到新的左點(diǎn)a5的線段，同理判斷新的右點(diǎn)a6在左線段和右線段范圍之內(nèi)，則更新右線段為起始點(diǎn)到新的右點(diǎn)a6的線段;

4)繼續(xù)下一條穿出邊的兩個(gè)端點(diǎn)a7和a6，判斷新的左點(diǎn)a7在左線段和右線段范圍之內(nèi)，則更新左線段為起始點(diǎn)到新的左點(diǎn)a7的線段，同理判斷新的右點(diǎn)a6在左線段和右線段范圍之內(nèi)，則更新右線段為起始點(diǎn)到新的右點(diǎn)a6的線段;

5)繼續(xù)下一條穿出邊的兩個(gè)端點(diǎn)a9和a8，判斷新的左點(diǎn)a9在右線段范圍之外，則a6為拐角點(diǎn)，起始點(diǎn)A到a6為搜索路徑的一部分，再從拐角點(diǎn)a6開始進(jìn)行搜索，更新左線段為a6到a9的線段，右線段為a6到a8的線段;

6)目的點(diǎn)在左線段和右線段范圍之內(nèi)，則a6到B為搜索路徑的一部分，至此路徑搜索結(jié)束，完整的路徑為A經(jīng)過a6到B.

4 結(jié)論

通過對(duì)路徑搜索算法A*和IDA*算法的分析比較，在此基礎(chǔ)上改善路徑搜索算法的運(yùn)行速度以及內(nèi)存的開銷，并且討論搜索空間的劃分方法，比較了柵格法、四叉樹分割法、可見點(diǎn)法、導(dǎo)航網(wǎng)格4種劃分方法，選定基于導(dǎo)航網(wǎng)格的路徑搜索，導(dǎo)航網(wǎng)格可以減少搜索空間的節(jié)點(diǎn)數(shù)量，提高路徑搜索的質(zhì)量.

［1］王豫峰，韓璞，王華彬.基于A*算法的游戲?qū)降脑O(shè)計(jì)與實(shí)現(xiàn)［J］.電腦知識(shí)與技術(shù)，2011，7(30):7450-7451.

［2］王志科，朱凡，彭建亮.基于啟發(fā)式A*算法的飛行器三維航路規(guī)劃［J］.電光與控制，2009，16(6):30-33.

［3］STAN K.Experimenting with IDA*search algorithm in heterogeneous pervasive environments［J］.Artificial Intelligence Review，2008，29(3/4):277-286.

［4］曹雷，饒真珍，賀毅輝.基于導(dǎo)航網(wǎng)格的三維空間表示［J］.系統(tǒng)仿真學(xué)報(bào)，2008，20(SI):232-234.

［5］MARCELO Kallmann.Navigation queries from triangular meshes［J］.The Visual Computer，2010，26(6-8):467-476.

(責(zé)任編輯:李 華)

Research on the Path Finding Technology in the Virtual Scene

KE Jian，LI Shuai，HAO Yuan-jun，ZHANG Qian-qian
(Department of Computer Engineering，Suzhou Vocational University，Suzhou 215104，China)

TP391.41

A

1008-5475(2012)02-0055-04

2012-03-20;

2012-04-15

蘇州市職業(yè)大學(xué)青年基金資助項(xiàng)目(2011SZDX06)

柯健(1974—)，男，江蘇常熟人，講師，碩士，主要從事計(jì)算機(jī)圖形學(xué)和GIS方向研究.