学位论文 > 优秀研究生学位论文题录展示

基于改进A*算法的游戏地图寻径的研究

作　者: 周小镜
导　师: 陈宏刚
学　校: 西南大学
专　业: 计算机软件与理论
关键词: 人工智能寻路算法 A*算法二叉堆
分类号: TP18
类　型: 硕士论文
年　份: 2011年
下　载: 227次
引　用: 4次
阅　读: 论文下载

内容摘要

随着计算机硬件性能的不断提升和软件技术的飞速发展,游戏行业也相应得到发展。近几年来,游戏里面的声音和视觉效果方面都得到了极大的提高和改善。但是,游戏中的人工智能技术的研究和应用还相对比较落后,所以游戏中虚拟角色的行为表现就显得比较单调和笨拙,只能重复做几个简单的动作,行走看起来非常机械,严重影响到了游戏的品质。然而,人工智能技术能够使虚拟角色看起来更加聪明更加智能化,因此,近几年来人工智能方面的技术就成为了改善和提高游戏品质的热门研究课题。在游戏软件中,人工智能是一个既重要又复杂的模块,而寻路算法又是人工智能运用于游戏中的最基本和最重要的问题之一。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%。

全文目录

摘要  5-7
Abstract  7-9
第1章绪论  9-17
  1.1 引言  9-10
  1.2 研究背景和意义  10-11
  1.3 游戏中路径搜索研究现状  11-14
  1.4 本文研究工作和组织结构  14-17
    1.4.1 本文研究工作  14
    1.4.2 本文组织结构  14-17
第2章搜索技术理论研究  17-33
  2.1 图搜索  18-21
    2.1.1 图的相关概念  18-20
    2.1.2 图的搜索过程  20-21
  2.2 盲目搜索算法  21-24
    2.2.1 宽度优先搜索  21-22
    2.2.2 深度优先搜索  22-24
  2.3 启发式搜索算法  24-26
    2.3.1 启发信息  24
    2.3.2 估价函数  24-25
    2.3.3 启发式搜索算法  25-26
  2.4 传统的最短路径算法  26-27
    2.4.1 Floyd算法  26-27
    2.4.2 Dijkstra算法  27
  2.5 A~*算法  27-32
    2.5.1 A~*算法原理  27-30
    2.5.2 A~*算法的性质  30-32
  2.6 本章小结  32-33
第3章 A~*算法的改进和优化  33-47
  3.1 A~*算法存在的不足  33-34
  3.2 估价函数的选取  34-36
    3.2.1 曼哈顿距离  34-35
    3.2.2 对角线距离  35-36
    3.2.3 欧几里得距离  36
  3.3 优化OPEN表查找速度  36-41
    3.3.1 二叉堆的定义  38-39
    3.3.2 插入节点  39-40
    3.3.3 删除节点  40-41
  3.4 分级路径搜索  41-43
    3.4.1 分级路径搜索思想  41-42
    3.4.2 分级路径搜索步骤  42-43
  3.5 分层寻路  43-44
  3.6 本章小结  44-47
第4章仿真实验与结论分析  47-55
  4.1 基于改进A~*算法的仿真实验步骤  47-49
  4.2 标准A~*算法路径搜索及实验数据分析  49-50
  4.3 采用二叉堆存储OPEN表节点的A~*算法对比实验  50-51
  4.4 采用分级路径搜索算法对比实验  51-52
  4.5 综合改进A~*算法对比实验  52-55
第5章总结和展望  55-57
  5.1 论文主要结论  55
  5.2 展望  55-57
参考文献  57-59
致谢  59-61
攻读硕士学位期间发表的论文  61

基于改进A*算法的游戏地图寻径的研究

内容摘要

全文目录

相似论文