3D游戏场景中虚拟角色的智能寻径应用研究

摘要

近年来人工智能渐渐成为改善和提高游戏质量的热门研究课题之一，在游戏设计中开发者越来越重视虚拟角色的智能行为。在游戏开发中，人工智能是一个既重要而又复杂的模块，虚拟角色的寻径问题是人工智能运用于游戏的最基本问题之一。在当今游戏领域，A*算法是被使用最广泛的智能寻路算法，也是最有效的最短路径搜索算法。 本文主要针对游戏开发过程中的智能寻径技相关术进行研究，并将智能寻径应用于3D游戏场景中；分析了在游戏设计中的寻路思想，游戏虚拟角色的智能行为以及三维场景中的路径规划系统；不同的寻路算法有不同的搜索策略、时间效率、空间消耗与应用场合，本文分析对比了多种路径搜索算法，选择被广泛应用的A*算法进行寻路，并通过导航网格数据来形成搜索空间，针对场景的地形因素对地形和障碍物进行分类，生成用于寻路的导航网格。在此基础上应用A*算法进行寻路，并分析了路径的优化技术，针对游戏中路径搜索的具体要求从搜索效率、路径的真实平滑性等方面对A*算法进行了优化和改进。最后根据不同地形的特征参数设计了地形代价因子，改进了传统A*算法的估价函数。 本文通过生成和优化多边形导航网格，并基于导航网格实现了A*寻路过程，从整体提高了路径搜索的效率，在实际应用中得到了较为理想的结果。

目录

文摘

英文文摘

声明

第1章 绪论

1.1本文的研究背景和意义

1.1.1研究背景

1.1.2研究意义

1.2国内外的研究状况

1.2.1游戏AI的现状及发展

1.2.2智能寻径研究现状

第2章 智能寻径的研究与分析

2.1虚拟角色的智能行为

2.1.1虚拟角色的智能模型

2.1.2虚拟角色与游戏场景的交互

2.2三维空间的划分

2.2.1栅格化方法

2.2.2可见点方法

2.2.3导航网格方法

2.3寻路算法

2.3.1深度和广度优先搜索

2.3.2 Dijkstra算法求最短路径

2.3.3最佳优先搜索算法

2.3.4 A*算法

2.4本章小结

第3章 导航网格的设计与实现

3.1三维场景的生成

3.1.1三维场景的建模与导出

3.1.2网格和场景的数据结构

3.2导航系统

3.2.1导航系统的规划

3.1.2 多边形导航网格的生成

3.3网格优化

3.3.1凸多边形合并算法

3.3.2 3-2合并

3.3.3网格细分再合并

3.4本章小结

第4章A*算法的改进与实现

4.1 A*算法的改进思路

4.1.1传统的A*算法分析

4.1.2引入地形代价因子的A*算法

4.2改进的A*算法的应用与分析

4.2.1基于导航网格的A*算法实现及分析

4.2.2引入地形代价因子的A*算法实现

4.2.3结果分析

4.3本章小结

第5章总结与展望

5.1工作总结

5.2展望

参考文献

在校期间发表的论文、科研成果等

致谢