資源描述：
《分層路徑搜索算法研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。
1、分層路徑搜索算法研究 摘要：自動尋路算法是智能游戲中的重要組成部分，通過對現(xiàn)有自動尋路算法的分析，了解目前已有自動尋路算法所存在的不足?；诘貓D劃分的思想設(shè)計分層路徑搜索算法，通過將地圖細分，計算細分區(qū)域中抽象節(jié)點的最短路徑，在地圖加載過程中，實現(xiàn)地圖的預處理，從而在確定了路徑起始點和結(jié)束點之后，快速實現(xiàn)自動尋路。 關(guān)鍵詞：自動尋路算法；地圖細分；抽象圖 中圖分類號：TP311文獻標識碼：A文章編號：1009-3044（2015）30-0066-02 1概述 隨著信息技術(shù)的發(fā)展，游戲的畫面質(zhì)量不斷提高，角色技能越來越豐富，當游戲的畫面質(zhì)量和角色技能發(fā)展到一定階段之后，單純的提高游戲畫
2、面效果和角色已經(jīng)難以滿足玩家的需求，而游戲的難易程度、趣味性和操作游戲就成為了智能游戲的研究熱點?！ ∽詣訉ぢ肥侵悄苡螒蛑蟹浅Ｖ匾慕M成部分，傳統(tǒng)的A*自動尋路算法通過剪枝優(yōu)化自動尋路搜索進程，最終找到一條路徑起點和終點之間的最短路徑。但A*的空間復雜度較高，在大地圖上的自動尋路效果較差。而M-A*、HPA*算法通過對地圖的多尺度劃分來縮小搜素空間，提高了自動尋路算法效率，但是降低了所尋路徑的最優(yōu)程度?！ ?自動尋路算法優(yōu)化思路6 目前，大多數(shù)的自動尋路算法都未考慮地圖中障礙物的分布問題，而且相同自動尋路算法的性能在不同障礙物分布地圖上的差別較大。Dijkstra和A*算法的難以滿足大地圖自
3、動尋路算法的性能要求；HPA*算法未考慮地形信息，降低最終路徑的最有程度；M-A*僅的分區(qū)僅考慮起點和終點的區(qū)域信息，導致每一次自動尋路都需要重新分區(qū)，造成性能降低；Quadtree算法的抽象節(jié)點較多，終止條件過于嚴格，內(nèi)存耗費嚴重?！ ♂槍δ壳爸髁髯詣訉ぢ匪惴ㄋ嬖诘牟蛔悖岢鲆环N考慮地圖分布信息的分層路徑搜索算法，通過對地圖的分區(qū)，根據(jù)區(qū)域中障礙物的分布情況來選擇合適的自動尋路算法來設(shè)計尋找路徑，進而提高整個自動尋路算法的性能?！ ?分層路徑搜索算法設(shè)計 分層路徑搜索算法根據(jù)大地圖中障礙物的分布情況，將大地圖分為不均等的若干區(qū)域，并根據(jù)每個區(qū)域的障礙物信息來設(shè)置區(qū)域狀態(tài)，并將區(qū)域邊界的空
4、白節(jié)點看做抽象節(jié)點來構(gòu)建地圖的抽象圖；并依據(jù)區(qū)域的狀態(tài)，選擇曼哈頓距離或者向上融合算法來獲得抽象節(jié)點間的最短路徑；使用A*算法在抽象圖上實現(xiàn)抽象尋路，依據(jù)相關(guān)節(jié)點在所在區(qū)域的狀態(tài)來選擇對應(yīng)的自動尋路算法進行細化；最終得到實際的最短路徑?！ ?.1相關(guān)系數(shù)設(shè)計 在分層路徑搜索算法中，引入了區(qū)域障礙物比例[α]，區(qū)域狀態(tài)標記[λ]和閾值[β]三個系數(shù)?！ ?）區(qū)域障礙物比例 區(qū)域障礙物比例[α6]用于計算區(qū)域的障礙物多少，為是否需要繼續(xù)細分提供依據(jù)，其計算公式如式（1）所示?！ α=當前分區(qū)障礙物總數(shù)當前分區(qū)的節(jié)點總數(shù)]（1） 2）區(qū)域狀態(tài)標記 區(qū)域狀態(tài)標記[λ]取值0或1，對分區(qū)過程中
5、所構(gòu)建四叉樹上不再細分的葉子及節(jié)點狀態(tài)進行標記。如果區(qū)域內(nèi)的障礙物較多，那么[λ]取值0，在該區(qū)域中使用A*算法實現(xiàn)自動尋路；如果[λ]取值1表示當前區(qū)域的障礙物較少，可以使用Bresenham直線方法尋找最優(yōu)路徑?！ ?）閾值 閾值[β]為是否需要對區(qū)域繼續(xù)進行劃分的邊界值，[β]值越大，那么區(qū)有的劃分就越細，地圖中的抽象節(jié)點額越多，擴展節(jié)點越少，耗費時間越少，但耗費的內(nèi)存越多；[β]值越小，區(qū)域劃分越粗糙，抽象節(jié)點越小，耗費的內(nèi)存越小。 3.2地圖區(qū)域劃分 將大地圖根據(jù)障礙物信息細分成多個區(qū)域是分層路徑搜索算法的核心思想。其區(qū)域劃分思想與同樣進行地圖劃分的Quadtree算法不同，在
6、算法中首選將地圖劃等分為四份，然后根據(jù)每個分區(qū)的區(qū)域障礙物比例[α]和閾值[β]的關(guān)系來設(shè)置區(qū)域狀態(tài)標記[λ]。根據(jù)三個參數(shù)的定義，地圖區(qū)域劃分分為如下三種情況?！ ?）[α=0]，表明當前區(qū)域沒有障礙物，設(shè)置[λ=1]，設(shè)置為葉子節(jié)點，表明該分區(qū)沒有障礙物，不再進行細分，該區(qū)域使用Bresenhhan直線方法來尋找最短路徑?！ ?）[0?α?β]，區(qū)域內(nèi)障礙物較多，繼續(xù)細分。6 3）[α?β?1]，區(qū)域內(nèi)障礙物較少，設(shè)置[λ=0]，設(shè)置為葉子節(jié)點，表明該分區(qū)有障礙物，在該區(qū)域內(nèi)使用A*算法進行自動尋路?！ 》謱勇窂剿阉魉惴ǖ姆謪^(qū)算法流程圖設(shè)計如圖1所示?！ ≡诎凑杖缟系乃悸愤M行地圖區(qū)域劃分
7、，最終得到一個包含地圖區(qū)域信息的一個四叉樹。 3.3抽象圖構(gòu)造 在完成地圖區(qū)域劃分之后，需要將所得到的四叉樹葉子節(jié)點上邊界上的非障礙物節(jié)點作為抽下點，來構(gòu)造地圖的抽象圖。根據(jù)區(qū)域的狀態(tài)分別采用曼哈頓距離或者自底向上融合算法來計算子區(qū)域抽象節(jié)點的最短距離?！ ∪绻訁^(qū)域的[λ=1]，則表明該區(qū)域內(nèi)沒有障礙物，直接使曼哈頓算法計算兩個抽象節(jié)點之間的距離；否則，改區(qū)域中含有障礙物，使用自底向上融合的
