Natural Motion Simulation: Steering Behaviors - 2
The first part of the article is here .
NPC often requires the ability to avoid obstacles to navigate properly. In this part, we will look at the steering behavior collision avoidance , which allows characters to safely dodge obstacles in the environment.
The basic idea of ​​avoiding collisions is to generate a control force to avoid obstacles every time they are close enough to impede movement. Even if there are several obstacles in the environment, this behavior will simultaneously use one of them to calculate the avoidance force.
')
Only obstacles in front of the character are analyzed; the closest one is selected for evaluation as representing the greatest threat. As a result, the character has the ability to evade all obstacles in the area, safely and without hesitation, moving from one to another.
The obstacles in front of the character are analyzed and the nearest (most threatening) is selected.
Collision avoidance behavior is not a pathfinding algorithm. It makes the characters move around the environment, avoiding obstacles, gradually finding their way through the blocks - but in cases with obstacles in the form of L or T, for example, it does not work very well.
Hint: This collision avoidance behavior may seem similar to Flee, but there is an important difference between them. A character moving along a wall will avoid her only when she blocks his path, and flee behavior always pushes the character away from the wall.
The first step necessary to avoid obstacles in the environment is their perception. The only obstacles that should excite the character are those that are in front of him and block the current route.
As explained in the previous article, the direction of movement of the character describes the velocity vector. We use it to create a new vector with the name
The vector
This vector is calculated as follows:
The length of the vector
The more
The greater the length ahead, the earlier the character will take measures to avoid obstacles.
To check the presence of a collision, each obstacle (or a rectangle describing it) must be described in a geometric form. The best results are obtained by using a sphere (in two dimensions - a circle), therefore every obstacle in the environment should be described in this way.
One solution is to check the collision of the intersection of the segment and the sphere - the segment is a vector
The
Same direction, half length.
The vector
We want to perform a collision check to test whether one of these two vectors is inside the sphere of an obstacle. This is easy to do by comparing the distance between the end of the vector and the center of the sphere.
If the distance is less than or equal to the radius of the sphere, then the vector is inside the sphere and a collision is detected:
The vector ahead intersects with an obstacle if d <r. To make it clearer, the vector ahead2 is removed.
If any of these two vectors ahead is inside the sphere of the obstacle, then this obstacle blocks the path. You can use the definition of the Euclidean distance between two points:
If a character’s path is blocked by several obstacles, then the nearest (most threatening) is chosen for calculations:
For calculations, the nearest obstacle (the most threatening) is selected.
The force of avoidance should push the character away from the obstacle, allowing him to dodge the sphere. This can be implemented using a vector formed with the center of a sphere (position vector) and the vector
After calculating the
Calculation of the power of avoidance. The dotted orange line shows the trajectory that the character will follow to avoid obstacles.
Hint: the position of any entity can be described as a vector so that they can be used in calculations along with other vectors and forces.
The finished implementation of the
The avoidance force must be added to the character's velocity vector. As explained in the previous article, all control forces can be combined into one, creating a force that represents all active behaviors acting on a character.
At a certain angle and direction of the avoidance force, it will not interfere with other control forces, such as seek or wander. The power of avoidance is added to the character’s speed in the usual way:
Since all steering behaviors are recalculated every time the game is updated, the avoidance power will be active as long as the obstacle blocks the path.
When an obstacle ceases to cross a segment of a vector
The current implementation has two problems with collision recognition. The first occurs when the
If this happens, the character will touch (or enter) the obstacle, skipping the avoidance process, because the collision is not detected:
Sometimes the
This problem can be eliminated by adding a third vector to the collision check: character position vector. Using three vectors greatly improves collision detection.
The second problem occurs when a character is close to an obstacle and moves away from it. Sometimes maneuvering can lead to collisions, even if the character just turns to look in a different direction:
Maneuvering can lead to a collision, even if the character just turns around.
This problem can be eliminated by changing the scale of the vectors
The variable
Therefore, if a character simply maneuvers without moving,
To demonstrate the behavior of avoiding obstacles in action, a horde of zombies would be best. Below is a demo with several zombies (all of them have different speeds) seeking to mouse cursor.
Flash online demo is here .
The collision avoidance behavior allows any character to dodge obstacles in the environment. Since all control forces are recalculated anew each time a game is updated, characters interact seamlessly with various obstacles, always analyzing the most threatening (nearest).
Even despite the fact that this behavior is not an algorithm for finding paths, the results achieved on densely populated maps look quite convincing.
The task of implementing the following along the way is often encountered when developing games. In this part, we will look at the steering behavior path following (following the path), allowing the characters to follow a predetermined path consisting of their points and segments.
The behavior of following the path can be implemented in several ways. In the original implementation of Reynolds , a path consisting of segments is used, and the characters strictly follow it, like a train on rails.
In some situations, this accuracy is not required. The character can move along the path, following the segments, but using them as a binding , and not as rails.
The follow-up implementation provided in this tutorial is a simplification of the implementation proposed by Reynolds. It also creates good results, but is not so tightly tied to heavy mathematical calculations like projection of vectors.
The path can be specified as a set of points (nodes) connected by segments. You can also use curves to describe the path, but it’s easier to work with points and lines, and they give almost the same results.
If you need to use curves, they can be reduced to a set of connected points:
Curves and segments.
The path class will be used to describe the route. In fact, the class has a vector of points and several methods for processing this list:
Each point of the path is a
To navigate along the path, the character will move from node to node until it reaches the end of the route.
Each point on the path can be viewed as a goal, so we can use the Seek behavior:
Performing Seek from one point to another.
The character will move to the current point until he reaches it, then the next point on the path becomes current, and so on. As previously stated in the part on avoiding collisions, the forces of each behavior are recalculated in each game update, that is, the transition from one node to another occurs smoothly and imperceptibly.
To process the navigation process, the character class will need two additional properties: the current node (the one the character is aiming at) and a link to the path it follows. The class will look like this:
The
The
If the distance between the current goal and the character’s position is less than
The force used to push a character to each node of the path is seek. The corresponding code is already selected in the
After calculating the force of following the path, it is necessary, as usual, to add the character’s speed to the vector:
The driving force of following the path is extremely similar to the behavior of Pursuit, in which the character is constantly changing its direction to catch the target. The difference lies in the fact that the character strives for a fixed target, which, after reaching, begins to ignore and strive for another.
The result will be as follows:
Flash online demo is here .
In the current implementation, all characters are required to “touch” the current point on the path in order to choose the next one. Consequently, a character can perform unwanted movement patterns, for example, move around a target in circles until he reaches it.
In nature, all movements tend to follow the principle of least effort . For example, a person does not walk constantly in the middle of a corridor; if there is a turn ahead, it approaches the wall to reduce the distance.
This pattern can be recreated by adding a radius to the path. The radius is applied to points and can be considered as the “width” of the route. He will control how far a character can move away from points, moving along the path:
The effect of the radius on the path.
If the distance between the character and the point is less than or equal to the radius, then the point is considered to be reached. Consequently, all characters will move using segments and points as guides :
Flash online demo is here .
The larger the radius, the wider the route and the greater the distance to the points that the characters will maintain during turns. The radius value can be changed to create different sequence patterns.
Sometimes, reaching the end of the path, it is useful for characters to keep moving. For example, in the patrol pattern, a character, having reached the end, must return to the beginning of the route, following the same points.
This can be achieved by adding the property
The
Unlike the previous version, now the value of
After this, the test checks whether the character has reached the end of the route. If this is the case,
As a result, we get a pattern of moving forward and backward.
Following the path allows characters to move along a given path. The route is determined by points and its width can be adjusted, creating patterns of movement that look more natural.
The implementation discussed in this part is a simplification of the initial behavior of following the path suggested by Reynolds, but still creates plausible and natural results.
In addition to being able to follow the path, the character (or group of characters) must also be able to follow some character (for example, the squad leader). This problem can be solved using the following leader behavior (following the leader).
The behavior of following the leader is a combination of other control forces arranged in such a way that a group of characters follow a certain character (leader). In a trivial approach, you can use Seek or Pursuit behaviors to create a following pattern, but the result will not be very good.
With seek behavior, the character is pushed towards the goal, sooner or later taking the same place as the goal. The pursuit behavior, on the other hand, pushes a character to another character, but with the goal of catching it (based on predictions) rather than just following it.
When following a leader, the task is to remain close enough to the leader, but slightly behind him . In addition, when a character is far away, he should move to the leader faster, but slow down while reducing the distance. This can be achieved by combining the three steering behaviors:
Below, I will explain how each of these behaviors can be combined to create a pattern of following the leader.
In the process of following the character should strive to remain a little behind the leader, like an army behind the commander. The following point (called
If the velocity vector is multiplied by
Here is a visual representation of the process:
Vector operations used to find the sequence point.
The more
The next step is for the character to follow the leader's point
The method calculates a point
The result of this implementation will be that a group of characters will be able to arrive at the
, , . , , «». — , (flocking) .
. :
As a result, we get a much more natural looking pattern ( Flash demo ).
If the leader suddenly changes the current direction, then there is a chance that the characters will be on his way. Since the characters follow the leader, it will be illogical to leave him in front of the leader.
If a character gets in the way of a leader, then he must immediately step back to clear the way. This can be achieved by evade behavior:
, , , , collision avoidance: (
We need to change the method
All characters, once in the scope of the leader, will instantly avoid his current position ( Flash demo ).
Hint: the power of following the leader is a combination of several forces. When a character is affected by the power of following, then in fact he is simultaneously influenced by the forces of arrival, separation and avoidance.
Below is a demo showing the behavior of following the leader. The blue soldier (leader) performs the behavior of arrive at the mouse cursor, and the green soldiers follow the leader.
When a player clicks on the screen, all the soldiers turn in the direction of the cursor and shoot. Monsters every few seconds apply the behavior of arrive at random points.
Flash online demo is here .
The leader following behavior (following the leader) allows a group of characters to follow a specific goal, staying slightly behind it. In addition, characters avoid the current location of the leader if they are in his path.
It is important to note that the behavior of following the leader is a combination of several other behaviors, such as arrive, evade and separation. It shows that simple behaviors can be combined to create extremely complex patterns of movement.
, . - . .
queue () , , .
Queuing ( ) , - . , , , . .
queue « ». , , ( Flash).
: seek collision avoidance.
The door consists of two rectangular obstacles, between which there is a gap (doorway). The character seeks (seek) to the point behind this door. Having reached there, the character moves to the bottom of the screen.
Without a queue, the scene looks like a horde of savages struggling to arrive at their destination. After the implementation of the behavior of the crowd will smoothly leave the room, creating rows.
The first ability that a character must receive in order to stand in line is the ability to find out if there is anyone in front of him. Based on this information, he can decide whether to keep moving or to stop.
Despite the existence of more sophisticated ways to check the presence of neighbors ahead, I use a simplified method based on the distance between the point and the character. This approach was used in collision avoidance behavior to check for the presence of obstacles ahead:
Checking neighbors using the ahead point.
Before the character is projected a point with the name
The point is
The speed, which also gives the character's direction, is normalized and scaled by
All this can be wrapped in a method
The method checks the distance between the point
As with all other behaviors, the lining force is calculated in a method called
The result
The method
The method
Since it
Steering behaviors are based on constantly changing forces, so the system as a whole becomes very dynamic. The more forces are used, the more difficult it becomes to identify and cancel the vector of a certain force.
In the implementation used in this series of steering behaviors, all forces are added. Therefore, to cancel the force, it is necessary to re-calculate it, to draw it and to add it again to the vector of the current control force.
This is what happens in Arrival's behavior, in which the speed is canceled to make the character stop. But what happens when several forces work together, for example, in collision avoidance, flee, and other behaviors?
In the sections below, two ideas are presented on how to make a character stop. The first uses the “hard stop” approach, which acts directly on the velocity vector and ignores all other control forces. The second uses a force vector called
Several controlling forces are based on the character's speed vector. If this vector changes, it affects all other forces, that is, they need to be recalculated. The idea of ​​a “hard stop” is quite simple: if there is a character ahead, then we “trim” the speed vector:
In the above code, when detecting a character in front, the vector scale
It is easier to understand by analyzing how the motion is calculated for each update :
If the force
After completion of the process of reduction in each update of the game, the vector
The solution with a “hard stop” creates the following results (Flash demo).
Even though the result is rather plausible, it still looks a bit “mechanical”. In a real crowd, between the participants there is usually no empty space left.
«»
Submission of braking force.
The force
Hint: direct use of force is
Strength
The result of using braking force is as follows:
Flash online demo is here .
The braking solution creates a more natural result compared to the “mechanistic” one, because all the characters are trying to fill in the empty spaces. However, it creates a new problem: the characters overlap each other.
To eliminate it, the solution with braking can be improved with a slightly modified version of the “hard stop” approach:
The new test is used to check the nearest neighbors. This time, instead of using a point to measure distance
MAX_QUEUE_RADIUS, , ahead.
, -
,
«», , - ( Flash).
, , , .
, (separation):
, leader following,
, :
Flash .
Behavior queue allows characters to queue up and wait patiently for arrival at their destination. While in the queue, the character tries not to "cheat" by jumping over positions; he will only move when the character in front of him moves.
The scene with the doorway shown in this tutorial demonstrates how versatile and customizable this behavior can be. Minor changes create a completely different result, which is easy to adjust to different situations. This behavior can also be combined with others, for example, with collision avoidance (collision avoidance).
I hope you enjoyed this new behavior and you will use it to create moving crowds in your game!
Part 6. Avoiding Collisions
NPC often requires the ability to avoid obstacles to navigate properly. In this part, we will look at the steering behavior collision avoidance , which allows characters to safely dodge obstacles in the environment.
Introduction
The basic idea of ​​avoiding collisions is to generate a control force to avoid obstacles every time they are close enough to impede movement. Even if there are several obstacles in the environment, this behavior will simultaneously use one of them to calculate the avoidance force.
')
Only obstacles in front of the character are analyzed; the closest one is selected for evaluation as representing the greatest threat. As a result, the character has the ability to evade all obstacles in the area, safely and without hesitation, moving from one to another.
The obstacles in front of the character are analyzed and the nearest (most threatening) is selected.
Collision avoidance behavior is not a pathfinding algorithm. It makes the characters move around the environment, avoiding obstacles, gradually finding their way through the blocks - but in cases with obstacles in the form of L or T, for example, it does not work very well.
Hint: This collision avoidance behavior may seem similar to Flee, but there is an important difference between them. A character moving along a wall will avoid her only when she blocks his path, and flee behavior always pushes the character away from the wall.
We look forward
The first step necessary to avoid obstacles in the environment is their perception. The only obstacles that should excite the character are those that are in front of him and block the current route.
As explained in the previous article, the direction of movement of the character describes the velocity vector. We use it to create a new vector with the name
ahead , which will be a copy of the velocity vector, but with a different length:The vector
ahead is the character's line of sight.This vector is calculated as follows:
ahead = position + normalize(velocity) * MAX_SEE_AHEAD The length of the vector
ahead (changeable with MAX_SEE_AHEAD ) determines the distance that a character can “see”.The more
MAX_SEE_AHEAD , the earlier the character will begin to evade the obstacle, because it will be perceived as a threat, even if you are far away:The greater the length ahead, the earlier the character will take measures to avoid obstacles.
Collision check
To check the presence of a collision, each obstacle (or a rectangle describing it) must be described in a geometric form. The best results are obtained by using a sphere (in two dimensions - a circle), therefore every obstacle in the environment should be described in this way.
One solution is to check the collision of the intersection of the segment and the sphere - the segment is a vector
ahead , and the sphere is an obstacle. This approach works, but I use its simplification, which is easier to understand and at the same time gives similar results (and sometimes even better).The
ahead vector will be used to create another vector half its length:Same direction, half length.
The vector
ahead2 calculated in the same way as ahead , but its length is shortened by half: ahead = position + normalize(velocity) * MAX_SEE_AHEAD ahead2 = position + normalize(velocity) * MAX_SEE_AHEAD * 0.5 We want to perform a collision check to test whether one of these two vectors is inside the sphere of an obstacle. This is easy to do by comparing the distance between the end of the vector and the center of the sphere.
If the distance is less than or equal to the radius of the sphere, then the vector is inside the sphere and a collision is detected:
The vector ahead intersects with an obstacle if d <r. To make it clearer, the vector ahead2 is removed.
If any of these two vectors ahead is inside the sphere of the obstacle, then this obstacle blocks the path. You can use the definition of the Euclidean distance between two points:
private function distance(a :Object, b :Object) :Number { return Math.sqrt((ax - bx) * (ax - bx) + (ay - by) * (ay - by)); } private function lineIntersectsCircle(ahead :Vector3D, ahead2 :Vector3D, obstacle :Circle) :Boolean { // "center" - Vector3D. return distance(obstacle.center, ahead) <= obstacle.radius || distance(obstacle.center, ahead2) <= obstacle.radius; } If a character’s path is blocked by several obstacles, then the nearest (most threatening) is chosen for calculations:
For calculations, the nearest obstacle (the most threatening) is selected.
Calculation of the avoidance force
The force of avoidance should push the character away from the obstacle, allowing him to dodge the sphere. This can be implemented using a vector formed with the center of a sphere (position vector) and the vector
ahead . We calculate this avoidance force as follows: avoidance_force = ahead - obstacle_center avoidance_force = normalize(avoidance_force) * MAX_AVOID_FORCE After calculating the
avoidance_force it is normalized and scaled to MAX_AVOID_FORCE , that is, to a value that defines the length of the avoidance_force . The more MAX_AVOID_FORCE , the stronger the power of avoidance pushes the character away from the obstacle.Calculation of the power of avoidance. The dotted orange line shows the trajectory that the character will follow to avoid obstacles.
Hint: the position of any entity can be described as a vector so that they can be used in calculations along with other vectors and forces.
Avoid obstacles
The finished implementation of the
collisionAvoidance() method, which returns the avoidance force, will look like this: private function collisionAvoidance() :Vector3D { ahead = ...; // ahead ahead2 = ...; // ahead2 var mostThreatening :Obstacle = findMostThreateningObstacle(); var avoidance :Vector3D = new Vector3D(0, 0, 0); if (mostThreatening != null) { avoidance.x = ahead.x - mostThreatening.center.x; avoidance.y = ahead.y - mostThreatening.center.y; avoidance.normalize(); avoidance.scaleBy(MAX_AVOID_FORCE); } else { avoidance.scaleBy(0); // } return avoidance; } private function findMostThreateningObstacle() :Obstacle { var mostThreatening :Obstacle = null; for (var i:int = 0; i < Game.instance.obstacles.length; i++) { var obstacle :Obstacle = Game.instance.obstacles[i]; var collision :Boolean = lineIntersecsCircle(ahead, ahead2, obstacle); // "position" - if (collision && (mostThreatening == null || distance(position, obstacle) < distance(position, mostThreatening))) { mostThreatening = obstacle; } } return mostThreatening; } The avoidance force must be added to the character's velocity vector. As explained in the previous article, all control forces can be combined into one, creating a force that represents all active behaviors acting on a character.
At a certain angle and direction of the avoidance force, it will not interfere with other control forces, such as seek or wander. The power of avoidance is added to the character’s speed in the usual way:
steering = nothing(); // , " " steering = steering + seek(); // , - steering = steering + collisionAvoidance(); steering = truncate (steering, max_force) steering = steering / mass velocity = truncate (velocity + steering, max_speed) position = position + velocity Since all steering behaviors are recalculated every time the game is updated, the avoidance power will be active as long as the obstacle blocks the path.
When an obstacle ceases to cross a segment of a vector
ahead , the avoidance force becomes zero (no effect) or recalculated to avoid another threatening obstacle. As a result of this, we get a character who can dodge obstacles.Improving Collision Detection
The current implementation has two problems with collision recognition. The first occurs when the
ahead vectors are outside the sphere of the obstacle, but the character is too close to the obstacle (or inside).If this happens, the character will touch (or enter) the obstacle, skipping the avoidance process, because the collision is not detected:
Sometimes the
ahead vectors are outside the obstacles, but the character is inside.This problem can be eliminated by adding a third vector to the collision check: character position vector. Using three vectors greatly improves collision detection.
The second problem occurs when a character is close to an obstacle and moves away from it. Sometimes maneuvering can lead to collisions, even if the character just turns to look in a different direction:
Maneuvering can lead to a collision, even if the character just turns around.
This problem can be eliminated by changing the scale of the vectors
ahead in accordance with the current speed of the character. For example, the code for computing the ahead vector is changed as follows: dynamic_length = length(velocity) / MAX_VELOCITY ahead = position + normalize(velocity) * dynamic_length The variable
dynamic_length changes from 0 to 1. When a character moves at full speed, dynamic_length is 1; when a character slows down or speeds up, dynamic_length is 0 or more (for example, 0.5).Therefore, if a character simply maneuvers without moving,
dynamic_length tends to zero, creating a zero vector ahead that has no collisions.Demo: zombie time!
To demonstrate the behavior of avoiding obstacles in action, a horde of zombies would be best. Below is a demo with several zombies (all of them have different speeds) seeking to mouse cursor.
Flash online demo is here .
Conclusion
The collision avoidance behavior allows any character to dodge obstacles in the environment. Since all control forces are recalculated anew each time a game is updated, characters interact seamlessly with various obstacles, always analyzing the most threatening (nearest).
Even despite the fact that this behavior is not an algorithm for finding paths, the results achieved on densely populated maps look quite convincing.
Part 7. Following the path
The task of implementing the following along the way is often encountered when developing games. In this part, we will look at the steering behavior path following (following the path), allowing the characters to follow a predetermined path consisting of their points and segments.
Introduction
The behavior of following the path can be implemented in several ways. In the original implementation of Reynolds , a path consisting of segments is used, and the characters strictly follow it, like a train on rails.
In some situations, this accuracy is not required. The character can move along the path, following the segments, but using them as a binding , and not as rails.
The follow-up implementation provided in this tutorial is a simplification of the implementation proposed by Reynolds. It also creates good results, but is not so tightly tied to heavy mathematical calculations like projection of vectors.
Setting the path
The path can be specified as a set of points (nodes) connected by segments. You can also use curves to describe the path, but it’s easier to work with points and lines, and they give almost the same results.
If you need to use curves, they can be reduced to a set of connected points:
Curves and segments.
The path class will be used to describe the route. In fact, the class has a vector of points and several methods for processing this list:
public class Path { private var nodes :Vector.<Vector3D>; public function Path() { this.nodes = new Vector.<Vector3D>(); } public function addNode(node :Vector3D) :void { nodes.push(node); } public function getNodes() :Vector.<Vector3D> { return nodes; } } Each point of the path is a
Vector3D , which is a position in space, similar to the way the character’s position property works.Movement from node to node
To navigate along the path, the character will move from node to node until it reaches the end of the route.
Each point on the path can be viewed as a goal, so we can use the Seek behavior:
Performing Seek from one point to another.
The character will move to the current point until he reaches it, then the next point on the path becomes current, and so on. As previously stated in the part on avoiding collisions, the forces of each behavior are recalculated in each game update, that is, the transition from one node to another occurs smoothly and imperceptibly.
To process the navigation process, the character class will need two additional properties: the current node (the one the character is aiming at) and a link to the path it follows. The class will look like this:
public class Boid { public var path :Path; public var currentNode :int; (...) private function pathFollowing() :Vector3D { var target :Vector3D = null; if (path != null) { var nodes :Vector.<Vector3D> = path.getNodes(); target = nodes[currentNode]; if (distance(position, target) <= 10) { currentNode += 1; if (currentNode >= nodes.length) { currentNode = nodes.length - 1; } } } return null; } private function distance(a :Object, b :Object) :Number { return Math.sqrt((ax - bx) * (ax - bx) + (ay - by) * (ay - by)); } (...) } The
pathFollowing() method is responsible for generating the force to follow along the path. While he does not create strength, but correctly chooses goals.The
path != null test checks whether a character follows a certain path. If this is the case, the currentNode property is currentNode to search for the current target (the one the character should aim at) in the list of points.If the distance between the current goal and the character’s position is less than
10 , then this means that the character has reached the current node. If this happens, the currentNode increased by one, and therefore, the character will tend to the next point on the way. The process is repeated until the points end on the way.Calculation and addition of forces
The force used to push a character to each node of the path is seek. The corresponding code is already selected in the
pathFollowing() method, so now it must return a force that pushes the character to this node: private function pathFollowing() :Vector3D { var target :Vector3D = null; if (path != null) { var nodes :Vector.<Vector3D> = path.getNodes(); target = nodes[currentNode]; if (distance(position, target) <= 10) { currentNode += 1; if (currentNode >= nodes.length) { currentNode = nodes.length - 1; } } } return target != null ? seek(target) : new Vector3D(); } After calculating the force of following the path, it is necessary, as usual, to add the character’s speed to the vector:
steering = nothing(); // , " " steering = steering + pathFollowing(); steering = truncate (steering, max_force) steering = steering / mass velocity = truncate (velocity + steering, max_speed) position = position + velocity The driving force of following the path is extremely similar to the behavior of Pursuit, in which the character is constantly changing its direction to catch the target. The difference lies in the fact that the character strives for a fixed target, which, after reaching, begins to ignore and strive for another.
The result will be as follows:
Flash online demo is here .
Motion smoothing
In the current implementation, all characters are required to “touch” the current point on the path in order to choose the next one. Consequently, a character can perform unwanted movement patterns, for example, move around a target in circles until he reaches it.
In nature, all movements tend to follow the principle of least effort . For example, a person does not walk constantly in the middle of a corridor; if there is a turn ahead, it approaches the wall to reduce the distance.
This pattern can be recreated by adding a radius to the path. The radius is applied to points and can be considered as the “width” of the route. He will control how far a character can move away from points, moving along the path:
The effect of the radius on the path.
If the distance between the character and the point is less than or equal to the radius, then the point is considered to be reached. Consequently, all characters will move using segments and points as guides :
Flash online demo is here .
The larger the radius, the wider the route and the greater the distance to the points that the characters will maintain during turns. The radius value can be changed to create different sequence patterns.
Forward and backward
Sometimes, reaching the end of the path, it is useful for characters to keep moving. For example, in the patrol pattern, a character, having reached the end, must return to the beginning of the route, following the same points.
This can be achieved by adding the property
pathDir to the character class; it is an integer value that controls the direction in which the character moves along the path. If pathDir is 1 , then the character moves to the end of the path; -1 indicates a start.The
pathFollowing() method can be changed as follows: private function pathFollowing() :Vector3D { var target :Vector3D = null; if (path != null) { var nodes :Vector.<Vector3D> = path.getNodes(); target = nodes[currentNode]; if (distance(position, target) <= path.radius) { currentNode += pathDir; if (currentNode >= nodes.length || currentNode < 0) { pathDir *= -1; currentNode += pathDir; } } } return target != null ? seek(target) : new Vector3D(); } Unlike the previous version, now the value of
pathDir added to the currentNode property (instead of simply adding 1 ). This allows the character to choose the next point on the path based on the current direction.After this, the test checks whether the character has reached the end of the route. If this is the case,
pathDir is multiplied by -1 , which reverses the value, causing the character to reverse its direction of movement.As a result, we get a pattern of moving forward and backward.
Conclusion
Following the path allows characters to move along a given path. The route is determined by points and its width can be adjusted, creating patterns of movement that look more natural.
The implementation discussed in this part is a simplification of the initial behavior of following the path suggested by Reynolds, but still creates plausible and natural results.
Part 8. Following the leader
In addition to being able to follow the path, the character (or group of characters) must also be able to follow some character (for example, the squad leader). This problem can be solved using the following leader behavior (following the leader).
Introduction
The behavior of following the leader is a combination of other control forces arranged in such a way that a group of characters follow a certain character (leader). In a trivial approach, you can use Seek or Pursuit behaviors to create a following pattern, but the result will not be very good.
With seek behavior, the character is pushed towards the goal, sooner or later taking the same place as the goal. The pursuit behavior, on the other hand, pushes a character to another character, but with the goal of catching it (based on predictions) rather than just following it.
When following a leader, the task is to remain close enough to the leader, but slightly behind him . In addition, when a character is far away, he should move to the leader faster, but slow down while reducing the distance. This can be achieved by combining the three steering behaviors:
- Arrive: movement to the leader with gradual deceleration and stopping of movement.
- Evade: if the character is on the path of the leader, then he must quickly move away.
- Separation : Avoiding crowding, when the leader is followed by several characters.
Below, I will explain how each of these behaviors can be combined to create a pattern of following the leader.
Finding the right point to follow
In the process of following the character should strive to remain a little behind the leader, like an army behind the commander. The following point (called
behind ) can be easily calculated based on the speed of the target, because it also represents the direction of the character. Here is the pseudocode: tv = leader.velocity * -1; tv = normalize(tv) * LEADER_BEHIND_DIST; behind = leader.position + tv; If the velocity vector is multiplied by
-1 , then the result will be the inverse of the velocity vector. This resultant vector (called tv ) can then be normalized, scaled, and added to the character’s current position.Here is a visual representation of the process:
Vector operations used to find the sequence point.
The more
LEADER_BEHIND_DIST , the greater the distance between the leader and the point behind him. Since the characters will follow this point, the further it is from the leader, the further the characters will be from it.Follow and Arrival
The next step is for the character to follow the leader's point
behind. As in all other behaviors, the follow-up process is controlled by the force generated by the method followLeader(): private function followLeader(leader :Boid) :Vector3D { var tv :Vector3D = leader.velocity.clone(); var force :Vector3D = new Vector3D(); // behind tv.scaleBy(-1); tv.normalize(); tv.scaleBy(LEADER_BEHIND_DIST); behind = leader.position.clone().add(tv); // behind force = force.add(arrive(behind)); return force; } The method calculates a point
behindand creates a force for arriving at this point. Then followLeaderyou can add strength to the control power of the character, as in all other behaviors: steering = nothing(); // , " " steering = steering + followLeader(); steering = truncate (steering, max_force) steering = steering / mass velocity = truncate (velocity + steering, max_speed) position = position + velocity The result of this implementation will be that a group of characters will be able to arrive at the
behindleader's point (interactive Flash demo ).Avoiding crowding
, , . , , «». — , (flocking) .
. :
private function separation() :Vector3D { var force :Vector3D = new Vector3D(); var neighborCount :int = 0; for (var i:int = 0; i < Game.instance.boids.length; i++) { var b :Boid = Game.instance.boids[i]; if (b != this && distance(b, this) <= SEPARATION_RADIUS) { force.x += b.position.x - this.position.x; force.y += b.position.y - this.position.y; neighborCount++; } } if (neighborCount != 0) { force.x /= neighborCount; force.y /= neighborCount; force.scaleBy( -1); } force.normalize(); force.scaleBy(MAX_SEPARATION); return force; } followLeader , , : private function followLeader(leader :Boid) :Vector3D { var tv :Vector3D = leader.velocity.clone(); var force :Vector3D = new Vector3D(); // behind tv.scaleBy(-1); tv.normalize(); tv.scaleBy(LEADER_BEHIND_DIST); behind = leader.position.clone().add(tv); // behind force = force.add(arrive(behind)); // force = force.add(separation()); return force; } As a result, we get a much more natural looking pattern ( Flash demo ).
Out of the way
If the leader suddenly changes the current direction, then there is a chance that the characters will be on his way. Since the characters follow the leader, it will be illogical to leave him in front of the leader.
If a character gets in the way of a leader, then he must immediately step back to clear the way. This can be achieved by evade behavior:
, , , , collision avoidance: (
ahead ); ahead , , 30 , .ahead , behind point; , : tv = leader.velocity; tv = normalize(tv) * LEADER_BEHIND_DIST; ahead = leader.position + tv; We need to change the method
followLeader()to check if the character is in scope. If this happens, then the variable force(representing the force of the sequence) is added to the value, the return evade(leader)value, that is, the force avoiding the position of the leader: private function followLeader(leader :Boid) :Vector3D { var tv :Vector3D = leader.velocity.clone(); var force :Vector3D = new Vector3D(); // ahead tv.normalize(); tv.scaleBy(LEADER_BEHIND_DIST); ahead = leader.position.clone().add(tv); // behind tv.scaleBy(-1); behind = leader.position.clone().add(tv); // , // . if (isOnLeaderSight(leader, ahead)) { force = force.add(evade(leader)); } // behind force = force.add(arrive(behind, 50)); // 50 - // force = force.add(separation()); return force; } private function isOnLeaderSight(leader :Boid, leaderAhead :Vector3D) :Boolean { return distance(leaderAhead, this) <= LEADER_SIGHT_RADIUS || distance(leader.position, this) <= LEADER_SIGHT_RADIUS; } private function distance(a :Object, b :Object) :Number { return Math.sqrt((ax - bx) * (ax - bx) + (ay - by) * (ay - by)); } All characters, once in the scope of the leader, will instantly avoid his current position ( Flash demo ).
Hint: the power of following the leader is a combination of several forces. When a character is affected by the power of following, then in fact he is simultaneously influenced by the forces of arrival, separation and avoidance.
Demo
Below is a demo showing the behavior of following the leader. The blue soldier (leader) performs the behavior of arrive at the mouse cursor, and the green soldiers follow the leader.
When a player clicks on the screen, all the soldiers turn in the direction of the cursor and shoot. Monsters every few seconds apply the behavior of arrive at random points.
Flash online demo is here .
Conclusion
The leader following behavior (following the leader) allows a group of characters to follow a specific goal, staying slightly behind it. In addition, characters avoid the current location of the leader if they are in his path.
It is important to note that the behavior of following the leader is a combination of several other behaviors, such as arrive, evade and separation. It shows that simple behaviors can be combined to create extremely complex patterns of movement.
Part 9. Queue
, . - . .
queue () , , .
Introduction
Queuing ( ) , - . , , , . .
queue « ». , , ( Flash).
: seek collision avoidance.
The door consists of two rectangular obstacles, between which there is a gap (doorway). The character seeks (seek) to the point behind this door. Having reached there, the character moves to the bottom of the screen.
Without a queue, the scene looks like a horde of savages struggling to arrive at their destination. After the implementation of the behavior of the crowd will smoothly leave the room, creating rows.
We look forward
The first ability that a character must receive in order to stand in line is the ability to find out if there is anyone in front of him. Based on this information, he can decide whether to keep moving or to stop.
Despite the existence of more sophisticated ways to check the presence of neighbors ahead, I use a simplified method based on the distance between the point and the character. This approach was used in collision avoidance behavior to check for the presence of obstacles ahead:
Checking neighbors using the ahead point.
Before the character is projected a point with the name
ahead. If the distance between this point and the neighboring character is less or equal MAX_QUEUE_RADIUS, it means that there is someone ahead and the character must stop.The point is
aheadcalculated as follows (pseudocode): // qa, ahead qa = normalize(velocity) * MAX_QUEUE_AHEAD; ahead = qa + position; The speed, which also gives the character's direction, is normalized and scaled by
MAX_QUEUE_AHEADto create a new vector, called qa. When added qato a vector, the positionresult is a point in front of the character at a distance of MAX_QUEUE_AHEADunits from it.All this can be wrapped in a method
getNeighborAhead(): private function getNeighborAhead() :Boid { var i:int; var ret :Boid = null; var qa :Vector3D = velocity.clone(); qa.normalize(); qa.scaleBy(MAX_QUEUE_AHEAD); ahead = position.clone().add(qa); for (i = 0; i < Game.instance.boids.length; i++) { var neighbor :Boid = Game.instance.boids[i]; var d :Number = distance(ahead, neighbor.position); if (neighbour != this && d <= MAX_QUEUE_RADIUS) { ret = neighbor; break; } } return ret; } The method checks the distance between the point
aheadand all other characters, returning the first character, the distance to which is less or equal MAX_QUEUE_AHEAD. If the character is not found, the method returns null.Creating a Queuing Method
As with all other behaviors, the lining force is calculated in a method called
queue(): private function queue() :Vector3D { var neighbor :Boid = getNeighborAhead(); if (neighbor != null) { // TODO: , } return new Vector3D(0, 0); } The result
getNeighborAhead()is stored in a variable neighbor. If neighbor != null, then there is someone ahead; otherwise, the path is clear.The method
queue(), like the methods of all other behaviors, must return power, which is the controlling force associated with the method itself. As long as queue()it returns strength without magnitude, that is, it will have no effect.The method
update()for all characters in the scene with the door looks like this for now (pseudocode): public function update():void { var doorway :Vector3D = getDoorwayPosition(); steering = seek(doorway); // seek steering = steering + collisionAvoidance(); // steering = steering + queue(); // steering = truncate (steering, MAX_FORCE); steering = steering / mass; velocity = truncate (velocity + steering , MAX_SPEED); position = position + velocity; Since it
queue()returns zero power, the characters will continue to move without creating rows. It is time for them to take some action when a neighbor is found ahead.A few words about stopping traffic
Steering behaviors are based on constantly changing forces, so the system as a whole becomes very dynamic. The more forces are used, the more difficult it becomes to identify and cancel the vector of a certain force.
In the implementation used in this series of steering behaviors, all forces are added. Therefore, to cancel the force, it is necessary to re-calculate it, to draw it and to add it again to the vector of the current control force.
This is what happens in Arrival's behavior, in which the speed is canceled to make the character stop. But what happens when several forces work together, for example, in collision avoidance, flee, and other behaviors?
In the sections below, two ideas are presented on how to make a character stop. The first uses the “hard stop” approach, which acts directly on the velocity vector and ignores all other control forces. The second uses a force vector called
brakecanceling all other controlling forces, that is, forcing the character to stop.Stop motion: "hard stop"
Several controlling forces are based on the character's speed vector. If this vector changes, it affects all other forces, that is, they need to be recalculated. The idea of ​​a “hard stop” is quite simple: if there is a character ahead, then we “trim” the speed vector:
private function queue() :Vector3D { var neighbor :Boid = getNeighborAhead(); if (neighbor != null) { velocity.scaleBy(0.3); } return new Vector3D(0, 0); } In the above code, when detecting a character in front, the vector scale
velocityis reduced to 30%from the current value (length). Consequently, the movement is significantly reduced, but eventually returns to its normal value when the character blocking the path leaves it.It is easier to understand by analyzing how the motion is calculated for each update :
velocity = truncate (velocity + steering , MAX_SPEED); position = position + velocity; If the force
velocitycontinues to decline, then it happens with force steering, because it is based on force velocity. This creates a vicious cycle that results in an extremely low value velocity. And then the character stops moving.After completion of the process of reduction in each update of the game, the vector
velocitywill increase slightly, also affecting the force steering. Gradually a few updates this will vectors velocityand steeringto their normal values.The solution with a “hard stop” creates the following results (Flash demo).
Even though the result is rather plausible, it still looks a bit “mechanical”. In a real crowd, between the participants there is usually no empty space left.
:
«»
brake : private function queue() :Vector3D { var v :Vector3D = velocity.clone(); var brake :Vector3D = new Vector3D(); var neighbor :Boid = getNeighborAhead(); if (neighbor != null) { brake.x = -steering.x * 0.8; brake.y = -steering.y * 0.8; v.scaleBy( -1); brake = brake.add(v); } return brake; } brake , brake steering , , :Submission of braking force.
The force
brakereceives the components xand yfrom the force steering, but turns them and changes their scale to 0.8. This means that it brakeis 80% of the magnitude steeringand points in the opposite direction.Hint: direct use of force is
steeringdangerous. If it queue()is the first behavior applied to a character, then the power steeringwill be “empty.” Consequently, queue()it is necessary to call after all other methods of behaviors so that he can get to full and final strength steering.Strength
brakeshould also cancel a character’s speed. This is done by adding -velocitystrength brake. After this methodqueue()may return the final force brake.The result of using braking force is as follows:
Flash online demo is here .
Decrease Character Overlay
The braking solution creates a more natural result compared to the “mechanistic” one, because all the characters are trying to fill in the empty spaces. However, it creates a new problem: the characters overlap each other.
To eliminate it, the solution with braking can be improved with a slightly modified version of the “hard stop” approach:
private function queue() :Vector3D { var v :Vector3D = velocity.clone(); var brake :Vector3D = new Vector3D(); var neighbor :Boid = getNeighborAhead(); if (neighbor != null) { brake.x = -steering.x * 0.8; brake.y = -steering.y * 0.8; v.scaleBy( -1); brake = brake.add(v); if (distance(position, neighbor.position) <= MAX_QUEUE_RADIUS) { velocity.scaleBy(0.3); } } return brake; } The new test is used to check the nearest neighbors. This time, instead of using a point to measure distance
ahead, the new test checks the distance between the character vectors position:MAX_QUEUE_RADIUS, , ahead.
, -
MAX_QUEUE_RADIUS , position . - , , , , .,
velocity 30% . « », velocity .«», , - ( Flash).
, , , .
, (separation):
private function queue() :Vector3D { var v :Vector3D = velocity.clone(); var brake :Vector3D = new Vector3D(); var neighbor :Boid = getNeighborAhead(); if (neighbor != null) { brake.x = -steering.x * 0.8; brake.y = -steering.y * 0.8; v.scaleBy( -1); brake = brake.add(v); brake = brake.add(separation()); if (distance(position, neighbor.position) <= MAX_QUEUE_RADIUS) { velocity.scaleBy(0.3); } } return brake; } , leader following,
brake , ., :
Flash .
Conclusion
Behavior queue allows characters to queue up and wait patiently for arrival at their destination. While in the queue, the character tries not to "cheat" by jumping over positions; he will only move when the character in front of him moves.
The scene with the doorway shown in this tutorial demonstrates how versatile and customizable this behavior can be. Minor changes create a completely different result, which is easy to adjust to different situations. This behavior can also be combined with others, for example, with collision avoidance (collision avoidance).
I hope you enjoyed this new behavior and you will use it to create moving crowds in your game!
Source: https://habr.com/ru/post/358460/
All Articles