Chapter 3 Movement

游戏行业内对于AI最为基本的要求可能就是移动游戏内的角色。即使是游戏行业内最早的AI控制的角色(吃豆人),其都有着保留至今的移动算法。

同时,AI角色的移动构成了我们AI模型内最底层的部分。

许多游戏,包括那些有着高质量AI的游戏,也是完全依靠移动算法来体现较好的AI,其在AI的决策方面并没有使用所谓的高科技技术。

通常,在AI与动画之间会有着部分的重叠,因为动画有时也包含一些移动。本章节的内容更着眼于宏观上的角色移动,比如角色在游戏关卡内的移动,而不是角色身体某一部分,比如其手臂或者头部的移动。但是很难去完全区分,动画的的移动与AI控制的移动。在许多游戏中,动画会控制一个角色,包括大范围的移动。简单的方面,例如角色往前移动几步拉下电闸。或者一个复杂的cut-scene,其完全由动画系统控制。由于这些移动都并非由AI系统所驱动,本章节并不会涉及。

本章节将会介绍一系列不同的AI控制移动算法,从最简单的吃动人中的AI移动,到复杂的steering行为(用于赛车游戏或者三维空间内的飞船游戏)。

3.1 移动算法的基础

除非你要写一个经济模拟游戏,大多数情况下,你游戏中的角色会一直需要移动。每一个角色拥有一个当前的位置,可能还会有附加的一些物理属性,它们也会控制这角色的移动。而我们的移动算法就是使用一些变量或者属性计算出角色下一帧将会处于什么位置。

所有的移动算法都有着其基本的模式,其使用自己当前状态以及周围的几何数据。有些移动算法只需要非常少的输入数据,可能只需要角色的位置,以及其目标对象的位置。有些算法有可能需要角色当前的状态值以及关卡的地形数据。例如,用于躲避墙壁的移动算法,其需要输入墙体的位置信息以检测出可能发生的碰撞。

移动算法的输出也有许多。大多数游戏中,移动算法可能只会输出一个速度值。例如,一个角色可能看到他的目标敌人在西方,那么其应该向西全速移动。在过去的游戏中,角色可能只有两个速度,静止状态(大于零)与跑步状态(等于零)。那么,移动算法的输出只是一个移动方向。这就是所谓的kinematic(运动学)移动;其并不会考虑角色是怎么样加速或者减速。

现在的游戏中,我们会考虑更多的物理属性。这一类的移动算法,作者称其为“steering behavior”。这一算法由Craig Reynolds命名,其并不属于kinematic的范畴,而属于dynamic(动力学)。动力学的移动算法会考虑角色当前的运动状态。一个动力学的算法则需要知道角色当前的速度与位置。动力学算法的输出可能是一个力,也可能是加速度,其目的是为了改变角色的运动速度。

动力学的移动增加了算法的复杂程度。比方说,你的角色需要从一个地点移动到另一个地点。kinematic算法需要将方向输出给角色;而你的角色只需要一直朝那个方向移动直到其到达目标,之后算法将不在输出方向。而动力学的移动算法则需要先在正确的方向上进行加速,之后当角色靠近目标时,需要在相反的方向加速,也就是让角色减速,以此准确的到达目标地点。在本书中,作者将会把所有的动力学移动算法称之为steering behavior。

Craig Reynolds还发明了集群算法(flocking algorith),并被广泛地用于电影与游戏行业,用来模拟鸟群以及其他动物。我们在之后会介绍。由于flocking是最出名的steering behavior,有时候所有的steering算法都被误称为“flocking”。

3.1.1 2D空间内的移动

许多游戏的AI只需要在二维空间运行。甚至有些3D游戏,由于游戏内重力的作用,角色一般会始终处于地面,而我们会将这部分移动简化到二维空间。

许多AI的移动能在2D空间内实现,并且大多数经典的算法也基于2D空间。在学习这些算法之前,我们会先快速地过一遍2D数学与其移动所需要的数据。

将角色看作一个点

虽然游戏内的角色常常由3D模型组成,但是大多数的移动算法会将角色当作一个点。碰撞检测,障碍物躲避以及一些其他算法会使用角色的大概尺寸和大小来影响其检测结果,但是移动本身则会将角色当坐一个点。

相同的情况,物理程序员会将游戏内的对象当作一个刚体,其重心位于对象的中心。碰撞检测以及其他的作用力可能会作用于物体的任何一个部分,但是决定物体移动的算法会将它们进行转化,这样只需要考虑作用于物体重心的情况即可。

3.1.2 静态

2D空间内的角色拥有两个线性坐标,其代表对象的位置。这两个坐标系都基于游戏世界空间内的两个轴,它们互相垂直且垂直于重力。这一组坐标轴被命名为2D空间垂直坐标系。

在大多数游戏中,几何体是存储在3D空间内的,也是渲染在3D空间内。而模型的几何体也有一个3D垂直坐标系,其包含三个轴:一般被称为x,y,z。我们会将y轴的方向定义为重力作用方向的反向,而x轴和z轴位于地面。游戏中角色的沿着x轴与z轴移动,则如下图所示。

因此,我们会使用x轴与z轴来表示2D空间内的移动,虽然有些书在描述2D空间的移动时更多地使用x轴和y轴。

除了两个线性的坐标,物体面向哪个方向由一个orientation朝向值决定。orientation代表一个相对轴的角度。在本书中,我们使用一个逆时针角度,由弧度表示,始于正z轴。这也是游戏引擎的标准。

有了这三个值,角色的静止状态如下图所示。

因为以上这些数据并不包含任何关于角色移动的信息,所以处理这些数据的算法或者等式被称为静态算法。数据结构如下所示:

class Static:
    position: Vector
    orientation: float

在本章节中,作者将会使用orientation来表示角色的朝向。当游戏引擎需要渲染角色时,我们将通过一个旋转矩阵(rotation matrix)使角色拥有正确的朝向。正因为此,许多开发者也将orientation称为rotation。本章节中,当作者提到rotation时,指的只是改变orientation的过程。

2.5D空间

有些3D空间中的数学运算会比较复杂。3D空间内的线性移动是十分简单的,其只是2D空间内线性移动的一个延申,但是3D空间内涉及到orientation时则会变得较为复杂。

作为某种妥协,开发者通常会使用2D与3D融合的计算,这也就是所谓的2.5D。

在2.5D的空间内,我们会处理完整的3D坐标,但是其orientation只是一个标量值,就像我们在2D空间内所使用的orientation。在大多数游戏中,重力会影响你的角色。大多数情况,角色在y轴上的位移是受限的,因为重力会将角色拉到地面。当与地面接触时,我们就可以在2D空间内进行运算,即使角色会跳跃,跌落,或者使用关卡内的电梯在y轴上发生位移。

即使当角色在上下方向上进行移动,角色往往也是保持直立状态。可能,角色在移动,跑步或者行走或者倚靠墙壁时,其动画会有一定的倾斜,但这并不会影响角色的移动;这仅仅只是一个动画效果。如果一个角色保持直立,那么其orientation只是基于y轴的旋转。

虽然在一些情况下我们会损失一些灵活性,但是2.5D有更简单的数学运算。

当然,如果你正在研发一个飞行模拟游戏或者一个宇宙飞船射击游戏,那么三个轴向的orientation对于AI来说都非常重要。但是,在大多数情况下,2.5D是最佳的选择。作者将会在本章末端介绍3D运动。

数学

位置坐标由一个带有x与z的向量所表示。在2.5D空间内,向量会包含y。

在2D空间内,我们只需要一个角度来表示orientation。根据上文所述,这一角度是基于z轴正轴并围绕着y轴正轴的逆时针方向。

在许多情况下使用向量来代表orientation更为方便。此时,该向量是一个单位向量并指向角色所面对的方向。我们可以直接使用之前的标量orientation角度值来计算该向量:

其中ws表示orientation的标量形式,而wv表示orientation的向量形式。此处笔者默认我们位于右手坐标系。如果基于左手坐标系,那么在wv的x的值需要加上负号,也就是-sin(ws)。

3.1.3 Kinematics 运动学

现在,本章节中的每个角色拥有两个值,位置坐标与orientation。我们能够创建一个移动算法,基于角色的位置与朝向,计算出其速度,并且算法输出的速度的变化是即时的。

虽然对于有些游戏来说,这种算法没太大问题。但是其看上去并不真实。因为根据牛顿的力学定律,现实世界中物体的速度并不能即刻改变。如果一个角色朝着某个方向移动,之后其突然改变方向和速度,那么这个角色的行为看上去肯定非常奇怪。为了使角色的运动更为平滑,我们需要某种平滑算法或者我们需要考虑角色当前的速度并且使用一个加速度来改变其速度。

为了支持上述情况,角色必须一直记录其当前的速度与位置。之后我们的移动算法才能在每一帧改变角色的速度,并且输出较为平滑的运动。

角色需要同时记录其线性速度与其角速度。线性速度在x轴和z轴上都有着相对应的速度。如果我们位于2.5D的空间内,那么线性速度将会包含x,y和z。

角速度表示角色orientation改变的快慢。其由一个标量值表示,每一秒弧度的改变值。作者将角速度称为rotation。以下结构体包含了一个角色所需要的所有的kinematic数据:

class Kinematic:
    position: Vector
    orientation: float
    velocity: Vector
    rotation:float

steering behavior将会处理上述数据,之后返回加速度,其将会改变角色的速度:

class SteeringOutput:
    linear: Vector
    angular: float

独立的朝向

还需要注意的一点,角色的移动的朝向并不一定与其身体的朝向相同。一个角色可以朝向x轴,但其正沿着z轴移动。虽然大多数情况下,游戏内的角色并不会这么运动。

许多steering behavior会完全忽略朝向。其只处理角色的线性数据,而角色的orientation将会强制匹配其运动的朝向。但是这么做的结果将是orientation的改变非常的生硬。

更好的做法是将角色的orientation按一定的比例,在几帧之内改变至其移动的方向。如下图所示,角色每一帧都会orientation都会更新为其运动朝向的一半。途中的三角形表示角色的朝向,灰色的阴影则表示之前几帧角色所处的位置。

更新位置与朝向

如果你的游戏使用了物理引擎,那么它可能会更新角色的位置坐标与orientation。但即使有了物理引擎,一部分开发者仍然倾向只在角色上使用物理引擎的碰撞检测,并且为移动controller编写特定的代码。所以,如果你需要手动更新位置与orientation,你可以使用一个相对简单的算法:

class Kinematic:
    # ...之前的数据...

    function updata(steering: SteeringOutput, time: float):
        # 更新位置与orientation
        half_t_sq: float = 0.5 * time * time
        position += velocity * time + steering.linear * half_t_sq
        orientation += rotation * time + steering.angular * half_t_sq

        # 速度与rotation
        velocity += steering.linear * time
        rotation += steering.angular * time

update函数使用了一些初中物理知识。如果游戏的帧率够高,那么每一帧的时间,也就是函数中的time将会非常小。那么它的平方将会更小,所以加速度对于位置以及orientation的影响也会非常小。不过下列更新算法更为常见:

 
class Kinematic: 
    # ...之前的数据... 
    function updata(steering: SteeringOutput, time: float): 
        # 更新位置与orientation          
        position += velocity * time  
        orientation += rotation * time 

        # 速度与rotation 
        velocity += steering.linear * time 
        rotation += steering.angular * time 

上述代码是游戏行业内最为常见的代码。需要注意但是,上面两段代码,我们都假设vector能够直接进行算术运算,例如向量相加以及直接标量直接乘以向量。根据你使用的语言,可能会需要替代某些运算符。

Game Physics以及作者的Game Physics Engine Development这两本书中,有着更多游戏内的物理计算以及工具。

变化的帧率

到现在为止,作者都假设速度的单位是基于每一秒而不是每一帧。早前的游戏通常会使用基于每一帧的速度,但这意味着物体的速度会随着帧率发生改变。

作用力与驱动 Forces and Actuation

在现实世界中,我们不能简单地对一个物体施加一个加速度并使其移动。通常,我们会施加一个力,这个力会改变物体的动能。之后物体才会开始加速,但是加速也取决于物体的惯量(inertia)。惯量与加速度正好相对;惯量越大,那么施加相同的力,其加速度就越小。

为了在游戏中模拟这一特性,我们可以使用物体的质量作为线性惯量和转动惯量(模拟角加速度)。

我们可以进一步延申角色的数据,记录上述变量,并且使用一个更为复杂的update函数来计算角色的速度与位置。这也就是物理引擎的原理:AI系统通过对角色施加一个作用里来控制角色的运动。但是这一方法很少用在人类角色上,更多的是用来控制赛车。

由于最著名的steering算法是以输出的加速度作为基础,一般来说steering算法并不会涉及到作用力。通常来说,移动控制器movement controller在预处理阶段会计算一个角色的动力dynamics,这个步骤就是所谓的驱动actuation。

Actuation将我们想要改变的速度变量作为输入,直接运用到kinematic系统。驱动器将会计算各个作用力的组合,以得到一个近似的速度改变量。

最简单的一种手段就是直接将加速度乘以惯量求出一个作用力。这也意味着,我们可以对角色施加任何作用力,但现实往往并非如此(一辆静止的车不可能在侧向有一个加速度)。Actuation算是AI系统与物理系统之间融合的一个主要知识点,作者将会在3.8节详细介绍。

留下评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据