论文部分内容阅读
随着计算机硬件性能的不断提升和软件技术的飞速发展,游戏行业也相应得到发展。近几年来,游戏里面的声音和视觉效果方面都得到了极大的提高和改善。但是,游戏中的人工智能技术的研究和应用还相对比较落后,所以游戏中虚拟角色的行为表现就显得比较单调和笨拙,只能重复做几个简单的动作,行走看起来非常机械,严重影响到了游戏的品质。然而,人工智能技术能够使虚拟角色看起来更加聪明更加智能化,因此,近几年来人工智能方面的技术就成为了改善和提高游戏品质的热门研究课题。在游戏软件中,人工智能是一个既重要又复杂的模块,而寻路算法又是人工智能运用于游戏中的最基本和最重要的问题之一。A*算法是目前被游戏开发人员最广泛使用的人工智能寻路算法。A*算法是一种启发式搜索算法,它采用的估价函数是:F(n)=G(n)+H(n),G(n)表示起始节点到当前节点实际走的距离,H(n)表示当前节点到目标节点的距离的估价值。利用这个函数计算出下一步将要搜索的所有节点的估价值,通过比较选择估价值最小的节点,作为下一步要走的节点,因此找到的是最优路径。本文首先优化OPEN表中节点的查找速度,然后运用将单个物体路径搜索和A*算法相结合的分级路径搜索方法来搜索路径。运用C++语言实现标准的A*算法和改进后的算法进行路径搜索,然后根据统计它们搜索的节点数和搜索路径所花费的时间,来验证改进后的算法的可行性和有效性。本文采用32*32的矩形方格来模拟游戏地图,黑色的方格代表障碍物,也即是代表游戏中的建筑物、墙、河流等无法通过的区域。具体的研究方法和步骤如下:第一,经过分析,我们可知A*算法最耗费时间的部分是:在OPEN表中查找F值最小的节点。本文采用二叉堆的方法,通过对OPEN表中的节点进行排序。采用二叉堆的方法比一般的排序方法更加高效,极大的优化了OPEN表内查找、增加和删除节点的速度。通过对比实验验证了采用二叉堆的方式来优化OPEN表中节点的查找速度的A*算法比标准的A*算法的搜索效率提高了5%。第二,在大型的游戏地图中,A*算法需要搜索的节点数量仍然非常巨大。通过分析我们发现,在没有障碍物的情况下,起始节点和目标节点之间就是一条直线路径。所以本文采用将单个物体寻径算法和A*算法相结合的分级路径搜索算法,进一步提升游戏地图路径搜索的速度。通过对比实验验证了采用分级路径搜索算法比标准的A*算法的搜索效率提高了11.5%。最后,本文将前面两个方面的改进和优化方法综合在一起,运用这个综合的算法来寻找路径。通过对比实验验证了这个基于改进A*算法的综合路径搜索算法比标准的A*算法的搜索效率提高了14.7%。