I'm a gameplay programmer
focused on developing
engaging and unique experiences!

My Resume Learn more

Physics-Based AI Movement Algorithms in openFrameworks

The code for this article can be found on GitHub here!

One of the many problems a game developer will run into is how to move an AI agent around in their game. This article will explore the common approach of using physics to compute basic movements that can eventually be combined to create seemingly intelligent emergent behaviors. We'll start from the ground up by discussing basic kinematic motion that will eventually build up to the popular Flocking behavior algorithm developed by Craig Reynolds!

Physics Movement

Basic physics movement algorithms can be broken down into two categories, Kinematic and Dynamic algorithms.

Kinematic Algorithms

Kinematic algorithms compute the linear and angular velocity an agent should use to update theirĀ  position and orientation. An agent applying the result of a kinematic algorithm would use it to set their linear and angular velocity directly. Behaviors that emerge from kinematic algorithms are responsive, but sometimes not very realistic.

Dynamic Algorithms

Dynamic algorithms compute the linear and angular acceleration and an agent should use to update theirĀ  position and orientation. An agent applying the result of a dynamic algorithm would set their linear and angular acceleration rather than the velocity. Behaviors that emerge from dynamic algorithms are smooth, but sometimes not very responsive.

Algorithm Outputs

Kinematic and dynamic algorithms output the same structure contain a Vector 2 and a float. These can represent either linear and angular velocity or acceleration.

struct SMovementOutput
{
    ofVec2f Linear;
    float Angular;
};

Rigidbody

The physical representation of an AI agent is usually represented as a rigidbody. This is an idealized representation of the agent's mass and can be structured like this.

struct SRigidbody
{
    ofVec2f Position;
    ofVec2f Velocity;

    float Orientation;
    float Rotation;
}

Our agent can then utilize this struct as the basis of their position and orientation on screen.

class CAgent
{
private:
    SRigidbody Rigidbody;
}

Algorithm Prototype

With all this, we can finally have a shared algorithm prototype for all our kinematic and dynamic algorithms.

class CMovementAlgorithm
{
public:
    virtual SMovementOutput GetMovement(const CAgent& InAgent) = 0;
};

Movement algorithms operate on a specific agent and return a movement output that dictate the velocity or acceleration that should be applied onto the agent.

Basic Kinematic Motion

With our algorithm prototype, we can finally implement our first physics movement algorithm by simply returning the desired velocity and orientation we'd like.

SMovementOutput CKinematicMotion::GetMovementOutput(const CAgent& InAgent)
{
    SMovementOutput MovementOutput;

    MovementOutput.Linear.x = VerticalSpeed;
    MovementOutput.Linear.y = HorizontalSpeed;

    MovementOutput.Angular = AngularSpeed;

    return MovementOutput;
}

This can then be expanded upon to have a agent traverse the edges of the screen!

Seek Steering Behavior

Seeking is a movement algorithm that moves an agent toward a specified location.

However, this then poses the question of what does the agent do when it gets to the location? With just a basic seek of moving towards the location, the agent will constantly go back and forth at the location bouncing back and forth.

Thus, there's another seeking movement algorithm called Arrive which has "radii of satisfaction" which allow the agent to slow down and stop if it's within a specific range of the target location. With this, arrive usually looks better than an agent constantly going back and forth on a single point. However, using seek versus arrive heavily depends on the type of behavior a game design requires.

Wander Steering Behavior

Wandering is a movement algorithm that has the agent move randomly about in the world.

As the agent moves about the world, having it look at an informed direction also makes it appear more intelligent. This is done with orientation algorithms like Dynamic Face and Dynamic Look Where You Are Going.

Dynamic Face is an orientation algorithm that has the agent rotate towards a target as its moving. Using this algorithm in conjunction with seek or arrive can create an agent that appears to know where it's going. However, it probably isn't a good orientation algorithm to use with Wander due to the agent not having a specific target to move towards.

Dynamic Look Where You Are Going is an orientation algorithm that has the agent rotate the same direction it is moving. Using this algorithm in conjunction with wander can create an agent that appears to know where it's going. However, it probably isn't a good orientation algorithm to use with Seek or Arrive due to the agent moving toward a target, but looking away from it. However, whichever orientation algorithm is used highly depends on what kind of behavior you want the agent to have.

Blending Behaviors

A special property of these physics movement algorithms is that they can be blended together through a linear combination of their results. This can be done with the help of a structure that pairs behaviors with a weight.

struct SWeightedAlgorithm
{
    CMovementAlgorithm* Algorithm;
    float Weight;
}

Then the linear combination would look like:

SMovementOutput ReturnMovementOutput;

for (auto WeightedAlgorithm : WeightedAlgorithmss)
{
    if (WeightedAlgorithm.Algorithm)
    {
        SMovementOutput MovementOutput = WeightedAlgorithm.Algorithm->GetMovementOutput(Agent);
        ReturnMovementOutput.Linear += MovementOutput.Linear * WeightedAlgorithm.Weight;
        ReturnMovementOutput.Angular += MovementOutput.Angular * WeightedAlgorithm.Weight;
    }
}

This blending can create complex and emergent behaviors from otherwise simple movement patterns.

Flocking Behavior

At it's core, flocking is an emergent behavior comprised of blending 2 movement algorithms, Dynamic Separation and Dynamic Seek.

Dynamic Separation is a movement algorithm that makes it so each agent in a group maintains proper spacing between other members of that group. However, this alone would cause the flock to statically sit at the perfect distance from each other member of the group. This is where Dynamic Seek comes in.

While Dynamic Separation pushes the group apart, Dynamic Seek can be used to pull the group together. This can be done by calculating the groups center of mass and having each agent in the group seek it. This in conjunction with Dynamic Separation can create a dynamic group with individual members reacting intelligently to other members of the group. However, these two movement algorithms still would have the flock sit at a single location. This is where Dynamic Wander comes in.

Dynamic Wander can be applied to a single agent of the flock. Then, every other agent can Dynamically Seek the "lead" agent which will cause the flock to move through a space intelligently.

With blending all these algorithms together through linear combination, each of the behaviors also need their own weights. These weights will be used to determine how heavily the algorithms outputs are favored in computing the final linear and angular values the agent uses to update their position and orientation. In the end I found having Dynamic Separation weighted the most, Dynamic Seek towards the lead agent weighted the second most, and Dynamic Seek towards the center of mass weighted the least produced the emergent behavior I was happiest with.

Flocking can also be expanded upon using Dynamic Velocity Match. This is a movement algorithm that makes sure a single agent in a group matches velocity with the rest of the flock

By upping the amount of followers, you'll be pushing the flocking algorithm's performance as it is O(n^2). This is due to Dynamic Separation iterating through every other member in a group.

Another value that can be changed in the flocking algorithm is having multiple lead agents. The members of the flock than have to determine which leader they would like to follow by comparing their distance to them. This can lead to multiple flocks that can converge or separate into distinct groups. This could then be used to emulate a group of fish!

 

 

No Comments Yet.

Leave a comment