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

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

(苏州市职业大学 计算机工程系，江苏 苏州 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表和closed表，open表由未考察的节点组成，closed表由已考察的节点组成，当某个节点的所有下一级节点被评估，并放入到open表中，则该节点为已考察的.

A*算法是目前寻找最小开销路径的最快算法，能够很好地解决基本的寻路问题.但是A*算法也有局限性，就是随着搜索空间的增大，算法的性能会骤然下降，而且对CPU和内存资源的需求也会急剧上升，A*算法弱点在于open表和closed表的维护，open表必须保持是已排序的，列表顶部是最低开销的节点，open表和closed表会被不断轮询来判断一个节点是否已经被评价，这会带来很高的计算负担，使得它无法解决那些搜索空间较大的问题.

A*算法的一种扩展是迭代延伸A*算法(IDA*)［3］，这个算法去掉了open表和closed表，但可以通过适当构建节点扩展的方式来适应特定的顺序、防止回溯等.在IDA*中，为f建立了一个开销阈值，定义了节点可以被评估的最大允许开销，所有的节点都在这个阈值下扩展，如果目的节点没有找到，阈值会增加.因为没有维护搜索历史，必须从起始点重新开始搜索，并用给予的阈值扩展所有允许的节点，虽然可能会重复评价以前的非目的节点，但是扩展和评价节点的开销远远低于维护open表和closed表，最终的结果是以搜索时间开销为代价，而获得内存上的最小开销.

A*算法一般比IDA*算法速度快一些，但IDA*算法比A*算法使用较少的内存，为此需要对A*和IDA*算法进行改进，综合两者的优点，使得搜索速度和内存开销相对平衡，改进后的算法如下open表为当前搜索节点列表，按估计值排序.closed表为待搜索节点表:

①设置当前节点为起始节点;②设置阈值为当前节点的g值;③把当前节点放到open表中;④当open表不为空时;⑤取得open表中的一个节点;⑥如果节点就是目的节点，则路径找到，停止搜索;⑦如果节点的f值大于阈值，则把节点放到closed表的末尾，否则把节点的子节点放到open表中该节点的后面;⑧把节点从open表中删除;⑨继续取open表的下一个节点，重复⑥～⑧;⑩把closed表转换为open表，清空closed表;⑪设置阈值为比当前阈值高的最小g值，跳到⑤.

改进后的算法中节点会像IDA*一样给予一个开销阈值来扩展，但是这里的边缘节点不会丢失，边缘节点在open和closed表中进行维护，首先评估open表中顶部的节点，如果它的f值比阈值大，会被移到closed表中，如果它的f值比阈值小，则扩展该节点的子节点，同时丢弃该节点，新扩展的子节点被添加到open表的顶部，准备做下一次评估.如果完成一次遍历open表还没有找到目的节点，阈值就会像在IDA*中一样增加.closed表转换为open表，搜索从open表的顶部重新开始，虽然该搜索过程需要维护open表和closed表，但是没有排序的开销，而且这两个表的内存开销也比A*算法要小，因为不需要存储所有以前评估过的节点，也不会在迭代重复搜索过程中花费太多时间，使得它在A*和IDA*算法之间取得了相对平衡的效率.

2 搜索空间的划分

虚拟角色在虚拟世界中的寻路行为的基础是对所处环境的感知，需要对虚拟环境进行分析处理，提取地形特征、实体的空间位置等形成寻路使用的导航图.空间划分方案决定了导航图的复杂度，导航图越简单，搜索路径的耗费就越小，合理的划分方法要能较好地匹配场景中的地理特征，使路径搜索和游戏角色的移动更加自然真实.搜索空间的构建方法有栅格法、四叉树分割法、可见点法、导航网格等［4－5］.

1)栅格法是将搜索空间分割为规则的正方形栅格，栅格的划分粒度决定着地形描述的准确程度.栅格中的每个单元代表一个点，栅格中的邻近边表示相邻两点互相可达.栅格法的优点是空间表示简单，比较适合二维游戏的空间划分，缺点是需要大量节点来表示空间，寻路的效率比较低.

2)四叉树分割法是将空间递归地划分为四个更小的正方形，直到每个正方形都包含基本一致的地形.它的缺点是搜索算法产生的路径轨迹不真实，需要进一步平滑处理.

3)可见点法，这种方法是把搜索空间抽象成一些点构成的一个图，这个图上的点代表了凸多边形形状的障碍物的角，两个能互相可见的点就用一条边连接起来，这种方法提供了高质量的解决方案，在障碍物相对较小并且具有凸多边形形状的时候尤其有用，而在障碍物不是凸多边形的情况下，效率会降低，这种方法还需要手工设置可见点和连通图，工作量较大.

4)导航网格是一个凸多边形的集合，将三维空间表示为由相连的多边形构成的网格.使用导航网格要满足几个条件才能正常工作，首先全部多边形必须是相邻的，其次所有相邻的凸多边形共享两个顶点和一条边，最后，在同一个平面内，没有多个多边形重叠.

导航网格的一个优点是使用较少的节点表示三维空间，减少了搜索空间的空间复杂度，从而提高路径搜索系统的性能.另外导航网格是从三维场景中提取出来并经过优化处理的，这些工作可以事先预处理完成，不会占有路径搜索运行时间，从而缩短了路径搜索系统运行时间.

3 导航网格路径搜索

图1为原始的场景地图，生成的导航网格如图2所示，场景中的不可行走区域已从导航网格中移除.

图1 场景地图

图2 导航网格

所有导航网格中多边形的顶点都按逆时针方向存储.要求计算从起始点A到目的点B的路径，根据改进的A*算法可以得到从起始点A到目的点B所经过的多边形为P1、P2、P3、P6、P7、P9，每两个多边形相邻的边为E1、E2、E3、E4、E5，这些相邻边也是从起始点到目的点所经过的多边形的穿出边，其网格路径见图3.在网格路径基础上生成路径点的过程，如图4所示.

图3 网格路径

图4 搜索路径

在网格路径基础上生成路径点的过程为:

1)从起始点A连接第一条穿出边E1的两个端点a1和a2，形成两条线段左线段和右线段;

2)继续下一条穿出边的两个端点a3和a4，判断新的左点a3在左线段和右线段范围之内，则更新左线段为起始点到新的左点a3的线段，同理判断新的右点a4在左线段和右线段范围之内，则更新右线段为起始点到新的右点a4的线段;

3)继续下一条穿出边的两个端点a5和a6，判断新的左点a5在左线段和右线段范围之内，则更新左线段为起始点到新的左点a5的线段，同理判断新的右点a6在左线段和右线段范围之内，则更新右线段为起始点到新的右点a6的线段;

4)继续下一条穿出边的两个端点a7和a6，判断新的左点a7在左线段和右线段范围之内，则更新左线段为起始点到新的左点a7的线段，同理判断新的右点a6在左线段和右线段范围之内，则更新右线段为起始点到新的右点a6的线段;

5)继续下一条穿出边的两个端点a9和a8，判断新的左点a9在右线段范围之外，则a6为拐角点，起始点A到a6为搜索路径的一部分，再从拐角点a6开始进行搜索，更新左线段为a6到a9的线段，右线段为a6到a8的线段;

6)目的点在左线段和右线段范围之内，则a6到B为搜索路径的一部分，至此路径搜索结束，完整的路径为A经过a6到B.

4 结论

通过对路径搜索算法A*和IDA*算法的分析比较，在此基础上改善路径搜索算法的运行速度以及内存的开销，并且讨论搜索空间的划分方法，比较了栅格法、四叉树分割法、可见点法、导航网格4种划分方法，选定基于导航网格的路径搜索，导航网格可以减少搜索空间的节点数量，提高路径搜索的质量.

［1］王豫峰，韩璞，王华彬.基于A*算法的游戏寻径的设计与实现［J］.电脑知识与技术，2011，7(30):7450-7451.

［2］王志科，朱凡，彭建亮.基于启发式A*算法的飞行器三维航路规划［J］.电光与控制，2009，16(6):30-33.

［3］STAN K.Experimenting with IDA*search algorithm in heterogeneous pervasive environments［J］.Artificial Intelligence Review，2008，29(3/4):277-286.

［4］曹雷，饶真珍，贺毅辉.基于导航网格的三维空间表示［J］.系统仿真学报，2008，20(SI):232-234.

［5］MARCELO Kallmann.Navigation queries from triangular meshes［J］.The Visual Computer，2010，26(6-8):467-476.

(责任编辑:李 华)

Research on the Path Finding Technology in the Virtual Scene

KE Jian，LI Shuai，HAO Yuan-jun，ZHANG Qian-qian
(Department of Computer Engineering，Suzhou Vocational University，Suzhou 215104，China)

TP391.41

A

1008-5475(2012)02-0055-04

2012-03-20;

2012-04-15

苏州市职业大学青年基金资助项目(2011SZDX06)

柯健(1974—)，男，江苏常熟人，讲师，硕士，主要从事计算机图形学和GIS方向研究.