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

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

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

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