【游戏 AI】9 – 运动学移动算法

如上一篇文章所说的，移动算法通常分为两大类：运动学移动算法 和 动态移动算法。这篇文章主要介绍运动学移动算法，相比较而言，运动学移动算法虽然更简单，但却十分实用。

运动学移动算法输入是静态数据（位置和方向，没有速度），输出是所需的速度。输出通常只是一个开或关、或者是目标方向、以全速移动、静止。运动学算法不使用加速度，尽管速度的突然变化可能被平滑在几个帧。

许多游戏甚至将事情简化得更简单：它强迫角色的方向与它所行进的方向一致；如果角色是静止的，它要么面对一个预先设定的方向，要么面对它移动的最后一个方向。

如果它的运动算法返回一个目标速度，那么这个速度将用于设置它的方向，这可以用下面的函数简单地完成

我们将看两种运动学移动算法：追逐和漫步。建立运动学移动算法是极其简单的，所以我们将只看这两个代表性的样例。而与之对应的动态移动算法会在后续的文章中更多地介绍。

然而，我必须强调，这种简洁并不是因为它们不常见或不重要，在许多游戏中，运动学移动算法仍然是移动系统的主要组成部分。后续文章中角色移动由物理引擎控制的动态算法确实很常见，但并不是全都是这样实现的。

一、追逐

运动学追逐行为以角色的静态数据和目标的静态数据作为输入，它计算从角色到目标的方向，并请求沿着这个方向的速度。该算法可以用几行代码中实现，

其中，将 normalize 方法应用于向量将其变成单位向量，即长度为1；当然，如果这个向量是零向量，那么它保持不变。

1.1 数据结构和接口

我们使用静态数据结构作为运动学移动算法的输出，输出数据结构形式如下所示，

该算法设计旋转，角色的方向是简单地根据他们的移动来设置的，当然如果你想要以某种方式独立地控制方向，就按照你想要的方式设置即可。

1.2 性能

算法的时间复杂度和空间复杂度都是 O(1)。

1.3 逃跑

如果我们想让角色远离目标，我们可以简单地反转 getSteering 方法的第二行，

然后角色会以相反的方向以最大速度移动。

1.4 到达

以上算法是为一个追逐的角色设计的，但如果真这么写，它永远不会达到它的目标，因为它总是以全速移动，它很可能会超过一个精确的点，并在连续的帧中前后摆动，试图到达那里。这种典型的摆动表现必然无法接受，我们必须要做到在目标点静止不动。

要做到这一点，我们有两个选择。我们可以给算法一个大的满足半径，当它更接近它的目标时就满足它。或者，我们可以给移动速度一个范围，在人物到达目标时减慢速度，使其不太可能跑过头。

第二种方法仍然会引起摆动表现，事实上我们可以稍微结合两种方法，让角色慢下来可以让我们使用一个更小的满足范围而不会摇摆，也不会让角色突然停止。

我们可以修改追逐算法来检查角色是否在半径内：如果在半径内，它不输出任何东西；如果不是，它就会试图在固定的时间内到达目标，比如用 0.25 秒，设定速度为距离除以 0.25 秒，如果这个速度超过了最大速度，那么它仍会以最大速度运动。固定的目标时间是一个简单的技巧，可以使角色逐渐减速到达目标。在 1 单位距离时，它想以每秒 4 单位的速度运动；在 0.25 单位距离时，它想以每秒 1 单位的速度运动；以此类推。可以通过调整这个固定的时间长度以获得正确的效果：数值越高，减速越平缓；反之，数值越低，刹车越突然。算法如下所示，

其中，假设了一个长度函数 length()，作用是得到一个向量的长度。

二、漫步

运动学漫步行为总是以最大速度沿着角色当前的方向运动，转向行为修改角色的方向，这允许角色在向前移动时转弯。下图说明了这一点，角色在连续的帧中显示，注意它只在每一帧向前移动，即它始终对着前一帧的方向。

1.1 伪代码

实现伪代码如下所示，

其中，方向值有一个转换成方向矢量的函数 asVector。

1.2 实现的注意事项

我使用了 randomBinomial 函数来生成旋转角度，这是一个便利的随机数函数，在编程语言的标准库中并不常见，它返回一个介于 -1 和 1 之间的随机数，其中值更可能在 0 左右。它可以简单地创建为，

其中，random() 返回一个从 0 到 1 的随机数。

对于我们的漫步行为，这意味着角色最有可能继续沿着当前的方向前进，微调方向的可能较大，而迅速改变方向的可能性较小。