Abstract: This paper presented a path-finding method in real-time 3D scene. The polygons in scene models were regarded as the searching elements, and the virtual scenes were abstracted into intermediate result in the form of connected graph. In this intermediate result the heuristic search was made according to the scene nodes connectivity properties. A path searching task management mechanism was also carried out to balance the processing time of each frame loop. The proposed method could work without any factitious mark and script information in the scene and high processing had been achieved.

Key words: AI(Artificial Intelligence), virtual reality, 3D game scene, path finding

摘要： 提出一种应用于实时渲染3D场景中的路径搜索实现方法，该方法以3D虚拟场景模型中的多边形为基本对象，根据多边形的拓扑关系，将虚拟场景抽象成连通图形式的中间结果。在这个中间结果中，根据场景地形的通用性属性，利用启发式搜索进行路径搜索，并在路径搜索中有效的任务调度机制优化渲染循环中的路径搜索性能。与传统方法比较，该方法不需要在场景中额外增加人工标记，具有良好计算通用性与性能。

关键词: 人工智能, 虚拟现实, 3D游戏场景, 路径搜索