三维游戏中的空中寻路算法研究

2009-12-18王淼田野

文化月刊·遗产 2009年12期

关键词：算法

王淼田野

摘要:本文针对现有关于三维游戏中脱离地表的寻路算法的研究文献较少的情况,讨论了二维寻路A*算法的改进和优化,在满足三维空间寻路要求的算法原理和计算过程中的作用。算法的改进和优化包括三维网格节点的优化,三维场景中障碍物的设定,估价函数的修改和优化,节点坐标计算以及OPEN表和CLOSED表的维护等。

关键词:空中寻路 A*算法估价函数移动步长坐标变换

近年来,三维游戏产业高速发展,带动了游戏相关技术,特别是人工智能(Artificial Intelligence,简称AI)技术的发展。游戏中的空中寻路问题,相对于紧贴地表的物体运动路径的计算,计算量大大增加,路径节点为三维网格而非二维三角面。除此之外,还需解决物体或角色随飞行方向(或游泳方向)产生的运动姿态改变问题。本文针对三维游戏中对空中寻路技术的需求,通过对二维寻路A*算法的改进,讨论了如何实现三维游戏中空中路径的计算过程。

一、寻路算法的选择

游戏开发中较为成熟的寻路算法有很多,可分为盲目搜索和启发式搜索两大类。针对三维游戏的空中寻路数据量大,障碍物环境复杂的特点,使用盲目搜索将导致搜索代价巨大,甚至无解的结果,故本文选择启发式搜索中的A*算法,并对其估价函数和搜索过程进行修改,使其适应三维环境下的路径的计算要求。

二、A*算法的主要思想

启发式搜索的各种算法中,A*算法是较为成熟的算法之一。它的思想是在对状态空间进行搜索时,对每一个被搜索的节点通过估价函数进行评估,指导搜索前进的方向,直到找到目标节点为止。估价函数的常规形式是:f(n)=g(n)+h(n),其中,f(n)是估价函数,g(n)是从起点S沿着产生的路径移动到节点n的当前已知最短路径,h(n)是指从节点n移动到终点D的预估移动耗费。估价函数的定义没有确定的模式,在A*算法中,对h(n)做了限制,使其对所有节点x均有h(x)≤h*(x),其中h*(x)是从节点x到目标节点的最小代价,即实际最短距离。这样设计的估价函数可以找出最短路径,称之为寻路算法的可采纳性,A*算法就是一个可采纳的寻路算法。

三、A*算法在三维空中寻路应用中的修改和优化

1.三维网格节点的优化

在三维游戏中,针对三维场景如果仿照二维游戏地图读取的做法,单位网格的数量将达到一个惊人的数字,这是不可行的。所以,三维场景中的节点,不是以边长为单位长度的立方体,其边长大小应参照寻路物体(或角色)的长度、宽度、高度中最大的数值来确定,即寻路物体(或角色)的移动步长(step),这样最终路径的节点数量才能被控制在可接受的范围。

2.估价函数的修改和优化

三维游戏中的空中寻路相对二维地图中的寻路,对于从起始点开始的节点的搜索,每个节点相邻节点的数量从8个激增至26个。使用传统的A*算法,寻路的过程将很可能因为CPU资源耗费太大而严重影响游戏的流畅性。决定A*算法寻路效率的关键因素是估价函数f(n),对它的修改和优化可从下面两个方面进行:

第一,节点g(n)值计算过程的优化。每一个新加入OPEN表的节点的g值的计算,可通过其父节点的g值(起始节点的g值为0)和从父节点到该节点的移动耗费相加来得到。在三维空间中,如果父节点和子节点的x、y、z坐标分量中有2个相同,则移动耗费为step(step为对移动步长取整操作后的结果),有1个相同,则移动耗费为1.4×step后取整,都不相同则为1.7×step后取整(这样可避免求根运算和小数)。

第二,节点h(n)值计算过程的优化。将h(n)设定为节点n与终点D的直线距离,可满足可采纳性的条件。由于h(n)>0,在h(n)的计算中是否开根号并不影响各节点f(n)值的比较结果,故h(n)=|Xd-Xn|+|Yd-Yn|+|Zd-Zn|。

3.节点坐标计算

在三维空间中,如果考虑物体或角色随飞行方向(或游泳方向)产生的运动姿态的改变问题,则会涉及到旋转操作。为了使用同样的方法,来处理平移和旋转变换并实现变换间的复合,需引入齐次坐标系,使线性变换以统一的格式进行。所以,平移变换(即计算当前节点的相邻节点的坐标)的计算公式可用矩阵乘法表示如下:

其中,Tx、Ty和Tz分别是节点在三个坐标轴方向上的位移量,Xn、Yn、Zn为当前节点的坐标,x、y、z为当前节点的相邻节点的坐标。因物体或角色运动姿态的改变,而需采取的旋转操作的计算公式可用矩阵乘法表示如下:

其中,Rx、Ry、Rz分别是绕X、Y、Z轴逆时针旋转的变换矩阵,对于围绕任意旋转轴旋转的情况,可由上面3个变换矩阵的复合变换得到。

4.OPEN表和CLOSED表的维护

OPEN表和CLOSED表的维护是A*算法中的重要组成部分,在《三维游戏中NPC的寻路算法研究》项目中,由于使用Virtools游戏引擎作为三维游戏平台搭建工具,故使用Virtools中的阵列来保存节点元素,如图1所示。

四、Virtools中的阵列具有类似数据库中表的功能,能够为阵列表中的列建立索引,并可通0

基于以上文中的算法思路,以《三维游戏中NPC的寻路算法研究》项目为实验平台,利用Virtools,VSL语言在三维地形中实现了三维游戏中空中最短路径的搜寻工作,最终的可视化结果如图2所示。

(作者单位:四川音乐学院成都美术学院)

参考文献:

[1]李慧哲、张丽萍等.A*算法在游戏寻径中的应用.内蒙古师范大学学报.2009年第2期.