简化真实感地形中爬行路径设计的算法研究

Design of Moving Path Based on Simplified Terran

该文在概括三维路径设计的基础上给出了爬行路径的定义,并且指出了真实感地形中爬行路径规划与点状图中路径规划的区别。文章首先对问题进行了简化,重点是把地形中地物的形状简化成包围其边界的凸多边形包围盒,提出使用改进的Dijkstra算法解决问题思想,并且提出了构造包围盒顶点间关联矩阵的方法。实验结果表明,该方案总能得到简化问题的解,并从理论上证明了解的最优性,具有较大应用价值。

This paper gives a definition of moving path based on summing up design of 3D path,and points out design method of moving path in real terran is different from path designing in point graph.This paper simplifies the problem firstly,emphasis is to simplify the shape of object,and seeing encasing box of planar convex polygon as simplified object,and puts forward using Dijkstra Algorithm to solve the problem,but this paper modifies Dijkstra Algorithm,and we present an algorithm of creating linked matrix of vertexes of encasing box.Experiments prove the method can get shortest path,and has preferable applied importance.