游戏地图寻路及其真实性研究

作     者：韩玮 

作者单位：西南大学 

学位级别：硕士

导师姓名：陈宏刚

授予年度：2013年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：路径搜索 贝塞尔曲线 A*算法 人工智能 

摘      要：随着社会的发展,人们物质水平的不断提高,同时得益于计算机的普及和软件技术的快速发展,游戏产业得到了快速的发展,尤其是在进入21世纪后,游戏产业迅速成为了朝阳产业。 游戏中路径搜索系统是游戏系统中非常重要的一部分,好的路径搜索算法对于游戏的重要性不可言喻。常见的路径搜索算法主要有深度优先搜索,广度优先搜索,Dijkstra, Floyd算法,A*算法等,其中A*算法是当前游戏开发中使用最为广泛的算法,也是游戏人工智能路径搜索中的研究重点。A*算法作为一种启发式搜索算法,在路径搜索时,相对其它搜索算法相当高效,它的评估函数是：F(n)=G(n)+H(n),其中G(n)表示从起始节点到当前节点的实际距离,H(n)表示从当前节点到下一步节点的估价值。A*算法总是寻找估价值最小的节点,因此能够找到最短路径,但是由于在游戏地图中,算法是基于节点搜索,所以在生成最终路径的时候,虽然是最优解,但是最终路径经常出现不符合现实情形,如何解决路径真实性问题,是一个非常重要的问题。 本文首先对A*算法进行深入研究,分析其产生问题的原因,然后针对A*寻路存在的问题,提出以了一种基于Floyd算法和Bezier曲线的改进A*算法,去掉了A*算法寻路中存在的拐点和多余的共线节点,避免了存在直线可走情况下走蛇型线路的问题,同时平滑了绕过障碍物时的生硬路径,较好的解决了A*算法路径真实性问题。最后,通过仿真实验对传统A*算法,基于二叉堆的A*算法和改进算法进行最终线路效果和时间效率的对比。实验中采用30*30的矩形方格来模拟地图,生成了固定地图和随机地图,固定地图主要是对比算法的时间效率方面,也比较最终的路径效果,随机地图主要观察在复杂的环境中,算法的路径效果。通过多次实验对比,得出的实验数据验证了改进算法的有效性,改进算法在时间消耗上优于传统A*算法,略低于二叉堆优化的A*算法,寻路效果更符合现实。