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

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

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

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

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