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

发布时间：2020-08-18 22:47

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

深度优先搜索,示例

点都是试探性的，称每一次访问过的节点为当前节点，那么在算法开始时的第一个当前节点就是起始节点。在搜索的过程中，假设访问到的当前节点为 V，首先将此节点的访问标志 visited[v]的值置为“1”，表示此节点已经被探查过。然后顺序访问与 V 相邻的所有节点，其中没有被访问过的节点当做下一次探查的当前节点。如果节点 V 的所有相邻节点的访问标志全都是“1”，则说明该节点的所有相邻节点都被访问过，就向上回溯，把当前节点设置为上一次探查过的当前节点。一直重复上述过程一直到整个连通图的所有节点全都被访问过。图 2-1 展示了深度优先搜索的一个经典示例。以顶点 A 为起始顶点进行深度优先搜索，能够遍历这个连通图的所有顶点。图 2-1 左侧是深度优先搜索的过程，每个顶点旁边的数字表示该顶点在遍历时被访问的次序。图 2-1 右侧是深度优先搜索结果，此结果由搜索过程中所有访问过的顶点以及搜索过程中经过的边组成，从而构成一个连通的无向图，实际上就是构成了树，而这种由深度优先搜索生成的树称为深度优先生成树（DFS 树），包括原图的 n 个顶点以及 n-1 条边。

广度优先搜索,示例,顶点

2.3.2 广度优先搜索广度优先搜索是一个逐层遍历的过程，其搜索过程有些类似于树的层序遍历。搜索过程中，图中有几个顶点就需要重复多少步，当然，每一步还是有一个当前顶点，最初的当前顶点为起始顶点。在访问当前顶点 v 时，首先设置该顶点访问标志visited[v]的值为“1”，接着访问顶点 v的每个未被访问过的邻接顶点1w ，2w ，…，tw ，接下来再顺序访问1w ，2w ，…，tw 的所有还没被访问过的邻接顶点，然后再从这些访问过的顶点出发，进一步访问他们仍没有被访问过的领结顶点。按这种方式搜索直到图中所有的顶点都已经被访问过了为止。图 2-2 展示了广度优先搜索的一个经典示例。以顶点 A 为起始顶点进行广度优先搜索。图 2-2 左侧是广度优先搜索的过程，每个顶点旁边的数字表示该顶点在遍历时被访问的次序。图 2-2 右侧是广度优先搜索的结果，又称为广度优先生成树，包括原图的 n 个顶点以及 n-1 条边。

带权图,邻接矩阵,顶点,最短路径

Dijkstra 算法适用于解决非负权值的单源最短路径问题。这类问题可描述为给定一个有向带权图 D 与源点 v，各边上的权值均非负。要求找出从 v 到 D 中其他各顶点的最短路径。Dijkstra 算法采用的是一种贪心的策略，按照路径长度的递增次序，逐步生成最短路径。首先，求出从起始顶点开始的一条最短路径然后在最短路径的基础上求出长度次短的一条路径，按照这种方式寻找，一直到从起始顶点到其他各顶点的最短路径全部求出为止。图 2-3 为一个带权有向图，以此为例介绍 Dijkstra 算法的具体做法。设图中的起始顶点为 v0，此时，集合 S 中只有一个顶点。设 W=V-S，那么 W 中的顶点为图中还未计算最短路径的顶点。规定 W 中顶点到起始顶点0v 的距离为0v 到该顶点的边上的权值，如果两顶点之间不存在权值，则距离为无穷大。以此距离为基础，接下来每计算出一条最短路径（0v ，…，kv ），就将kv 加入到集合 S 中直到所有的顶点都加入到了集合 S 中。表 2-1 为 Dijkstra 算法逐步求解的过程。

【参考文献】