() translation by (you can also view the original English article)
La navegacion decente de NPCs (Personajes no Jugables) frecuentemente requiere la habilidad de evitar obstáculos. Este tutorial cubre el comportamiento del volante para evitar colisiones, lo cual permite a los personajes esquivar con gracia cualquier número de obstáculos en el ambiente.
Aunque este tutorial se ha escrito usando AS3 y Flash, deberías ser capaz de usar las mismas técnicas y conceptos en casi cualquier ambiente de desarrollo de juegos. Debes tener un entendimiento básico de vectores matemáticos.
Introducción
La idea básica detrás de evitar la colisión es generar una fuerza de dirección para evitar obstáculos cada vez que uno está lo suficientemente cerca para bloquear el paso. Aún si el ambiente tiene varios obstáculos, este comportamiento usará uno de ellos a la vez para calcular la fuerza de evasión.
Sólo los obstáculos enfrente del personaje son analizados: el más cercano, el cual se considera más amenazante, se selecciona para evaluación. Como resultado, el personaje es capaz de esquivar todos los obstáculos en el área, haciendo la transición de uno a otro elegante e impecablemente.
Los obstáculos frente al personaje son analizados y el más cercano (el más amenazador) se selecciona.
El comportamiento de evasión no es un algoritmo para encontrar un camino. Hará que los personajes se muevan a través del ambiente, evitando obstáculos, eventualmente encontrando una ruta la cual tomar para atravesar los bloques - pero no funciona muy bien con obstáculos "L" o "T", por ejemplo.
Viendo al frente
El primer paso para evitar obstáculos en el ambiente es percibirlos. Los únicos obstáculos de los cuales el personaje se tiene que preocupar son los que están frente a él y que bloquean la ruta directamente.
Cómo se explicó antes, el vector de velocidad describe la dirección del personaje. Se usará para producir un nuevo vector llamado ahead, el cual es una copía del vector de velocidad, pero con una extensión diferente.
El vector
ahead es la línea de visión del personaje.Este vector se calcula de la siguiente manera:
1 |
|
2 |
ahead = position + normalize(velocity) * MAX_SEE_AHEAD |
El largo del vector ahead (ajustado con MAX_SEE_AHEAD) define cuan lejos el personaje "verá".
A mayor MAX_SEE_AHEAD, más rápido el personaje comenzará a actuar para evadir un obstáculo porque se percibirá como una amenaza aunque se encuentre lejos:
Mientras más grande sea la distancia al frente, más antes el personaje comenzará a actuar para evadir un obstáculo.
Verificando si hay Riesgo de Colisión
Para verificar si hay riesgos de colisión, cada obstáculo (o su caja limitante) debe ser descrita como una forma geométrica. Usar una esfera (un círculo en dos dimensiones) da el mejor resultado, asi que cada obstáculo en el ambiente será descrito como tal.
Una solución posible para ver si hay riesgo de colisión esla intersección línea-esfera – la línea es el vector ahead y la esfera es el obstáculo. Ese planteamiento funciona, pero voy a usar una simplificación de él, lo cual es más fácil de entender y tiene resultados similares (a veces aúnmejores).
El vector ahead se usará para producir otro vector con la mitad de su longitud.
La misma dirección, la mitad de la longitud.
El vector ahead2 se calcula exáctamente como ahead, pero su longitud se corta a la mitad.
1 |
|
2 |
ahead = position + normalize(velocity) * MAX_SEE_AHEAD |
3 |
ahead2 = position + normalize(velocity) * MAX_SEE_AHEAD * 0.5 |
Queremos llevar a cabo una revisión de colisión para probar si alguno de esos dos vectores se encuentran dentro de la esfera obstáculo. Eso se logra fácilmente al comparar la distancia entre el final del vector y el centro de la esfera.
Si la distancia es menor o igual al radio de la esfera, entonces el vector está dentro de la esfera y se encontró una colisión:
El vector ahead está interceptando el obstáculo si d < r. El vector ahead2 fue omitido para claridad.
Si cualquiera de los dos vectores ahead están dentro de la esfera del obstáculo entonces ese obstáculo está bloqueando el camino. La distancia Euclideana entre dos puntos puede ser usada:
1 |
|
2 |
private function distance(a :Object, b :Object) :Number { |
3 |
return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); |
4 |
}
|
5 |
|
6 |
private function lineIntersectsCircle(ahead :Vector3D, ahead2 :Vector3D, obstacle :Circle) :Boolean { |
7 |
// the property "center" of the obstacle is a Vector3D.
|
8 |
return distance(obstacle.center, ahead) <= obstacle.radius || distance(obstacle.center, ahead2) <= obstacle.radius; |
9 |
}
|
Si más de un obstáculo bloquea el camino, entonces el más cercano (el "más amenazador") se selecciona para hacer el cálculo:
El obstáculo más cercano (el más amenazador) se selecciona para hacer el cálculo:
Calculando la Fuerza de Evasión
La fuerza de evasión debe presionar al personaje lejos del obstáculo, permitiendole esquivar la esfera. Se puede hacer usando un vector formado al usar el centro de la esfera (el cual es un vector de posición) y el vector ahead. Calculamos esta fuerza de evasión de la siguiente manera:
1 |
|
2 |
avoidance_force = ahead - obstacle_center |
3 |
avoidance_force = normalize(avoidance_force) * MAX_AVOID_FORCE |
Después que la avoidance_force es calculada, se normaliza y se escala por MAX_AVOID_FORCE, el cual es un número usado para definir la longitud de la avoidance_force. A mayor MAX_AVOID_FORCE, más fuerte presiona la fuerza de evasión al personaje lejos del obstáculo.
Cálculo de fuerza de evasión. La línea anaranjada punteada muestra la trayectoria que el personaje tomará para evitar el obstáculo.
Evitando el Obstáculo
La implementación final para el método collisionAvoidance( ), el cual regresa la fuerza de evasión, es:
1 |
|
2 |
private function collisionAvoidance() :Vector3D { |
3 |
ahead = ...; // calculate the ahead vector |
4 |
ahead2 = ...; // calculate the ahead2 vector |
5 |
|
6 |
var mostThreatening :Obstacle = findMostThreateningObstacle(); |
7 |
var avoidance :Vector3D = new Vector3D(0, 0, 0); |
8 |
|
9 |
if (mostThreatening != null) { |
10 |
avoidance.x = ahead.x - mostThreatening.center.x; |
11 |
avoidance.y = ahead.y - mostThreatening.center.y; |
12 |
|
13 |
avoidance.normalize(); |
14 |
avoidance.scaleBy(MAX_AVOID_FORCE); |
15 |
} else { |
16 |
avoidance.scaleBy(0); // nullify the avoidance force |
17 |
}
|
18 |
|
19 |
return avoidance; |
20 |
}
|
21 |
|
22 |
private function findMostThreateningObstacle() :Obstacle { |
23 |
var mostThreatening :Obstacle = null; |
24 |
|
25 |
for (var i:int = 0; i < Game.instance.obstacles.length; i++) { |
26 |
var obstacle :Obstacle = Game.instance.obstacles[i]; |
27 |
var collision :Boolean = lineIntersecsCircle(ahead, ahead2, obstacle); |
28 |
|
29 |
// "position" is the character's current position
|
30 |
if (collision && (mostThreatening == null || distance(position, obstacle) < distance(position, mostThreatening))) { |
31 |
mostThreatening = obstacle; |
32 |
}
|
33 |
}
|
34 |
return mostThreatening; |
35 |
}
|
La fuerza de evasión debe ser agregada a la velocidad del vector del personaje. Como se explicó previamente, todas las fuerzas de dirección pueden ser combinadas en una, produciendo una fuerza que representa todo el comportamiento activo en el personaje.
Dependiendo del ángulo de la fuerza de evasión y la dirección, no interrumpirá otras fuerzas de dirección, tales como buscar y alejarse. La fuerza de evasión es agregada a la velocidad del jugador como es usual:
1 |
|
2 |
steering = nothing(); // the null vector, meaning "zero force magnitude" |
3 |
steering = steering + seek(); // assuming the character is seeking something |
4 |
steering = steering + collisionAvoidance(); |
5 |
|
6 |
steering = truncate (steering, max_force) |
7 |
steering = steering / mass |
8 |
|
9 |
velocity = truncate (velocity + steering, max_speed) |
10 |
position = position + velocity |
Ya que todos los comportamientos de manejo son recalculados en cada actualización del juego, la fuerza de evasión se mantendrá activa siempre y cuando el obstáculo bloquee el camino.
Tan pronto como el obstáculo no intercepte la línea del vector ahead, la fuerza de evasión se volverá nula (sin efecto) o se recalculará para evitar el nuevo obstáculo amenazante. El resultado es un personaje que es capaz de evitar los obstáculos.
Mueve el cursor del ratón. Haz clic para ver las fuerzas.
Mejorando la Detección de Colisión
La implementación actual tiene dos problemas, ambos relacionados a la detección de colisión. El primero sucede cuando los vectores ahead están fuera de la esfera obstáculo, pero el personaje está demasiado cerca (o dentro) del obstáculo.
Si eso sucede, el personaje tocará (o entrará) al obstáculo, saltandose el proceso de evasión porque no se detectó una colisión.
A veces los vectores
ahead están fuera del obstáculo, pero el personaje está dentro.El problema se puede corregir al agregar un tercer vector al control de colisión: el vector de posición del personaje. El uso de tres vectores mejora ampliamente la detección de colisión.
El segundo problema sucede cuando el personaje se encuentra cerca del obstáculo, alejandose de él. A veces maniobrar causará una colisión, aunque el personaje solamente está rotando para ver en otra dirección.
El maniobrar podría causar una colisión aunque el personaje solamente esté rotando.
Ese problema puede ser arreglado al llevar a escala los vectores aheadde acuerdo a la velocidad actual del personaje. El código para calcular el vector ahead, por ejemplo, se cambia a:
1 |
|
2 |
dynamic_length = length(velocity) / MAX_VELOCITY |
3 |
ahead = position + normalize(velocity) * dynamic_length |
La variable dynamic_length variará de 0 a 1. Cuando el personaje se mueve a velocidad máxima, la dynamic_length es 1; cuando el personaje está disminuyendo la velocidad o acelerando, la dynamic_length is 0 o mayor (por ejemplo 0.5)
Como consecuencia, si el personaje está simplemente maniobrando sin moverse, la dynamic_length tiende a zero, produciendo un vector ahead nulo, el cual no tiene colisiones.
Abajo está el resultado con estas mejoras:
Mueve el cursor del ratón. Haz clic para ver las fuerzas.
Demo: ¡Es Hora de los Zombies!
Para mostrar el comportamiento de evasión de colisión en acción, creo que una horda de zombies es el ejemplo perfecto. Abajo hay un demo que muestra varios zombies (con velocidades diferentes) buscando el cursor del ratón. El arte es de SpicyPixel y Clint Bellanger, de OpenGameArt.
Mueve el cursor del ratón. Haz clic para ver las fuerzas.
Conclusión
El comportamiento de evasión de colisión le permite a cualquier personaje esquivar obstáculos en el ambiente. Ya que todas las fuerzas de conducción son recalculadas en cada actualización del juego, los personajes interactuan implecablemente con cada obstáculo, siempre analizando los más amenazadores (los más cercanos).
Aunque este comportamiento no es un algoritmo para encontrar el camino, los resultados alcanzados son bastante convincentes para mapas abarrotados.
