Game Ai Chapter 3

This is the reading note after reading by Mat Buckland.

Here is the part of the Chapter 3.

What is an autonomous agent?

An autonomous agent is a system situated within and a part of an environment that senses that environment and acts on it, over time, in pursuit of its own agenda and so as to effect what it senses in the future.

If an autononous agent stumbles upon an enexpected situation, like finding a wall in its way, it will have the ability to respond and adjust its motion accordingly.

The movement of an autonomous agent can be broken down into three layers:

• Action Selection: This is the part of the agent’s behavior responsible for choosing its goals and deciding what plan to follow.
• Steering: This layer is responsible for calculating the desired trajectories required to satisfy the goals and plans set by the action selection layer.
• Locomotion: The bottom layer, locomotion, represents the more mechanical aspects of an agent’s movement.

The Vehicle Model

I will use Unity to simulate the model. (Do later)

The Steering Behaviors

Seek

The seek steering behavior returns a force that directs an agent toward a target position.

protected Vector2 Seek(Vector2 target){
	Vector2 desiredVelocity = (target - (Vector2)transform.position).normalized * maxSpeed;

	return (desiredVelocity - velocity);
}

Flee

Flee is the opposite of seek.

Flee can be easily adjusted to generate a fleeing force only when a vehicle comes within a certain range of the target.

protected Vector2 Flee(Vector2 target){
    Vector2 relativePos = (Vector2)transform.position - target;
    if(relativePos.sqrMagnitude < fleeRange)
        return relativePos.normalized * maxSpeed - velocity;
    else
        return Vector2.zero;
}

Arrive

Arrive is a behavior that steers the agent in such a way it decelerates onto the target position while almost arriving.

Arrive uses a parameter to calculate how much time the agent desires to take to reach the target.

Pursuit

Pursuit behavior is useful when an agent is required to intercept a moving target (Keep seeking wouldn’t really help to create illusion of intelligence). The agent will run toward the position the target is going to be in the future.

The success of the pursuit function depends on how well the pursuer can predict the evader’s trajectory in limited clock cycles.

One of the difficulties in creating a good predictor is deciding how far into the future the agent should predict. Clearly, the amount of look-ahead should be proportional to the separation between the pursuer and its evader, and inversely proportional to the pursuer’s and evader’s speeds.

Evade

Evade is almost the same as pursuit except that this time the evader flees from the estimated future position.

Wander

Wander is designed to produce a steering force that will give the impression of a random walk through the agent’s environment.

Obstacle Avoidance

Obstacle avoidance is a behavior that steers a vehicle to avoid obstacles lying in its path (An obstacle can be considered as a circle/sphere).

We use a rectangular area — a detection box help to avoid obstacles. The box’s width is equal to the bounding radius of the vehicle, and it’s length is proportional to the vehicle’s current speed.

Finding the Closest Intersection Point

1. Iterates through all the obstacles and tags those that are within a range for further consideration.
2. Transfroms all the tagged obstacles into the vehicle’s local space.
3. Checks to see if any obstacles overlap the detection box by comparing the local y value with the sum of half of the box’s width and the radius of obstacles.
4. Finds the intersection point closest to the vehicle by a simple line/circle intersection test.

Calculating the Steering

The steering force can be calculated in two parts: a lateral force and a breaking force.

Lateral force is proportional to the vehicle’s distance from the obstacle both horizontal and vertical.

Breaking force is a force acting backward, along the horizontal axis as shown in the figure, and is also scaled in proportion to the vehicle’s distance from the obstacle.

Wall Avoidance

Wall avoidance steers to avoid potential collision with a wall.

It does this by projecting three “feelers” out in front of the vehicle and testing to see if any of them intersect with any walls in the game world.

When the closest intersecting wall has been found, a steering force is calculated. It’s deduced by calculating how far the feeler tip has penetrated through the wall and then by creating a force of that magnitude in the direction of the wall normal.

Using three feeler gives a relatively good result. But using more feelers or just use one feeler that continuously scans left and right is also possible, depending on how many processor cycles you have to play with.

Interpose

Interpose returns a steering force that moves a vehicle to the midpoint of the imaginary line connecting two other agents.

The first step in calculating this force is to determine the midpoint of a line connecting the positions of the agents at the current time step. The distance from this point is computed and the value divided by the vehicle’s maximum speed to give the time required to travel the distance. This is our T value.

Using T, the agents’ positions are extrapolated into the future. The midpoint of these predicted positions is determined and finally the vehicle uses the arrive behavior to steer toward that point.

Hide

Hide attemps to position a vehicle so that an obstacle is always between itself and the agent(the hunter).

Step 1: For each of the obstacles, a hiding spot is determined.

Step 2: The vehicle then uses the arrive behavior to steer toward the closest. If no appropriate obstacles can be found, the vehicle evades the target.

A few modifications can be made:

1. You can allow the vehicle to hide only if the target is within its field of view. This tends to produce unsatisfactory performance though, because the vehicle starts to act like a child hiding from monsters beneath the bed sheets. This can be countered slightly though by adding in a time effect so that the vehicle will hide if the target is visible or if it has seen the target within the last n seconds.
2. The vehicle only tries to hide if the vehicle can see the target and the target can see the vehicle.
3. It might be desirable to produce a force that steers a vehicle so that it always favors hiding positions that are to the side or rear of the pursuer.
4. At the beginning of any of the methods a check can be made to test if the target is within a “threat distance” before proceeding with any fur- ther calculations. If the target is not a threat, then the method can return immediately with a zero vector.

Path Following

Path following creates a steering force that moves a vehicle along a series of waypoints forming a path.

The simplest way of following a path is to set the current waypoint to the first in the list, steer toward that using seek until the vehicle comes within a target distance of it, then grab the next waypoint and seek to that, and so on, until the current waypoint is the last waypoint in the list. When this happens the vehicle should either arrive at the current waypoint, or, if the path is a closed loop, the current waypoint should be set to the first in the list again, and the vehicle just keeps on seeking.

Offset Pursuit

Offset pursuit calculates the steering force required to keep a vehicle posi- tioned at a specified offset from a target vehicle.

The first thing to do when calculating this steering force is to determine the offset’s position in world space. After that the function proceeds similar to pursuit: A future position for the offset is predicted and the vehicle arrives at that position.

Group Behaviors

Group behaviors are steering behaviors that take into consideration some or all of the other vehicles in the game world.

For example, the flocking behavior is a good example of a group behavior. In fact, flocking is a combination of three group behaviors — cohesion, separation, and alignment — all working together.

To determine the steering force for a group behavior, a vehicle will con- sider all other vehicles within a circular area of predefined size — known as the neighborhood radius — centered on the vehicle.

Here we can pep up the realism slightly for group behaviors by adding a field-of-view (FOV) to our agent.

Separation

Separation creates a force that steers a vehicle away from those in its neighborhood region.

Prior to calling separation, all the agents situated within a vehicle’s neighborhood are tagged. Separation then iterates through the tagged vehicles, examining each one. The vector to each vehicle under consideration is normalized, divided by the distance to the neighbor, and added to the steering force.

Alignment

Alignment attempts to keep a vehicle’s heading aligned with its neighbors.

The force is calculated by first iterating through all the neighbors and averaging their heading vectors. This value is the desired heading, so we just subtract the vehicle’s heading to get the steering force.

Cohesion

Cohesion produces a steering force that moves a vehicle toward the center of mass of its neighbors.

This method proceeds similarly to the last, except this time we calculate the average of the position vectors of the neighbors. This gives us the cen- ter of mass of the neighbors — the place the vehicle wants to get to — so it seeks to that position.

Flocking

A combination of separation, cohesion and alignment.

Tweaking the magnitudes of each of the contributing behaviors will give you different effects such as shoals of fish, loose swirling flocks of birds and so on.

Combining Steering Behaviors

Often you will be using a combination of steering behaviors to get the behavior you desire. Very rarely will you only use one behavior in isolation.

All the steering behaviors described in this chapter are methods of one class: SteeringBehaviors. A Vehicle owns an instance of this class and activates/deactivates the various behaviors by switching them on and off using accessor methods. And finally determines the resultant force from all the active behaviors.

Weighted Trucated Sum

The simplest approach is to multiply each steering behavior with a weight, sum them all together, and then truncate the result to the maximum allow- able steering force.

This can work fine, but the trade-off is that it comes with a few problems. The first problem is that because every active behavior is calculated every time step, this is a very costly method to process. Additionally, the behavior weights can be very difficult to tweak. For example, we imagine a vehicle is backed up against a wall by several other vehicles.

Weighted Truncated Running Sum with Prioritization

This is the method used to determine the steering forces for all the examples used in this book, chosen mainly because it gives a good compromise between speed and accuracy. This method involves calculating a prioritized weighted running total that is truncated after the addition of each force to make sure the magnitude of the steering force does not exceed the maximum available.

In addition to the prioritization, this method iterates through every active according to their priorities, summing up the forces (with weighting) as it goes. Immediately after the calculation of each new behavior, the resultant force, together with the running total, is dispatched to a method called AccumulateForce. This function first determines how much of the maximum available steering force is remaining, and then one of the following happens:

• If there is a surplus remaining, the new force is added to the running total.
• If there is no surplus remaining, the method returns false. When this happens, Calculate returns the current value of m_vSteeringForce immediately and without considering any further active behaviors.
• If there is still some steering force available, but the magnitude remaining is less than the magnitude of the new force, the new force is truncated to the remaining magnitude before it is added.

Prioritized Dithering

This method checks to see if the first priority behavior is going to be evaluated this simulation step, dependent on a preset probability. If it is and the result is non-zero, the method returns the calculated force and no other active behaviors are considered. If the result is zero or if that behavior has been skipped over due to its probability of being evaluated, the next priority behavior is considered and so on, for all the active behaviors.

Ensuring Zero Overlap

Often when combining behaviors, the vehicles will occasionally overlap one another. The separation steering force alone is not enough to prevent this from happening.

This can be prevented with the use of a non-penetration constraint. This is a function that tests for overlap. If there is any, the vehicles are moved apart in a direction away from the point of contact (and without regard to their mass, velocity, or any other physical constraints).

Coping with Lots of Vehicles: Spatial Partitioning

When you have many interacting vehicles, it becomes increasingly inefficient to tag neighboring entities by comparing each one with every other one.

Large speed improvements can be made by partitioning the world space. There are many different techniques to choose from. You’ve probably heard of many of them — BSP trees, quad-trees, oct-trees, etc. — and may even have used them, in which case you’ll be familiar with their advan- tages. The method I use here is called cell-space partitioning, sometimes called bin-space partitioning (that’s not short for binary space partitioning by the way; in this case “bin” really means bin). With this method, 2D space is divided up into a number of cells (or bins). Each cell contains a list of pointers to all the entities it contains. This is updated (in an entity’s update method) every time an entity changes position. If an entity moves into a new cell, it is removed from its old cell’s list and added to the current one.
This way, instead of having to test every vehicle against every other, we can just determine which cells lie within a vehicle’s neighborhood and test against the vehicles contained in those cells. Here is how it’s done step by step:

1. First of all, an entity’s bounding radius is approximated with a box.
2. The cells that intersect with this box are tested to see if they contain any entities.
3. All the entities contained within the cells from step 2 are examined to see if they are positioned within the neighborhood radius. If they are, they are added to the neighborhood list.

Smoothing

Sometimes a vehicle can twitch or jitter slightly when it finds itself in a situation with conflicting responses from different behaviors.

To negotiate the scenario successfully and smoothly, the vehicle needs to be able to foresee the conflict ahead of time and change behavior accordingly. Although this can be done, the solution can require a lot of calculation and additional baggage.

One simple alternative suggested by Robin Green of Sony is to decouple the heading from the velocity vector and to average its value over several update steps. The averate value is used by the world transfrom function in the render call to transfrom a vehicle’s vertices to the screen.

Practice Makes Perfect

In his paper “Steering Behaviors for Autonomous Characters,” Reynolds describes a behavior called leader following. Leader following is a behav- ior that creates a steering force to keep multiple vehicles moving in single file behind a leader vehicle. If you’ve ever watched goslings follow their mother you’ll know what I mean. To create this sort of behavior the follow- ers must arrive at an offset position behind the vehicle in front while using separation to remain apart from one another.

Leader following can be improved further by creating a behavior that steers a vehicle laterally away from the direction of the leader if it finds itself in the leader’s path.

Create a group of 20 vehicles that behave like a flock of sheep. Now add a user-controlled vehicle you can steer using the keyboard. Program your sheep so they believe the vehicle is a dog. Can you get the flock’s behavior to look realistic?