多尺度路徑搜索與基于接觸面的地圖復(fù)雜性度量研究.pdf

1、尋路算法在人工智能領(lǐng)域里處于基礎(chǔ)性的地位,很多相關(guān)應(yīng)用都需要優(yōu)良的尋路算法的支持。在地圖類游戲中,無論是玩家控制角色還是電腦控制角色都需要從地圖上一個(gè)位置轉(zhuǎn)移到另一個(gè)位置,即在地圖上進(jìn)行尋路。尤其是一些實(shí)時(shí)戰(zhàn)略游戲?qū)ぢ返男枨蟾宇l繁。自從A*算法被提出以后,諸多的改進(jìn)算法應(yīng)運(yùn)而生。有進(jìn)行均勻分區(qū)的HPA*算法,有基于聚類的KM-A*算法,還有對(duì)地圖進(jìn)行多尺度分區(qū)的M-A*算法等等。他們都對(duì)待搜索地圖進(jìn)行抽象,但HPA*搜得的路徑并非最

2、優(yōu),KM-A*和M-A*則存在抽象過程過長的缺點(diǎn)。另一方面,尋路算法的性能很大程度上受到地圖中障礙物分布的影響。因此,對(duì)于某種特定的尋路算法而言,如常用的A*類算法,創(chuàng)建一個(gè)適合該尋路算法的地圖也顯得尤為重要。于是,對(duì)于地圖復(fù)雜性度量的研究也在一直進(jìn)行。本文的工作主要有以下兩點(diǎn):
　　1.針對(duì)M-A*在分區(qū)過程中不考慮地形分布并且形成的抽象圖結(jié)點(diǎn)較多等問題,本文提出了一種考慮地形分布的多尺度分解路徑規(guī)劃加速方法(MTD-A*),用

3、以快速尋找地圖上兩個(gè)指定點(diǎn)之間的最短路徑。該算法在形成抽象圖過程中,對(duì)于大面積的無障礙分區(qū)不再進(jìn)行細(xì)分,簡(jiǎn)化了抽象過程;在空白分區(qū)細(xì)化實(shí)際路徑時(shí),利用Bresenham直線算法代替 A*尋路,加速了尋路過程。實(shí)驗(yàn)結(jié)果表明,與 M-A*相比,該算法形成抽象圖時(shí)間更短、抽象圖結(jié)點(diǎn)數(shù)更少、搜索速度更快。
　　2.本文首先提出了全連通地圖的概念,而后給出了接觸面的定義,提出了基于接觸面的地圖復(fù)雜性度量方法。在對(duì)地圖進(jìn)行分析的過程中,我們發(fā)