游戏人工智能的移动

一、引言

游戏中的人工智能指拥有决策能力的智能体，会对环境的改变作出相应的决策。其中，移动是智能体最基本也是最通用的行为。

智能体的移动可以分为三个环节：

行为选择：该部分负责选定目标、制定计划。它来告诉我们“到这来”和“做好A、B，然后做C”。
操控：该环节负责计算运动数据，根据选择的行为计算得到一个操控力，它决定智能体往哪儿移动以及如何快速移动。
移动：主要表现智能体运动的机械因素，即控制智能体的移动方式。比如，人和汽车有不同的移动方式，虽然他们具有同样的意向，收到相同的操控力，但是最终的移动表现是完全不同的。

二、模型建立：MovingEntity

在开始之前首先建立一个最基本的移动智能体的模型，即确定下移动的环节。

通常一个移动的智能体具有以下属性：

位置：position
方向：rotation
质量：mass
速度：velocity
操控力：force
最大速度：maxSpeed
最大操控力：maxForce
最大转动速率：maxTurnRate

MovingEntity类中需要有Update()方法来每帧更新智能体的物理状态，代码如下：

public void Update()
{
		if (mass == 0) mass = 1;
		Velocity = Force / mass * Time.deltaTime + Velocity;
		if (Velocity.sqrMagnitude > maxSpeed * maxSpeed)
      	Velocity = Velocity.normalized * maxSpeed;
		transform.position += Velocity * Time.deltaTime;

		var fn = Velocity.normalized;
		var vn = transform.forward;
		if (fn == default) return;
		var angle = Vector3.Angle(fn, vn);
		if (angle < 5) return;
		var axis = Vector3.Cross(fn, vn);
		transform.Rotate(axis, -maxTurnRate * Time.deltaTime, Space.World);
		transform.Rotate(transform.forward * rotationSpeed * Time.deltaTime, Space.World);
}

三、个体行为

接下来是最关键的部分，根据不同的行为计算需要施加的操控力。在分析各种行为过程中，我们总是遵循一个公式：

操控力 = 预期速度 - 当前速度

Seek（靠近）

预期速度：这个速度为智能体在理想状态下到达目标位置所需的速度，方向为智能体到目标位置的向量，大小为最大速度。
所需操控力：方向为 (预期速度-当前速度)，大小为最大操控力大小。

public static Vector3 Seek(this MovingEntity entity, Vector3 target)
{
		var dis = target - entity.transform.position;
		var needVelocity = dis.normalized * entity.maxSpeed;
		var deltaVelocity = needVelocity - entity.Velocity;
		return deltaVelocity.normalized * entity.maxForce;
}

Flee（远离）

预期速度与Seek正好相反。
可以进行适当调整，如当目标进入到一定范围内才产生远离的操控力。

public static Vector3 Flee(this MovingEntity entity, Vector3 target, float keepDistance)
{
    var pos = entity.transform.position;
    if ((pos - target).sqrMagnitude >= keepDistance * keepDistance)
    {
        if (entity.Velocity.sqrMagnitude < 0.1)
        {
            entity.Stop();
            return Vector3.zero;
        }
        return entity.Velocity.normalized * -1;
    }
    var needVelocity = (pos - target).normalized * entity.maxSpeed;
    var deltaVelocity = needVelocity - entity.Velocity;
    return deltaVelocity.normalized * entity.maxForce;
}

Arrive（抵达）

与Seek不同，Arrive可以实现减速并停在目标位置。当与目标距离大于阈值时算法与Seek相同，当距离小于阈值时需要进行减速。
进入阈值时的预期速度：方向为智能体到目标位置的向量，大小与距离的1/2次幂成正比。
所需操控力：方向为 (预期速度-当前速度)，大小为最大操控力大小。

public static Vector3 Arrive(this MovingEntity entity, Vector3 target, float slowDownDis = 10)
{
    var toTarget = target - entity.transform.position;
    var dis = toTarget.magnitude;
    if (dis > slowDownDis) return entity.Seek(target);
    if (dis > 0.1)
    {
        var needSpeed = (float)Math.Sqrt(2 * entity.maxForce / entity.mass * dis);
        var needVelocity = toTarget.normalized * needSpeed;
        return (needVelocity - entity.Velocity).normalized * entity.maxForce;
    }
    entity.Stop();
    return Vector3.zero;
}

Pursuit（追逐）

在追逐目标时，我们通常不会直接向目标的当前位置跑，而是会预测目标未来的位置，向预测的位置跑，期间不断通过调整来缩短差距。
预测目标位置的算法可以变得很复杂，但我们可以做个折衷的选择，在保证足够的精度的同时又不会消耗过多的性能。
我们主要要计算的就是追上的位置距离当前目标的位置有多远，这个距离与当前自己与目标的距离成正比，与目标速度的二次幂成正比，与自己速度的二次幂成反比。
此外，需要考虑一种特殊情况，当目标朝向自己跑时，这时候不需要预测位置，直接朝向目标当前位置跑就能追上了。

public static Vector3 Pursuit(this MovingEntity entity, MovingEntity target, float keepDistance = 0.1f)
{
    var dir = entity.transform.position - target.transform.position;
    // 追到目标后停止
    if (dir.sqrMagnitude <= keepDistance * keepDistance)
    {
        entity.Stop();
        return Vector3.zero;
    }
    //当目标朝向自己时，直接向目标当前位置移动
    if (Vector3.Angle(dir, target.transform.forward) < 20)
    {
        return Seek(entity, target.transform.position);
    }
    //当目标在向其他方向移动时，需要预判目标一段时间后的位置。
    var tarSpeed = target.Velocity.magnitude;
    var lookAheadDis = dir.magnitude * tarSpeed / entity.maxSpeed;
    var tarPos = target.transform.position + target.Velocity.normalized * lookAheadDis;
    return entity.Seek(tarPos);
}

Evade(逃避)

和追逐类似，只是方向相反，且不用检查是否正面。

public static Vector3 Evade(this MovingEntity entity, MovingEntity target, float keepDistance)
{
    var dir = entity.transform.position - target.transform.position;
    var tarSpeed = target.Velocity.magnitude;
    var lookAheadDis = dir.magnitude * tarSpeed / entity.maxSpeed;
    var tarPos = target.transform.position + target.Velocity.normalized * lookAheadDis;
    return entity.Flee(tarPos, keepDistance);
}

Wander（徘徊）

定义：产生一个操控力，使智能体在场景内随机移动。
两个错误（欠优）的思路：1.使用普通的随机算法每帧都计算一个随机的驱动力：因为随机算法取到的随机数不是连续的，所以无法实现持续的驱动力变化，会产生抖动。2.使用Perlin噪声，可以产生连续的转弯，但是性能开销较大。
Reynolds的解决方案：在智能体前端突出一个圆圈，目标被限制在该圆圈上。每帧给目标添加一个随机的位移，来产生一个随机但连续的操控力。通过控制圆圈的半径、圆圈到智能体的距离以及每帧随机位移的大小，就能产生各种形式的随机运动。
三维空间中，智能体的目标就改成限制在一个球体上。

public static Vector3 Wander(this MovingEntity entity, float wanderRadius, float wanderDistance, float wanderJitter,
    bool limit = true)
{
    entity.WanderTarget += new Vector3(Random.Range(-1 * wanderJitter, wanderJitter),
        Random.Range(-1 * wanderJitter, wanderJitter), 0);
    var limitParam = limit ? 0 : 1;
    var wanderCirclePoint = entity.Velocity.normalized * wanderDistance + entity.transform.position * limitParam;
    entity.WanderTarget = wanderCirclePoint + wanderRadius * (entity.WanderTarget - wanderCirclePoint).normalized;
    return entity.Seek(entity.WanderTarget);
}

Interpose（插入）

定义：产生一个操控力，控制智能体移动到两个智能体的中点，可以用于运动员截球，保镖保护老板等行为。
实现方法：
- 计算智能体移动到当前两个目标连线中点需要的时间t。
- 计算t时间后两个目标所在的位置。
- 连线中点就是智能体的目标位置，使用Arrive移向它。

public static Vector3 Interpose(this MovingEntity entity, MovingEntity targetA, MovingEntity targetB)
{
    var targetAPos = targetA.transform.position;
    var targetBPos = targetB.transform.position;
    var centerNow = (targetAPos + targetBPos) / 2;
    var time = (entity.transform.position - centerNow).magnitude / entity.maxSpeed;
    var targetAPosPre = targetAPos + targetA.Velocity * time;
    var targetBPosPre = targetBPos + targetB.Velocity * time;
    return entity.Arrive((targetAPosPre + targetBPosPre) / 2);
}

Offset Pursuit（保持一定偏移的追逐）

定义：在追逐的同时保持智能体与目标之间有一个指定的偏移。可用于体育比赛中的盯防、实现战斗编队、空中飞船对接等。
实现思路：与追逐类似，需要预测下一个带偏移的目标位置，然后用Arrive接近该位置（不能用Seek）。

public static Vector3 OffsetPursuit(this MovingEntity entity, MovingEntity target, Vector3 offset)
{
    var dir = entity.transform.position - target.transform.position;
    var tarSpeed = target.Velocity.magnitude;
    var lookAheadDis = dir.magnitude * tarSpeed / entity.maxSpeed;
    var tarPos = target.transform.position + target.Velocity.normalized * lookAheadDis +
                 target.transform.TransformVector(offset);
    return entity.Arrive(tarPos, 10);
}

四、群体行为

在群组中，通常个体的感知范围是有限的，因此每个智能体都有邻域的概念，只有在距离自己一定范围内的智能体才能感知到。这个数据可以以列表的形式存在MovingEntity中，在每一帧去更新这个列表。
更进一步地，可以增加可视域的限制，智能体只能看见一定视角范围内的其他智能体，来达到更真实的模拟。

Separation（分离）

定义：产生一个操控力，使得智能体远离临近的智能体，且这个力的大小反比于两个智能体之间的距离。
结合：分离可与其他个体行为结合，形成各种群体行为，如群体追逐、群体靠近、群体远离等。

public static Vector3 Separate(this MovingEntity entity, List<MovingEntity> teammate, float desiredSeparation = 2)
{
    var force = Vector3.zero;
    Vector3 dir;
    float dis;
    var count = 0;
    foreach (var mv in teammate)
    {
        if (mv == entity) continue;
        dir = entity.transform.position - mv.transform.position;
        dis = dir.magnitude > 0.1f ? dir.magnitude : 0.1f;
        if (dis <= desiredSeparation)
        {
            force += dir.normalized / dis;
            count++;
        }
    }
    if (count == 0) return Vector3.zero;
    return force.normalized * entity.maxForce;
}

Alignment（队列）

定义：智能体企图与邻域中的智能体保持一致的方向。
预期速度：邻域中所有智能体的平均速度。
可用于模拟马路上汽车的运动

public static Vector3 Align(this MovingEntity entity, List<MovingEntity> teammate, float neighborDist = 10)
{
    var needVelocity = Vector3.zero;
    var count = 0;
    foreach (var mv in teammate)
    {
        if (mv == entity) continue;
        if ((entity.transform.position - mv.transform.position).sqrMagnitude <= neighborDist * neighborDist)
        {
            needVelocity += mv.Velocity;
            count++;
        }
    }
    if (count <= 0) return Vector3.zero;
    needVelocity /= count;
    return (needVelocity - entity.Velocity).normalized * entity.maxForce;
}

Cohesion（聚集）

定义：智能体试图朝向邻域中所有智能体的质心移动。
实现思路：求邻域的质心并靠近（Seek）。

public static Vector3 Cohesion(this MovingEntity entity, List<MovingEntity> teammate, float neighborDist = 10)
{
    var center = Vector3.zero;
    var count = 0;
    foreach (var mv in teammate)
    {
        if (mv == entity) continue;
        if ((entity.transform.position - mv.transform.position).sqrMagnitude <= neighborDist * neighborDist)
        {
            center += mv.Velocity;
            count++;
        }
    }
    if (count <= 0) return Vector3.zero;
    center /= count;
    return entity.Seek(center);
}

Flocking（群集）

鸟群算法（Boids）：Reynolds提出将分离、队列、聚集三种群体行为以一定权重组合，就能模拟各种群集的移动，如：鸟群、鱼群、羊群等。
特点：群集不需要任何控制中心或Leader就能实现自发的移动，每个单元都是平等的，受到整体的影响，同时也会影响整体。
在此基础上可以加入Wander或Seek，保证单位掉队时不会停下。
扩展：为了达到更自然的模拟效果，可以用Perlin噪声生成权重，使分离、队列、聚集三种行为的权重随着时间变化。

五、组合操控行为

带优先级的加权截断总和

每个行为都有优先级，按照优先级顺序计算操控力。
每一帧有可用操控力的概念。
计算步骤：
- 计算优先级最高的行为的操控力。
- 若该操控力已将可用操控力用完，则不进行后续运算，直接执行该操控力。
- 若还有剩余的操控力，则进行下一个优先级行为的计算，计算结果按照最大操控力和剩余操控力的值两者的较小值截断。
- 以此类推直到可用操控力用完。

带优先级的抖动

每个行为都有优先级和执行概率。
计算步骤：
- 根据优先级最高行为的执行概率计算是否需要计算该行为的操控力。
- 如果要求值而且求出的操控力不为零，则直接执行该行为，不考虑其他行为。
- 否则继续计算下一优先级的行为，以此类推。
适用于不需要非常精确的情形。

六、优化方法

尽量使用距离的平方。
若经常需要计算三角函数，可以建立正余弦查询表。
减少不必要的中间结果变量创建，特别是在循环中。
网格空间分隔
- 问题：在群体移动行为相关的算法中，通常每个智能体都需要遍历邻域中的所有智能体，复杂度为O(N2)。
- 网格空间分隔：将空间分割为若干网格，每个网格维护一个List，储存其中的智能体。每帧开始时根据位置更新所有网格的数据。在具体行为的计算时，每个智能体能根据自己的位置确定处于哪个网格，该网格（或包含相邻网格）下的所有智能体就是自己邻域中的智能体。
- 复杂度：O(N)

参考资料：

《游戏人工智能编程案例精粹》第3章：如何创建自治的可移动游戏智能体
《代码本色》第6章：自治智能体

Demo地址：https://github.com/Luciano-0/AIMovement.git