Optimización Logística con World of Warcraft y Python
Vamos a aplicar un solver de optimización para resolver un problema de ruteo en el mundo de World of Warcraft.
El World of Warcraft es uno de los juegos online multijugador masivos más jugados de todos los tiempos.
La extensa cantidad de territorio a recorrer, la profunda y desarrollada historia y los detalles en cada rincón, además de su fluida jugabilidad, convirtieron al World of Warcraft en el preferido de varios jugadores durante años.
Elegimos entre varios personajes de distintas razas y clases y avanzamos de nivel, a la vez que nos equipamos cada vez con mejores ítems. Todo esto en un mundo abierto y lleno de otros jugadores.
Existen muchas versiones del juego, pero desde 2019, se reflotó la versión Classic, una mirada al pasado, a la primera década. En ese nos vamos a centrar en esta nota.
Nota: Todo el código listo para ejecutar se puede descargar de mi repositorio Github y está explicado en la sección “Generalización del caso”.
Profesiones de extracción y el problema del viajero
Además de elegir la clase y raza de nuestro personaje, existen profesiones con las que podremos extraer materiales del entorno o crear nuevos.
Las del primer tipo son las que nos interesan para esta nota. Las profesiones de extracción son la minería y la herboristería.
Con la primera podemos extraer minas de varios metales como el oro, plata, cobre, estaño, entre otros. Luego, usarlos para fundir en lingotes y aprovecharlos por el resto de las profesiones.
Lo mismo sucede con la herboristería; nos permite recolectar plantas del suelo que son útiles para otras profesiones como la Alquimia.
Tanto las minas de metales como las plantas, tienen posiciones fijas en cada uno de los mapas. Existe una probabilidad de que se encuentren o no, en un punto fijado con anterioridad. Una vez extraído, el objeto desaparece temporalmente.
Si pudiéramos conocer la posición fija de alguna planta o metal, podríamos recorrerlos de forma eficiente sin caminar aleatoriamente por el mapa. Y, lo que es mejor, existiría la posibilidad de optimizar un recorrido de exploración.
Obtener esta información, es posible gracias a la web Wowhead, que cuenta con una comunidad que a través de los años recolectó y organizó toneladas de información del juego.
Con Wowhead, por lo tanto, podemos visualizar cada uno de los mapas, con la posición de sus objetos de extracción.
Veamos el ejemplo de Teldrassil, tierra de los Elfos de la Noche. En la siguiente captura de pantalla, elegimos visualizar las coordenadas de las plantas de Flor de Paz, que se encuentran en el suelo, sobre toda la región y están indicadas con pines rojos.
La pregunta es simple:
¿Es posible armar un recorrido óptimo para recolectar Flor de Paz en Teldrassil?
Con recorrido óptimo, nos referemimos a visitar cada uno de los nodos una sola vez, con la menor distancia de viaje total posible.
A este problema, en Investigación Operativa y Optimización Logística, se lo conoce como El Problema del Viajero o TSP.
Es uno de los problemas computacionales más complejos al día de hoy. Además, no existe un algoritmo de resolución que pueda asegurar la mejor solución, es decir, la mínima distancia global, para cualquier problema. Sin embargo, las soluciones provistas por la variedad de algoritmos con los que contamos actualmente, son muy buenas.
En esta nota, vamos a intentar resolver el recorrido de extracción, modelizado como un TSP e implementado en Python.
Herramientas
Para resolver este problema vamos a utilizar Python 3.8.12 con las librerías:
- beautifulsoup4: Web Scraping.
- matplotlib: Visualización.
- numpy: Manipulación y operación con vectores.
- ortools: Investigación operativa y optimización.
- requests: HTTP requests.
- re: Regular Expressions.
Parámetros iniciales: ID de Zona e ID de Objeto
Si bien podríamos tomar como punto de partida el nombre de la región, Teldrassil y el nombre de la entidad, Flor de Paz; en Wowhead pueden existir objetos con el mismo nombre.
Por lo tanto, es mejor comenzar buscando el ID de zona y objeto de lo que queremos optimizar.
Si hacemos una búsqueda en Wowhead, y seleccionamos la entidad buscada, el ID aparecerá sobre la url. Hay que tener en cuenta, que si buscamos en español, la url de búsqueda deberá ser: https://es.classic.wowhead.com/.
Por otro lado, luego de buscar la región deseada, Teldrassil, el ID del mapa aparece claramente indicado en la información de la región.
Por lo tanto, como parámetros iniciales:
id_zona = 141
id_objeto = 1618Web scraping de objetos en Wowhead
Si bien los datos que podemos encontrar manualmente en la web de Wowhead son muy valiosos. Necesitamos extraer esta información para que un código de Python la utilice.
Vamos a usar la librería BeautifulSoup para hacer la extracción de coordenadas de objetos de Wowhead.
En primer lugar, hacemos un request GET con el ID de objeto, en la url: https://classic.wowhead.com/object=<id_objeto>
Dentro de la web están las coordenadas geoespaciales de los objetos, mezcladas con el resto de la información. Usamos la librería Regex para extraer solamente la parte de interés.
El resultado es un objeto de BeautifulSoup que hay que convertir en diccionario de python mediante la librería json.
Además, la estructura contiene las coordenadas de todas las regiones donde podemos extraer la entidad. Dado que ya estamos trabajando con diccionarios, podemos filtrar nuestra región con el ID de zona.
Una muestra parcial del resultado sería la siguiente:
Resolviendo el problema del viajero (TSP) en Python
Existen muchas formas de resolver el TSP con Python. Una de las más eficientes es con la librería Google OR-Tools.
Todo lo que se va a mostrar a partir de ahora, se hizo siguiendo la documentación de la librería; y muchos códigos fueron reformulados a partir del caso de ejemplo.
OR-Tools con python, funciona como un wrapper de C++, que es el lenguaje en donde está implementado el solver. Todos los objetos que utilizamos son intermediarios entre ambos lenguajes y hacen la traducción del problema.
Dadas las coordenadas que obtuvimos en la sección anterior, comenzamos construyendo un objeto RoutingIndexManager que gestiona la posición de los nodos de ruteo y su relación con el problema a resolver.
El objeto manager contiene tres argumentos: número de nodos, que se obtiene de la longitud total de coordenadas; vehículos, que para el TSP es uno solo, ya que es un caso límite de ruteo; y por último, el punto de partida inicial.
A continuación, creamos el modelo de ruteo como un objeto RoutingModel. Su argumento es el manager creado anteriormente.
El TSP que vamos a resolver es simétrico, parte de un grafo completo no direccionado, no contiene ciclos y todos sus nodos se comunican. Algunos de estos supuestos, podemos desafiarlos más adelante, luego de ver el resultado.
Necesitamos obtener una Matriz Nodo-Nodo, que contiene las distancias euclideanas entre todos los nodos del grafo.
La forma más fácil y una de las más eficientes, es utilizar la función euclidean_distances(.), de la librería sklearn. Toma como input la lista de coordenadas y devuelve una matriz cuadrada, simétrica, con las distancias euclideanas en cada elemento.
Para nuestro ejemplo de entidad de Flor de paz en Teldrassil, el resultado sería el siguiente.
Lo próximo será cargarle al objeto de routing que tiene el modelo, la matriz nodo-nodo. Es a través de esta matriz que se puede evaluar la función objetivo, mediante la cual se optimiza la distancia total del recorrido.
En primer lugar, necesitamos crear una función de Callback que pueda invocar a la Matriz Nodo-Nodo, dependiendo de los nodos que esté requiriendo en ese momento el optimizador. Esta función además traduce los indices de nodos del optimizador en nodos de la matriz.
En el bloque siguiente podemos ver la función que devuelve la distancia cada vez que la invoca el optimizador.
El callback que necesita el objeto de routing, solamente permite cargar como input el índice de nodo origen y el índice de nodo destino. Por lo tanto, a través de una función lambda, precargamos el manager y la Matriz Nodo-Nodo, dejando como argumentos de la función los inputs de los índices.
Esta función callback ya está lista para registrase mediante el método RegisterTransitCallback del objeto de routing y luego cargarse con el método SetArcCostEvaluatorOfAllVehicles del mismo objeto.
Y ahora, la parte más esperada: resolver el TSP.
Por último, necesitamos crear una lista de coordenadas de cada nodo ordenadas según el recorrido a seguir. A través del objeto solución que obtuvimos, reconstruimos el recorrido iterando en cada nodo.
Plot de la solución
Para poder mostrar la solución, necesitamos armar un plot que una con una línea recta cada punto ordenado de la ruta.
Primero tenemos que desagregar la lista de coordenadas (x, y), en dos listas separadas con todas las x y todas las y.
Armamos un plot de Matplotlib.
Obtenemos el siguiente gráfico:
No sabemos si es un óptimo global, pero es una solución muy buena, sin cruces de caminos, es decir, limpia.
Sin embargo, es muy confuso visualizar la ruta sin estar ubicados en el mapa de Teldrassil. Es por eso que necesitamos superponer la ruta al mapa de la región.
Recurrimos nuevamente a Wowhead, que contiene una base de todos los mapas del juego. Para traer una imagen dependiendo del ID de zona, lo hacemos con la siguiente función.
En el juego, los puntos de interés como los minerales o las plantas, se muestran con un símbolo muy característico, un pin. Vamos a traer esta imagen, para agregarla al gráfico como el símbolo de cada nodo.
Creamos una función para traer este pin.
Con nuestra función para obtener la imagen del mapa de Wowhead, solicitamos la región de Teldrassil con su ID.
De este mapa, recuperamos sus dimensiones y lo dividimos por un número de DPI (puntos por pulgada).
Con estos datos podemos afectar nuestras coordenadas de Wowhead para que estén a la misma escala que el mapa descargado.
Luego, creamos un objeto de subplots de matplotlib del tamaño de la imagen y ploteamos las coordenadas escaladas.
Obtenemos la imagen de los símbolos de pin de Wowhead con la función obtener_imagen_pin(.). Lo agregamos en el plot para cada nodo del recorrido.
Por último, agregamos la imagen de fondo del mapa y ploteamos.
El resultado final:
Generalización del caso
En el repositorio de Github, el caso está generalizado para poder resolver cualquier objeto y mapa cambiando el id_objeto e id_zona.
Todo el código explicado en las secciones anteriores se encapsuló en las siguientes funciones:
- obtener_coordenadas_wowhead(id_objeto, id_zona) en utils.py hace el Web scraping y retorna las coordenadas del objeto y zona requerida.
- optimizar_recorrido(coordenadas) en tsp_solver.py ejecuta el solver según las coordenadas deseadas y retorna las coordenadas ordenadas en una ruta.
- crear_plot(coordenadas_ordenadas, id_zona) en utils.py muestra el gráfico para visualizar con la ruta sobre el mapa.
Las tres se ejecutan en orden dentro de la funión: obtener_mapa_optimizado(id_objeto, id_zona) del archivo wow_tsp.py.
Por último, al final del archivo wow_tsp.py podemos ingresar cualquier ID de zona (parámetro id_zona) y objeto (parámetro id_objeto). Luego, al ejecutar este archivo se retorna el mapa como popup.
Muestra de varios mapas y objetos
- Mapa: Bosque de Elwynn (ID 12)
- Entidad: Mina de Cobre (ID 1731), recolectado con minería.
- Mapa: Cráter de Un’Goro (ID 490)
- Entidad: Sansam dorado(ID 176583), recolectado con herboristería.
- Mapa: Silithus (ID 1377)
- Entidad: Mina pequeña de torio (ID 324), recolectado con minería.
Limitaciones y posibilidades de mejora
Si bien el resultado del optimizador es excelente, muchas soluciones no son totalmente correctas por los supuestos fijados.
Los caminos entre nodos, no siempre pueden recorrerse en forma recta. A veces, la geografía del mapa impide este tipo de caminos. Veamos el siguiente ejemplo del Mapa Tierras del Interior (ID 47) con Minas de Mitril (ID 2040).
Las líneas rectas, como vimos anteriormente, son el camino sugerido por el optimizador. En rojo, el camino posible, y en amarillo el que geográficamente no se puede completar.
El espacio habilitado para que el jugador explore, es una figura cóncava delimitada por montañas o acantilados. En este caso, las líneas amarillas cortan estos dos accidentes.
Podríamos proponer las siguientes soluciones:
- Penalizar con distancias muy altas los arcos que cortan los accidentes en la Matriz Nodo-Nodo.
- Eliminar arcos del grafo completo del problema.
- O lo que es mejor: posibilitar caminos que no sean rectos para cada arco entre nodos.
Conclusiones
El Ruteo es un tema de optimización que tiene facilidad para adaptarse a múltiples problemas más allá de la logística real.
Todo comienza con una simple inquietud de mejorar un recorrido, y cada propuesta adicional termina en un modelo más preciso que el anterior. Sucede con este y cualquier otro caso de la realidad.
Pudimos ver como un juego como el World of Warcraft puede darnos la excusa perfecta para poner a prueba los algortimos y métodos conocidos de Investigación Operativa.
No es casual que sea de los mejores juegos para explorar técnicas de optimización. Miles de personas desde su salida en 2004, se esforzaron por crear fuentes de información enormes, listas para explotar por herramientas actuales y poderosas, pero simples como Python y su ecosistema.
Por último, es un ejemplo perfecto para enseñar, y para abordar estos temas de forma didáctica y divertida sin recurrir a los clásicos de siempre.
¡Por la Alianza!
