Trabajos interiores del Sistema de Navegación

Cuando usted quiera mover de manera inteligentes los personajes en su juego (o agentes como son llamados en Círculos AI), usted tiene que resolver dos problemas: cómo razonar acerca del nivelo para encontrar el destino, luego cómo moverse allí. Estos problemas están muy cerca, pero son bastante diferentes en naturaleza. El problema del razonamiento acerca del nivel es más global y estático, en que toma en cuenta la escena entera. Moverse al destino es más local y más dinámico, solo considera la dirección para moverse y cómo prevenir colisiones con otros agentes que se mueven.

Áreas que se pueden caminar

El sistema de navegación necesita su propia data para representar las áreas que se pueden caminar en la escena del juego. Las áreas caminables definen las partes en la escena dónde el agente se puede parar y caminar. En Unity los agentes son descritos como cilindros. El área caminable es construida automáticamente desde la geometría en la escena al probar ubicaciones dónde el agente se puede parar. Luego las ubicaciones son conectadas a una superficie manteniendose arriba de la geometría de la escena. Esta superficie es llamada el navigation mesh (NavMesh para corto).

El NavMesh almacena esta superficie como polígonos convexos. Los polígonos convexos son representaciones útiles, debido que nosotros sabemos que no hay obstrucciones entre cualquier dos puntos dentro de un polígono. En adición a los limites del polígono, nosotros almacenamos información acerca qué polígonos son vecinos de otro. Esto nos permite razonar acerca el área entera dónde se puede caminar.

Encontrando caminos

Para encontrar un camino entre dos ubicaciones en la escena, primero nosotros necesitamos mappear las ubicaciones del inicio y destino a sus polígonos más cercanos. Luego nosotros comenzamos a buscar desde la ubicación de inicio, visitando todos los vecinos hasta que alcancemos el polígono destino. Marcando los polígonos visitados nos permite encontrar la secuencia de polígonos las cuales llevan del inicio al destino. Un algoritmo en común para encontrar un camino es A* (pronunciado “A Star”), el cual Unity es el que usa.

Siguiendo el Camino

La secuencia de polígonos que describen el camino desde el inicio al polígono destino es llamada un corridor. El agente va a alcanzar el destino siempre volteando hacia la siguiente esquina visible del corridor. Si usted tiene un juego simple dónde solamente un agente se mueve en la escena, es bien con encontrar todas las esquinas del corridor en un solo barrido y animar el personaje a que se mueva a lo largo de los segmentos de linea conectando las esquinas.

Cuando se trata con múltiples agentes moviéndose al mismo tiempo, estos necesitan desviarse desde el camino original cuando se eviten el uno con el otro. Intentando corregir tales desviaciones utilizando un camino consistiendo de segmentos de linea pronto se vuelve muy difícil y propicio al error.

Debido a que el movimiento de los agentes en cada frame es bastante pequeño, nosotros podemos utilizar la conectividad de los polígonos para arreglar el corridor en caso de que nosotros necesitemos tomar un detour. Luego nosotros rápidamente encontranmos la siguiente esquina visible para girar hacia ella.

Evitando Obstáculos

La lógico volteando toma la posición de la siguiente esquina y basándose en eso encuentra una dirección deseada y velocidad necesitada para alcanzar el destino. Utilizando la velocidad deseada para mover el agente puede llevar a colisiones con otros agentes.

La evasión de obstáculos escoge una nueva velocidad la cual balancea entre moviéndose a la dirección deseada y previniendo colisiones futuras con otros agentes y bordes del navigation mesh. Unity está utilizando obstáculos de velocidad recíprocas (RVO) para predecir y prevenir colisiones.

Moviendo el Agente

Finalmente después de girar y evitar el obstáculo la velocidad final es calculada. En Unity los agentes son simulados utilizando un modelo dinámico simple, que también toma en cuenta la aceleración para permitir un movimiento más natural y suave.

En esta etapa, puede alimentar la velocidad del agente simulado al sistema de animación para mover el personaje usando el movimiento de la raíz, o deje que el sistema de navegación se encargue de eso.

Una vez el agente ha sido movido utilizando cualquiera de los métodos, la ubicación simulada del agente es movida y restringida al NavMesh. Este pequeño paso es importante para una navegación robusta.

Global y Local

Una de las cosas más importantes para entender acerca de la navegación es la diferencia entre la navegación global y local.

La Navegación Global es utilizada para encontrar el corridor a lo largo del mundo. Encontrar un path a través del mundo es una operación costosa requiriendo un alto poder de procesamiento y memoria.

La lista linea de polígonos describiendo el camino es una estructura de data flexible para los giros, y puede ser ajustada de manera local en la medida que la posición del agente se mueva. La navegación local intentar averiguar cómo moverse de manera eficiente hacia la siguiente esquina sin colisionar con otros agentes o mover objetos.

Dos casos para obstáculos

Muchas aplicaciones de navegación requieren otros tipos de obstáculos en vez de solo otros agentes. Estos pueden ser las cajas usuales y barriles en un juego de disparos, o vehículos. Los obstáculos pueden ser manejados utilizando la evasión de obstáculos locales o un pathfinding (encontrar caminos) global.

Cuando un obstáculos se esté moviendo, es mejor manejado utilizando una evasión de obstáculos locales. De esta manera el agente puede predecir y evitar el obstáculo. Cuando el obstáculo se vuelve estacionario, y puede ser considerado para bloquear el camino de todos los agentes, el obstáculo debería afecta la navegación global, eso es, la navegación del mesh.

Cambiar el NavMesh se llama Carving. El proceso detecta qué partes del obstáculo toca el NavMesh y carves (talla) un hueco al NavMesh. Esto es caro en términos operaciones computacionales, lo cual es otra razón convincente de por qué los obstáculos deberían ser manejados utilizando la evasión de colisiones.

La evasión de colisiones locales a veces pueden ser utilizadas para girar alrededor de obstáculos esparcidos de manera igual también. Debido a que el algoritmo es local, éste solo va a considerar la siguiente colisión inmediata, y puede no girar alrededor de trampas o manejar casos dónde el obstáculo bloquea un camino. Estos casos pueden ser solucionados utilizando carving.

Describiendo Enlaces Off-Mesh

Las conexiones entre los polígonos NavMesh son descritos utilizando enlaces dentro del sistema pathfinding( que encuentra caminos). A veces es necesario dejar el agente navegar a través de lugares los cuales no son caminables, por ejemplo, saltar sobre una reja, o atravesar a través de una puerta cerrada. Estos casos necesitan saber la ubicación de la acción.

Estas acciones pueden ser anotadas utilizando Enlaces Off-mesh (Off-mesh links) que le dice al pathfinder(encuentra caminos) que una ruta existe a través del enlace especificado. Este enlace puede luego ser accedido cuando el siguiente camino, y la acción especial puede ser ejecutada.