运动是游戏AI中一个最基本的问题。

在游戏中,运动主要是要更新物体的位置、方向、速度。对于他们的控制算法可以分为两大类,一种是基于“运动学”(Kinematics)的,另一种是基于“动力学”(Dynamic)的。

简单来说,运动学的算法直接控制速度。而动力学的算法通过控制力,来控制速度。

这两种方法现在都有使用,主要根据游戏的特性来选择,而且也比较容易分辨。使用运动学算法的游戏,往往角色的移动没有惯性,想走就走,想停就停,也没有加速、减速的过程,现在大多游戏是使用这种方法。使用动力学算法的游戏,有惯性,有加速减速过程,典型的是赛车竞速游戏。

这篇文章主要介绍基于运动学的运动算法,并以二维情况为例。该算法非常简单,只涉及中学物理知识。

数据结构

算法涉及两类数据,一类是描述静止状态的变量(位置、方向),另一类是描述运动状态的变量(速度、角速度)。

就二维的情况而言,一般用一个二维向量描述物体位置,再用一个角度描述方向。也有一些情况,用一个单位向量描述方向(大部分是三维的情况)。速度、角速度的描述方式和位置、方向的描述方式对应。

方向的控制

绝大多数使用了运动学算法的游戏中,会直接忽略角速度。他会让角色始终朝向运动方向(例如魔兽世界)。但是也有例外,比如魔兽争霸。熟悉Dota的应该知道,Dota中不同英雄的转身速度是不同的。

追踪

以追踪为例来讲述运动学的运动算法。在追踪这个任务中,有一个本角色,还有一个目标角色。简单的说就是本角色追着目标角色跑。每个角色除了有自己的位置、方向、速度、角速度外,还需要一个最大速度。

我们马上就能想到,在游戏的每一帧,本角色通过目标角色的位置就能更新自己的速度。并且直接将速度设为最大速度。在真实世界中确实是如此,但在游戏中这样是有问题的

游戏的世界和真实世界有一个区别,真实世界的时间是连续的,游戏世界的时间是离散的。例如每秒60帧,那么对于游戏而言这一秒就只有60个时间点。这样一来,如果按照上面的方法,即使目标角色是静止的,本角色也会绕着目标角色摇摆。因为恰好追到目标角色的时间点是达不到的。

为了解决这个问题,我们可以设定一个目标距离,只要小余那个目标距离,就可以停止。但这样仍然存在问题,当角色速度过快,或者帧数过低的时候,为了避免摇摆的问题,我们不得不设定比较大的目标距离。

为了解决这个问题,我们可以给本角色设定一个减速的机制,即随着距离减小,将速度也减小。一种比较好的算法是:

$$本角色速度=min(最大速度, a/距离)$$

此处$a$是一个可调的参数。这样一来,本角色在距离目标角色较远时就会以最大速度追踪,到一定范围内时,就渐渐减小速度,最终趋于无穷小。用这个算法,既解决了摇摆问题,也不再需要设定目标半径。当目标角色逃离时,本角色还会加速追踪。

另外,这个追踪的算法可以一些改变,例如,本角色在决定速度方向时,先预测目标角色未来的位置,根据目标角色未来的位置决定本角色的速度方向。未来位置是可以根据目标角色的速度来预测的。

除了追踪以外,还有很多其他任务,但基于这样的思想,也都大同小异。