Experimento sobre búsqueda de ruta en 3D y para personajes con diferentes reglas de movimiento

Pretendo programar un juego de construcción de colonias similar a Dwarf Fortress. Desde el principio supe que debía arreglármelas primero para que el sistema calculara las rutas de los agentes de manera fiable, aprovechando los diferentes hilos del procesador, y que generara rutas adecuadas para agentes que pudieran andar, volar, nadar en aguas poco profundas, en aguas profundas, o una combinación de cualquiera de esas posibilidades.

Hace un par de semanas programé una versión sólida de un generador de mapas locales basado en el ruido Perlin. El vídeo recoge el resultado. Ninguna inteligencia artificial involucrada: el personaje lo muevo yo con el teclado numérico.

Sin embargo, tras varios experimentos en los que yo no tenía claro desde un principio cómo proceder, la arquitectura se había vuelto engorrosa. Dediqué varios días a refactorizar la mayoría del código e implementar nuevas clases que representaban abstracciones que antes ni siquiera existían. El bucle actual consiste en lo siguiente:

  • Una clase llamada Inputs gestiona si el usuario ha presionado alguna tecla, ha movido el ratón o pulsado alguno de sus botones. El sistema ejecuta las funciones dependiendo de las relaciones escritas en un archivo json.inputsMapping.png
  • Una clase llamada Display encapsula todo lo relacionado con dibujar los elementos en la pantalla. Aparte de que aislar esas responsabilidades mejora la arquitectura, ya empezaba a ver que pygame se quedaba corto incluso para dibujar el mapa a una velocidad consistente. Pronto deberé averiguar si puedo sustituir todas las referencias a pygame con llamadas a OpenGL.displayMapping.png
  • Si el usuario pulsa la tecla punto, se simula un turno. Sabía desde un principio que para programar una simulación compleja tendría que aislarla y limitar la cantidad de veces que se ejecutaría en un segundo, aunque la simulación acabara aprovechando los diferentes núcleos del procesador.
  • Durante la simulación de un turno, una clase Messenger, encargada de publicar mensajes a su subscriptores, envía el mensaje de update para que todas las clases que deban hacerlo ejecuten su lógica de actualización. Para encapsular este comportamiento tuve que reestructurar por completo cómo representaba una entidad en el programa. Aunque ya conocía la tendencia moderna de representar entidades mediante componentes en vez de como jerarquías de herencias, consideré que para los experimentos simples del principio bastaba con heredar de clases simples como Actor y Personaje. Había programado las casillas del mapa como entidades aparte, pero la necesidad de todos esos objetos de actualizarse y mostrarse en la pantalla evidenciaba que necesitaba reducir la idea de cada entidad a un identificador (en este caso, un UUID), y que una multitud de componentes independientes se encargaran de su funcionalidad. Programé el sistema para que bastara con definir los componentes de cada entidad en un archivo de texto json. Una serie de constructores y factorías compondrían una entidad cuando fuera necesario.

entities.png

  • Una clase llamada ComponentManager se encarga de archivar la relación de identificador y componente en un diccionario. Permite recuperar cualquier componente existente de un identificador concreto sin involucrar al resto de componentes.

componentManager.png

  • Una clase de componentes que reciben el mensaje para actualizarse son los Behavior trees, o árboles de comportamiento. La inteligencia artificial para los agentes modernos se ha reducido a estos árboles o a planning systems (sistemas de planificado), sobre los que no he leído todavía. Pero los árboles de comportamiento encajan de maravilla con la neuroevolución. Algunos de los nodos de un árbol de comportamiento se limitan a decidir qué comportamiento se ejecutará, así que bastaría con crear nodos específicos que cumplieran esa función mediante redes neurales evolucionadas. Los árboles de comportamiento son enrevesados, y a pesar de su aparente simplicidad, decidir su estructura para que reflejen el comportamiento exacto que quieres puede complicarse bastante. Para empezar, decidí que bastara con definir un comportamiento aislado en un archivo json. Una serie de constructores y factorías crearía la red final de objetos. La siguiente es la definición de la inteligencia artificial completa que permite a cada uno de los agentes del siguiente vídeo moverse:

moveToBT.png

  • Refleja el siguiente esquema:

Move_to_destination Behavior.jpg

  • La mayoría de los libros y artículos sobre árboles de comportamiento recomiendan reducir su composición a los selectores básicos: sequencias y fallbacks (o selectores clásicos), aparte de decoradores. La sequencia funciona de la siguiente manera: si el primer hijo falla, la sequencia entera falla y envía el fallo al nivel superior. Si todos sus hijos devuelven que han satisfecho su tarea, la sequencia se considera satisfecha. Los fallback funcionan al revés: si un hijo falla, se prueba el siguiente. Si todos fallan, el fallback falla, pero si alguno de los hijos ha satisfecho su tarea, el fallback se considera satisfecho. Aunque me devané los sesos para componer el árbol de manera que no necesitara repetir ningún nodo, no lo conseguí. Como el diagrama refleja, la lógica considera dos veces si el agente ha terminado de calcular su ruta, y otras dos veces si puede moverse al siguiente punto de la ruta. Pero funciona como está.
  • Este comportamiento tiene poco de inteligente, claro. Sólo refleja una secuencia lógica de acciones para pedir un cálculo de ruta, asegurarse de que haya terminado de calcularse, consumirla y determinar si el agente ha alcanzado su destino. Pero la estructura está dispuesta para implementar comportamientos mucho más complicados.
  • En un principio pretendí ejecutar los árboles de comportamiento en diferentes hilos o procesos, para aliviar el núcleo principal del procesador. Sin embargo, Python es muy peculiar a la hora de tratar los hilos, y para ejecutar cada árbol de comportamiento en un núcleo diferente, el sistema copiaría todo el árbol y las clases involucradas. Si la estructura se limitara a la lógica, no habría mucho problema, pero muchos de esos nodos deben preguntar cosas a diferentes componentes de la entidad, lo que implica tener que copiar el diccionario entero de comportamientos. Podría arreglármelas para aislarlo, pero en el futuro es de esperar que alguno de los nodos debiera mirar dentro del mapa, lo que implicaría copiar el mapa entero a otro proceso. Demasiado pronto para decidirme.
  • Lo que sí implementé fue separar la idea de razonar de la de ejecutar el razonamiento. Los árboles de comportamiento sólo devuelven tareas a ejecutar, y no se encargan de modificar el mundo ni los actores. Cada turno, otra clase dedicada a almacenar tareas y procesarlas las ejecuta como considere oportuno, ya sea en el mismo núcleo o en los hilos disponibles. En el futuro también debería ejecutar tareas en otros procesadores.

tasksScheduler.png

  • Mencionaré que aunque había implementado el algoritmo A* de búsqueda de ruta hace unas semanas, no encontré la manera de incorporar las reglas de movimiento en él, así que tuve que programarlo otra vez desde cero siguiendo otro ejemplo. Pero la versión actual es mucho mejor, y refleja las reglas de movimiento perfectamente.
  • De momento sólo ejecuta fuera del hilo principal los cálculos de ruta, y únicamente en los hilos disponibles. Mis primeros intentos por implementar mediante el multiproceso la búsqueda de ruta fueron descorazonadores: tardaba al menos tres o cuatro segundos en devolver incluso las rutas vacías. No acababa de verle el sentido, pero se debía a que no entendía la diferencia entre hilos y procesos. Los hilos existen en un proceso y usan el mismo espacio de memoria. Pueden acceder a los datos. Si uno de ellos escribe un dato mientras otro hilo intenta leerlo, se producirán inconsistencias, pero para evitar ese problema basta con dividir la ejecución interna de los efectos externos. Sin embargo, yo mandaba calcular la ruta mediante un pool de procesos, para lo que el ordenador debía iniciar el Python en otro núcleo del procesador y copiar todos los datos involucrados. Ahora resulta evidente que sólo las tareas que puedan permitirse tardar varios segundos en devolver un resultado se benefician del multiproceso, pero de todas formas son muchas: por ejemplo, si se quiere procesar la temperatura, la presión del aire, etc., de cada casilla del mapa, o calcular un mapa de amenazas o de visibilidad, o procesar qué pasa en el mundo en general mientras el juego transcurre en el mapa local. En el futuro imagino que podría aprovechar el octree del mapa, que distribuye a los agentes según su cercanía, para ejecutar la inteligencia de los agentes cercanos en hilos, pero procesar la de los demás en otros procesadores.
  • Algunas tareas producen comandos: acciones que modifican a algunos agentes y/o el mapa. En este caso producen la acción de moverse al siguiente punto de su ruta. Como se verá en el vídeo, también gestiona si el siguiente punto de la ruta está bloqueado por otro agente, y en ese caso permitirá volver a buscar una ruta otro par de veces antes de renunciar a ese destino. Una clase se encarga de procesar la cola de comandos ejecutándolos uno tras otro.

El experimento tenía una complejidad añadida: yo quería que convivieran agentes que andaran por el suelo con otros que volaran, nadaran en aguas poco profundas, en profundas, etc. En vistas al futuro, el sistema debería permitir añadir comportamientos como por ejemplo los de un agente que se moviera abriendo túneles en los bloques sólidos de roca, o que nadara en lava. Además, esas capacidades de movimiento deberían poder combinarse: algunos agentes deberían poder volar, nadar y además abrir túneles en roca, por ejemplo. Para ello tuve que abstraer las reglas de movimiento a archivos json.

movementRules.png

La búsqueda de ruta necesitaba conocer las posibles casillas vecinas de cada casilla que consideraba. La accesibilidad de cada casilla dependía del agente que pedía la ruta, así que en un primer momento no se me ocurría otra cosa que calcular los vecinos cada vez que se pedía calcular una ruta. Eso ralentizaba mucho la búsqueda, obviamente. Al final opté por generar cada posible vecino en un diccionario interno del mapa, poco después de generarse al comienzo del experimento. Eso tarda unos ocho segundos, pero no necesitará volver a hacerlo durante el transcurso del experimento o del juego salvo que alguna casilla cambie, y aun así sólo deberán recalcularse los vecinos inmediatos de la casilla que haya cambiado. Esa tarea se puede delegar a un hilo aparte.

Sin embargo, la lógica que genera los vecinos de cada casilla es de lo más complicado que he programado recientemente:

neighbors.png

El resultado se ve en el siguiente vídeo. Hay cuatro tipos diferentes de agentes. Unos andan, y sólo pueden moverse por la tierra (aunque podría incluir sin problemas que nadaran en aguas poco profundas). Otros vuelan, lo que implica que pueden moverse por el aire y por la tierra. Otro agente sólo nada por aguas poco profundas. El último agente nada por aguas poco profundas y por las profundas.

Cuando todo funcionaba ya, he cambiado un par de detalles de la implementación. La búsqueda de ruta se ejecuta en hilos; aunque los hilos funcionan de manera semiindependiente, si a una búsqueda le costaba encontrar el camino, bloqueaba el sistema durante un segundo o algo más. Las búsquedas normales consideran unas veinte, treinta o cincuenta casillas. Algunas raras superan las cien. Pero esas búsquedas que bloqueaban el sistema consideraban hasta mil quinientas o más. Acabé limitando artificialmente la consideración de casillas a unas trescientas. Como resultado, algunos agentes no se moverán a ese destino, pero en el transcurso de un juego podría considerarse razonable: el destino es demasiado complicado como para alcanzarlo desde su punto de origen. La inteligencia artificial lo tendría en cuenta y lo derivaría a otras acciones.

Después de esto me toca refactorizar un poco más el sistema para integrar a la arquitectura los bloques más sólidos del experimento, y luego investigaré cómo trabaja Python con OpenGL y si es factible reemplazar pygame por completo.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s