路径规划一直是机器人学中的重要研究领域，广泛应用于移动机器人的基础；导航，机械臂运动以及机器人足球等热点领域。将路径规划算法应用到虚拟实现中，实现虚拟场景的三维路径规划有重要的理论意义和实用价值。由于虚拟场景中所有物体的信息对系统来说都是已知的，相比机器人学路径规划问题，虚拟场景的路径规划有其特殊性。

目前，路劲规划领域有很多典型的方法，部分算法也扩展到了三维虚拟场景的路径规划问题。在国外，Satomon等提出了基于路径图的概率路径图（PRM）算法，可以进行交互或自动路径规划，但是该算法效率容易手采样的粒度影响，不够稳定。Srikanth Bandi等提出了基于精确栅格法的简单林区着火（simple bushfire）路径规划算法，能扩展应用到多目标以及动态场景的复杂3D环境下，但其效率收到受场景复杂程度的影响。J Voros提出了通过构造基于非精确栅格的树型结构（四叉树或八叉树）的距离图（distance map）来搜索获取合理的路径算法，效率较高，但只能够实现简单场景的路径规划。在国内，史红兵等尝试了将机器人的运动路径规划算法和摄像机控制的美学标准结合起来，采用基于八叉树的环境模型层次分解建立连接图,然后利用IDA*算法搜索最优路径，最后对运动轨迹进行了优化，能应用在较复杂的实际三维虚拟场景中。由畅宇等提出了一种基于遗传算法的三维路径规划方法，通过对机器人的运动行为进行编码，从而将路径规划问题转化为行为编码的遗传进化问题，可以规划出合理可行的运动轨迹，但该算法存在容易陷入U型障碍物空间的问题。刘利强等以蚁群算法中的ACS算法为基础设计了一种路径优化搜索算法，能够方便有效地解决水下潜器三维空间路径规划问题，但该算法存在运行时间较长、规划出的航线非最优航线的问题。综合国内外研究现状来看，三维虚拟场景规划算法还比较少，部分算法存在效率不稳定的问题，且大多没有应用于实际的复杂三维虚拟场景，仅停留在理论模型的探讨上。

2. 研究的基本内容与方案

基本内容;

本题课设需要实现一个自动寻路系统，该系统具有一下几个功能。

1. 系统能够自动分析出起点到终点的最短路径。

2. 系统能够根据路径的情况（拐弯，躲避行人等），在最短路径的基础上优化路径，使得小车能够更快的到达终点。

3. 系统能够在虚拟仿真的地形中完成（1）（2）条功能

实现方法和措施

要完成本课题的研究，首先必须熟练的掌握编程思想和自动寻路的算法，能够在给出起点终点以后的迅速的分析出最短路径和最优路径来。其次必须熟练的掌握虚拟现实仿真系统，能够完成虚拟现实中进行仿真出较为真实的地形和小车来。

措施。

1.用Dijkstra算法完成最短路径和最速路径分析。

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。