基于Cocos2d-x引擎的游戏的寻路算法研究与实现

发布时间：2018-11-10 16:39

【摘要】：随着移动互联网的蓬勃发展和软硬件水平的稳步提高,游戏产业发展速度迅猛,手机作为游戏的新时代载体,手机游戏呈爆发式增长趋势。如今市场对游戏产品的需求逐渐增大,用户对游戏产品的要求也大幅度提高。如何快速高效地开发出一款趣味性强、用户体验度高的游戏成为游戏业界值得关注的问题。本课题主要是基于Cocos2d-x游戏引擎,进行相关技术的研究,游戏项目的实现和寻路算法的优化。通过开发一款仙侠类手机游戏项目,对开发涉及的引擎整体架构、碰撞检测技术、有限状态机、寻路算法等相关技术进行掌握和应用。从整个游戏项目的角度出发,以软件工程的开发思想,完成项目的需求分析、功能设计、功能实现、打包运行和测试维护等一系列流程。本课题重点针对在地图游戏中A*算法的寻路性能不足进行研究与改进。A*算法中节点的F值表示从初始节点经由该节点到达目标节点的代价,open列表存放所有已生成而未考察的节点。针对在游戏寻径过程中寻找最小F值节点耗时长,地图规模越大寻路越缓慢和未考虑障碍物分布问题进行改进,提出两点优化:其一针对寻路过程频繁访问open列表,寻找最小F值节点耗时长问题,提出采用最小二叉堆的方式来优化open列表,高效地选取最小F值节点和维护列表有序性;其二针对地图规模较大和障碍物分布不均导致寻径时空消耗过大问题,提出采用地图分层搜索方式予以改进,将地图划分为不均等的子区域并构成完整的抽象图,根据障碍物分布情况选择不同的寻路算法进行寻径,以缩短寻径时间和减少访问节点个数。本课题分别将标准A*算法和改进后的A*算法在仿真实验和游戏项目中进行对比分析,验证了改进后的A*算法能够提高路径搜索效率,证明了寻路性能问题得以解决。达到了缩短游戏开发周期、提高游戏品质、增加用户体验度的目的,是一个很有意义的课题研究。
[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.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP317

【参考文献】