基于CDT空间剖分的虚拟角色全局路径规划

Global Path Planning for Virtual Character Based on CDT Spatial Partition

针对大范围复杂虚拟城市环境中虚拟角色的自主导航问题,研究了虚拟城市环境的环境建模以及基于层次道路图的改进A*算法。用自适应剪切平面切割三维地物几何模型,把三维城市空间投影到2D平面空间,利用约束Delauny三角化方法剖分城市自由空间,通过调整约束边的长度调整提取道路图的精度,并构建顾及地形起伏特征的层次道路拓扑图;为适应基于层次道路图的路径搜索,对传统A*算法进行了改进。实验结果表明:该方法可以快速完成虚拟角色在虚拟城市环境中的全局路径规划,且环境建模需求空间小,路径搜索效率高并顾及了地形环境的起伏特征。

A new approach of environment modeling and an improved A^＊ algorithm applicable to hierarchical road map for autonomous navigation of virtual character in large complex virtual urban environments were proposed. An adaptive plane was used to cut geometric models of objects to translate the 3D space to 2D space. A hierarchical road map of the environment was precomputed by using the constrained Delauny triangulation algorithm to partition the free space, which took into consideration the uneven feature of terrain. The accuracy of the road map might be adjusted by resizing the length of constrained segment. The experimental results show that the method can quickly finish the global path planning for virtual character with less memory and consideration of terrain feature.