Decent NPC navigation often requires the ability to avoid obstacles. This tutorial covers the collision avoidance steering behavior, which allows characters to gracefully dodge any number of obstacles in the environment.
Note: Although this tutorial is written using AS3 and Flash, you should be able to use the same techniques and concepts in almost any game development environment. You must have a basic understanding of math vectors.
Introduction
The basic idea behind collision avoidance is to generate a steering force to dodge obstacles every time one is close enough to block the passage. Even if the environment has several obstacles, this behavior will use one of them at a time to calculate the avoidance force.
Only the obstacles ahead of the character are analyzed; the closest one, said to be the most threatening, is selected for evaluation. As a result the character is able to dodge all obstacles in the area, transitioning from one to another gracefully and seamlessly.
Obstacles ahead of the character are analyzed and the closest one (most threatening) is selected.
The collision avoidance behavior is not a path finding algorithm. It will make characters move through the environment, avoiding obstacles, eventually finding a route to go through the blocks – but it does not work really well with “L” or “T” obstacles, for instance.
Tip: This collision avoidance behavior may sounds similar to the flee behavior, but there is an important difference between them. A character moving near a wall will avoid it only if it’s blocking the way, but the flee behavior will always push the character away from the wall.Seeing Ahead
The first step to avoid obstacles in the environment is to perceive them. The only obstacles the character must worry are the ones that are in front of it and directly blocking the current route.
As previously explained, the velocity vector describes the direction of the character. It will be used to produce a new vector called ahead, which is a copy of the velocity vector, but with a different length:
The
ahead vector is the character’s line of sight. This vector is calculated as follows:
ahead = position + normalize(velocity) * MAX_SEE_AHEAD
The ahead vector length (adjusted with MAX_SEE_AHEAD) defines how far the character will “see”.
The greater MAX_SEE_AHEAD is, the earlier the character will start acting to dodge an obstacle, because it will perceive it as a threat even if it’s far away:
The greater the ahead length is, the earlier the character will start acting to dodge an obstacle.
Checking for Collision
In order to check for collision, every obstacle (or its bounding box) must be described as a geometric form. Using a sphere (circle in two dimensins) gives the best results, so every obstacle in the environment will be described as such.
One possible solution to check for collision is the line-sphere intersection – the line is the ahead vector and the sphere is the obstacle. That approach works, but I’m going to use a simplification of that which is easier to understand and has similar results (even better ones at times).
The ahead vector will be used to produce another vector with half of its length:
Same direction, half the length.
The ahead2 vector is calculated exactly like ahead, but its length is cut in 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 either of those two vectors are inside the obstacle sphere. That’s easily accomplished by comparing the distance between the vector’s end and the sphere’s center.
If the distance is less than or equal to the sphere radius, then the vector is inside the sphere and a collision was found:
The ahead vector is intercepting the obstacle if d < r. The ahead2 vector was omitted for clarity.
If either of the two ahead vectors are inside the obstacle sphere, then that obstacle is blocking the way. The Euclidean distance between two points can be used:
private function distance(a :Object, b :Object) :Number { return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } private function lineIntersectsCircle(ahead :Vector3D, ahead2 :Vector3D, obstacle :Circle) :Boolean { // the property "center" of the obstacle is a Vector3D. return distance(obstacle.center, ahead) <= obstacle.radius || distance(obstacle.center, ahead2) <= obstacle.radius; } If more than one obstacle is blocking the way, then the closest one (the “most threatening”) is selected for calculation:
The closest obstacle (most threatening) is selected for calculation.
Calculating the Avoidance Force
The avoidance force must push the character away from the obstacle, allowing it to dodge the sphere. It can be done using a vector formed by using the center of the sphere (which is a position vector) and the ahead vector. We calculate this avoidance force as follows:
avoidance_force = ahead - obstacle_center avoidance_force = normalize(avoidance_force) * MAX_AVOID_FORCE
After avoidance_force is calculated it is normalized and scaled by MAX_AVOID_FORCE, which is a number used to define the avoidance_force length. The greater MAX_AVOID_FORCE is, the stronger is the avoidance force pushing the character away from the obstacle.
Avoidance force calculation. The dashed orange line shows the path the character will take to avoid the obstacle. Tip: The position of any entity can be described as a vector, so they can be used in calculations with other vectors and forces.
Avoiding the Obstacle
The final implementation for the collisionAvoidance() method, which returns the avoidance force, is:
private function collisionAvoidance() :Vector3D { ahead = ...; // calculate the ahead vector ahead2 = ...; // calculate the ahead2 vector 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); // nullify the avoidance force } 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" is the character's current 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 previously explained, all steering forces can be combined into one, producing a force that represents all active behavior acting on the character.
Depending on the avoidance force angle and direction it will not interrupt other steering forces, such as seek or wander. The avoidance force is added to the player velocity as usual:
steering = nothing(); // the null vector, meaning "zero force magnitude" steering = steering + seek(); // assuming the character is seeking something 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 re-calculated every game update, the avoidance force will remain active as long as the obstacle is blocking the way.
As soon as the obstacle is not intercepting the ahead vector line, the avoidance force will become null (no effect) or it will be re-calculated to avoid the new threatening obstacle. The result is a character that is able to avoid obstacles:
Move the mouse cursor. Click to show forces.
Improving Collision Detection
The current implementation has two problems, both related to the collision detection. The first one happens when the ahead vectors are outside the obstacle sphere, but the character is too close to (or inside) the obstacle.
If that happens, the character will touch (or enter) the obstacle, skipping the avoidance process because no collision was detected:
Sometimes the
ahead vectors are outside the obstacle, but the character is inside. This problem can be fixed by adding a third vector to the collision check: the character’s position vector. The use of three vectors greatly improves the collision detection.
The second problem happens when the character is close to the obstacle, steering away from it. Sometimes the maneuvering will cause a collision, even though the character is just rotating to face another direction:
Maneuvering might cause a collision, even though the character is just rotating.
That problem can be fixed by scaling the ahead vectors according to the character’s current velocity. The code to calculate the ahead vector, for instance, is changed to:
dynamic_length = length(velocity) / MAX_VELOCITY ahead = position + normalize(velocity) * dynamic_length
The variable dynamic_length will range from 0 to 1. When the character is moving at full speed, dynamic_length is 1; when the character is slowing down or accelerating, dynamic_length is 0 or greater (e.g. 0.5).
As a consequence, if the character is just maneuvering without moving, dynamic_length tends to zero, producing a null ahead vector, which has no collisions.
Below is the result with these improvements:
Move the mouse cursor. Click to show forces.
Demo: It’s Zombie Time!
In order to demonstrate the collision avoidance behavior in action, I think a horde of zombies is the perfect fit. Below is a demo showing several zombies (with different velocities) seeking the mouse cursor. Art by SpicyPixel and Clint Bellanger, from OpenGameArt.
Move the mouse cursor. Click to show forces.
Conclusion
The collision avoidance behavior allows any character to dodge obstacles in the environment. Since all steering forces are re-calculated every game update, the characters seamlessly interact with different obstacles, always analyzing the most threatening one (the closest).
Even though this behavior is not a path finding algorithm, the results achieved are quite convincing for crowded maps.
Entradas
No hay comentarios:
Publicar un comentario