Voxel-Based Navigation Mesh Generation And Path-Finding In Large-Scale Terrain

With the rapid growth of the game industry,online games are more popular among players because of more vivid pictures,more magnificent scenes and higher responsiveness.On one hand,in the game production,the navigation mesh needs to be generated after editing the terrain,and the current algorithm cannot supports the real-time requirements.This paper uses voxel-based navigation mesh partitioning technology to deal with the problem of real-time generation of the navigation mesh.On the other hand,with the development of 3D game technique,the players have higher requirements for the path-finding realistic.In order to meet the requirements,this paper solves the problem by improving the traditional path-finding algorithm of the navigation mesh.Four methods are commonly used in generating the navigation mesh:grid-based method,triangle-based method,visibility graph method and voxel-based method.The reason we use voxel-based method is that it can afford the high responsiveness.The voxel-based navigation mesh is a data structure which is composed of interconnected polygons.Navigation mesh is generated by clustering voxels,which are obtained from the voxelization of the scene.This thesis designs and implements a real-time large-scale terrain navigation mesh generation system by partitioning the large-scale terrain into blocks,generating the navigation meshes for each block,and connecting the navigation meshes.The results show that the system meets the requirement of responsiveness,the response time of creating obstacle reaches 300 milliseconds for each,removing obstacle 300 milliseconds for each,and path-finding 1 millisecond once.In the aspect of navigation mesh path-finding,considering the problem of unreal path deviation in the "middle point" algorithm,this paper proposes "nearest point"algorithm to solve that.A variance is defined to measure the deviation level between the estimated path and the actual path.By comparing the variance of path deviation level,the number of nodes to be searched,and the searching duration between the"nearest point" algorithm and the "middle point" algorithm,the "nearest point"algorithm performs better than the "middle point" algorithm.This thesis has two contributions.One is achieves the real-time goal of creating obstacle,removing obstacle,path planning by partitioning the large-scale scene into blocks,generating voxel-based navigation mesh for each block and connecting navigation meshes;The other is proposes the "nearest point" algorithm to solve the problem of the unreal path deviation.By comparing the variance of path deviation level,the number of nodes to be searched,and the searching duration between"nearest point" algorithm and "middle point" algorithm,the experiment proves that the "nearest point" algorithm is correct and effective.