STEERING BEHAVIORS

If you happen to have even a slight interest in motion planning and related branches of computer science, you cannot afford to miss out on this paper by Craig Reynolds titled: "Steering behaviors for autonomous characters". In it, Reynolds lays out a collection of elementary methods for steering virtual agents and demonstrates how their extension and combination may result in emergent realistic-looking behavior.

In this project, we implement these elementary steering behaviors and use them to model a variety of agent archetypes.

Note: most of the time we will stick to the terminology and implementation details found in Reynolds' paper, but not always.

Table of contents

Introduction

We begin with a concrete definition of the virtual world we intend to simulate, which consists of two aspects: (1) vehicles, and (2) the logic that drives them.

Modeling vehicles

Remaining true to Reynolds' terminology, in this context we rather refer to virtual agents as vehicles, thereby setting aside any non-locomotion related abilities they may possess as they fall outside the scope of this discussion. We model vehicles operating in \(d\) dimensions (where in most cases \(d \in \{2, 3\}\)) as having the following properties:

  1. Mass — a scalar \(m \in \mathbb{R}, m > 0\)
  2. Orientation — \(d\) basis vectors \(\{\boldsymbol{\hat{x_1}}, \boldsymbol{\hat{x_2}}, \ldots, \boldsymbol{\hat{x_d}}\}\) or an equivalent representation.
  3. Position — a vector \(\boldsymbol{p} \in \mathbb{R}^d\)
  4. Velocity — a vector \(\boldsymbol{v} \in \mathbb{R}^d\)
  5. Maximum thrust — a scalar \(r_{max} \in \mathbb{R}, r_{max} \ge 0\)
  6. Maximum speed — a scalar \(s_{max} \in \mathbb{R}, s_{max} \ge 0\)

Steering behaviors

The forces operating on a vehicle are generated by one or more steering behaviors \(\{b_1, b_2, \ldots, b_n\}\). A steering behavior is a function taking a vehicle \(h\) and a set of other behavior-specific parameters \(P_i\) in order to yield a force vector \(\boldsymbol{F_i}\) representing that behavior's desired change in the vehicles's velocity:

$$ b_i(h, P_i) = \boldsymbol{F_i} $$

When a vehicle is steered by several behaviors, each one is associated with a specified weight \(w_i \in \mathbb{R}\) representing its relative contribution to the total hypothetical force \(\boldsymbol{F_h}\) to be applied to the vehicle:

$$ \overline{w_i} = \frac{w_i}{w_1 + w_2 + \cdots + w_n} $$ $$ \boldsymbol{F_h} = \sum\limits_{i=1}^n \overline{w_i} \boldsymbol{F_i} $$

Advancing the simulation

Provided with the force \(\boldsymbol{F_h}\) generated by the steering behaviors, the simulation's time-step duration \(dt\), and the vehicle's current position and velocity (\(\boldsymbol{p_0}\) and \(\boldsymbol{v_0}\), respectively) we are now able to compute its new position and velocity (\(\boldsymbol{p_1}\) and \(\boldsymbol{v_1}\), respectively) using forward Euler integration. Begin by first truncating the hypothetical force's magnitude to conform to the vehicles maximum thrust \(r_{max}\), yielding the actual force \(\boldsymbol{F}\) to be applied:

$$ \boldsymbol{\hat{x}} = \frac{\boldsymbol{x}}{\|\boldsymbol{x}\|} $$ $$ truncate(\boldsymbol{x}, \ell) = \begin{cases} \boldsymbol{x}, \text{if } \|\boldsymbol{x}\| \le \ell \\ \boldsymbol{\hat{x}} \cdot \ell, \text{if } \|\boldsymbol{x}\| > \ell \\ \end{cases} $$ $$ \boldsymbol{F} = truncate(\boldsymbol{F_h}, r_{max}) $$

Using \(\boldsymbol{F}\), we compute the vehicle's acceleration \(\boldsymbol{a}\), its hypothetical new velocity \(\boldsymbol{v_h}\), and its actual new velocity \(\boldsymbol{v_1}\) as is limited by the vehicle's maximum speed \(s_{max}\):

$$ \boldsymbol{a} = \frac{\boldsymbol{F}}{m} $$ $$ \boldsymbol{v_h} = \boldsymbol{v_0} + \boldsymbol{a} \cdot dt $$ $$ \boldsymbol{v_1} = truncate(\boldsymbol{v_h}, s_{max}) $$

Finally, compute the vehicle's new position \(\boldsymbol{p_1}\):

$$ \boldsymbol{p_1} = \boldsymbol{p_0} + \boldsymbol{v_1} \cdot dt $$

The vehicle's new orientation basis can be derived from its new heading. For example, a vehicle operating in two-dimensions on the \(xz\)-plane and having velocity \(v\) could be described as having the orientation basis \(\{ \boldsymbol{\hat{x}}, \boldsymbol{\hat{z}} \}\), where:

$$ \boldsymbol{\hat{x}} = \boldsymbol{\hat{v}} $$ $$ \boldsymbol{\hat{y}} = (0, 1, 0)^T $$ $$ \boldsymbol{\hat{z}} = \boldsymbol{\hat{x}} \times \boldsymbol{\hat{y}} $$

Elementary behaviors

In this section we go over some elementary steering behaviors, and in the next section we show how they can be extended and combined in order to create more advanced patterns.

Seek/Flee

The Seek behavior drives the vehicle towards a specified target position \(\boldsymbol{p_t}\) and with a specified target speed \(s_t\). To compute its output force, we begin by expressing our desired velocity \(\boldsymbol{v_d}\) through:

$$ \boldsymbol{p_d} = \boldsymbol{p_t} - \boldsymbol{p} $$ $$ \boldsymbol{v_d} = s_t \cdot \boldsymbol{\hat{p_d}} $$

Next, compute the force \(\boldsymbol{F_{seek}}\) such that when it is continuously applied to a vehicle with current velocity \(\boldsymbol{v}\), will yield the change in velocity \(\boldsymbol{v_d} - \boldsymbol{v}\) after a time duration of \(dt\):

$$ \boldsymbol{v_d} - \boldsymbol{v} = \boldsymbol{a} \cdot dt = \frac{\boldsymbol{F_{seek}}}{m} \cdot dt $$ $$ \boldsymbol{F_{seek}} = \frac{m(\boldsymbol{v_d} - \boldsymbol{v})}{dt} $$
Figure 1: A vehicle driven by Seek. The target is at the center.

The opposite behavior to Seek is Flee: it drives the vehicle away from the target position at a specified speed. The computation of the output force generated by Flight is almost identical to the one performed for Seek except that the target velocity's sign is negated, which gives:

$$ \boldsymbol{F_{flee}} = \frac{m(-\boldsymbol{v_d} - \boldsymbol{v})}{dt} $$
Figure 2: A vehicle driven by Flee. The target is at the center.

Wander

The Wander behavior drives the vehicle in random directions with a specified target speed \(s_t\). In two dimensions, this could be achieved as follows: Begin by choosing two related parameters, the vehicle's maximum turn rate \(\theta > 0\), and the maximum change \(\phi > 0\) in its current turn rate. Now, given the vehicle's current orientation \(\alpha\) representing the angle between the vehicle's heading \(\boldsymbol{\hat{v}}\) and \((1, 0)^T\), and its current turn rate \(d\alpha_0\), derive its new turn rate \(d\alpha_1\):

$$ \Delta = \text{random uniform sample from } [-\phi, \phi] $$ $$ d\alpha_1 = min(\theta, max(-\theta, d\alpha_0 + \Delta)) $$

Using the rotation matrix \(R\) associated with \(d\alpha_1\), the output force is given by:

$$ \boldsymbol{v_d} = s_t \cdot R \boldsymbol{\hat{v}} $$ $$ \boldsymbol{F_{wander}} = \frac{m(\boldsymbol{v_d} - \boldsymbol{v})}{dt} $$
Figure 3: A vehicle driven by Wander, with \( theta = 0.1\pi \) and \(phi = 0.001\pi\).

Pursue/Evade

Seek and Flee both relate to a static target, but what about a dynamic one? The Pursue and Evade behaviors use Seek and Flee internally, but instead of the target position \(p_t\) being supplied as a constant, it is given through a function \(g: \rightarrow \mathbb{R^d}\) invoked during each step of the simulation.

Figure 4: Three vehicles: one driven by Wander (green), one chasing it driven by Pursue (orange), and one avoiding it driven by Evade (blue).

If the target we are interested in pursuing/evading is another vehicle, then we would be naive to define \(g\) simply as:

$$ g: \rightarrow \boldsymbol{p} $$

with \(\boldsymbol{p}\) being the target's current position, as this way we will always lag behind. A better approach would be to attempt to predict the target's position in the future, and head there to intercept it. One way this could be achieved is by defining \(g\) like so:

$$ g_t: \rightarrow \boldsymbol{p} + \boldsymbol{v} \cdot t $$

where \(\boldsymbol{v}\) is the target's current velocity and \(t\) a positive scalar. This formulation assumes the target's velocity would remain constant for the next \(t\) duration of time, and computes the target's future position based on that.

Figure 5: Naive pursuit vs. pursuit with future position approximation.
Naive
With future position approximation

Arrive

You have probably noticed an uncomfortable quirk vehicles driven by Seek exhibit: they do a good job of getting to the target, however they do do not stop once they get there. Arrive is an extension of Seek that handles that problem. As long as the distance between a vehicle driven by Arrive and its target is greater than some specified threshold \(D\), Arrive's operation is identical to Seek. However, once the threshold is breached Arrive initiates a gradual break.

Given the regular desired speed \(s_t\), the current distance to target \(d\), the breaking distance threshold \(D\), and an interpolation function \(f: [0, 1] \rightarrow [0, s_t]\), the actual target speed \(s_a\) is given by:

$$ s_a = \begin{cases} s_t, \text{if } d > D \\ f(d/D), \text{if } d \le D \\ \end{cases} $$

with \(f\) being smooth and having boundary values \(f(0) = 0\) and \(f(1) = s_t\).

Figure 6: A vehicle driven by Arrive.

Advanced behaviors

In this section we give some exemplary cases where extension and/or combination of the previously defined elementary steering behaviors yields desired navigational patterns.

Separate

As our first example of a neighbourhood-related behavior, we take Separate. The goal behind Separate is to cause vehicles to ensure a minimum distance between themselves and nearby 'repulsion sites'. These repulsion sites could be other vehicles, or simply static obstacles in the environment, the point is that through Separate they exert a repulsing force on a vehicle that is too close to their sphere of influence.

Given the set of positions of nearby repulsion sites \(A = \{\boldsymbol{x_1}, \boldsymbol{x_2},\ldots, \boldsymbol{x_n}\}\), Separate first computes their average \(\boldsymbol{x_{avg}}\) and then makes use of Flee with \(\boldsymbol{x_{avg}}\) as target and some user-specified speed \(s_t\). If the repulsion set \(A\) is empty, then Separate generates a breaking force instead:

$$ \boldsymbol{F_{separate}} = \begin{cases} \boldsymbol{F_{flee}} \text{, if } \|A\| > 0 \\ \frac{-m}{dt}\boldsymbol{v} \text{, if } \|A\| = 0 \\ \end{cases} $$
Figure 7: Two vehicles driven by Separate.

Patrol

Patrol is another behavioral archetype that is quite prevalent, especially in the video-game industry. It is where a character visits a predetermined sequence of checkpoints in order. Patrol is expressed as successive invocations of Arrive for each checkpoint in the order specified, with the possibility of endless repeat.

Figure 8: A vehicle driven by Patrol.

Align

Align is an important behavior to have for crowd simulation. Align drives a vehicle's velocity to match the average velocity of other vehicles in its vicinity.

Figure 9: A vehicle driven by Align (yellow).

Conclusion

In this project we have played around with some elementary (and some more advanced) steering behaviors for virtual characters. There are many more interesting behaviors to be derived from the ones we specified and others. The trick is finding the right combination of behaviors to produce a desired result.

Source code

You can view the source code and documentation of the library on GitHub.

See also

References

  1. Reynolds, Craig W. "Steering behaviors for autonomous characters". Game developers conference. Vol. 1999. 1999.