Viveckh's Notepad

# Acceleration

  • With kinematic movement, velocity can change instantly.
  • The agent movement can look more natural with acceleration. This can be accomplished by generating a steering acceleration/force according to the desired location. Velocity is maintained as kinematic state (along with statics) and is updated according to the steering force calculated each frame.
  • For any calculated acceleration, the current agent velocity is updated.
  • This update likely won't orient the agent with the desired direction in a single frame, it will take multiple frames.
  • Unbounded acceleration can lead to extreme velocities, so we can impose a speed limit.
  • Instead of speed limit, drag can be used in games where agents are simulated by physics engine.

# Variable Matching

  • With accelerating, one can consider objectives other than directing the agent to a target.
  • For example, the agent could accelerate towards matching the target's velocity
  • Possibilities for matching: position, velocity, orientation, angular velocity
  • Also the opposite of matching can be considered, like maximizing the difference

Using all the following types of variable matching, steering behaviors can be created

steering-behaviors-chart.png

# Seek

steering-seek-flee.png

seek-orbit-problem.png

seek-orbit-problem-2.png

# Arrive

steering-arrive.png

steering-arrive.png

# Align

  • Matching target's orientation
  • Same basic algorithm as Arrive but working with orientation and angular velocities and acceleration
  • Use a slow angle and a capture angle
  • Angle are unique and must be mapped to a [-pi, pi] range relative to current facing angle. Turn in the shorter direction

# Velocity Matching

  • Agent matches the velocity of the target
  • Not especially useful on its own, but can be combined with other behaviors, like multi-agent flocking, group movement
  • Implementation is basically the capture radius from Arrive
    • Acceleration is clipped to

# Turn-First Steering Behavior

  • Orientation and the direction of velocity can be locked together
  • One approach is for the agent's angular velocity to dictate direction of translation
  • The main advantage is the agent won't ever appear to slide

# Basic approach

  • Agent first attempts to align with relative vector to target (angular acceleration)
  • Next, agent moves towards target
  • Simplest case: agent always goes at full velocity (unless arriving or matching speeds)
    • Problem: wide turns

# Advanced approach

  • Turn-induced deceleration and variable forward acceleration

  • Project previous frame's velocity vector onto new forward (orientation) vector

  • This deceleration is immediately applied as velocity change (due to turning)

  • But the agent also accelerates

  • Can always try to accelerate to max speed (unless arriving, etc)

  • Project the relative target unit vector scaled by max speed onto current velocity

    • This is the target velocity to accelerator towards
    • If negative direction, agent can even back up while turning

# Delegated Behaviors

# Pursue

  • Seek with prediction
  • We can use a heuristic, doesn't have to be precise
  • Must be efficient calc since it is done every frame
  • Linear extrapolation assumption (zero acceleration/constant velocity)

steering-pursue-heuristic.png

# Prediction gotchas

  • Watch out for extreme predictions (very large lookahead t values)
  • Could send your agent off the map or result in odd behavior
  • Consider clamping max time prediction (and even minimum)
  • Consider clipping extrapolated future positions to fit on navmesh or map
    • you can abandon certain predictions, like if the future position is on the edge since the target is bound to move away from there

# Face

  • Align towards a position
  • Determine a relative position vector to target for a direction
  • Use ATan2() to calculate goal orientation angle from x, y components of directions
  • Apply Align

# Look where going

  • Align towards current velocity
  • Apply in conjunction with other behaviors affecting velocity
  • Same as Face but use the agent's linear velocity to determine orientation angle

# Wander

steering-wander.png

# Path Following

steering-path-following.png

steering-path-following-closest.png

# Predictive Path Following

steering-predictive-path-following.png

  • One downside might be that the agent might cut corners if it has a winding corners. Therefore, this approach might not be ideal for guard patrols, races, etc

# Separation

  • Separate agents without fleeing forever

  • Good for crowd simulation (heading in same direction)

  • Only separate within some distance threshold

  • In a crowd, to calculate separation force: can separate from only the closest neighbor or sum of forces from nearby neighbors (clipped to )

  • Need Space Partitioning and Coherence to quickly identify neighbors

# Attraction

  • Opposite of separation
  • Not often useful. Mainly for group behaviors such as flocking
  • Typical to use with a negative k (constant of decay)

# Collision Avoidance

# Cone

steering-collision-avoidance-cone.png

steering-collision-avoidance-cone-problem.png

# Constant Velocity Assumption

  • Points of closest approach
  • Will be different than intersection of trajectories
  • Due to differing speeds
  • Find time (t) of closest approach

steering-collision-avoidance-velocity.png

# Obstacle and Wall avoidance

steering-obstacle-avoidance.png

steering-obstacle-avoidance-ray.png

steering-raycast-corner-trap.png

  • Collision detection with physics engine support can be used but this is computationally expensive and difficult to interpret collisions and appropriate avoidance behavior.

# Blended Behaviors

What if agent needs to steer towards a goal while also avoiding a danger? The solution is blending steering forces additively or arbitrate.

  • Sum of forces
    • Need to enforce max acceleration
  • Weighted sum
    • Each force has a weight that is multiplied by generated force
    • Weights don't need to sum to 1.0 but we can normalize them
    • Weights can be based on some metric like health, to favor one strategy over other

# Problems with blending

steering-blending-problem-1.png

steering-blending-problem-2.png

# Constrained environment

  • Indoor environments, canyons, lots of agents can create constrained environments
  • Constraints that lead to lots of steering forces can create obvious failures detrimental to the gameplay experience
  • Steering behavior agents act most strongly to local influences. This creates near-sightedness which leads to failures.

steering-constrained-env.png

# Solutions to blending problems

  • Higher level planning
  • Path planning
  • Decision making, often reactive

# Priority Blending

  • Beginning to blur the lines between simple steering behaviors and integration of reactive decision making

  • Observation: Many of the steering behaviors we have seen only return a steering force in presence of a stimulus (e.g. obstacle avoidance). These forces are generally important (responding to imminent threats) but can become diluted than others.

  • With priority blending, we can prioritize steering behaviors that activate above a certain force threshold

  • Can be applied to a single steering behavior or a set (combination)

  • Can immediately avoid unstable equilibria and stable equilibira with a small enough basin of attraction

  • Constrained environments and large basins of attraction are still an issue

# Animation

animation-blending.png

motion-table.png

  • Improvement: Add linear interpolation to table selection
  • For any parameters looked up, find the closest cells
  • Then perform a weighted average according to distance to each cell

# Applications

Unique agents can be authored by:

  • Blending steering behaviors
    • add small perturbations with wandering along with seeking
    • use different params for prediction in pursue, obstacle avoidance, etc
  • Defining a performance envelope
    • Set unique max (angular) velocity, max (angular) acceleration
    • Possibility driven by animation system (root motion)

Cool implementation: OpenSteer

← Additional Topics →