Steering behaviors

I’m going to implement basic steering behaviors using unreal engine, but these behaviors shouldn’t be too hard to implement in any environment. I will stick to 2d movement, but these behaviors can be used with a few modifications for 3d movement as well.

Steering is the process of driving a vehicle like autonomous character (boid) with steering forces. The boid is just a simple extruded triangle for now, which has a velocity (vector 2d) with a maximum magnitude, and you can change it’s velocity by applying a force to it. The force (a) is passed down to change the velocity. (v += a * dt), then the position can be modified according to velocity (pos += v * dt).

Simple vehicle model:

– For simplicity, the boid’s velocity (simple_velocity) and the applied force is truncated to be in a unit circle (max magnitude is 1), and the boid has a velocity_scale float variable so that the actual velocity can be retrieved by multiplying the simple_velocity with the velocity_scale.

– The force’s effect is symmetrical.

– The boid is always facing its velocity. This way the boid can turn around quickly when its velocity is low which might be unwanted behavior.

More realistic behavior can be implemented by using a more complex model:

– The force can be applied asymmetrically where braking, acceleration and lateral steering forces have different strengths

– For the quick turnaround: limit the lateral force at low speeds, or separate the velocity by  having a forward speed, and a rotational speed (like in UE4 flying template)

So let’s see that in unreal engine:

After creating a new blueprint project (from flying template) I have made an abstract class for the boid, but that can’t be done in blueprints, so it’s in code. You can add code to the project from within the editor by choosing File/Add Code to Project…  then you can choose the parent class, and the name of your class (I chose DefaultPawn with the name Boid, in code an ‘A’ gets inserted before Boid because Pawn is a subclass of Actor, and the ‘A’ is a sign that it is an actor subclass). After doing that, the editor creates your files for you with some content, and you can edit it in Visual Studio:

Header file:

//includes ...

UCLASS(abstract)

class BOIDS_API ABoid: public ADefaultPawn

{

GENERATED_BODY()

protected:

UFUNCTION(BlueprintNativeEvent, BlueprintCallable, Category = "Steering")
void ApplySteeringForce(const FVector2D& Force);

UFUNCTION(BlueprintNativeEvent, BlueprintCallable, Category = "Steering")
void UpdateTransform();

UFUNCTION(BlueprintNativeEvent, BlueprintCallable, Category = "Steering")
FVector2D GetEstimatedFuturePosition(float DeltaSeconds);

UFUNCTION(BlueprintNativeEvent, BlueprintCallable, Category = "Steering")
FVector2D Seek(const FVector2D& Target);

UFUNCTION(BlueprintNativeEvent, BlueprintCallable, Category = "Steering")
FVector2D Pursue(ABoid* boid);

//...

virtual FVector2D Seek_Implementation(const FVector2D& Target);

};

Note the abstract parameter in UCLASS(): this prevents from drag & dropping this object from the content browser to the level.

BlueprintNativeEvent means you provide a c++ implementation but you can override it in blueprints. BlueprintCallable means you can call these functions from blueprints. Category is just to help organize your functions. In my case these functions will be seen from the editor under Steering.

ApplySteeringForce sets the internal speed (or rotational) variables. UpdateTransform updates the boid’s position and orientation based on those speed variables. GetEstimatedFuturePosition is a simple guess for where the boid is going to be after some time (this can be used in pursue, and evade).

You can see in Seek’s declaration, that it has a simple 2D target position and returns a force which points in the target’s direction. The exact same function declaration can be used for Flee and Arrival.

Pursue is different because it takes the target’s estimated future position into calculation so it takes a boid pointer as a parameter.

Since I declared these methods BlueprintNativeEvents, they must be implemented in C++, and can be overriden in a blueprint subclass. This means you have to provide a virtual <functionName here>_Implementation(<parameters here..>) for all these functions. You can see Seek’s declaration above.

CPP file:

//includes..

FVector2D ABoid::Seek_Implementation(const FVector2D&amp;amp; Target)
{
return FVector2D();
}

//...

Seek’s definition can be seen above. Since I intend to override this in a blueprint, I just return a zero vector.

After the code is done, and compiled, you can create a blueprint subclass of Boid in the editor (right click in content browser, Blueprint Class, choose your superclass).

I set up the collision sphere with locked axis Z, and the following collision matrix:

Collision

 

This way, the boids will not collide with each other, but they will collide with the walls in the level.

I chose Shape_Wedge_A for the static mesh component to have an extruded triangle like shape, but you could choose anything you want. I added an arrow to know which way is forward. I set collision to the no collision preset for everything that can collide except the collision sphere.

Boid

 

Now let’s implement the basic steering behaviors:

In the editor under functions you can click on override and select the method you need to override (except for void methods, because they appear as events – you can create logic for those in the event graph)

The motor of these behaviors lie in ApplySteeringForce, and UpdateTransform:

ApplySteeringForce

applysteeringforce_blueprint

ApplySteeringForce is responsible for setting speed variables according to a force (and the time passed). Whatever force gets in, it get’s truncated to a vector size of 1, then the force affects the velocity (v += a * dt), and it gets truncated too. As a reminder: the simple_velocity refers to the velocity of the boid with a max. magnitude of 1, and that will be scaled with velocity_scale to get the actual velocity.

UpdateTransform

updatetransform_blueprint

UpdateTransform sets the position (pos += v * dt), and orientation (the boid faces its velocity’s direction).

GetEstimatedFuturePosition estimates the future position with the exact same expression (future pos = pos + v * dt).

Seek

Seek steers in the direction of a target point. It calculates the desired velocity for the target point, and the force’s direction = desired velocity – current velocity

Seek

The bottom boid has a velocity facing left, the desired velocity is up and left, so the resulting force is up.

seek_blueprint

 

The way this works is if the boid’s velocity is zero, and the desired velocity is (1, 0), then the force will be (1, 0), so the boid gets full throttle forward. When the velocity is backwards (-1, 0), then the force is (2, 0), but it will get truncated along the way in ApplySteeringForce.

When the target is reached, the boid will go over the target, because it can’t stop immediately, so it will turn backwards then, and it will have an oscillating movement around the target at the end.

Flee

Flee is the same as seek, except the desired velocity is the opposite.

Pursue

pursue

 

pursue_blueprint

Pursue uses GetEstimatedFuturePosition’s position as a target, and seeks that. On the picture above you can see an example of 8 boids pursuing each other.

Evade

Evade is the same as pursue but flees from the future position instead of seeking.

Wander

Wander is a random movement. It uses a circle in front of the boid and there is a point on the circle which can move a little bit every frame, so the wander direction can’t change too fast which makes this ideal for a wandering movement. The point defines the direction of the steering force.

I split the image in two parts

wander_bp1

 

First part is about updating the wander angle (this is in degrees): wander angle = (wander angle + 1500 * dt * RandomFloatInRange(-1, 1)) % 360

1500 is just a speed parameter for the change of wander angle which you have to tweak for your self to get decent results.

wander_bp2

Second part is calculating the point for a given wander angle:

Point relative position = forward * radius * sqrt(2) + Rotate Vector Around (Vector(1, 0, 0), wander angle, Vector(0, 0, 1)) * radius

Keep in mind that the actual circle radius (100 in the picture) does not matter this way, since the same steering force will be applied with any radius. But it will matter once the center of the circle is translated forward or backwards or even left/right to make an agent tending to steer more frequently left/right, or if the point’s relative position is not normalized.

 

Arrival

Arrival is a lot like seek, but instead of constantly oscillating around the target, it gradually slows down after reaching a distance from the target which makes for a nice smooth movement.

Consider the vector from us to the target: ToTarget = Target – position

Until the ToTarget Vector’s length is bigger than the slowing_distance the desired speed is the same as in seek. Once it is smaller, the desired speed get’s slowed down linearly. I slowed it down quadratically because my boid seemed to overshoot the target a little, and I didn’t want to increase the slowing distance. I made the desired velocity zero, once the target was really close (5 for now) and it would be unnecessary to continue moving towards it.

Slowing Radius = 800

ToTarget = Target – position

Distance = ToTarget.length()

Desired velocity = Distance > 5 ? ToTarget.normalized() : Vector(0,0))

if ( Distance < Slowing Radius ) Desired velocity *= Distance^2 / Slowing Radius^2

Force = Desired velocity – simple_velocity //same as always

 

Before we go further to the following behaviors, we have need the boids to know which other boids are near it (sensing). In unreal engine you can do that this in an aicontroller. Let’s create an AIController for the boid if you haven’t already done so : I called it BoidAIController (with AIController as the parent class). Add a Pawn Sensing component to it, and set its parameters.

pawnsensing

 

The important parameters for our purpose are only sense players (should be false), sight radius, peripheral vision angle and sensing interval. After it’s done, add an array for holding the pawns (Local Pawns), and override the OnSeePawn event: (Should_update_pawns is a boolean variable for checking whether or not the array should be passed to the controlled boid on the next tick event)

onseepawn

 

This should add any pawn sensed by the component to the array. The problem is, there is no OnLostSightOfPawn event (yet), so I’m going to remove any pawn from the array that shouldn’t be there. I have made a custom event for this which get’s called every once in a while (0.1 sec)

pawnlostsight

The graph might look a little chaotic, because I had to squeeze it together to fit, but it’s quite simple. Losing a pawn out of our sight (or sense) can mean one or more of the following:

  • Pawn is further than the sight radius
  • Pawn is behind us where we can’t see it
  • Pawn can’t be seen – meaning there is probably an obstacle (eg. a wall) blocking our view

Now only the tick event remains:

boidaicontroller_tick

 

(The Update Neighbour Boids function is actually one of the public methods in the ABoid abstract class – in your implementation you can just store the boid array parameter)

When this is done, we can move on for more sophisticated behaviors.

Separation

This behavior tries to stay away from the boids that are close (I’ll call them local boids). This is achieved by the sum of repulsive forces that point from the local boids to our position which are normalized, and weighted by 1 / distance (or something similar, like 1 / (distance + 1) to avoid division by 0). The resulting sum of force can be then scaled or normalized.

separation_blueprint

 

A boid needs to know the neighboring boids’ velocities for the alignment behavior. If you haven’t already created a way to get the velocity of a boid, now is as good time as any, you will need it not only for alignment. There are several ways:

  • public function in ABoid abstract class within which you can return current_velocity
  • just cast the boid to the blueprint class to be able to reach your variables
  • use the built-in movement component’s velocity
  • create your own movement component

I chose the third option. The current_velocity variable can be replaced by the movement component’s velocity variable. By doing that the Update Transform event’s translation part becomes useless, because the movement component will handle the translation for you, (I noticed this when the boid became faster after setting the velocity of the movement component) so you have to take out that part, and then you can replace current_velocity everywhere with the movement component’s velocity. This way you not only eliminate the need for a cast, but you improve your component’s cooperation with other components/classes. Your boid’s velocity will be available through AActor’s getVelocity function. The bad part of it is, you don’t really know much about how the movement component uses this velocity variable, so for custom velocity handling you can just stick to the other options, though for bigger projects the best bet is to create your own custom pawn movement component.

If you’re going with the third or fourth option, don’t forget to replace all occurrence of the current_velocity variable with either the getVelocity function, or the movement component’s velocity variable.

 

Alignment

Alignment means a boid tries to steer so it faces the same direction as the neighboring boids. If you can reach the velocities, the desired velocity will be the average of the neighboring boids’ velocities. (Alternatively you can average the forward direction instead of velocities.) The force direction is same as usual: desired velocity – velocity

Cohesion

Cohesion is about the boids getting close to each other. The target is the average position of the nearby boids, then you can seek towards that target.

cohesion_blueprint

 

Combined steering behaviors:

You can combine these to achieve a higher level steering behavior, like flocking:

Flocking

Combining separation, alignment, and cohesion (I added wander too) as a weighted sum (in other words, a linear combination) results in flocking. After tweaking the weights, I’ve had a decent looking flocking behavior

flocking

 

Related documentation:

You can learn a great deal more about steering behaviors from Craig Reynolds:

http://www.red3d.com/cwr/boids/

For me this javascript based tutorial helped a lot too:

http://gamedevelopment.tutsplus.com/series/understanding-steering-behaviors–gamedev-12732

Unreal engine AI pawn sensing:

http://unreal-ai-tutorial.info/index.php/9-blueprint-ai/11-t04-basic-perception