基于Cocos2d-x引擎的游戲的尋路算法研究與實(shí)現(xiàn).pdf

1、隨著移動互聯(lián)網(wǎng)的蓬勃發(fā)展和軟硬件水平的穩(wěn)步提高，游戲產(chǎn)業(yè)發(fā)展速度迅猛，手機(jī)作為游戲的新時代載體，手機(jī)游戲呈爆發(fā)式增長趨勢。如今市場對游戲產(chǎn)品的需求逐漸增大，用戶對游戲產(chǎn)品的要求也大幅度提高。如何快速高效地開發(fā)出一款趣味性強(qiáng)、用戶體驗(yàn)度高的游戲成為游戲業(yè)界值得關(guān)注的問題。
　　本課題主要是基于Cocos2d-x游戲引擎，進(jìn)行相關(guān)技術(shù)的研究，游戲項(xiàng)目的實(shí)現(xiàn)和尋路算法的優(yōu)化。通過開發(fā)一款仙俠類手機(jī)游戲項(xiàng)目，對開發(fā)涉及的引擎整體架構(gòu)、碰撞

2、檢測技術(shù)、有限狀態(tài)機(jī)、尋路算法等相關(guān)技術(shù)進(jìn)行掌握和應(yīng)用。從整個游戲項(xiàng)目的角度出發(fā)，以軟件工程的開發(fā)思想，完成項(xiàng)目的需求分析、功能設(shè)計、功能實(shí)現(xiàn)、打包運(yùn)行和測試維護(hù)等一系列流程。
　　本課題重點(diǎn)針對在地圖游戲中A*算法的尋路性能不足進(jìn)行研究與改進(jìn)。A*算法中節(jié)點(diǎn)的F值表示從初始節(jié)點(diǎn)經(jīng)由該節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的代價，open列表存放所有已生成而未考察的節(jié)點(diǎn)。針對在游戲?qū)竭^程中尋找最小F值節(jié)點(diǎn)耗時長，地圖規(guī)模越大尋路越緩慢和未考慮障礙物分

3、布問題進(jìn)行改進(jìn)，提出兩點(diǎn)優(yōu)化:其一針對尋路過程頻繁訪問open列表，尋找最小F值節(jié)點(diǎn)耗時長問題，提出采用最小二叉堆的方式來優(yōu)化open列表，高效地選取最小F值節(jié)點(diǎn)和維護(hù)列表有序性;其二針對地圖規(guī)模較大和障礙物分布不均導(dǎo)致尋徑時空消耗過大問題，提出采用地圖分層搜索方式予以改進(jìn)，將地圖劃分為不均等的子區(qū)域并構(gòu)成完整的抽象圖，根據(jù)障礙物分布情況選擇不同的尋路算法進(jìn)行尋徑，以縮短尋徑時間和減少訪問節(jié)點(diǎn)個數(shù)。
　　本課題分別將標(biāo)準(zhǔn)A*算法和