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

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

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

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