產(chǎn)生規(guī)避障礙物的導(dǎo)航力的解決方案

摘要:給出了一種規(guī)避障礙物的導(dǎo)航力的實(shí)現(xiàn)方案，這種方案在進(jìn)行相交檢測(cè)時(shí)使用了一種高效而簡(jiǎn)單的排除法，大大提高了計(jì)算效率#65377;在計(jì)算導(dǎo)航力時(shí)使用模糊邏輯，使自治角色在規(guī)避障礙物時(shí)表現(xiàn)得更加智能#65377;

關(guān)鍵詞:自治角色; 導(dǎo)航行為; 規(guī)避障礙物; 模糊邏輯

中圖分類號(hào):TP18文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2007)10-0251-03

0引言

導(dǎo)航行為是Reynolds在1987年提出來(lái)的#65377;它很適合應(yīng)用到游戲中(如模擬鳥群#65380;蜂群的運(yùn)動(dòng)，控制NPC的運(yùn)動(dòng)等)，在游戲中得到了廣泛的應(yīng)用#65377;導(dǎo)航行為包括一些簡(jiǎn)單的行為和復(fù)雜的行為#65377;簡(jiǎn)單的行為如尋找和逃避#65380;追逐和逃避等;復(fù)雜的行為如群體行為等#65377;本文是規(guī)避障礙物行為的一種實(shí)現(xiàn)#65377;

導(dǎo)航行為是關(guān)于自治角色的行為#65377;Reynolds對(duì)自治角色是這樣定義的:一個(gè)自治角色是一個(gè)適應(yīng)其所在環(huán)境并感知它，對(duì)它作出反應(yīng)的一個(gè)系統(tǒng)#65377;如果一個(gè)自治角色被一個(gè)沒(méi)有預(yù)料到的情況困惑時(shí)，如在它前進(jìn)的路上發(fā)現(xiàn)了一堵墻，它必須有對(duì)此作出反應(yīng)并且根據(jù)當(dāng)前情況對(duì)它的運(yùn)動(dòng)作出調(diào)整的能力#65377;這并不是說(shuō)一個(gè)自治角色必須有能力處理它所遇到的任何可能的情況#65377;但是它還是要能自己處理一些經(jīng)常遇到的情況#65377;例如，一種普遍的情況是在編寫路徑搜索代碼時(shí)，必須處理出現(xiàn)動(dòng)態(tài)障礙物的情況#65377;在一個(gè)適當(dāng)?shù)沫h(huán)境中，將恰當(dāng)?shù)目刂菩袨橘x予游戲中的一個(gè)角色可以不需要編寫額外的代碼來(lái)處理動(dòng)態(tài)障礙物#65377;一個(gè)自治角色在這種情況發(fā)生時(shí)能自己處理#65377;

一個(gè)自治角色的運(yùn)動(dòng)可以分為三個(gè)層次:

a)動(dòng)作選擇層#65377;它負(fù)責(zé)選擇目標(biāo)和決定執(zhí)行什么樣的計(jì)劃#65377;

b)導(dǎo)航層#65377;它負(fù)責(zé)產(chǎn)生用于動(dòng)作層所需要設(shè)定的目標(biāo)和計(jì)劃所需要的軌跡#65377;導(dǎo)航行為就是在這層實(shí)現(xiàn)的#65377;這個(gè)層次負(fù)責(zé)產(chǎn)生導(dǎo)航力以決定自治體應(yīng)該朝哪個(gè)方向移動(dòng)以及它需要以多快的速度到達(dá)目標(biāo)#65377;

c)運(yùn)動(dòng)層#65377;這是最底層，它代表了一個(gè)自治體運(yùn)動(dòng)的更多機(jī)械性的方面#65377;它是用來(lái)決定如何從一點(diǎn)移動(dòng)到另一點(diǎn)的[1]#65377;

Reynolds在他的工作中采用了一個(gè)簡(jiǎn)單的vehicle模型#65377;一個(gè)vehicle模型是由位置和速度定義的#65377;本文也使用這種模型#65377;Vehicle的速度方向?yàn)榫植孔鴺?biāo)系X軸的方向#65377;

1產(chǎn)生導(dǎo)航力

要產(chǎn)生一個(gè)規(guī)避障礙物的導(dǎo)航力，首先必須在自治角色的周圍進(jìn)行探測(cè)，看看是否有其他物體的存在(靜態(tài)或動(dòng)態(tài)的)#65377;如果有就進(jìn)行相交檢測(cè)，檢測(cè)在自治角色周圍的物體是否會(huì)與自治角色發(fā)生碰撞;如果會(huì)，則產(chǎn)生相應(yīng)的導(dǎo)航力#65377;

1.1進(jìn)行相交檢測(cè)

要實(shí)現(xiàn)規(guī)避障礙物的行為的第一件事就是虛擬環(huán)境中障礙物的幾何表示#65377;在二維空間下，對(duì)一個(gè)障礙物的表示的簡(jiǎn)單模型是一個(gè)圓(三維空間為球)#65377;這個(gè)圓必須包圍整個(gè)障礙物#65377;這種表示可能會(huì)產(chǎn)生很多不必要的空間，如對(duì)一堵墻來(lái)說(shuō)，用一個(gè)圓表示就是一個(gè)不合適的選擇#65377;用圓來(lái)表示的優(yōu)點(diǎn)是在與別的幾何物體進(jìn)行相交檢測(cè)時(shí)可以用簡(jiǎn)單的計(jì)算公式#65377;對(duì)于一個(gè)有復(fù)雜形狀的物體這是一個(gè)很不好的抽象，但這種方法在大部分的模擬中采用，在Craig Reynolds的實(shí)現(xiàn)中他采用了圓或球(3D空間)來(lái)表示障礙物#65377;本文中可以用多邊形來(lái)代替它，好處是這種表示法更符合大部分障礙物的外形特征，而且這種方法擴(kuò)展到三維坐標(biāo)系下也是沒(méi)有問(wèn)題的#65377;

要檢測(cè)vehicle是否會(huì)與障礙物碰撞的第一步是查找在它的附近有沒(méi)有別的物體，這就需要進(jìn)行相交檢測(cè)#65377;進(jìn)行直線與多邊形的相交檢測(cè)需要進(jìn)行一些乘法運(yùn)算，因此，在進(jìn)行大量的相交檢測(cè)時(shí)需要花費(fèi)很多計(jì)算時(shí)間#65377;應(yīng)用本文所介紹的排除法可以大大地減輕計(jì)算負(fù)擔(dān)#65377;方法是對(duì)障礙物的每一條邊進(jìn)行測(cè)試，這種計(jì)算只包含一些簡(jiǎn)單的if判斷語(yǔ)句，這樣做可以在很大程度上提高計(jì)算效率#65377;在應(yīng)用此方法時(shí)，需要定義一個(gè)測(cè)試向量，它的起點(diǎn)為vehicle的位置，方向?yàn)関ehicle速度的方向，長(zhǎng)度由用戶自己設(shè)定#65377;它分為以下四步執(zhí)行:

a)計(jì)算出一個(gè)點(diǎn)作為測(cè)試向量的終點(diǎn)(根據(jù)預(yù)定義的向量長(zhǎng)度決定)，現(xiàn)在所有的在預(yù)定義區(qū)域之外的頂點(diǎn)都會(huì)被排除#65377;下面為如何排除一條邊的偽碼#65377;其中:v表示vehicle;detectX為測(cè)試向量終點(diǎn)的X坐標(biāo)值;detectY為測(cè)試向量終點(diǎn)的Y坐標(biāo)值;p1和p2為所測(cè)試的邊的兩個(gè)頂點(diǎn)#65377;

……

(a)如果vehicleX坐標(biāo)值大于0

{if((p1.x()>detectX)(p2.x()>detectX))

continue; //滿足條件的點(diǎn)就被排除

if((p1.x()

continue;

}

(b)如果vehicleX坐標(biāo)值小于0

{if((p1.x()

continue;

if ((p1.x>v.x())(p2.x()>v.x())) 

continue;

}

(c)如果vehicleY坐標(biāo)值大于0

{if ((p1.y()>detectY) (p2.y>detectY)) 

continue;

if ((p1.y()

continue;

}…

這一步可排除的邊的情況如圖1所示#65377;

b)通過(guò)了第一步測(cè)試的邊會(huì)被轉(zhuǎn)換到局部坐標(biāo)系中，測(cè)試向量現(xiàn)在代表X軸#65377;如果一條邊所有的頂點(diǎn)都在Y軸的上面或下面，這條邊就不會(huì)與測(cè)試向量相交#65377;于是這條邊就通過(guò)了第二步的測(cè)試#65377;這一步可排除的邊的情況如圖2所示#65377;

c)測(cè)試一條邊的后方是否朝向vehicle#65377;一條邊的頂點(diǎn)是按反時(shí)針?lè)较蚨x的，因此那些第一個(gè)點(diǎn)在X軸的上方而第二個(gè)點(diǎn)在X軸的下方的邊可以被忽略#65377;這一步可排除的邊的情況如圖3所示#65377;

d)檢測(cè)一條邊的所有頂點(diǎn)的X坐標(biāo)值是否大于測(cè)試向量的長(zhǎng)度，或者它們的X坐標(biāo)值是否都小于0#65377;在這種情況下障礙物位于vehicle的后面#65377;這一步可排除的邊的情況如圖4所示#65377;

在這四步測(cè)試過(guò)后，大部分的邊被排除了，這樣可以節(jié)省大量的計(jì)算時(shí)間#65377;剩下的邊需要計(jì)算測(cè)試向量到相交點(diǎn)的角度以及測(cè)試向量和相交邊的夾角#65377;測(cè)試邊表示如下:

這就是相交點(diǎn)到vehicle的距離#65377;如果a為測(cè)試邊的斜率，對(duì)a取反正切值就得到相交角度#65377;如果出現(xiàn)多個(gè)障礙物重疊的情況，所有障礙物的邊都必須在測(cè)試中考慮，相交距離最短的邊被用來(lái)計(jì)算導(dǎo)航力#65377;

1.2運(yùn)用模糊邏輯來(lái)計(jì)算導(dǎo)航力

模糊邏輯是數(shù)學(xué)的一個(gè)分支，該方法采用實(shí)數(shù)值(而不是傳統(tǒng)的布爾值，即“是”與“否”)來(lái)表示對(duì)象屬于集合的程度#65377;與傳統(tǒng)邏輯相比，模糊邏輯的表達(dá)能力更為豐富和細(xì)致，能夠進(jìn)行更好的推理#65377;在產(chǎn)生規(guī)避障礙物的導(dǎo)航力時(shí)，使用模糊邏輯來(lái)計(jì)算規(guī)避力的方向，能使自治角色規(guī)避障礙物的行為看起來(lái)更加逼真#65377;

本文使用模糊邏輯來(lái)產(chǎn)生導(dǎo)航力，使用相交距離和角度作為輸入，使用三個(gè)定義來(lái)表示障礙物與vehicle的距離，如表1所示#65377;

相交角度也是決定產(chǎn)生vehicle對(duì)一個(gè)障礙物的規(guī)避力方向的重要因素#65377;相交角度被分為五個(gè)部分，如表2所示#65377;

根據(jù)輸入值決定建立一個(gè)規(guī)則矩陣#65377;它定義了根據(jù)角度和距離所產(chǎn)生的結(jié)果#65377;規(guī)則集如表3所示#65377;

結(jié)果是-90°到90°，這個(gè)角度決定了vehicle規(guī)避的方向#65377;規(guī)避力的大小則是進(jìn)行相交檢測(cè)前就定義好的測(cè)試向量的長(zhǎng)度#65377;

下面是一個(gè)應(yīng)用此方法的例子#65377;如圖5所示，根據(jù)前面介紹的相交檢測(cè)的方法，得到了一個(gè)30°的相交角，相交距離為測(cè)試向量長(zhǎng)度的55%#65377;

根據(jù)圖6#65380;7所示的兩個(gè)歸屬函數(shù)，距離值輸入所得到的結(jié)果是0.83 DM和0.16 DB，角度值輸入所得到的結(jié)果值是0.75 NS和0.25 NM#65377;

根據(jù)規(guī)則矩陣第三行第三列可知，DM與NS組合的結(jié)果是PS#65377;在這里使用邏輯與運(yùn)算法，選0.83和0.75中的較小值作為結(jié)果值#65377;同理，根據(jù)規(guī)則矩陣最終得出結(jié)果如表4所示#65377;

在此使用邏輯或運(yùn)算法，選用ZE(0.25)，PS(0.75)來(lái)計(jì)算角度#65377;這兩個(gè)結(jié)果分別如圖8#65380;9所示#65377;將這兩個(gè)結(jié)果合并過(guò)后的結(jié)果如圖10所示#65377;

本文使用最大平均法來(lái)解模糊化#65377;之所以選用這種方法是因?yàn)檫@種方法相對(duì)于面積中心法來(lái)說(shuō)運(yùn)算簡(jiǎn)單，而且得到的結(jié)果也很接近用面積中心法的計(jì)算結(jié)果#65377;使用下面的公式來(lái)計(jì)算規(guī)避力的方向:

crisp_value=∑representative_value×confidence/∑confidence(4)

兩個(gè)representative_value分別為-45°/2=-22.5°#65380;(45°+90°)/2=67.5°#65377;將值代入式(4)可得

angle=(-22.5°×0.25+67.5°×0.75)/(0.25+0.75)=45°

因此45°為規(guī)避障礙物的導(dǎo)航力的方向，如圖11所示#65377;

如果在實(shí)際情況中出現(xiàn)有凹多邊形形狀的障礙物，可以采

用在原來(lái)測(cè)試向量的左邊和右邊各增加一個(gè)測(cè)試向量，或在計(jì)算規(guī)避力的方向時(shí)對(duì)規(guī)則矩陣作一些修改的方法來(lái)處理#65377;

2結(jié)束語(yǔ)

本文給出了一種規(guī)避障礙物的導(dǎo)航力的實(shí)現(xiàn)方案#65377;這種方案可以被應(yīng)用在游戲中對(duì)NPC的控制上，尤其是游戲中動(dòng)態(tài)障礙物的處理上(靜態(tài)障礙物在路徑搜索中會(huì)被考慮)#65377;這樣可以避免路徑重計(jì)算，而路徑重計(jì)算需要消耗大量的計(jì)算時(shí)間#65377;因此，對(duì)于游戲中動(dòng)態(tài)障礙物的處理，這是一種效率比較高的方法#65377;

參考文獻(xiàn):

[1]REYNOLDS C W. Steering behaviors for autonomous characters[C]//Proc of Game Developers Conference. San Jose:[s.n.]， 1999.

[2]REYNOLDS C W. Interaction with groups of autonomous characters[C]//Proc of Game Developers Conference. San Francisco:[s.n.]， 2000.

[3]MOHAMMADIAN M. Integrating knowledge based systems， fuzzy logic and genetic algorithms for intelligent control and obstacle avoidance[EB/OL].[2006-07-25].http://www.complexity.org.au/ci/vol02/mm94n2/mm94n2.html.

[4]KIM J， KHOSLA P. Realtime obstacle avoidance using harmonic potential functions[J]. IEEE Transactions on Robotics and Automation， 1992，8(3):338-349.

[5]BUCKLAND M. Programming game AI[M].[S.l.]:Wordware Publishing， 2005.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”