miércoles, 18 de junio de 2014

Pathfinding en Boo & Marung (I)

Este artículo es más técnico que otros. Avisaré de esta característica al principio de cada entrada.

En Boo & Marung se hace un uso intensivo de un algoritmo de pathfinding. Se trata de una implementación del algoritmo A*, concretamente del algorítmico que encontré en la versión inglesa de Wikipedia. No quise buscar más.



La forma en que los actores (como yo los llamo) hacen uso de esto en las escenas y en sus estados requeriría otra entrada. Aquí sólo hablaré de aspectos más relacionados con el algoritmo en sí y con la representación del espacio del juego para este fin.

La acción de encontrar un camino en el laberinto que conforman los bloques de cada nivel, lo llamé "pacificar", derivada de path, en su acepción de ruta, que en inglés de mi barrio se pronuncia como "paz". Pues eso, se trataba de encontrar la paz... Jajajaja...
(¬ _¬)


Los preparativos

Lo primero fue construir estructuras de datos adecuadas para la representación del grafo.
Desarrollé Boo & Marung sin motores ni librerías de terceros, todo desde cero, con la lógica excepción de las librerías estándar más básicas de Java y Android. En las de esta plataforma encontré una interesante estructura para guardar pares clave-valor llamada SparseArray, que es más eficiente que HashMap cuando la clave es un entero. La utilicé para representar listas de nodos y arcos.

A partir de ahí construí interfaces y clases que culminaron con la clase Grafo. La representación básica consistió en una lista de nodos, cada uno con otra lista de semiarcos, que es como llamé a cada par nodo-coste al que estaba ligado un nodo concreto.

Aunque quizá no sea lo más acertado, la misma clase Grafo implementa el algoritmo que devuelve la lista de nodos para llegar de un nodo a otro con el menor coste posible.

Como curiosidad decir que la implementación recursiva del paso final que ordena los nodos que forman el camino, resultó más rápida que una versión iterativa para el tamaño medio de los grafos.

Otro ejemplo de búsqueda de eficiencia que resultó infructuosa, fue que comencé implementado como heurística la distancia Manhattan. Esto no sólo introducía un margen de error apreciable, sino que no merecía en absoluto la pena porque el ahorro computacional era ínfimo. Acabé implementando sin más complicaciones el cálculo de la distancia real tirando de la raíz cuadrada que aún sigue siendo tan temida por algunos.


Representación del espacio del juego

El verdadero problema era la representación del espacio de juego, o más bien su traducción como grafo. ¿Qué eran los nodos y qué eran los arcos en el espacio del juego?


La imagen anterior da una pista sobre los candidatos a ser nodos gracias a que en este nivel se aprecia la "cuadrícula": los candidatos son las casillas en las que se divide.

No quiero profundizar en esta idea ahora pero no toda la resolución de un juego tiene que ser la misma para todos sus aspectos. En Boo & Marung los actores se mueven en transiciones suaves y en este sentido la resolución es la de la pantalla, pero el cálculo de las rutas tiene menos resolución.

He hablado de "candidatos" porque no todas las casillas serán un nodo del grafo, sólo algunas pocas. He visto enfoques en libros y foros que no me han gustado. En esas representaciones el grafo es una bestialidad de nodos y arcos porque casi que cada punto libre del juego se trata como un nodo. En Boo & Marung no sólo se reduce el número de posibles nodos al cuadricular el espacio en celdas, sino que al cargar cada nivel se determinan las celdas realmente útiles para ser los nodos del grafo.

A partir de aquí llamaré "mapa" al espacio del juego, al escenario, y "celda" a sus casillas.

Las celdas útiles son las que permiten bordear cualquier obstáculo. Como en este juego todos los obstáculos se componen de rectángulos (realmente cuadrados), es fácil determinar que esas celdas son las que hay en las esquinas. Las geometrías de otros juegos pueden requerir otros métodos.

En esta imagen vemos un ejemplo de mapa con obstáculos:


Como hemos dicho, no todas las celdas serán nodos del grafo sino sólo las esquinas, marcadas en azul:


Se puede observar que las esquinas de algunas formas coinciden con las de otras, esas esquinas sólo cuentan como un nodo. Otras quedan fuera del mapa y podemos ignorarlas.

Ya tenemos los nodos de nuestro grafo. Podremos sortear los obstáculos gracias a estos nodos porque cualquier celda del mapa es accesible desde alguno de ellos, y cualquier nodo es visible desde algún otro.

Ahora nos falta determinar los arcos. Para ello hice un algoritmo que llamo "de conectividad" y del que hablaré específicamente más adelante. Por ahora nos vale con saber que ese algoritmo dice si entre dos celdas hay un segmento de recta que no toca a ningún bloque.

Este sería el arco válido que conecta dos nodos, proyectado sobre el mapa.


No es una recta, realmente, como la que se aprecia en la imagen, si la mostramos así es por simplificar el dibujo. La verdadera recta, siempre que sea oblicua, la ensanchamos haciéndole una especie de antialiasing porque no nos basta con que los nodos sean conectables, sino que además el actor debe caber por ese "pasillo". Es un ensanchamiento muy generoso porque exige caminos muy anchos, pero por la propia geometría del juego no es ningún problema y nos permite una implementación fácil. En el siguiente ejemplo vemos un arco que no es válido, puesto que una de las X que representan el ensanchamiento de la línea toca un bloque:


Esta sería la configuración completa del grafo:


Los arcos son bidireccionales por lo que en realidad hay dos para cada pareja de nodos conectados, un arco en cada sentido. No he querido resaltar ese aspecto en los dibujos para no sobrecargarlos más. También en los dibujos hay arcos que se han pintado encima de otros, algo que tampoco he querido diferenciar.

Aún así salen muchos menos nodos y arcos que si hubiésemos considerado todas las celdas libres o si hubiésemos seguido otros métodos de interpretación del espacio. No es la solución óptima, estoy seguro, pero sí es razonablemente optimal.

Realmente el algoritmo de conectividad devuelve la distancia entre dos celdas o -1 si las celdas no son conectables con los criterios que manejamos. Esto nos permite determinar si dos celdas son conectables y al mismo tiempo nos proporciona la distancia para asignarle ese coste al arco.

El algoritmo de conectividad además facilita el no tener que usar el algoritmo de pathfinding, porque la primera comprobación entre un origen y un destino dados, es si son directamente conectables. En caso afirmativo ya tenemos el camino: una línea recta. Este subproblema de recorrer una línea recta, ya sea para ir directamente al destino o para ir de un nodo a otro, lo comentaré más adelante.

En la próxima entrada hablaré también de cómo integrar en el grafo el origen y el destino concretos de un actor, así como de otros aspectos relacionados con el pathfinding de este juego.


No hay comentarios:

Publicar un comentario