三维仿真地形中寻路算法优化研究.doc

三维仿真地形中的寻路算法优化研究 　　摘 要 路径规划和寻路问题主要是指在已有的原始地图路网中选出一条从起点到目标点之间的最佳路径，受到越来越多的计算机研究人员的重视，具有非常重要的实际意义。本文介绍了三维仿真地形中的寻路算法，并在构造寻路路网的基础上进行了寻路算法的优化。 　　【关键词】三维仿真地形 寻路算法优化 栅格表示 　　1 前言 　　路径规划和寻路问题主要是指在已有的原始地图路网中选出一条从起点到目标点之间的最佳路径，具有非常重要的实际意义[1]。本文介绍了三维仿真图形中的寻路算法，并在构造寻路路网的基础上进行了寻路算法的优化。 　　2 寻路算法理论与技术 　　到目前为止，很多研究人员都至力于寻路算法的研究并取得了很大进展，产生了一些研究成果，这些研究成果主要表现在两个方面：静态寻路方法和动态寻路方法。 　　静态寻路方法主要是指在外界环境（寻路地形信息）不变的情况下，计算最优路径。其次，A*算法的使用环境约束条件较多，非常适用于方形网格构造的路网，对使用其他方式构造的路网并不适用。再次，A*算法无法在动态地形环境中使用，所以对于地形状态实时改变的情况，无法作出正确的判断。而且在一张大范围的路网中，A*算法可能需要遍历数百甚至上千个节点，这样就花费了太多CPU时间并且占据大量的存储空间。 　　动态寻路方法是指外界环境（寻路的地形信息和寻路条件）不断发生变化，在不能预估计的情况下计算最短路径[5]。其次，D*算法虽然可以工作在简单的具有三维高程信息的地形模型上，但对于多个寻路对象从源点向目标点出发进行寻路这种协同交互合作的情况，D*算法无能为力。 　　3 三维仿真地形中的寻路算法 　　三维仿真地形是指在传统的二维平面栅格地形表示中，加入第三维高度维。使得每一个在计算机中存储和表示的坐标点，除了具有在XOY平面中的相对位置之外，还具有高度Z的信息。这样，形成的地形不再只具有二维平面空间上的位置信息，通过第三维高度维的表述，得到了形如同自然界中高低起伏的真实地形的存储、显示以及计算的方法。 　　三维仿真地形中的寻路：在三维仿真地形中，路径规划问题仍然是找到一条从起始点到中止点的最优路径。但是寻路环境的变化对寻路方法提出了很大的挑战。分形布朗运动是现代非线性时序分析中的重要随机过程，它能有效地表达自然界中许多非线性现象，也是迄今为比能够描述真实地形的最好的随机过程。 　　4 局部栅格表示方法 　　由于现实自然景物的复杂性，真实模拟自然景物的计算量还是很大的，因此特别需要探索出一些高效的算法，尤其在虚拟仿真系统中，通常希望产生实时动画的效果，因此算法的效率更显重要。各相邻三角形间没有信息传递导致了地景表面留有不自然的线型轨迹，并且不能通过局部平滑去除，即所谓的“折痕问题”。为了消除折痕，提出了改进的随机中点位移法。 　　对于已经生成的三维随机分形地形，需要对其进行路网的构造，以此来形成可寻路的路网，为寻路算法的正确执行提供保证。以下是寻路路网构造的简单步骤： 　　（1）输入具有自相似性可控分形地形图； 　　（2）进行地形的三角化； 　　（3）对划分完成的具有TIN地形网格特征的地形进行顶点重要度估价； 　　（4）计算所有边的特征值； 　　（5）对符合一定条件的边进行塌陷和消除处理。 　　在3D交互虚拟现实引擎中，主要完成寻路个体的路径决策和路径规划过程，寻路模块指导寻路个体找到从起始节点到目标节点的最优路径。在此模块中，我们实现了多对象协同决策、判断、寻路的算法。以下是路径选择算法的设计： 　　算法功能：进行多寻路个体路径选择及行进决策 　　输入：寻路个体的初始信息；寻路个体所在的路网网格的当前状态和相临状态信息。 　　输出：若存在最优路径，输出。否则，返回路径不存在的标志信息。 　　（1）为第k个寻路个体初始化两个列表：Openk和Closedk。Open列表存储当前位置的所有相临网格的信息。Closed表存储己被访问过的网格及此网格的各种相关属性。 　　（2）对于第k个寻路个体，前面k-1个寻路个体己经出发了，那么在t时刻，和三角形网格i相临的三个三角形网格j，m，n上的决策信息量，，就有可能不是初始值。 　　（3）以第i个网格为起点，检查所有与网格i相临的网格j，m，n是否已经存在于Closedk列表中，将还没有进入Closedk列表中的网格纳入进入Closedk列表中。然后分别计算出网格j，m，n的，，。既求出网格i相临的网格j，m，n的状态行进决策函数。 　　（4）在三个相临的网格中找出D（t）值最小的网格j，这个网格是我们所要选择的网格。切换第J个网格为当前位置。 　　（5）在第j个网格成为当前位置之后，根据第三章协同交互系统的理论，更新第j个网格上的决策信息