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:
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:
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:
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 ]
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.
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 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.
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.
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.
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.
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.
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.
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.
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.
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:
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.