【摘要】：隨著移動互聯(lián)網(wǎng)的蓬勃發(fā)展和軟硬件水平的穩(wěn)步提高,游戲產(chǎn)業(yè)發(fā)展速度迅猛,手機作為游戲的新時代載體,手機游戲呈爆發(fā)式增長趨勢。如今市場對游戲產(chǎn)品的需求逐漸增大,用戶對游戲產(chǎn)品的要求也大幅度提高。如何快速高效地開發(fā)出一款趣味性強、用戶體驗度高的游戲成為游戲業(yè)界值得關(guān)注的問題。本課題主要是基于Cocos2d-x游戲引擎,進(jìn)行相關(guān)技術(shù)的研究,游戲項目的實現(xiàn)和尋路算法的優(yōu)化。通過開發(fā)一款仙俠類手機游戲項目,對開發(fā)涉及的引擎整體架構(gòu)、碰撞檢測技術(shù)、有限狀態(tài)機、尋路算法等相關(guān)技術(shù)進(jìn)行掌握和應(yīng)用。從整個游戲項目的角度出發(fā),以軟件工程的開發(fā)思想,完成項目的需求分析、功能設(shè)計、功能實現(xiàn)、打包運行和測試維護(hù)等一系列流程。本課題重點針對在地圖游戲中A*算法的尋路性能不足進(jìn)行研究與改進(jìn)。A*算法中節(jié)點的F值表示從初始節(jié)點經(jīng)由該節(jié)點到達(dá)目標(biāo)節(jié)點的代價,open列表存放所有已生成而未考察的節(jié)點。針對在游戲?qū)竭^程中尋找最小F值節(jié)點耗時長,地圖規(guī)模越大尋路越緩慢和未考慮障礙物分布問題進(jìn)行改進(jìn),提出兩點優(yōu)化:其一針對尋路過程頻繁訪問open列表,尋找最小F值節(jié)點耗時長問題,提出采用最小二叉堆的方式來優(yōu)化open列表,高效地選取最小F值節(jié)點和維護(hù)列表有序性;其二針對地圖規(guī)模較大和障礙物分布不均導(dǎo)致尋徑時空消耗過大問題,提出采用地圖分層搜索方式予以改進(jìn),將地圖劃分為不均等的子區(qū)域并構(gòu)成完整的抽象圖,根據(jù)障礙物分布情況選擇不同的尋路算法進(jìn)行尋徑,以縮短尋徑時間和減少訪問節(jié)點個數(shù)。本課題分別將標(biāo)準(zhǔn)A*算法和改進(jìn)后的A*算法在仿真實驗和游戲項目中進(jìn)行對比分析,驗證了改進(jìn)后的A*算法能夠提高路徑搜索效率,證明了尋路性能問題得以解決。達(dá)到了縮短游戲開發(fā)周期、提高游戲品質(zhì)、增加用戶體驗度的目的,是一個很有意義的課題研究。
[Abstract]:With the vigorous development of mobile Internet and the steady improvement of software and hardware, the game industry is developing rapidly. Mobile phone as the carrier of the new era of games, mobile phone games show explosive growth trend. Nowadays, the market demand for game products is gradually increasing, and the requirements of users for game products are also greatly increased. How to quickly and efficiently develop a game with strong interest and high user experience has become a problem worthy of attention in the game industry. This subject is mainly based on Cocos2d-x game engine, the research of related technology, the realization of game project and the optimization of route finding algorithm. Through the development of a Xianxia mobile phone game project, the development involved in the overall structure of the engine, collision detection technology, finite state machine, routing algorithm and other related technologies to master and apply. From the point of view of the whole game project, a series of processes such as requirement analysis, function design, function realization, package operation and test maintenance are completed with the development idea of software engineering. This paper focuses on the research and improvement of the lack of routing performance of the A * algorithm in the map game. The F value of the node in the A * algorithm represents the cost of reaching the target node from the initial node through the node. The open list holds all generated nodes that have not been investigated. In order to improve the problem of finding the minimum F-value node in the game path finding process, the larger the map scale is and the slower the map is and the problem of distribution of obstacles is not considered, two optimizations are put forward: firstly, the open list is accessed frequently during the path finding process. In order to find the minimum F-value node, the paper proposes to optimize the open list by using the least square stack, and to select the minimum F-valued node efficiently and maintain the order of the list. Secondly, aiming at the problem that the large scale of map and uneven distribution of obstacles lead to excessive space-time consumption of path finding, the paper proposes to improve the method of map hierarchical search, and divide the map into unequal sub-regions and form a complete abstract map. In order to shorten the searching time and reduce the number of access nodes, different routing algorithms are selected according to the distribution of obstacles. In this paper, the standard A * algorithm and the improved A * algorithm are compared and analyzed in the simulation experiment and the game project, which proves that the improved A * algorithm can improve the efficiency of path search and prove that the problem of routing performance can be solved. It is a meaningful research topic to shorten the period of game development, improve the quality of game and increase the degree of user experience.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP317

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 段曉忠;;幾種常見排序算法思想及比較分析[J];中國市場;2016年19期

2 熊壬浩;劉羽;;A*算法的改進(jìn)及并行化[J];計算機應(yīng)用;2015年07期

3 邱磊;;利用跳點搜索算法加速A*尋路[J];蘭州理工大學(xué)學(xué)報;2015年03期

4 黃海威;鄧開發(fā);;改進(jìn)的A*算法在游戲地圖尋路中的應(yīng)用[J];信息技術(shù);2015年04期

5 黎首希;;RPG游戲角色設(shè)定的藝術(shù)特征和方法分析[J];藝術(shù)與設(shè)計(理論);2014年12期

6 王亞美;魯田;;基于OpenGL ES的二三維地圖可視化客戶端設(shè)計與實現(xiàn)[J];計算機應(yīng)用與軟件;2013年09期

7 歐陽圣;胡望宇;;幾種經(jīng)典搜索算法研究與應(yīng)用[J];計算機系統(tǒng)應(yīng)用;2011年05期

8 于水華;;淺淡RPG游戲開發(fā)的關(guān)鍵技術(shù)[J];電腦與電信;2011年02期

9 鄒益勝;丁國富;許明恒;何邕;;實時碰撞檢測算法綜述[J];計算機應(yīng)用研究;2008年01期

10 何國輝;陳家琪;;游戲開發(fā)中智能路徑搜索算法的研究[J];計算機工程與設(shè)計;2006年13期

相關(guān)碩士學(xué)位論文 前2條

1 吳超帥;改進(jìn)A*算法及其在ASR移動機器人路徑規(guī)劃中的應(yīng)用[D];湘潭大學(xué);2012年

2 王海玲;三維游戲技術(shù)的研究與實現(xiàn)[D];哈爾濱工程大學(xué);2009年

，

本文編號：2322983