Inteligencia artificial para videojuegos/Planificación de rutas

Sabemos que planificar y seguir rutas es un problema presente en una gran variedad de géneros; y para resolverlo se suele usar Dijkstra para varias soluciones pero para soluciones únicas se usa el famoso A* o alguno parecido.

Aunque la clave reside en las heurísticas ultilizas ya que cuanto más precisa sea la estimación, menor será el coste del algoritmo (por nodos). El problema es que a veces nos vemos obligados a usar una heurística no admisible.

Representar el entorno

Antes de aplicar el planificador es necesario la traducción de nuestro entorno tridimensional a un grafo. Esto se hace según varios esquemas de divisíon con las propiedades de cuantificación y localización, generación y por último validez.

• Cuantificación y localización: cómo traduce de posiciones del espacio a nodos y viceversa.
• Generación: cómo divide el espacio en regiones (manual, semiautomática o automáticamente).
• Validez: cómo garantiza que siempre se llega de un punto a otro en regiones conectadas.

Podemos destacar 4 entornos diferentes que son:

Grafo de baldosas:

El escenario puede ser en 3D, pero su estructura no. Relación directa con las coordenadas.

Automática y hasta en tiempo real (es fácil). No suele permitirse bloqueo parcial de baldosas.

Teselación de Dirichlet:

Partición 2D en regiones de puntos que comparten un mismo punto característico más cercano.

Directamente con los puntos característicos. Triangulación de Delaunay o manualmente. Todo revisado empíricamente, no queda otra.

Puntos de visibilidad:

Poner puntos característicos cerca de las esquinas, ya que la ruta óptima siempre pasa por ellas.

Teselación de Dirichlet sobre estos puntos. Dos puntos conectan si se “ven” entre ellos. También toca revisarlo empíricamente todo.

Mallas de navegación:

Se construyen a partir de la geometría del entorno y es el esquema de división más popular hoy día.

Cada polígono (triángulo) del suelo es un nodo. Los polígonos-nodos conectan si comparten lado. Los polígonos del suelo deberían ser revisados.

Suavizado de ruta

Algoritmo que suaviza la ruta quitando algunos de sus puntos. Ayuda usar comportamientos de direccionamiento.

Entornos inteligentes

La filosofía de los “entornos inteligentes” es que sean las zonas del entorno las que influyan sobre el NPC, cuya ruta se dirigirá al que tenga mejor ratio utilidad/distancia. Marcar puntos de salto, zonas de aterrizaje, etc. y en general la mayor parte del marcado del entorno se podría hacer automáticamente aprovechando el algoritmo de preparación para la planificación de rutas (esquema de división).

Planificación jerárquica de rutas

Simplifica la planificación trabajando a varios niveles (de nuevo agrupando nodos). Aunque A* puede planificar rutas de decenas de miles de nodos en un frame, y es fácilmente interrumpible, sigue habiendo desafíos.

Las agrupaciones se conectan usando heurísticas con distancia mínima, máxima o mínima promedio.

Y las rutas a niveles distintos al actual se pueden guardar en memoria, y las rutas de partes prefabricadas del escenario se reutilizan.

Planificación parcial de rutas

A* puede tener varios objetivos, aunque suele evitarse porque no queda muy bien. Si el entorno cambia mucho, se planifica la ruta dinámica (incrementalmente) mediante algoritmos como D* (A* dinámico).

Además de variantes restringidas en memoria como IDA*, MA* o SMA*, hay otras que gastan mucha porque se guardan partes reutilizables de la planificación.

Planificación de rutas en tiempo continuo

D* funciona mejor cuanto menos y más concretos sean los cambios en el entorno. Planificar en tiempo real supone dejar de considerar las posiciones como nodos.
Los nodos serán estados del entorno junto al tiempo que se supone que tarda todo en llegar allí. Primero se crea este grafo dinámico y luego se usa SMA* u otro para resolverlo.

Planificación de rutas con movimientos

La orientación del agente normalmente o se ignora o se trata con comportamientos de direccionamiento pero también se puede adaptar los algoritmos de planificación de rutas para que el agente rote bien.

Ahora hay animaciones permitidas por rangos, las cuales no se pueden forzar porque no quedaría creíble. El grafo ahora incluirá la posición,velocidad y animaciones permitidas; y sobre este se puede ejecutar el A*.

Actualmente los controladores de animación saben hacer “pisadas” y dichas "pisadas" se podrían planificar.

Resumen

Planificar rutas en un videojuego real requiere dominar las heurísticas.

El entorno se puede representar como grafo de baldosas, teselación de Dirichlet, puntos de visibilidad o mallas de navegación.

La planificación jerárquica de rutas agrupa nodos y trabaja a varios niveles.

Si el entorno está en cambio continuo se requiere planificar rutas en tiempo real.

Planificar movimientos trata la orientación.

Realizado por Sergio Juan Higuera Velasco