Movement forms the most basic level of AI techniques and is a fundamental requirement in almost any games. Each character in the game has a position and some other properties that help in controlling its movement. A movement algorithm uses these properties in finding the next position to move the character. All movement algorithms take data about the current state of character and the world and produce a movement request which is then fed back into the character. Not all movement algorithms require complex input and not all provide a complex output.
There are two basic types of movement algorithms
Kinematic: Kinematic movement algorithms have a single output namely the direction to move. They normally provide only velocity and direction and not accelerations. The characters tend to move in the required direction at full speed, and this results in movement that is not quite realistic.
Dynamic: Dynamic movement algorithms are also called steering algorithms as they provide the accelerations necessary to move the character into a required position. Craig Reynolds first describes steering behaviors for the movement algorithms that he developed. Dynamic algorithms add an extra layer of computational complexity but result in a more realistic movement of characters.
To develop our algorithms, we only consider the character in 2D space, with the 3rd axis representing gravity.
I wrote all the algorithms in C++ with OpenFrameworks. I am depicting the input and outputs as classes and structs in the following manner. The classes and structures as shown below have been evolving as I write more algorithms.
struct DynamicSteeringOutput
{
DynamicSteeringOutput(){}
~DynamicSteeringOutput() {}
DynamicSteeringOutput(ofVec2f linear, float angular) : LinearAcceleration(linear), AngularAcceleration(angular){}
ofVec2f LinearAcceleration = ofVec2f(0,0);
float AngularAcceleration = 0;
DynamicSteeringOutput operator+ (DynamicSteeringOutput& i_Dymamic);
DynamicSteeringOutput operator- (DynamicSteeringOutput& i_Dymamic);
template <typename T>
DynamicSteeringOutput operator* (T i_Other);
};
struct KinematicSteeringOutput
{
ofVec2f Velocity = ofVec2f(0, 0);
float Rotation = 0;
};
class Kinematic
{
public:
ofVec2f Position;
float Orientation = 0;
ofVec2f Velocity;
float Rotation = 0;
void Update(KinematicSteeringOutput i_SteeringInput);
void Update(DynamicSteeringOutput i_SteeringInput);
private:
float mMaxVelocity;
};
The kinematic class is the main class which holds the Position, Rotation, Orientation and Velocity of an object. The update functions in the class take respective Outputs and update the above variables based on the outputs. I also have a boid class which draws a circle and triangle on screen and checks if the boid is out of bounds and wraps around if it does. It also leaves breadcrumbs on the screen so that we can follow the boid around. All algorithms are implemented in their own classes and have a common function named GetSteering, which takes various inputs depending on the algorithm.
Implementing the algorithms:
There are quite a few algorithms that I’ve written to create different behaviors. Kinematic algorithms update both the Velocity and Rotation, which Dynamic algorithms only update one of linear acceleration or angular acceleration. So, to create complex dynamic algorithms, we sum the outputs of different simple algorithms.
The first algorithm I will discuss is ‘Seek.’ Seek is one of the basic movement algorithms, it essentially moves the character to a specific target. We will discuss both kinematic and dynamic seek algorithms. Firstly, kinematic seek. It takes as input the positions of both character and targets and calculates the direction between them both and moves the character in that direction with a maximum velocity that we provide. We can directly set the orientation, if needed, using the arctangent of the velocity. Since the velocity is never set to zero, the character keeps on moving. Hence this algorithm is used for chasing a target that is moving.
Dynamic Seek: Dynamic seek keeps everything the same as kinematic seek, but updates acceleration instead of velocity. Since acceleration increases velocity exponentially, we clamp the max value the velocity can reach.
Kinematic and Dynamic Flee: Flee is similar to seek, but instead of applying acceleration or velocity in the direction of target, we apply them in the opposite direction.
Kinematic Arrive: since kinematic seek never stops once it reached the destination, we need an algorithm that stops the character at the target which is, arrive. The arrive algorithms use a target radius surrounding the target and stop the target as soon as the target enter that radius. If the radius is small, the character moves in the opposite directions to get to target which results in a wiggle like motion. Hence I used a large radius such a 100, which eliminates such wiggle but results in the character not reaching the target.
Dynamic Arrive: Like kinematic arrive, the dynamic arrive also contains a target radius, but it also has a radius bigger than the target radius, the space in which character can slow down. The rate of deceleration is proportional to the distance between character within slow and target radii. Once the character reaches the target radius, we can stop the movement. In my case, I was using a very large slow radius with a very small target radius resulting in a slow stop at the target. Below is a video in which the character can be seen moving to the target which is the mouse click position.
Dynamic Look Where You Are Going (LWYG): As discussed above, all basic dynamic algorithms generate either linear acceleration or angular acceleration. To generate the rotation on the character towards a target as seen above, we use an LWYG algorithm along with dynamic align which we will discuss next. The LWYG takes in the character movement and calculates the orientation in which the character has to align itself to using its velocity.
Dynamic Align: Dynamic align is the main algorithm which creates the angular acceleration that is required to rotate. It calculates the rotation between the character orientation and a target orientation, which can be sent from other places apart from LWYG. It then maps that rotation to one between -180 and 180, calculates the required acceleration and clamps it to max speed and returns this acceleration to us. As dynamic arrive, I used a large slow angle and a small target angle and based on the other algorithm that is calling, set the value of max speed to achieve the desired results as seen in the above video.
Kinematic wander: The wander algorithm generates a random movement in a direction. The kinematic version does this by changing the current orientation and moving the character in the new orientation with maximum speed. To create the orientation, we use a random binomial which generates a random number between -1 and one but generates values nearer to 0 more often. This makes the change in orientation to be random yet small. The same technique is used in dynamic wander too.
[1]
Dynamic Wander: Dynamic wander algorithm is part of a group called delegated behaviors of which LWYG is also a part. All delegated behaviors behave in almost the same way. They generate a target and either position or acceleration and then delegate the steering to other basic dynamic behaviors — for example, LWYG delegates to align. In kinematic wander, we randomly selected an orientation, which can be thought of as selecting a point on a circle at some radius. In dynamic wander, we create the target on a circle at a fixed distance in front of the character.
[1]
I am using arrive to move to the point and LWYG to rotate towards the point. We can also implement that same using dynamic face, and then apply maximum acceleration in that direction. I implemented both the methods to perform wander and found that arrive + LWYG gave me the best results as seen in the video below.
Blending: Blending is the process in which we linearly combine different behaviors. The usual way of doing blending is to assign weights to different algorithms based on our requirements. We multiply the weight of each algorithm to the output and sum all these outputs together to get the final output for our required scenario. The most common blending algorithm is flocking developed by Craig Reynolds and used in many games and movies. Flocking is the behavior of mimicking the movement of a pattern of birds. There are three main behaviors as part of flocking; they are separation, velocity and alignment match, and moving to the center of mass. In our case, we are assigning a mass of 1 to all the boids in which case the center of mass is the center of all their positions. We will discuss individual algorithms below.
Dynamic Separation: In its fundamental state, dynamic separation checks the distance of boid with each other boid in the scene and if it is too close, applies an acceleration in the opposite direction so that the boid moves away. The amount of steering that is applied to the boid is equal to the sum of all the individual forces applied on that boid due to surrounding boids and can also be zero when it is surrounded by an even number of equidistant boids. To make the forces more realistic, we use inverse square law which applies a force is applied inverse to the distance between the two objects.
Dynamic Velocity Match: This algorithm gets the difference between the velocities of character and target and clamps it to a maximum speed. Then sets that as the linear acceleration to the character.
I’ve implemented moving to the center using Dynamic Align and LWYG algorithms.
Flocking can be done only as a group or as a group following a leader. In our assignment, we are supposed to do the second. So for the calculation of the center of mass, I first average the position of all the boids except the leader and then average this average with the position of leader. This gives the leader’s position more weight and lets the followers follow a little behind the leader. All the boids including the leader avoid each other. I’ve made the leader click to move, and even when the leader reaches the required position, you can still see that he is moving around trying to avoid the other boids.
You can see the flocking in the above video. I’ve also implementing changing the leader. If you notice carefully, once the new leader is selected, the old leader joins the pack and the pack moves away from the new leader. Increasing the number of followers might make the screen a bit crowded since, all the boids tend to repel each other. I’ve experimented with having 5 – 10 followers and having 10 followers made it harder for the leader to go to the designated position when we click on screen.
I also added the ability to add a different leader who moves randomly. The followers then follow the leader who is closest to them. You can enable and switch between the secondary leaders by pressing ‘k’ and disable secondary leader by using ‘l’.
Analysis:
Most of the algorithms that I’ve implemented are dynamic algorithms. I also implemented kinematic ones for seek, arrive, and wander but dynamic algorithms are much better when compared to kinematic ones as they provide much smoother motion. The most I spent is on finding the right values for the maximum speeds, accelerations and other values in these algorithms. Since, even a small change in acceleration or speed drastically changed the output, I had to find the right values with whom I’m satisfied enough with the output. I think I can still make small changes to the values to get even more precise movement, but as my professor said in class, we are not trying to find the perfect movement, but if it is good enough to pass without further close inspection, then we are in a good place.
For flocking, I assigned weights of 2,1 ,3 and 2 to separation, velocity match, Arrive and LWYG respectively. I think for a good flock, even if they fall behind sometimes to the main group, they should mainly avoid colliding with others and try to go to the center. If we change the values to other, I believe we can see some different behaviors. I’ve checked with having fractional values as weights for separation and this caused some of the boids to collide with each other while trying to reach the center. Also, currently I have the leader and followers move at the different speeds and different weights at avoidance. Since, the followers always follow the leader, I’ve halved the leader’s avoidance weight and increased its maximum speed to try reaching the destination better.
Adding a secondary leader to flocking changes a lot of things as the boids have to continuously check which leader they are close to which still staying close to the whole of center of mass.
Download:
You can download the sample here: Download. All code is open source and is available at my GitHub.
Controls on Keyboard
press 1 – Basic movement
press 2 – Move to mouse click
press 3 – Wander
press 4 – Flocking
press N – When flocking, to change the leader.
press K – When flocking, to enable secondary leader and change secondary leader.
press L – When flocking, to disable secondary leader and change secondary leader.
When flocking or seek to mouse, use the mouse left button to set the position.
References:
[1] I. Millington, J. Funge , Artificial Intelligence For Games, 2nd ed. Reading, CRC Press, 2009. [E-book] Available: Safari e-book