基于多邊形場(chǎng)景的多智能體尋路系統(tǒng)研究.pdf

1、近幾年來(lái)，由于游戲產(chǎn)品市場(chǎng)的激烈競(jìng)爭(zhēng)，對(duì)游戲新技術(shù)的要求越來(lái)越高。人工智能，作為能夠讓構(gòu)建出的虛擬角色更加聰明，更加智能化的技術(shù)，隨著游戲產(chǎn)業(yè)的發(fā)展，越來(lái)越受到業(yè)界和學(xué)界的重視。其中，尋路系統(tǒng)是當(dāng)今游戲和路徑導(dǎo)航系統(tǒng)等領(lǐng)域的基礎(chǔ)和重要組成部分。
　　對(duì)于游戲中的復(fù)雜場(chǎng)景出現(xiàn)的各種實(shí)際問(wèn)題，本文探討了在連續(xù)的二維空間內(nèi)，以多邊形構(gòu)成的場(chǎng)景中，多智能體角色在不發(fā)生相互重疊的前提下的整個(gè)尋路系統(tǒng)的構(gòu)架與實(shí)現(xiàn)，主要研究?jī)?nèi)容包括以下幾個(gè)方面

2、:
　　(1)在進(jìn)行場(chǎng)景分析并生成可見(jiàn)點(diǎn)方面，提出了基于形態(tài)學(xué)膨脹的障礙附近可見(jiàn)點(diǎn)生成算法，具有計(jì)算量較小，便于局部修改的特點(diǎn);并提出了另一種基于圓柱體的可見(jiàn)點(diǎn)生成算法，來(lái)生成連通性更好的可見(jiàn)點(diǎn)集合;
　　(2)在尋路過(guò)程中的相關(guān)算法方面，介紹了一種基于向量乘積的兩線段相交判斷的方法，并提出了可見(jiàn)性圖結(jié)構(gòu)緩存的生成方法和具體闡述了基于該結(jié)構(gòu)的A*尋路算法過(guò)程;
　　(3)用智能體中具有旋轉(zhuǎn)不變性的包圍圓作為研究對(duì)象，來(lái)

3、探討它們的碰撞檢測(cè)算法，在繞行中避免智能體相互重疊方面，依據(jù)兩圓之間位置關(guān)系與接近和遠(yuǎn)離的檢測(cè)，提出了改進(jìn)的前向預(yù)防碰撞檢測(cè)方法，提升了數(shù)值健壯性;在繞行中避免與多邊形障礙發(fā)生碰撞方面，提出了對(duì)場(chǎng)景中的各個(gè)多邊形以給定的單位半徑進(jìn)行預(yù)膨脹的方法，從而可以用點(diǎn)是否在膨脹后多邊形內(nèi)的條件，來(lái)判斷是否發(fā)生碰撞;
　　(4)對(duì)于包圍圓形式的多智能體的繞行，提出了整個(gè)群體下時(shí)間復(fù)雜度為O(n2)的，對(duì)單個(gè)智能體、多個(gè)智能體的繞行算法，以及對(duì)

4、多智能體的提前繞行算法，并能夠逐步明顯地起到了總體接近目標(biāo)的效果，同時(shí)保證了計(jì)算的實(shí)時(shí)性;
　　(5)在繞行算法與基于可見(jiàn)點(diǎn)的A*尋路算法的結(jié)合方面，提出了一種對(duì)可見(jiàn)點(diǎn)的范圍判斷方法，讓單位不至于過(guò)分接近可見(jiàn)點(diǎn)，從而提升了多個(gè)智能體通過(guò)可見(jiàn)點(diǎn)的速度，改善了尋路效果，并讓單位在碰到場(chǎng)景中的障礙時(shí)作另外的尋路。
　　本文的創(chuàng)新之處主要在于提出了兩種不同的可見(jiàn)點(diǎn)生成算法，減少了游戲關(guān)卡制作者的工作量;以及提出了多種繞行算法，來(lái)不斷