游戏领域中启发式寻径算法的运用和优化

摘要

传统的路径搜索系统是使用A*算法对场景搜索空间进行搜索。由于A*算法已经被广泛的应用和研究，从算法的角度基本已经达到了极限，因此优化路径搜索系统的重点就集中在设计优化的搜索空间之上。 本项目是三维网络角色扮演游戏研发项目中路径搜索系统部分。研究如何针对三维复合场景生成并优化搜索空间。在早期的版本中，曾使用多层高度栅格对游戏场景进行划分，但是由于空间复杂度过高而无法适应各种需求。最终使用多边形导航网格替代传统的三角形导航网格的方法对场景进行划分。多边形导航网格具有节点数更少、覆盖率更高等优点，是更为适合三维场景路径搜索空间的方法。通过对原始场景数据进行数据提取、网格生成、多边形合并、网格优化等步骤，和对路径分层搜索进行的预处理，多边形导航网格可以进行自动的生成和优化。 经过自动生成和优化的多边形导航网格比使用传统的三角形导航网格减少了30％左右的检测节点数，从而整体提高了路径搜索系统的性能。在实际应用中，收到了较为理想的效果，成为网络游戏核心引擎的重要组成部分。 现阶段的导航网格还存在着对实际地形描述不够精确、不支持动态障碍等不足。同时，该系统仅针对非玩家角色(NPC)的路径搜索，不考虑通过跳跃、摔落等行为进行移动的可能性，因此NPC的移动能力略低于玩家角色。所以，玩家可以利用这个缺陷引领NPC的移动，使NPC在一些区域里往返移动，从中获益。这些问题都需要在以后的工作中修正和补充。

目录

文摘

英文文摘

声明

第1章项目背景及研究意义

第2章三维复合场景中的路径搜索系统

2.1路径搜索系统的主要功能

2.2路径搜索算法

2.3路径搜索空间

2.4三维复合场景中自动划分路径搜索空间

第3章三维复合场景中路径搜索系统的实现

3.1通用的A*搜索算法

3.2导航网格生成工具

3.3从三维模型中提取导航网格的数据源

3.4生成凸多边形

3.5凸多边形的再次合并

3.5.1外部合并

3.5.2内部合并

3.5.3再次合并的利弊

3.6离散导航网格的合并

3.6.1二维合并方法

3.6.2三维合并方法

3.6.3二维合并与三维合并的比较

3.7修正导航网格寻径的结果

第4章应用实例与结果分析

4.1连接性筛选

4.2多边形合并

4.3多边形再次合并

第5章结论与展望

5.1工作总结

5.2多边形导航网格的不足

5.3路径搜索系统的展望

附录

参考文献

致谢