交互型虚拟场景下人物的动态路径规划研究

• 作 者: 贺小舟
• 出 处: 中国地质大学(北京)
• 发表日期: 2004年期
• 关键词: 虚拟现实 三维场景 路径规划 A*算法

随着硬件和图像渲染引擎的发展,虚拟现实技术得以长足的发展。通过图像渲染引擎营造出的虚拟现实场景,可以给用户营造出一种身临其境的感觉,也是这个原因,虚拟场景在各个领域都有广泛的应用。路径规划则是虚拟场景中的一项基本功能。而且由于虚拟场景中存在复杂的交互和频繁的路线导航,如何在交互型的虚拟场景下进行准确、高效的路径规划则成为一个关键性问题。本论文以交互型虚拟现实场景为背景,讨论了如何在此场景下进行人物的路径规划。以路径规划中的寻路算法为切入点,深入讨论了智能寻路算法在虚拟现实场景下的应用。本论文重点介绍了智能寻路中常用的A*算法,分析了标准的A*算法在实现时存在的问题,并针对这些问题对算法实现进行改进。改进主要有两个方向,第一,针对A*算法中耗时较大的问题,采用最小堆存储A*算法的开启列表,从而可以快速的找出代价值最小的相邻节点;第二,针对虚拟场景改进A*算法的启发函数,给启发函数添加更多适用于虚拟场景的启发信息,在保证准确性的同时让算法尽量少的遍历地图节点,从而提高算法的效率。本论文基于Unity3D引擎设计并制作出了以公园漫游为背景的虚拟场景,并为场景中的人物添加了多种交互的机制。然后重点研究了寻路算法在此场景下的应用,调整算法使其更适用于虚拟场景。首先,在寻路之前对场景地图进行预处理,使用K-means算法对场景中的障碍进行分类,进而对障碍进行模块化处理,从而减少寻路过程中需要遍历的节点数;然后,在寻路之后对计算出的路径进行平滑处理,这样人物在最优路径上的行走会更加自然,避免不必要的转向;最后,通过Unity3D引擎的碰撞检测机制对动态障碍物进行位置的预判,用来达到对动态障碍物智能避障的目的。通过改进后的A*算法在虚拟公园场景中的应用,表明改进后的A*算法在经过调整之后,更适用于交互型虚拟场景下人物的动态路径规划。