本文關(guān)鍵詞：基于多邊形場(chǎng)景的多智能體尋路系統(tǒng)研究，，由筆耕文化傳播整理發(fā)布。

【摘要】：近幾年來,由于游戲產(chǎn)品市場(chǎng)的激烈競(jìng)爭(zhēng),對(duì)游戲新技術(shù)的要求越來越高。人工智能,作為能夠讓構(gòu)建出的虛擬角色更加聰明,更加智能化的技術(shù),隨著游戲產(chǎn)業(yè)的發(fā)展,越來越受到業(yè)界和學(xué)界的重視。其中,尋路系統(tǒng)是當(dāng)今游戲和路徑導(dǎo)航系統(tǒng)等領(lǐng)域的基礎(chǔ)和重要組成部分。對(duì)于游戲中的復(fù)雜場(chǎng)景出現(xiàn)的各種實(shí)際問題,本文探討了在連續(xù)的二維空間內(nèi),以多邊形構(gòu)成的場(chǎng)景中,多智能體角色在不發(fā)生相互重疊的前提下的整個(gè)尋路系統(tǒng)的構(gòu)架與實(shí)現(xiàn),主要研究?jī)?nèi)容包括以下幾個(gè)方面：(1)在進(jìn)行場(chǎng)景分析并生成可見點(diǎn)方面,提出了基于形態(tài)學(xué)膨脹的障礙附近可見點(diǎn)生成算法,具有計(jì)算量較小,便于局部修改的特點(diǎn)；并提出了另一種基于圓柱體的可見點(diǎn)生成算法,來生成連通性更好的可見點(diǎn)集合；(2)在尋路過程中的相關(guān)算法方面,介紹了一種基于向量乘積的兩線段相交判斷的方法,并提出了可見性圖結(jié)構(gòu)緩存的生成方法和具體闡述了基于該結(jié)構(gòu)的A*尋路算法過程；(3)用智能體中具有旋轉(zhuǎn)不變性的包圍圓作為研究對(duì)象,來探討它們的碰撞檢測(cè)算法,在繞行中避免智能體相互重疊方面,依據(jù)兩圓之間位置關(guān)系與接近和遠(yuǎn)離的檢測(cè),提出了改進(jìn)的前向預(yù)防碰撞檢測(cè)方法,提升了數(shù)值健壯性；在繞行中避免與多邊形障礙發(fā)生碰撞方面,提出了對(duì)場(chǎng)景中的各個(gè)多邊形以給定的單位半徑進(jìn)行預(yù)膨脹的方法,從而可以用點(diǎn)是否在膨脹后多邊形內(nèi)的條件,來判斷是否發(fā)生碰撞；(4)對(duì)于包圍圓形式的多智能體的繞行,提出了整個(gè)群體下時(shí)間復(fù)雜度為O(n2)的,對(duì)單個(gè)智能體、多個(gè)智能體的繞行算法,以及對(duì)多智能體的提前繞行算法,并能夠逐步明顯地起到了總體接近目標(biāo)的效果,同時(shí)保證了計(jì)算的實(shí)時(shí)性；(5)在繞行算法與基于可見點(diǎn)的A*尋路算法的結(jié)合方面,提出了一種對(duì)可見點(diǎn)的范圍判斷方法,讓單位不至于過分接近可見點(diǎn),從而提升了多個(gè)智能體通過可見點(diǎn)的速度,改善了尋路效果,并讓單位在碰到場(chǎng)景中的障礙時(shí)作另外的尋路。本文的創(chuàng)新之處主要在于提出了兩種不同的可見點(diǎn)生成算法,減少了游戲關(guān)卡制作者的工作量；以及提出了多種繞行算法,來不斷調(diào)整智能體單位的陣型,從而可以在保證了性能的前提下,更好地接近目標(biāo)。此外在其他方面也做出了一些優(yōu)化和改進(jìn)。
【關(guān)鍵詞】：場(chǎng)景分析 尋路算法 A~* 多智能體 碰撞檢測(cè)
【學(xué)位授予單位】：廣東工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18
【目錄】：

• 摘要4-6
• Abstract6-14
• 第一章 緒論14-18
• 1.1 研究背景和意義14
• 1.2 智能尋路的國(guó)內(nèi)外研究狀況14-16
• 1.3 相關(guān)研究中存在的局限16
• 1.4 本文的主要工作及貢獻(xiàn)16-17
• 1.5 本文的結(jié)構(gòu)安排17-18
• 第二章 尋路系統(tǒng)的場(chǎng)景分析方法18-31
• 2.1 各類型場(chǎng)景的簡(jiǎn)介18-19
• 2.2 基于形態(tài)學(xué)膨脹的可見點(diǎn)生成方法19-22
• 2.2.1 凹凸角的形態(tài)學(xué)膨脹方法19-21
• 2.2.2 多邊形的形態(tài)學(xué)膨脹方法21-22
• 2.3 基于圓柱體的可見點(diǎn)生成方法22-29
• 2.3.1 圓與線段是否有交集的判斷23-25
• 2.3.2 障礙之間的幾種情況和生成可見點(diǎn)的流程25-29
• 2.4 對(duì)障礙內(nèi)部可見點(diǎn)的剔除29-30
• 2.5 本章小結(jié)30-31
• 第三章 基于可見點(diǎn)的A~*尋路算法31-40
• 3.1 基于向量外積的兩線段相交判斷方法31-32
• 3.2 可見性圖結(jié)構(gòu)緩存生成的算法與優(yōu)化32-35
• 3.3 基于可見性圖結(jié)構(gòu)的A~*尋路算法過程35-39
• 3.3.1 起點(diǎn)到終點(diǎn)直線路徑上的碰撞檢測(cè)35-36
• 3.3.2 A~*尋路的準(zhǔn)備36
• 3.3.3 A~*尋路算法的循環(huán)過程36-37
• 3.3.4 A~*尋路算法的結(jié)束循環(huán)條件與路徑的形成37-39
• 3.4 本章小結(jié)39-40
• 第四章 智能體間的碰撞檢測(cè)算法40-43
• 4.1 包圍圓簡(jiǎn)介40
• 4.2 多智能體之間碰撞檢測(cè)的算法及改進(jìn)40-42
• 4.3 本章小結(jié)42-43
• 第五章 多智能體間的繞行算法43-50
• 5.1 對(duì)單個(gè)智能體的繞行算法43-44
• 5.2 對(duì)多個(gè)智能體的繞行算法44-47
• 5.3 對(duì)多個(gè)智能體的提前繞行算法與到達(dá)目標(biāo)點(diǎn)效果的優(yōu)化47-48
• 5.5 結(jié)合基于可見點(diǎn)的A~*尋路算法48-49
• 5.6 本章小結(jié)49-50
• 第六章 尋路系統(tǒng)的程序設(shè)計(jì)與實(shí)驗(yàn)分析50-64
• 6.1 MinGW與Qt簡(jiǎn)介50
• 6.2 Qt的消息機(jī)制與繪圖函數(shù)50-52
• 6.3 總體設(shè)計(jì)52-54
• 6.4 障礙生成模塊54-57
• 6.4.1 自繪障礙54-55
• 6.4.2 隨機(jī)生成障礙55-56
• 6.4.3 界面設(shè)計(jì)56-57
• 6.5 可見點(diǎn)生成模塊57-58
• 6.6 智能體單位模塊58-59
• 6.7 實(shí)驗(yàn)與分析59-63
• 6.7.1 不含障礙的情形59-61
• 6.7.2 需要繞行固定的多邊形障礙的情形61-63
• 6.8 本章小結(jié)63-64
• 總結(jié)與展望64-66
• 總結(jié)64-65
• 展望65-66
• 參考文獻(xiàn)66-69
• 攻讀學(xué)位期間發(fā)表的論文69-71
• 致謝71

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前7條

1 蒯銳;洪金敏;;自動(dòng)尋路A*算法的應(yīng)用及優(yōu)化設(shè)計(jì)[J];上海應(yīng)用技術(shù)學(xué)院學(xué)報(bào)(自然科學(xué)版);2014年02期

2 余帥;李艷;王熙照;趙鶴玲;;游戲場(chǎng)景中基于勢(shì)場(chǎng)的交互尋路方法[J];計(jì)算機(jī)科學(xué);2014年02期

3 徐翔;黃敏;;一種改進(jìn)的群體智能尋路算法[J];計(jì)算機(jī)應(yīng)用與軟件;2012年05期

4 黃進(jìn);黃宗文;凌子燕;;多智能體尋路系統(tǒng)在計(jì)算機(jī)游戲上的應(yīng)用[J];電腦知識(shí)與技術(shù);2012年13期

5 邱磊;;基于A~*算法的游戲地圖尋路實(shí)現(xiàn)及性能比較[J];陜西科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年06期

6 王培俊;王文靜;陳鵬;何麗亞;;基于OBB算法和前向預(yù)防的快速碰撞檢測(cè)[J];西南交通大學(xué)學(xué)報(bào);2011年06期

7 梁毅;周剛;;基于定位點(diǎn)和路徑復(fù)用的大型多人在線游戲?qū)ぢ匪惴╗J];計(jì)算機(jī)應(yīng)用;2010年12期

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前4條

1 荊東星;人工神經(jīng)網(wǎng)絡(luò)在游戲?qū)ぢ分械膽?yīng)用研究[D];長(zhǎng)沙理工大學(xué);2010年

2 楊科選;人工智能尋路算法及其在游戲中的應(yīng)用研究[D];中南大學(xué);2009年

3 何文雅;3D游戲場(chǎng)景中虛擬角色的智能尋徑應(yīng)用研究[D];華中師范大學(xué);2009年

4 盧s

本文編號(hào)：401955