Explorando algoritmos de búsqueda de caminos para Wall-E

Explorando algoritmos de búsqueda de caminos para Wall-E' can be condensed as 'Explorando algoritmos de búsqueda de caminos para Wall-E'.

La Historia detrás

Hace algunos años, Yandex organizó un concurso llamado Robots Couriers con un premio tentador: un boleto para una conferencia cerrada de conducción autónoma para profesionales. El concurso se parecía a un juego, donde los participantes tenían la tarea de encontrar rutas óptimas en un mapa y optimizar la entrega utilizando mensajeros robóticos.

A medida que profundicé en el tema, descubrí que a pesar de que encontrar rutas es un problema resuelto, seguía siendo de interés para la comunidad profesional de desarrollo de juegos. Entre 2010 y 2020, los ingenieros realizaron optimizaciones significativas en el algoritmo A*, especialmente beneficioso para juegos AAA con mapas masivos. Leer artículos e investigaciones sobre estas optimizaciones fue una experiencia emocionante.

Además, los requisitos del concurso estaban diseñados para permitir una evaluación fácil de las salidas del programa por parte del sistema de prueba del concurso. Como resultado, había poco énfasis en la visualización.

Me resultó intrigante explorar este campo y desarrollar una pequeña aplicación que utiliza algoritmos de grafos bien conocidos para encontrar rutas en un mapa de cuadrícula. Para visualizar mis descubrimientos, utilicé la biblioteca de gráficos SFML.

Objetivo

Este proyecto se basa en uno de mis esfuerzos anteriores, donde demostré que cuatro algoritmos conocidos de búsqueda de caminos (BFS, DFS, Dijkstra y A*) no son fundamentalmente diferentes y pueden implementarse de manera universal. Sin embargo, fue un desafío mostrar diferencias significativas de rendimiento entre estos algoritmos en ese proyecto.

En este artículo, mi objetivo es utilizar datos de prueba mejorados y diseñar algo visualmente emocionante. Si bien la tarea del Concurso de Yandex mencionada anteriormente se alinea bien con mis objetivos, no resolveré su problema específico aquí, ya que depende en gran medida de su sistema de pruebas, que actualmente no está disponible.

En cambio, extraeré ideas generales para los parámetros de entrada de ese concurso y crearé mi propia implementación.

Mundo Imaginario

Imagina una ciudad tecnológicamente avanzada e innovadora donde el futuro llegó hace mucho tiempo. En esta ciudad, la mayoría de los pedidos son entregados por robots mensajeros, y se ha convertido en una rareza que una persona entregue un pedido desde una cafetería. En esta tarea, te invitamos a participar en la búsqueda de rutas óptimas para entregar pedidos de manera eficiente.

Visualicemos la ciudad como un mapa de N × N. Para simplificar, suponemos que cada robot ocupa exactamente una celda y cada celda puede ser transitable o no para los robots. En un paso, un robot puede moverse en cualquiera de las cuatro direcciones cardinales (arriba, abajo, izquierda o derecha) si la celda objetivo está libre.

Y estoy ignorando el resto de mi tarea original: Al comienzo de la prueba, debes mostrar el número de robots que deseas utilizar para entregar los pedidos y sus coordenadas iniciales. La construcción de cada robot costará Costc rublos.

A continuación, se realizarán T iteraciones de la simulación. Una iteración representa un minuto virtual y consta de 60 segundos. En cada iteración, tu programa recibirá el número de nuevos pedidos y, como respuesta, el programa deberá indicar qué acciones realiza cada robot (60 acciones por robot).

Por cada pedido entregado con éxito, recibirás como propina un máximo de (0, MaxTips – DeliveryTime) dólares, donde MaxTips es el número máximo de propinas por pedido, y DeliveryTime es el tiempo desde que apareció el pedido hasta su entrega en segundos.

El número total de puntos que ganas en una prueba se calcula mediante la fórmula TotalTips – R × Costc, donde TotalTips es el número total de propinas obtenidas, R es el número de robots utilizados y Costc es el costo de construir un robot. Los valores de Costc y MaxTips se establecen en cada prueba. Si ganas menos propinas de las que gastaste en hacer robots, tus puntos totales serán 0. También recibirás 0 puntos por la prueba si realizas alguna acción incorrecta.

Entrada

El programa utiliza la entrada estándar para leer los parámetros. Este enfoque nos permite especificar datos de prueba de diversas complejidades utilizando archivos de entrada.

La primera línea de entrada contiene tres números naturales: N (el tamaño del mapa de la ciudad), MaxTips (el número máximo de propinas por pedido) y Costc (el costo de construir un robot). Ignoro tanto los parámetros MaxTips como Costc para mi primera implementación y tal vez los considere en el futuro.

A continuación, cada una de las siguientes N líneas contiene N caracteres que representan el mapa de la ciudad. Cada cadena puede consistir en dos tipos de caracteres:

‘#’ – indica una celda ocupada por un obstáculo.
‘.’ – indica un espacio libre.

Luego, se te proporcionarán dos números naturales: T y D (T ≤ 100,000, D ≤ 10,000,000). T representa el número de iteraciones de interacción y D representa el número total de pedidos.

Salida

Tu tarea es visualizar el mapa y las rutas óptimas utilizando la biblioteca de gráficos SFML.

Modelando los Mapas

Soy fan de los mapas representados como una cuadrícula de celdas. Por lo tanto, prefiero renderizar todos los resultados y mapearlos como una cuadrícula celda por celda.

También existe la opción de ejecutar la búsqueda de rutas directamente en la cuadrícula sin utilizar ninguna estructura de datos adicional (y también he implementado esto con fines de aprendizaje: ver en el código).

Pero debido a una cuadrícula, es fácil representar un mapa como un grafo utilizando una u otra forma. Prefiero usar una lista de adyacencia de celdas para la mayoría de los algoritmos como BFS, Dijkstra y A-Star. Para algoritmos como Bellman-Ford, puede tener sentido utilizar una lista de bordes en lugar de una lista de adyacencia. Es por eso que si exploras el código, encontrarás todo eso, y todos son ejemplos funcionales.

Para dividir la lógica y la responsabilidad, tengo una entidad llamada Navegador que es responsable de ejecutar la búsqueda de rutas de acuerdo con las órdenes y la configuración de tareas que se especifica a través del archivo AppConfig y los archivos de mapa relacionados.

La configuración de la aplicación se ve así:

Ten en cuenta que map_, map__, etc., no son realmente propiedades de configuración. Se ignoran durante la ejecución de la aplicación. Dado que no hay forma de comentar en la parte del archivo JSON, utilizo subrayados en el nombre de la propiedad para que pueda permanecer en el archivo de configuración pero no ser utilizado.

El archivo de mapa se ve así:

25 50 150
#########################
#########################
#########################
###.......#####.......###
###.......#####.......###
###.......#####.......###
###...................###
###.......#####.......###
###.......#####.......###
###...................###
######.###########.######
######.###########.######
######.###########.######
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
######.###########.######
#########################
#########################
#########################
#########################
2 4
2
6 6 4 20

Este es uno de los ejemplos más simples que contiene celdas bloqueadas o no bloqueadas. He preparado muchos ejemplos diferentes de parámetros de entrada y datos de prueba, comenzando desde partes muy pequeñas que te permiten depurar y aprender el código, hasta un gran mapa (de una ciudad real existente) que nos permite medir el rendimiento de un algoritmo de gráficos.

¿Cómo dibujamos los mapas?

Cuando un mapa contiene solo celdas con un estado binario (bloqueadas o no bloqueadas), esto básicamente significa que cualquier borde de un grafo existe o no.

Para encontrar una ruta en el grafo, tenemos que representarlo de manera eficiente. Como en mi publicación anterior, he utilizado una lista de adyacencia con la relación como Vector[IdNodo]->puntos a->Vector[NodosVecinos]:

Curiosamente, cuando exploramos cuadrículas, en realidad no es necesario utilizar grafos en absoluto. Somos capaces de recorrer la cuadrícula utilizando los algoritmos BFS/DFS celda por celda sin pensar en los bordes. Ver el método _GetPathByBFSOnGrid.

Primero, el código de inicialización lee el archivo y lo convierte en la cuadrícula fila por fila y columna por columna:

Luego, crea un grafo real como una lista de adyacencia:

La representación de la cuadrícula es útil para dibujar en la pantalla utilizando la biblioteca SFML. Podemos dibujar creando objetos geométricos (esto es exactamente lo que hago para mapas pequeños):

O podemos hacerlo eficientemente píxel por píxel para mapas más grandes:

Finalmente, veamos cómo se vería un mapa definido por el archivo test_25_xmax.

Originalmente, el archivo definía esto:

Y un mapa renderizado con SFML se vería así:

Porque quería que todo eso fuera controlado por el usuario con el teclado, dejé toda la lógica de comportamiento del usuario en el main.cpp. Me gusta llamarlo lógica del “Controlador”.

La biblioteca SFML facilita mucho el manejo de eventos del teclado:

La idea principal es que los disparadores del usuario (presionar el botón ESPACIO) lean el archivo de mapa y rendericen el mapa, y luego un segundo disparador (segunda presión del botón ESPACIO) cargue la tarea de enrutamiento y calcule la ruta más corta entre dos puntos en el mapa:

Necesitamos ir más profundo

Quería jugar con más algoritmos de grafos, y todos tienen sus limitaciones, así que decidí implementar también mapas de varios colores que pueden ser representados por grafos de múltiples pesos.

Cada celda está coloreada, y el color significa que la arista no solo existe sino que también aplica algún peso (o tarifa, o multa, como quieras llamarlo). Por lo tanto, la arista puede estar bloqueada, medio bloqueada, no bloqueada… ya te haces una idea.

Así que he implementado mapas de varios colores que lucen más alegres y están listos para el juego (ejemplo del archivo test_31_multi_weight_graph_map):

Algunos de los archivos de configuración contienen mapas más complejos de ciudades que realmente existen, como test_29_yandex_weighten_real_map:

Como desafío, ahora debemos manejar mapas con configuraciones muy flexibles. RectangularMap.cpp contiene esencialmente mucha lógica interna, que incluye todos los algoritmos de grafos e incluso más de lo necesario (porque me gusta jugar con las cosas, aunque no sean especialmente útiles por ahora).

He implementado los algoritmos BFS#Línea 598, Dijkstra#Línea 299, A-Star#Línea 356, Bellman-Ford#Línea 428, y varios algoritmos “utilitarios” adicionales como Ordenación Topológica, Camino de una sola fuente, que no son útiles para el estado actual de la aplicación (porque funcionan en Grafos Directamente Acíclicos, que no son el tipo de Grafos que uso actualmente), pero tengo algunas ideas para usarlos en futuras mejoras.

No pulí todo el código y no lo hice lo suficientemente ideal, pero me permite (y espero que te permita a ti) jugar con el código y comparar las métricas de rendimiento.

Disculpa algunas líneas comentadas aquí y allá, tal vez algún código sucio… es una forma de aprender :). Para entender la idea de lo que hay dentro, te recomiendo que revises RectangularMap.h.

También hay algunas características divertidas, como una función de Enfoque que permite renderizar solo una parte particular de un mapa. Cambia el enfoque volviendo a renderizar la parte necesaria utilizando el patrón Observer cuando el usuario presiona los botones PgDown o PgUp. Es bastante fácil mejorar esta función e implementar la funcionalidad de “Zoom”. Tómalo como tarea, si te gusta.

Función de Enfoque con el archivo de mapa test_29_yandex_weighten_real_map en funcionamiento:

El diagrama de clases se ve así:

Ejecuta y juega

Creo que la parte más divertida es simplemente ejecutar esta pequeña aplicación, jugar con variaciones de su configuración y algoritmos. Puedes hacer muchos experimentos utilizando varios archivos de mapa como parámetros de entrada con diferentes datos de prueba, así como cambiando la lógica en el código.

Después de iniciar, debes presionar ESPACIO. La aplicación renderizará un mapa según el archivo de configuración, y tiene mucho sentido comenzar a explorar desde los casos de prueba más simples avanzando hacia los más complejos.

Pulsando ESPACIO una vez más, se ejecutan los algoritmos de enrutamiento y encuentra el camino entre el inicio y el pedido más cercano. Por cierto, aún no está terminado, pero es fácil implementar la lectura de todos los demás pedidos disponibles en los archivos de configuración de mapas y ejecutar la búsqueda de ruta para todos ellos.

Aquí está la ruta encontrada en el mapa definido por el archivo test_18_yandex_super_high_res:

También es capaz de encontrar rutas en los mapas que simulan ciudades existentes, como test_29_yandex_weighten_real_map:

Encontrar rutas eficientes entre dos coordenadas se vuelve desafiante para algoritmos como BFS, pero puede hacerse fácilmente con A-star.

Según las celdas encontradas en los archivos de configuración del mapa, la aplicación tratará el mapa como un grafo ponderado o no ponderado y seleccionará el algoritmo correcto para ello (y también puedes cambiar esto fácilmente). Es fácil ver la diferencia de rendimiento entre BFS y A-Star:

Palabras finales

Con esto, quiero dejarte solo y dejarte jugar con estos ejemplos de código. Espero que te resulte fascinante y aprendas mucho de ello.

¡Manténte al tanto!

Enlaces

Implementación universal de los algoritmos BFS, DFS, Dijkstra y A-Star
JPS+: Más de 100 veces más rápido que A* por Steve Rabin
Optimizaciones y mejoras de A* por Lucho Suaya

Explorando algoritmos de búsqueda de caminos para Wall-E