viernes, 20 de junio de 2014

Pathfinding en Boo & Marung (y II)

Continuamos la entrada anterior y finalizamos la revisión del pathfinding de Boo & Marung, recurriendo de nuevo a detalles más técnicos de lo habitual. Descansaremos de esto en la próxima entrada.


Integración del origen y el destino

Habíamos obtenido un grafo a partir de las esquinas de los bloques que nos permitiría bordear obstáculos aplicando un algoritmo A*. Mostramos de nuevo el grafo proyectado sobre el mapa:


Pero lo normal será que tanto el origen como el destino de un actor no coincidan con estas esquinas. Incluso puede que el actor no esté centrado en una casilla al recibir la orden de desplazarse.

Supongamos primero el caso general. El actor está centrado en una casilla y recibe la orden de desplazarse a un destino, el cual siempre estará centrado en una casilla. En la siguiente imagen el origen es el cuadro verde y el destino el rojo.


Estamos tratando, pues, el caso en el que no se pueda ir directamente de un punto a otro, algo que averiguamos con el algoritmo de conectividad.

Lo que se hace es tratar estas dos celdas como dos nuevos nodos del grafo, en el cual los integramos. El origen sólo tendrá arcos de salida y comprobaremos si puede conectarse a cualquiera de los nodos (esquinas) que ya existen.


Lo mismo hacemos con el destino teniendo en cuenta que sus arcos serán de entrada. En este ejemplo sólo conecta con un nodo esquina.


A esta acción de incluir nuevos nodos en el grafo la llamo integración y a la posterior de quitarlos la llamo desintegración. Podríamos copiar el grafo, integrar los nuevos nodos y luego desechar todo el conjunto en lugar de desintegrar los nodos añadidos, pero por la estrategia que he seguido de minimizar los objetos creados y desechados durante el juego, opté por modificar de nuevo el grafo para dejarlo otra vez sólo con las esquinas, algo que no es muy costoso.

De esta manera tenemos el grafo completo:


El grafo será procesado por el algoritmo A* para devolver la lista ordenada de nodos con el recorrido más corto:


Quiero recalcar que aunque la detección de esquinas y la construcción del grafo principal se hace al cargar cada nivel, la integración y desintegración de orígenes y destinos se hace durante el juego.

Veamos ahora el caso que dejamos pendiente, en el que el actor no está centrado en una casilla, quizá porque se le ordena ir a otro sitio cuando estaba realizando un desplazamiento. Sea de nuevo la casilla verde el origen (descentrada) y la casilla roja el destino:


Calculamos la ruta suponiendo que el actor está centrado en la casilla más cercana, que es la que hay un poco arriba y a la izquierda del origen:


Pero luego, una vez obtenido el resultado, modificamos la primera casilla a visitar según sea lo más apropiado, y siempre teniendo en cuenta que no haya bloques sólidos cercanos que nos impidan ese recorte. En el ejemplo sería más apropiado que la primera casilla del desplazamiento sea la de la arriba a la derecha:


De hecho en Boo & Marung se emplea una heurística algo más anticipativa que hace que el desplazamiento inicial se dirija incluso más a la derecha.

Para cuando estaba implementando todo esto, ya se me había quitado el complejo a la hora de hacer ajustes posteriores a los cálculos teóricos. En los meses que pasaron entre Lucky Rain y el inicio de este juego, me metí entre pecho y espalda libros y artículos de Inteligencia Artificial aplicada a juegos con ejemplos más o menos reales. En todos los casos eran necesarios este tipo de ajustes posteriores.

Una cosa es hacer un ejemplo para explicar un algoritmo de IA y otra es que esa solución tenga que convivir con otros aspectos de un juego real. Esos ajustes posteriores se extendían además a elementos dinámicos, como puertas que se pueden cerrar en cualquier momento, enemigos en la ruta, etc.

Lo importante es que los ajustes no sean costosos y que estén desacoplados del sistema que ajustan, para que así sean fácilmente tratables.

Pues bien, llegados a este punto en el que tenemos una lista de celdas a las que ir desplazándonos en orden, el movimiento en sí de una a otra (el "subproblema" del que hablamos en la entrada anterior) se hace con aritmética de vectores. De alguna forma es la parte inversa al problema inicial. Si partíamos de la necesidad de traducir el espacio del juego a un espacio algebraico en el que calcular la solución más fácilmente, ahora necesitamos traducir esa solución al espacio del juego y aplicarla.

Por mencionar algún aspecto concreto, dado un vector de trayecto de un actor, un método de ese vector como el siguiente lo modificaría para dirigirse del origen al destino en incrementos de "magnitud" (que representaría la velocidad).
public Vector dirigir(Vector vOrigen, Vector vDestino, float magnitud) {
        set(vDestino).restar(vOrigen);
        normalizar().multiplicar(magnitud);
        return this;
}
El trayecto debería aplicarse en cada frame hasta alcanzar el destino. Esto de nuevo necesita ajustes o supervisiones para evitar, por ejemplo, pasarnos si estamos muy cerca del punto final.


El algoritmo de conectividad

Para finalizar, comentaré algo sobre el algoritmo de conectividad. Es muy versátil porque me ayudó a determinar la distancia entre dos celdas, saber si eran conectables (esto es, si no tenían obstáculos entre ellas y había un pasillo suficientemente ancho entre ellas), si un actor tenía a otro a la vista, etc.

La idea es sencilla, se trata de dibujar una línea entre dos celdas pero en unidades de celdas completas. Básicamente es un algoritmo de dibujado de rectas típico de Informática Gráfica.

La novedad para mí es que lo implementé desde cero según mi criterio. Imaginemos que tenemos estas dos celdas para determinar su conectividad:


Primero se obtiene el rectángulo de celdas más pequeño que las abarca:


Determinamos el lado más largo y el más corto para establecer el número de segmentos y la longitud de los mismos que necesitaremos para conectar ambos extremos mediante celdas. En este ejemplo bucólico y pastoril salen tres segmentos de dos celdas cada uno (en otros casos la solución es más irregular). El origen y el destino forman parte del primer y último segmento respectivamente.


Es muy rápido preguntar en las pocas celdas resaltadas si hay una sólida. En cuanto encontremos una dejamos de preguntar puesto que se trata de dos puntos no conectables. Nótese que el algoritmo también ofrece fácilmente una aproximación de la distancia entre los extremos, aunque yo he preferido la distancia real.

Sin embargo, esta solución tal cual podría hacer que se considerasen conectables puntos por cuya ruta de conexión el actor no cabe o por la que sencillamente no puede "ver", como se muestra aquí:


Por ello es necesario ensanchar la recta dentro del rectángulo (no hace falta fuera), a modo de antialiasing, y hacer comprobaciones también en esa ampliación que en la siguiente imagen mostramos con casillas azules.


El dibujo no pretende reproducir exactamente los resultados reales del algoritmo de conectividad, sólo mostrar la idea general en la que se basa. La determinación de las celdas a ampliar se hace por vecindad de las amarillas iniciales.

Si todas las celdas resaltadas están libres, garantizamos que un actor que tuviera que desplazarse de una celda a otra, cabe por esa ruta. Lo mismo si estamos preguntando si un actor orientado hacia otro, puede ver a ese otro. Como dije en la entrada anterior, el ensanchamiento es generoso, puede que demasiado, porque un obstáculo cercano podría invalidar la visibilidad entre dos actores, exigiendo que el espacio entre ellos estuviese ampliamente despejado. Pero este enfoque es razonablemente bueno para los pocos y rápidos cálculos que requiere.

Reitero que siempre necesitaremos hacer ajustes y comprobaciones posteriores durante el desplazamiento para tener en cuenta puertas que se cierran y otros actores.

Todas las operaciones de este algoritmo son muy rápidas de hacer y no tiene muchos pasos, por lo que su empleo es continuo durante el juego con un coste bastante asumible.


Conclusiones

Para mí resulta bonito investigar algoritmos sencillos de Inteligencia Articial que sean razonablemente eficientes para el problema que han de resolver. He aprendido que tras las bases teóricas normalmente hay que aplicar ajustes posteriores. Esos ajustes no sólo suelen ser necesarios, sino que a menudo facilitan el diseño del algoritmo principal, dejando para una fase posterior el tratamiento de casos especiales.

La construcción del grafo para el algoritmo A* mediante las esquinas de los bloques, fue una idea que se me ocurrió hace muchísimos años y que ahora he tenido la oportunidad de comprobar. La implementación del algoritmo de conectividad fue más reciente. Se me ocurrió en un bar mientras asentía a mis acompañantes como un autómata; mi mente estaba en estas ideas que acabé apuntando en una servilleta de papel. Todo esto es una muestra de lo que me gustan esta clase de temas.

Por eso explico así las cosas, dando las ideas básicas más que detallando el código, porque así es como yo quisiera encontrar las claves del desarrollo de videojuegos cuando busco ayuda. (Salvo, claro está, que se trate de un problema de implementación concreto.)

En Boo & Marung lo pasé muy bien haciendo estas cosas aunque hubo momentos en los que temí por mi salud mental por abarcar tantos aspectos diferentes.

Por supuesto, todo es mejorable y estoy abierto a comentarios y críticas, así como a ofrecer más detalles a quien me los pida ;)

Escribo estos artículos porque necesito expresar mi agradecimiento a la comunidad en Internet que tanto me ha ayudado sin saberlo, aportando soluciones en foros que luego son leídas por gente como yo. Esto es una humilde aportación para quien la considere útil y hasta para quien no, porque son caminos que se ahorrará explorar.


No hay comentarios:

Publicar un comentario