Steering Behaviors 详解

作者:吴小含

导语

Steering Behaviors 意在使游戏中的AI个体具备真实的运动行为,通过对力的施加与整合,使游戏个体具备类生命体般的运动特征。这项技术并不基于寻路或者别的宏观算法,而是基于个体局部周围空间的信息,单个的行为实现起来非常的方便,它们组合在一起又能有非常复杂的行为方式。

Seek

实现Steering所涉及到的所有运算都可以用向量计算来实现,而Steering系统产生的力会运用在游戏个体的速度和位置更新上,所以最好是用向量来表示物体的速度和位置。

虽然说向量表示方向,但是在其表示位置时又会被忽略。

上图表示一个个体在位置(x,y),并且它的速度是(a, b)。它的移动用欧拉积分表示为

position = position + velocity

速度向量的方向控制个体移动的朝向,速度向量的长度控制个体的移动速度。长度越大,个体移动得越快。速度向量会被截取在一个范围里。

velocity = normalize(target - position) * max_velocity

以上的算法是一个基本Seek行为,但不带任何Steering输出的力,可以注意到,在该公式作用下,游戏个体的移动方式是直线型的,如果target的位置变了的话,个体会立即响应,并且会以新的方向,以直线的形式向目标位置靠近,这会给人一种从当前路径突兀的变换到新路径的感觉。

如果只考虑速度方向的力,就会有这种突兀的行为,Steering Behaviors 的核心理念就是通过施加多个力(Steering Forces)来影响个体的移动,个体的运动方向根据这些力的合力得出。

就Seek行为来说,每帧向游戏个体施加一个额外的转向力来调整速度,会使路径变化没有那么突兀。如果目标位置变了,个体也会根据新位置慢慢的转变自己的速度向量。

Seek行为被分解为两个力:目标速度,和转向速度。

目标速度始终朝向目标位置,转向力是目标速度减去个体的当前速度得出的,它的物理意义就是向着目标位置给个体一个推力。

desired_velocity = normalize(target - position) * max_velocity
steering = desired_velocity - velocity

计算了转向力之后,它必须和原先版本的速度方向合成,再施加给个体。这个每帧施加的额外转向力会使得个体以平滑的方式靠近目标点。

最终的计算方法为

steering = truncate (steering, max_force)
steering = steering / mass

velocity = truncate (velocity + steering , max_speed)
position = position + velocity

转向力会被截断在一个范围,防止其超过个体最大可承受力。被截断的转向力会除以个体的质量,因为不同重量的物体运动快慢是不同的。

Flee

之前描述的seek行为基于两个力,一个是目标速度,一个是朝目标位置的推力。

desired_velocity = normalize(target - position) * max_velocity
steering = desired_velocity - velocity

desired_velocity在这里就是离目标位置的最短路径,根据目标点的位置和个体的位置相减得出,代表了一个以个体位置为起点,朝向目标点的力。

Flee行为也用到这两个力,区别是它们被调整为使游戏个体远离目标位置。

Flee行为中 desired_velocity 根据个体的位置和目标点的位置相减得出,产生了一个以目标点为起点,朝向个体的力。

最终合力的计算几乎和Seek行为一样:

desired_velocity = normalize(position - target) * max_velocity
steering = desired_velocity - velocity

在Flee行为中,desired_velocity 代表了个体逃离目标的最短路径,转向力会将个体推向目标速度方向。

比较在Seek行为 和 Flee行为里 desired_velocity 的关系,会得出以下的关系:

flee_desired_velocity = -seek_desired_velocity

同样在计算完转向力之后,它也必须和个体的速度向量合成来作用于个体。因为这一次转向力始终将个体推离目标位置,这将会产生一条逃离路径。

目前,不管多远距离目标位置都会影响到个体,可以通过添加一个影响范围来只在个体靠近目标点时作用。

Arrival

我们看到Seek行为使个体向目标位置移动,当个体移动到目标点后,算法仍旧作用在个体之上,对它施加转向力,这会导致个体在目标点周围来回移动。

Arrival行为会规避个体移动超过目标点的现象,当个体靠近目标点时,它会使个体减速,最终停在目标点上。

行为被分成两个阶段,第一阶段是个体还远离目标点时,它的工作方式和之前介绍的Seek行为一样,第二阶段是个体靠近目标点时,在减速范围内。

当个体进入到减速范围内,它会持续减速直到停在目标点上。

当个体进入到减速范围内,速度会线性的衰减到 0,通过加入一个新的转向力来达到这个效果,这个转向力最终会变成 0 ,意味着最终个体在目标点上,不会再有任何别的力施加了。

velocity = truncate(velocity + steering, max_speed)
position = position + velocity

function truncate(vector:Vector3D, max:Number) :void {
    var i :Number;
    i = max / vector.length;
    i = i < 1.0 ? i : 1.0;
    vector.scaleBy(i);
}

为了确保个体在它完全停止前线性的减速,速度不能直接设为 0,减速计算将会根据 个体到目标点的距离,和减速区域,得出一个线性的结果。

desired_velocity = target - position
distance = length(desired_velocity)
if (distance < slowingRadius) {
   desired_velocity = normalize(desired_velocity) * max_velocity * (distance / slowingRadius)
} else {
    desired_velocity = normalize(desired_velocity) * max_velocity
}

steering = desired_velocity - velocity 如果距离比slowingRadius大,这意味着个体离目标点还远,那它的速度将保持为max_velocity。

如果距离比slowingRadius小,这意味着个体已经进入到减速区域,那以为着它应该减速。

表达式 distance / slowingRadius 会从1变化到 0,这种线性的变化会使速度平滑的变到0。

steering = desired_velocity - velocity
velocity = truncate (velocity + steering , max_speed)
position = position + velocity

根据之前说的个体 Steering运动的表达形式,如果desired_velocity降为0,那么转向力会是

  • velocity,那么它和速度方向的合力为 0,个体就不会运动了。

Wandering

游戏中的个体常常会有随机性的巡逻情景。通常这些个体在等待某些事情发生,比如说发现玩家然后开战,或者寻找某些东西。当这些行为呈现在玩家面前时,它们必须在视觉感官上市真实可信,富有乐趣的。

如果玩家能够很容易的分辨出游戏AI的运动路径,或者别的不真实的移动行为,这会增加玩家的挫败感。最差的情况,玩家可以很清楚的预判AI的移动行为,这最终会导致一个枯燥的游戏体验。

Wander 行为意图产生一种真实可玩的移动行为,使玩家以为游戏AI是真实的生命体在游戏中巡逻。

基于SteeringBehaviors 有几种方法来实现Wander的特征。最简单的是使用前面提到过的Seek行为,在游戏AI进行Seek行为的时候,它会朝着目标不断前进,如果目标点每隔几秒钟改变一次,那么游戏AI就永远也到不了目标点,在游戏场景中不断的改变目标点,会让游戏AI不断的去追踪目标。

实现代码:

private function wander() :Vector3D {
   var now :Number = (new Date()).getTime();
   if (now >= nextDecision) {
    // Choose a random position for "target"
   }
   return seek(target);
}

public function update() :void {
   steering = wander()
   steering = truncate (steering, max_force)
   steering = steering / mass
   velocity = truncate (velocity + steering , max_speed)
   position = position + velocity
}

尽管这是一个不错的解决方法,但是最终的结果并不是那么让人信服。有时候游戏AI会完全翻转他们的行动路径,因为目标点正好随机到了身后。游戏AI的行为看上去更像是“哎呀,我忘记了我的钥匙”然后是“好吧,我就顺着这个方向走”。

Wander行为

另一种实现方式是每帧产生一个 小而随机的 移位力来作用在游戏AI当前移动方向之上。因为速度向量代表了个体移动的方向,所以任何微小的改变会影响到个体的行进方向。

每一帧施加一个微小的 移位力会规避游戏AI突然改变自己路径的突兀感,比如游戏AI上一帧是朝上方运动并朝右转向,那这一帧该游戏对象同样是朝上方运动并朝右转向,区别只是角度有一点不同。

有很多种方式实现这种思路,起中一种简单的方式是在游戏AI的前方加一个圈,圈的半径以及角色到圈的距离越大,施加在角色身上的推力就越强。

要计算Wander力,第一步是要得出圈的中心位置,因为圈必须是在角色的正前方,所以我们可以利用速度向量作为方向。

var circleCenter :Vector3D;
circleCenter = velocity.clone();
circleCenter.normalize();
circleCenter.scaleBy(CIRCLE_DISTANCE);

上面的circleCenter向量是速度向量的拷贝,它被归一化后乘以了一个放大系数。

下一步是计算移位力,它负责使个体左转和右转。因为这是一个用于扰乱的力,所以它其实可以指向任意方向,我们暂且用一个和Y轴平行的力来表示。

var displacement :Vector3D;
displacement = new Vector3D(0, -1);
displacement.scaleBy(CIRCLE_RADIUS);
setAngle(displacement, wanderAngle);
wanderAngle += (Math.random() * ANGLE_CHANGE) - (ANGLE_CHANGE * .5);

移位力被创建出来,并且根据圈的半径被放大,和前面提到的一样,圈的半径越大,移位力就越大,wadnerAngle是一个缩放因子,它定义了移位力该倾斜多少,这里使用了一个随机值来让它每帧都不一样。为了更好的理解原理,我们假设移位力是在圈的中心计算的。因为它的向量长度等于圈的半径,所以它看起来如同这样:

在计算完圈的中心和,移位力的大小之后,将他们整合在一起就是Wander力。

var wanderForce :Vector3D;
wanderForce = circleCenter.add(displacement);

从视觉上来看,它应该是这样:

wander力可以想象成以游戏AI为起点,指向圈上的某个点向量,具体这个点的位置会决定施加在游戏AI身上的力是朝左还是右,是强还是弱:

wander力越和速度向量平行,游戏AI转变得就越少,wander力和之前介绍的seek和flee力一样,会将游戏AI推向一个方向。但是不同的是前者是根据圈上的一个随机位置来决定推向哪,而后者是根据一个目标位置。

private function wander() :Vector3D {
   var circleCenter :Vector3D;
   circleCenter = velocity.clone();
   circleCenter.normalize();
   circleCenter.scaleBy(CIRCLE_DISTANCE);
   var displacement :Vector3D;
   displacement = new Vector3D(0, -1);
   displacement.scaleBy(CIRCLE_RADIUS);
   setAngle(displacement, wanderAngle);
   wanderAngle += Math.random() * ANGLE_CHANGE - ANGLE_CHANGE * .5;
  var wanderForce :Vector3D;
   wanderForce = circleCenter.add(displacement);
   return wanderForce;
}

public function setAngle(vector :Vector3D, value:Number):void {
   var len :Number = vector.length;
   vector.x = Math.cos(value) * len;
   vector.y = Math.sin(value) * len;
}

Pursuit

追踪是指朝着移动目标运动并试图抓住它,这里说的“抓住”很重要,如果只是朝着目标运动,那基本上只是重复目标的运动轨迹。在追踪的时候,追踪者必须做出一定的预判,如果能够预判出目标接下去几秒的位置,就能够调整自己当前的速度来抓住它。

如同Seek章节里说的,运动用欧拉插值法来表示

position = position + velocity

如果游戏个体的位置和速度是可知的,那就可以预测它在未来一段时间 T 之后的位置。假设被预测的物体是以直线方式运动的,并且我们只预测,三次Update之后的位置。那么游戏个体被预测的位置就是:

position = position + velocity * T

预测的关键是找到合适的 T 的值,如果这个值太大了,那么追踪者会追踪一个太过靠前的幽灵,如果T太小了那么追踪者实际追踪当前个体位置,没有预测成分,变成追随行为。

追踪行为和seek行为工作方式基本差不多,位移区别是追踪的目标不是目标本身而是目标未来的位置。

假设游戏中的个体都叫Boid,下面的伪代码实现了基本的追踪原理:

public function pursuit(t :Boid) :Vector3D {
  T :int  = 3;
  futurePosition :Vector3D = t.position + t.velocity * T;
  return seek(futurePosition);
}

在计算完追踪力后,同样它必须和当前速度相加。

public function update() :void {
  steering = pursuit(target)
  steering = truncate (steering, max_force)
  steering = steering / mass
  velocity = truncate (velocity + steering , max_speed)
  position = position + velocity
}

追踪者会顺着橙色的路径,追捕目标。

当T是一个常数时,会有一个问题:在离目标点很近的距离下,追踪的准确度会变得很差。这是因为当追踪者靠近目标后,追踪者还是以常数T时间后的位置进行预测。这和真实的追踪行为相违背,真实的追铺在靠近物体后会停止预测,并且以物体当前实际位置作为目标点。有一个简单的方式来改进我们上面的追捕逻辑,就是用动态的T来替换之前恒定的T。

T = distanceBetweenTargetAndPursuer / MAX_VELOCITY

新的T根据两个角色间的距离计算得出,新的T的意义是,得出根据追踪者的最大速度,需要多少个Update来逮住目标。距离越长,T就越大,这个时候追踪者就会预测得比较远,相反追踪者会预测最近的时间位置。

public function pursuit(t :Boid) :Vector3D {
  var distance :Vector3D = t.position - position;
  var T :int = distance.length / MAX_VELOCITY;
  futurePosition :Vector3D = t.position + t.velocity * T;
  return seek(futurePosition);
}

整合

每一个Steering行为会产生一个力,他们会作用在速度向量上,这个合力的方向和大小会驱动AI个体实现一些行为(如Seek,Flee,Wander等),大致的计算方式如下:

steering = seek(); // this can be any behavior
steering = truncate (steering, max_force)
steering = steering / mass

velocity = truncate (velocity + steering , max_speed)
position = position + velocity

因为Steering力是向量,向量能和别的向量叠加。真正神奇的事情是它能和任意数量的向量叠加。

steering = nothing(); 
steering = steering + seek();
steering = steering + flee();
(...)
steering = truncate (steering, max_force)
steering = steering / mass

velocity = truncate (velocity + steering , max_speed)
position = position + velocity

整合后的Steering力最终会形成一个代表了所有分力的合力。在上面的代码中,最终的Steering力会使游戏角色在Seek某些东西的同时躲避另一些东西。

看一下下面的合力的例子:

这种将单个行为整合在一起的方式可以产生非常复杂的运动行为。想象一下如果是通过编码来实现会有多困难,这些计算可能需要计算距离,区域,路径,图结构等,如果你关心的事情还是动态的,那基本上每一帧都要去计算这些东西。

而Steering行为中,所欲的力都是动态的,它们本身就是在游戏的每一帧计算的,因此它们能够顺应环境的变化。

为了同时能够方便的使用多个Steering行为,一个用于管理的Manager很有必要。目的是能够创建一个黑盒,使得所有游戏中的个体都能够具备Steering的能力。

Manager会持有游戏个体的一个引用,这个游戏个体姑且称为Host, Manager会提供给这个个体一堆Steering方法,比如Seek 和 Flee。每一次方法被调用,Manager会更新其内部的属性产生一个Steering力。

在Manager处理完所有的调用后,Manager会将Steering力赋给Host作为其速度向量。

Manager有一堆方法,每个代表了一个Steering行为,每个行为都需要外部的一些信息来使自己工作,比如Seek行为需要外部提供一个目标点,追踪行为需要目标更多的一些信息,如当前位置和速度。空间中的位置也可以用向量表示,这在大多数游戏引擎中非常常见。

在追踪行为中的目标实际上可以是任何东西。为了让Manager更通用,Manager所接收的target必须遵循一定的规则,提供一些查询接口。

假定IBoid描述了游戏中可以使用Steering行为的所有个体。只要实现这个接口,就能够被Manager接收。

public interface IBoid
{
    function getVelocity() :Vector3D;
    function getMaxVelocity() :Number;
    function getPosition() :Vector3D;
    function getMass() :Number;
}

现在Manager可以以一种通用的方式和个体进行交互了。Manager由两个基本属性和一堆方法构成。

public class SteeringManager
{
    public var steering :Vector3D;
    public var host :IBoid;

    // The constructor
    public function SteeringManager(host :IBoid) {
        this.host   = host;
        this.steering   = new Vector3D(0, 0);
    }

    // The public API (one method for each behavior)
    public function seek(target :Vector3D, slowingRadius :Number = 20) :void {}
    public function flee(target :Vector3D) :void {}
    public function wander() :void {}
    public function evade(target :IBoid) :void {}
    public function pursuit(target :IBoid) :void {}

    // The update method. 
    // Should be called after all behaviors have been invoked
    public function update() :void {}

    // Reset the internal steering force.
    public function reset() :void {}

    // The internal API
    private function doSeek(target :Vector3D, slowingRadius :Number = 0) :Vector3D {}
    private function doFlee(target :Vector3D) :Vector3D {}
    private function doWander() :Vector3D {}
    private function doEvade(target :IBoid) :Vector3D {}
    private function doPursuit(target :IBoid) :Vector3D {}
}

Manager在实例化的时候必须接收一个对Host的引用,Manager会在之后改变Host的速度向量。

每个行为被表示为两个方法,一个Public的一个Private的。拿Seek来作为例子:

public function seek(target :Vector3D, slowingRadius :Number = 20) :void {}
private function doSeek(target :Vector3D, slowingRadius :Number = 0) :Vector3D {}

Public的Seek方法用来告诉Manager应用这种行为。这个方法没有返回值,它的参数和行为本身有关。在之后的Private方法里会返回一个经过Steering计算的向量值,这个向量值会存放在Manager的属性中。

public function seek(target :Vector3D, slowingRadius :Number = 20) :void {
    steering.incrementBy(doSeek(target, slowingRadius));
}

// The real implementation of seek (with arrival code included)
private function doSeek(target :Vector3D, slowingRadius :Number = 0) :Vector3D {
    var force :Vector3D;
    var distance :Number;

    desired = target.subtract(host.getPosition());

    distance = desired.length;
    desired.normalize();

    if (distance <= slowingRadius) {
        desired.scaleBy(host.getMaxVelocity() * distance/slowingRadius);
    } else {
        desired.scaleBy(host.getMaxVelocity());
    }

    force = desired.subtract(host.getVelocity());

    return force;
}

别的行为也是类似的实现方式。

public function pursuit(target :IBoid) :void {
    steering.incrementBy(doPursuit(target));
}

private function doPursuit(target :IBoid) :Vector3D {
    distance = target.getPosition().subtract(host.getPosition());

    var updatesNeeded :Number = distance.length / host.getMaxVelocity();

    var tv :Vector3D = target.getVelocity().clone();
    tv.scaleBy(updatesNeeded);

    targetFuturePosition = target.getPosition().clone().add(tv);

    return doSeek(targetFuturePosition);
}

每次行为方法被调用,返回的向量会被加到Manager的属性steering中。这个属性就代表了所有行为的结果。

在所有行为被调用之后,Manager会把steering的值赋给host的velocity。

public function update():void {
    var velocity :Vector3D = host.getVelocity();
    var position :Vector3D = host.getPosition();

    truncate(steering, MAX_FORCE);
    steering.scaleBy(1 / host.getMass());

    velocity.incrementBy(steering);
    truncate(velocity, host.getMaxVelocity());

    position.incrementBy(velocity);
}

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能头条

浅析强化学习及使用Policy Network实现自动化控制

1262
来自专栏云时之间

NLP系列学习:命名实体识别(一)

在自然语言处理中,分词,词性标注,命名实体识别和句法情感分析是非常关键的分支,因为最近需要对此有一些应用,便去了解了一下特定领域目前使用的方法以及一些困难,特此...

1113
来自专栏智能算法

机器人算法专题介绍

算法 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规...

3526
来自专栏Soul Joy Hub

基于Spark的大数据精准营销中搜狗搜索引擎的用户画像挖掘

转载请注明:转载 from http://blog.csdn.net/u011239443/article/details/53735609 from C...

7173
来自专栏CDA数据分析师

测试:你是否具备企业的数据挖掘能力?

1.某超市研究销售纪录数据后发现,买啤酒的人很大概率也会购买尿布,这种属于数据挖掘的哪类问题? A. 关联规则发现 B. 聚类 C. 分类 D. 自然语言处理 ...

1976
来自专栏yw的数据分析

R语言各种假设检验实例整理(常用)

一、正态分布参数检验 例1. 某种原件的寿命X(以小时计)服从正态分布N(μ, σ)其中μ, σ2均未知。现测得16只元件的寿命如下:           ...

4614
来自专栏机器之心

谷歌微软等科技巨头数据科学面试107道真题:你能答出多少?

选自Learndatasci 机器之心编译 参与:李泽南 来自 Glassdoor 的最新数据可以告诉我们各大科技公司最近在招聘面试时最喜欢向候选人提什么问题。...

2567

组和分组卷积

考虑一个正方形。它是对称的吗?它是如何对称的?它有多少对称性?它有什么样的对称性?

25210
来自专栏机器人网

机器人参数坐标系有哪些?各参数坐标系有何作用?

工业机器人的坐标形式有直角坐标型、圆柱坐标型、球坐标型、关节坐标型和平面关节型。

722
来自专栏牛客网

头条算法岗

无论走到哪里,都应该记住,过去都是假的,回忆是一条没有尽头的路,一切以往的春天都不复存在,就连那最坚韧而又狂乱的爱情归根结底也不过是一种转瞬即逝的现实。——马尔...

1154

扫码关注云+社区