IA - Búsqueda de caminos en juegos - Parte 2

Continuando con la entrada anterior, en la que veíamos el inicio de la búsqueda de caminos en juegos. Comenzamos viendo el primer problema que se plantea en la búsqueda de caminos: representación del mapa. Después de ver las representaciones más sencillas como pueden ser mediante Grids o Hexágonos, en esta entrada pasamos a ver otras formas de representación más avanzadas que pueden ser utilizadas.

En esta entrada veremos las siguientes formas de representación:

• Puntos de visibilidad
• Incluyendo Waypoints
• Dominios de Dirichlet
• Navmesh
• Jerarquica

Estos son los métodos que podemos encontrar en la representación, podremos observar como la representación que elijamos puede perder optimalidad y naturalidad de las rutas de los personajes.

Puntos de Visibilidad

Está técnica consiste en definir puntos en las distintas "esquinas" que podemos tener en nuestro mapa. A continuación se deberá unir cada uno de estos puntos con los puntos que tiene a la vista. Es decir, reducimos todo nuestro mapa, a un conjunto reducido de puntos y uniones. Teniendo que realizar un algoritmo para la visibilidad, para ello tengo que ver la visibilidad de cada uno de los puntos con todos los demás.

Sin embargo, vemos que existen puntos que no tenemos en nuestra representación (casi todos). ¿Qué ocurre si me encuentro en una posición que no es un punto de visibilidad y quiero ir a otra posición que tampoco lo es? Está pregunta se dará casi siempre, debido a que lo extraño es que estemos y vayamos a puntos de visibilidad. La resolución es sencilla, debemos agregar los puntos de salida y destino como si fueran puntos de visibilidad, calcular la visibilidad con el resto de puntos y realizar la ruta.

Sin embargo, podemos ver una perdida en cuanto a lo optimo qué es el camino. Esto no debería ser un problema, pero vemos como los movimientos no son naturales, yendo a esquinas que no sería necesario pasar por ello y lo que haría tener un personaje con movimientos muy poco realistas. Esto se podría solucionar con algoritmos como string pulling. Un camino más lógico (natural) sería el siguiente:

Este problema, es un problema muy importante planteado por los puntos de visibilidad. Debido a ello se pensó en una posible solución: Los waypoints. Esto consiste en definir los puntos (Waypoints) que deseamos almacenar previamente. Con un buen diseño de waypoints podemos ganar más naturalidad. Ejemplo de waypoints en el mapa anterior:

En resumen: todos los cálculos de visibilidad, uniones entre puntos, etc son preprocesados en ambas técnicas por lo que no es un problema (no lo realizamos durante el juego). Además, reducimos el coste de memoria debido a que tan solo almacenamos unos pocos puntos, y los cálculos durante el juego (rutas) son muy rápidos. Sin embargo, con estos algoritmos perdemos mucha naturalidad de movimientos.

Dominios de Dirichlet

En los dominios de Dirichlet se definen unos puntos especiales (como si fueran Waypoints). A partir de estos puntos se generan zonas, estas zonas se definen mediante cercanía a cada uno de estos puntos especiales. Es decir, generaremos regiones de Voronoi.

Está es una representación que posee problemas a la hora del intercambio entre subgrafos (zonas). Es decir, a menudo se suele definir un punto de intercambio entre zonas  dado por la recta que une los puntos de definición de la zona. Es por ello que los intercambios entre zona pueden parecer muy poco natruales, iendo siempre a pasar por el mismo sitio.

Navmesh

Esta es la técnica de representación más utilizada, por lo que resultará más sencilla encontrar información al respecto, por lo que no me centraré demasiado en este punto (más información). 

Mediante la técnica de Navmesh en el mapa definiremos una serie de polígonos convexos que contendrán todo nuestro mapa exceptuando los obstáculos. Es obligatorio dejar los obstáculos fuera.  

Este método simplificará la búsqueda de caminos, pues se reducirá la lista de puntos a las conexiones entre los polígonos. De está forma el movimiento es más natural y fluido.

Fuente: http://udn.epicgames.com/Three/NavigationMeshReference.html

Como se puede comprobar el movimiento es más recto y natural que mediante Waypoints. Además dejando los obstáculos fuera conseguimos evitar que estos aparezcan en las búsquedas de caminos y nos ahorren tiempo y memoria.

En caso de que tengamos un mapa por el que movernos en 3D la representación mediante Navmesh sigue siendo posible, se pueden definir los polígonos en diferentes orientaciones, etc. También es muy probable que en diferentes juegos nos encontremos como los polígonos son definidos por cambios de material, por ejemplo al pasar de un camino a la hierba. El camino y la hierba también tendrán polígonos, pero se podrá reconocer como existe una división definida entre los tipos de materiales.

Jerarquía

Realmente la jerarquía nos ayuda a aunar todo lo que tengamos hasta ahora en mapas más grandes. Para ella lo que tenemos es una resolución de la búsqueda de forma jerárquica. ¿En qué consiste esto? En dividir nuestros mapas de forma que tengamos diferentes zonas diferentes. Por ejemplo, tengo un juego con 2 ciudades que estarán en la cima de la jerarquía, a continuación tendremos las zonas principales de la ciudad, seguida de los barrios, las calles, las casas, las habitaciones. Con esto conseguimos ir resolviendo nuestra búsqueda paso a paso, si estoy en una habitación y quiero ir a la otra ciudad resolveré primero la salida de la habitación, de la casa, el barrio, la zona y el cambio de ciudad. De esta forma hemos dividido jerárquicamente nuestra búsqueda en búsquedas más localizadas y pequeñas. Con esto si yo necesitase simplemente moverme de una habitación a otra no tendría en cuenta nada más que búsqueda en habitación y casa, sin necesidad de cargar el resto de problemas. 

Esto es todo lo que respecta la representación de los mapas para realizar búsquedas de caminos. Con esto hemos conseguido abordar el primer problema que se planteaba: la representación. En siguientes entradas se abordarán los diferentes algoritmos que tenemos a nuestra disposición para realizar las búsquedas. Es decir, abordaremos por fin el problema de búsqueda.