Movement Algorithms

One of the most basic requirements of an AI is to move around. Movement can be anything from basic going to a target location to following a target. In this writeup, I will try to throw some light on various AI movement algorithms and explain their implementation in C++.
All movement algorithms take some information about their state and the state of the world and returns a geometric output representing the movement they would like to make. These algorithms can be classified into two major types:

• Kinematic Algorithms: It returns the direction to the target and the entity moves in the direction until it arrives. If the algorithm returns no direction, entity has reached the location.
• Dynamic Algorithms: It uses acceleration. It first accelerates in the right direction and as it gets near the target, it accelerates in the opposite direction so as to precisely decrease the speed and stop at the correct location.

Application Architecture
I am using C++ openFramework library in these assignments. It is an open framework which we use to as graphics library to render shapes on the screen. Currently, I have divided my game world into four parts:

• Game Object: This is the representation of any game object in the world. A game object will have a reference to physics (for movement) and renderer (for graphics) to have a desired behavior in the world.
• Renderer: I have created a pure virtual class IRendrer which will be used to draw anything on screen.
• Physics: Physics system has the Kinematics class which will store position, orientation, velocity and rotation of any object.
• Movement: Every movement algorithm is part of this movement namespace. I have again used a pure virtual class for movement algorithms which has the below three virtual functions:
  • GetKinematicSteering(): It return the kinematic steering output for various algorithms.
  • GetDynamicSteering(): It returns the dynamic steering output for various algorithms.
  • CalculateNewOrientation(): It returns the orientation based on the velocity passed as argument.
• Output Structs: All the structs used in this assignment are stored in a single file. I have declared the following three structs:
  • MovementInputs: It contains all the parameters which are required as input for all the movement algorithms. The default constructor of this struct set every parameter as 0. The idea behind this struct is that each movement algorithm will use this as input and set the values of required variables of this struct.
  • KinematicSteeringOutput: This struct is returned by every kinematic steering algorithm. It contains the velocity and rotation.
  • DynamicSteeringOutput: This struct is returned by every dynamic steering algorithm. It contains the linear and angular acceleration.
• A kinematic class is created which will contain the various information required to achieve the movement of any game object. Each game object will have a pointer to this kinematic class. Member variables of this class which are used in the movement are position (2D Vector), orientation (float), rotation (float) and velocity (2D vector).

Movement Input Struct

Algorithms
Now to actual algorithms. There are lot of ways through which we can get the desired result of movement output. Generally, the algorithms take two kinematic objects as input along with various parameters used for implementing the desired movement algorithm. Below are some of such basic algorithms:

Seek
In seek, character seeks a target point. Direction from character to target is calculated and velocity is generated accordingly. Orientation is ignored in kinematic seek but orientation can be calculated based on the velocity calculated. For calculating the basic motion of the character around the screen, I have used this seek algorithm. One application of this algorithm where we ignore the orientation can be to have player aim at the target while moving [as per Core Design Ltd., 1996]. The complexity of this algorithm is O(1) in terms of both time and memory. For dynamics seeking, we calculate the acceleration instead of speed and the player accelerates towards the target.
[Note: We also have Flee as an algorithm which is just opposite of Seek i.e., we move away from the target ]
Arrive
Similar to seek, if the player has to chase a target, we use arrive. It is not advisable for stationary targets as the player moves with max speed towards the target and if the target is stationary, player can overshoot and we will see a back and forth wiggle around the point. To avoid this, we maintain a radius of satisfaction and as soon as the player is within that radius, it stops. For dynamic arrive, we maintain two radii and player starts to slow down as it reaches the out radii and stop in inner radii. This give a sense of de-acceleration as the player approaches its target. The complexity is O(1) for both time and memory.
Align
For matching the orientation, we use align. Align does not care about the position or velocity, it only take care of the rotation or angular acceleration of the player. While implementing this algorithm, it is important to warp the output rotation within [-pie, pie] radians. To face the opposite direction, we simply add ‘pie’ to the align result.
Face
Face is a delegated algorithm. Any algorithm which uses some primitive algorithm along with some additional functionality of its own is known as delegated algorithm. It uses align to calculate the rotation but first the orientation of target is calculated.
Blended Algorithms (eg., Flocking)
Blending algorithm takes the behavior output of various algorithms, associate a weight to each behavior and then output the blended behavior. We usually take the linear combination (weighted sum) of all the behaviors passes as the argument to blended behavior. In my implementation, I have created a struct of behavior and weight and I am passing a vector of this struct as the argument to achieve wandering. Playing with different values of weight can generate interesting and unique behaviors.

Kinematic Motion
The first algorithm that I started with is the basic Kinematic motion. Below video shows the bot moving on the screen. The bot starts at the top left corner of the screen. To mark the movement on screen, I am leaving some breadcrumbs on screen.

Bot's movement around the screen with breadcrumbs

​To put it in technical terms, I used the basic kinematic seek for this behavior. The idea behind seek is that there will be a target point which the bot has to seek. For complete movement, there will be four target points on each corner of the screen. As soon as the bot will reach an edge of the screen, I will update its orientation and then set another target point. This will continue and the bot will keep moving around the screen.

Basic Motion.

One interesting thing here is the bot actually doesn’t follow the same exact path each time. This is because how I have setup the seek behavior. I have given the seeking bot a wiggle room of 50 units. So based on the instantaneous velocity at the moment it reach the end, it calculates the next seek. Leaving no wiggle room can cause the bot to get stuck and kinematic seek can shoot the bot a bit up from intended location.
​
​Seek Steering Behavior
In seek steering, I will make the bot move towards the mouse click position. We first have to orient the bot in the direction of target and then move towards the target. I have implemented two different types to arrive to achieve this behavior; Kinematic arrive and Dynamic Arrive.
Kinematic arrive takes max speed, target radius and time to achieve target as inputs. The idea behind this is that the bot will change its orientation towards the target and will move towards the target radius. The output velocity is scaled using time to target so that we get a slowing down movement.

Kinematic Arrive.

​Dynamic arrive define two radii; target radius and slow radius. We only scale the output velocity once we are inside the target radius, otherwise the bot moves with max velocity. We usually define these radii close by to each other so there is very less slowing down. This gives much smoother motion.

Dynamic Arrive.

Though The dynamic arrive algorithm is little bit complicated than kinematic arrive, I believe this added complexity is worth the smoother movement achieved by this.

Wander Steering Behaviors
Wander is a delegate behavior where we calculate a target point and then delegate to face or seek to reach that point. Once the target point is reached, new target point is calculated and this continues to give a sense of wandering on screen. Wandering uses random binomial function to randomly change the orientation of the object.
I have implemented two type of wandering; kinematic and dynamic. Kinematic wandering take max speed and max rotation as input and calculate move the player with max velocity in the direction of randomly calculated new orientation. The movement we see in the below video is bit jittery because the orientation is calculated each frame. We calculate the orientation by multiplying the max rotation with a random binomial output.

Kinematic Wandering.

​However in dynamic wandering, we have few more parameters as input and hence we get a better, smoother movement. Along with max speed and acceleration, we have wander radius, wander offset and wander rate as the parameters. A wander point is set in a circle of wander radius which is wander offset units forwards from player. Wander rate describes how often wander orientation can change. The character tries to align with the target each frame and then accelerates in the direction of target.

Dynamic Wandering.

Boundary violation in wandering
Since using wandering, the bot can wander of anywhere, it is generally preferred to handle this boundary violation in some manner. I have used screen wrapping for this purpose. The screen wraps around and the bot appears on the other side if it crosses the screen on either X or Y axis.

Breadcrumbs showing wander path

Flocking Behavior
Flocking is a blended algorithm. It takes the output of the various previous steering algorithms, associated each of them with a weight and then outputs a linear combination of those inputs. In flocking we have ‘n’ number of bots, and they travel randomly in the screen, together, avoiding each other while maintaining some distance with each other. There is generally a seek target which the flock seeks and a velocity for the flock to match.
For the flocking shown in the video, I have used dynamic separation, dynamic velocity match, dynamic seek and dynamic align.  The flock I designed will try to do the following:

• Dynamic Separation (): Try to avoid every other member of the flock. Dynamic separation takes a coefficient and a threshold distance to achieve this.
• Dynamic Velocity Match (): Every member of the flock will try to match the same velocity. For the flock without the leader, the average velocity of the flock will be taken as the velocity to match.
• Dynamic Seek (): Flock will seek a position. The average of the positions of each member of the flock is taken as the input in case of no leader.
• Dynamic Align (): Flock will align in the same direction. Average orientation of the flock is taken as the input in case of no leader.

Along with these individual algorithms, each algorithm is associated with a weight. It up to the designer to decide what weight should go with each algorithm. Tweaking the values of these weights results in the tweaking of the algorithm. It’s usually hit and trial with these values and we just have to keep on tweaking them until we get the right behavior. In the below video, I am showing how just tweaking a single weight results in some different behavior.

Flocking Demo.

​Blending of algorithms help us achieving emergent. With ‘variable’ weights associated with the algorithms, designers can really change how the entities behave. The important learning with these algorithms was that the time we put in to write the algorithm, equally important is to put in the appropriate parameters for these algorithms. These all are pretty simple algorithms, and with correct values they generate a pretty powerful behavior.