基于Cocos2d-x引擎的游戲的尋路算法研究與實(shí)現(xiàn)
發(fā)布時(shí)間：2018-11-10 16:39
【摘要】：隨著移動(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)品的要求也大幅度提高。如何快速高效地開發(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)目,對(duì)開發(fā)涉及的引擎整體架構(gòu)、碰撞檢測(cè)技術(shù)、有限狀態(tài)機(jī)、尋路算法等相關(guān)技術(shù)進(jìn)行掌握和應(yīng)用。從整個(gè)游戲項(xiàng)目的角度出發(fā),以軟件工程的開發(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ū)竭^程中尋找最小F值節(jié)點(diǎn)耗時(shí)長(zhǎng),地圖規(guī)模越大尋路越緩慢和未考慮障礙物分布問題進(jìn)行改進(jìn),提出兩點(diǎn)優(yōu)化:其一針對(duì)尋路過程頻繁訪問open列表,尋找最小F值節(jié)點(diǎn)耗時(shí)長(zhǎng)問題,提出采用最小二叉堆的方式來優(yōu)化open列表,高效地選取最小F值節(jié)點(diǎn)和維護(hù)列表有序性;其二針對(duì)地圖規(guī)模較大和障礙物分布不均導(dǎo)致尋徑時(shí)空消耗過大問題,提出采用地圖分層搜索方式予以改進(jìn),將地圖劃分為不均等的子區(qū)域并構(gòu)成完整的抽象圖,根據(jù)障礙物分布情況選擇不同的尋路算法進(jìn)行尋徑,以縮短尋徑時(shí)間和減少訪問節(jié)點(diǎn)個(gè)數(shù)。本課題分別將標(biāo)準(zhǔn)A*算法和改進(jìn)后的A*算法在仿真實(shí)驗(yàn)和游戲項(xiàng)目中進(jìn)行對(duì)比分析,驗(yàn)證了改進(jìn)后的A*算法能夠提高路徑搜索效率,證明了尋路性能問題得以解決。達(dá)到了縮短游戲開發(fā)周期、提高游戲品質(zhì)、增加用戶體驗(yàn)度的目的,是一個(gè)很有意義的課題研究。
[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é)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP317
本文編號(hào)：2322983
[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é)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP317
【參考文獻(xiàn)】
相關(guān)期刊論文 前10條
1 段曉忠;;幾種常見排序算法思想及比較分析[J];中國市場(chǎng);2016年19期
2 熊壬浩;劉羽;;A*算法的改進(jìn)及并行化[J];計(jì)算機(jī)應(yīng)用;2015年07期
3 邱磊;;利用跳點(diǎn)搜索算法加速A*尋路[J];蘭州理工大學(xué)學(xué)報(bào);2015年03期
4 黃海威;鄧開發(fā);;改進(jìn)的A*算法在游戲地圖尋路中的應(yīng)用[J];信息技術(shù);2015年04期
5 黎首希;;RPG游戲角色設(shè)定的藝術(shù)特征和方法分析[J];藝術(shù)與設(shè)計(jì)(理論);2014年12期
6 王亞美;魯田;;基于OpenGL ES的二三維地圖可視化客戶端設(shè)計(jì)與實(shí)現(xiàn)[J];計(jì)算機(jī)應(yīng)用與軟件;2013年09期
7 歐陽圣;胡望宇;;幾種經(jīng)典搜索算法研究與應(yīng)用[J];計(jì)算機(jī)系統(tǒng)應(yīng)用;2011年05期
8 于水華;;淺淡RPG游戲開發(fā)的關(guān)鍵技術(shù)[J];電腦與電信;2011年02期
9 鄒益勝;丁國富;許明恒;何邕;;實(shí)時(shí)碰撞檢測(cè)算法綜述[J];計(jì)算機(jī)應(yīng)用研究;2008年01期
10 何國輝;陳家琪;;游戲開發(fā)中智能路徑搜索算法的研究[J];計(jì)算機(jī)工程與設(shè)計(jì);2006年13期
相關(guān)碩士學(xué)位論文 前2條
1 吳超帥;改進(jìn)A*算法及其在ASR移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用[D];湘潭大學(xué);2012年
2 王海玲;三維游戲技術(shù)的研究與實(shí)現(xiàn)[D];哈爾濱工程大學(xué);2009年
，本文編號(hào)：2322983
本文鏈接：http://www.wukwdryxk.cn/kejilunwen/ruanjiangongchenglunwen/2322983.html
最近更新
教材專著
