论文部分内容阅读
随着游戏行业的迅速发展,人们对游戏应用中自动寻路算法的有效性和性能都提出了更高的要求。自动寻路是指在有阻挡的游戏地图中搜寻两点之间最佳的可通行路径。如何高效地完成自动寻路是游戏研究领域中重要的方向之一。在游戏网格地图寻路算法的研究中,最常见的算法为A*算法。A*算法是启发式算法,其启发函数为f(n)=g(n)+h(n)。对于游戏网格地图中的节点n,g(n)是起始节点至节点n已花费路径成本的实际值,h(n)是节点n至目标节点路径成本的估计值。A*算法通过在路径查找的过程中,通过选取最小f(n)值节点作为路径节点,可以有效地计算两点之间最短可行路径。A*算法的研究中存在以下难点问题：第一,标准A*算法中f(n)的度量方法为曼哈顿距离,该度量方法不能广泛地适用于不同类型的游戏网格地图。第二,A*算法集合操作的时间复杂度是影响游戏性能的关键因素,在当代游戏对性能要求越来越高的背景下,如何提高A*算法的性能是A*算法研究面临的主要挑战。第三,在两个节点之间通常存在多个最佳等效路径,A*算法会考察所有等效路径从而影响了A*算法的运行效率。本文针对上述三个问题,进行了以下研究：(1)研究了A*算法启发式函数f(n)=g(n)+h(n)在不同游戏网格类型中选择不同度量方法的差异,获得了在不同游戏网格类型中A*算法启发式函数的选择方案。(2)通过组合优先队列和字典类,提出了一种优化数据结构集合替代A*算法中的集合,降低了A*算法数据操作的时间复杂度。(3)提出了一个A*算法加速方案。通过采用节点的方向信息(详见4.2.2小节)进行深度优先查找,降低了A*算法查找节点的数量,提高了A*算法的查找速度。最终结合实际游戏项目实践,采用C#语言和Unity3D引擎实现了本文提出的A*算法优化方案。通过数据对比实验,分析比较了标准A*算法和优化加速A*算法各自的寻路时间和查找节点数量,验证了研究方案的有效性。