柯 健，李 帅，郝沅君，张倩倩

(苏州市职业大学 计算机工程系，江苏 苏州 215104)

虚拟场景中路径搜索技术的研究

柯 健，李 帅，郝沅君，张倩倩

(苏州市职业大学 计算机工程系，江苏 苏州 215104)

路径搜索系统一般是游戏或虚拟现实中常用的人工智能的一部分.分析讨论路径搜索系统中几种常用的路径搜索算法，对启发式路径搜索方法A*算法和IDA*算法进行了改进，在存储空间和运行时间上取得了较为平衡的效果.讨论搜索空间的几种划分方法，在导航网格的基础上实现了路径的搜索.

路径搜索;A*算法;导航网格

Abstract:The path finding system is a part of the artificial intelligence which is often used in games or virtual reality.A few path finding algorithms often used in path finding system are discussed，heuristic path finding algorithm such as A*and IDA*are improved，which obtains balanced result in storage space and running time.A few methods which dividing searching space are discussed，and path finding is implemented based on navigation mesh.

Key words:path finding;A*algorithm;navigation mesh

目前，大部分游戏或虚拟现实都使用了人工智能(AI)，而路径搜索系统一般都是这些AI模块中的一个组成部分.路径搜索就是在虚拟世界中规划出一条路径，使其从一个初始地点到达另一个目的地点.

1 路径搜索算法

路径搜索系统主要由路径搜索算法和搜索空间划分两部分组成，A*算法［1－2］是比较流行的启发式搜索算法之一，常用于路径搜索.A*算法从一个起始位置开始，先进行广度优先搜索，再进行启发式搜索，利用评估函数对当前节点的邻近节点进行评估，选出最好的节点，再从这个最好的节点开始进行下一轮搜索直到搜索到目标节点为止.A*算法的评估函数为f(n)=g(n)+h(n)，其中g(n)表示从起点到节点n所需要的移动开销，这是Dijkstra算法所考虑的，其移动开销是确定的;h(n)表示从节点到目的点的移动开销，是通过启发式方法预估出来的.A*算法需要维护两个表:open表……