随着游戏行业的快速发展,画面逼真、场面宏大、实时性高的在线游戏更能获得玩家的青睐。一方面对于游戏开发公司来说,在制作地形之后,需要生成导航网格,当前算法无法达到实时性要求,本文采用基于体素导航网格分块技术,解决了导航网格实时生成的问题;另一方面,随着3D游戏技术的发展,玩家对寻路真实性有更高的要求,本文通过改进传统导航网格寻路算法,解决了寻路的真实性问题。在导航网格生成方面,常用的方法有基于格子、基于三角面、基于可见图、基于体素等四种方法,其中只有基于体素的导航网格方法可以满足实时性要求,因此本文采用该方法。所谓基于体素的导航网格是将场景体素化后,通过对体素进行聚类而生成的相互连接的多边形网格数据结构。通过对大规模地形进行分块,分别生成体素导航网格,再对分块进行实时连接生成场景导航网格的方法,设计实现了实时的大规模地形导航网格生成系统。测试结果显示系统达到了实时性要求,其中障碍物添加响应速度为300毫秒/个,障碍物删除响应速度达到300毫秒/个,路径规划响应速度达到1毫秒/次。在导航网格寻路方面,本文针对传统导航网格“边中点”寻路算法存在不真实的问题,提出新的导航网格寻路算法,称为“最近点”方法。定义路径偏离方差来度量估算路径与实际路径的偏离程度,对“最近点”方法和传统“边中点”方法在路径偏离方差、搜索节点数、搜索耗时方面进行比较。实验表明新的方法在以上方面的表现均优于传统方法。本文主要贡献在于两个方面,一个是通过对大规模地形进行分块,分别生成体素导航网格,再对分块进行实时连接生成场景导航网格,达到了障碍物添加与删除、路径规划的实时性要求。第二个是提出“最近点”算法,解决了传统算法路径不真实的问题,对“最近点”算法和“边中点”算法在路径偏离方差、搜索节点数、搜索耗时方面的比较,证明新的方式正确有效。