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

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

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

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