La semana pasada, hablamos en nuestro blog sobre los cambios que permitirían a los enemigos (mordientes) no encontrarse, pero esta no fue la única actualización relacionada con los mordientes. Casualmente, las actualizaciones de esta semana incluyeron lo que trabajamos en las últimas semanas: actualizar el sistema de búsqueda de enemigos.
Busca un camino
Cuando una unidad quiere moverse a algún lugar, primero necesita entender cómo llegar allí. En el caso más simple, puedes moverte directamente a la meta, pero a veces surgen obstáculos en el camino: rocas, árboles, nidos enemigos (reproductores), unidades de jugadores. Para allanar el camino, necesitamos decirle a la función del buscador de ruta la posición actual y final, y el buscador de
ruta regresará a nosotros (quizás después de muchas medidas) un
camino que es simplemente un conjunto de puntos de ruta que la unidad debe mover para llegar a destino
Para realizar su trabajo, pathfinder utiliza un algoritmo llamado A * (pronunciado "A star"). En el video se muestra un ejemplo simple de encontrar una ruta usando A *: mordiente quiere encontrar una ruta alrededor de las rocas. La función de búsqueda de ruta comienza a explorar el mapa alrededor del mordedor (el estudio se muestra con puntos blancos). Al principio, trata de ir directamente a la meta, pero tan pronto como llega a los acantilados, "se derrama" en ambas direcciones, tratando de encontrar una posición desde la cual nuevamente sea posible moverse hacia la meta.
El algoritmo en este video se ralentiza para que pueda ver mejor cómo funciona.Cada punto en la animación representa un
nodo . Cada nodo recuerda la distancia desde el inicio de la búsqueda y una estimación de la distancia desde este nodo hasta el objetivo (esta estimación se calcula mediante la
función heurística ). Gracias a la función heurística, A * funciona: dirige el algoritmo en la dirección correcta.
En el caso más simple, esta función es simplemente calcular la distancia en línea recta desde el nodo a la posición de destino: este es el enfoque que utilizamos en Factorio desde el comienzo del desarrollo, y gracias a él, el algoritmo inicialmente se mueve en línea recta. Sin embargo, esta no es la única opción: si la función heurística conociera algunos de los obstáculos, podría dirigir el algoritmo a su alrededor, lo que aceleraría la búsqueda, ya que no tendría que examinar los nodos adicionales. Obviamente, cuanto más inteligente es la heurística, más difícil es implementarla.
Una función heurística simple de estimación de distancia en línea recta es buena para encontrar caminos en distancias relativamente cortas. Nos convenía en versiones anteriores de Factorio: casi siempre los mordedores se movían largas distancias solo porque estaban enojados por la contaminación, y esto no sucedía muy a menudo. Sin embargo, ahora tenemos artillería. La artillería puede disparar fácilmente a un gran número de mordedores en el otro lado de un gran lago (y "agrificarlos"), después de lo cual intentan allanar el camino alrededor del lago. El video a continuación muestra cómo el simple algoritmo A * que usamos anteriormente trata de sortear el lago.
Este video muestra la velocidad del algoritmo en realidad; No se ralentiza.Reducción de bloque
Encontrar un camino es una tarea de larga historia, y existen muchas técnicas para mejorarlo. Algunas de estas técnicas pertenecen a la categoría de
búsqueda de ruta jerárquica : en este caso, el mapa se simplifica al principio, la ruta se ubica en este mapa simplificado, que luego se utiliza para encontrar la ruta real. Repito, hay varias implementaciones específicas de dicha técnica, pero todas requieren simplificación del espacio de búsqueda.
¿Cómo puedes simplificar el mundo de Factorio? Nuestros mapas se generan aleatoriamente y cambian constantemente: colocar y eliminar entidades (por ejemplo, coleccionistas, muros o torretas): esta es probablemente la mecánica más básica de todo el juego. No queremos contar todo el mapa simplificado cada vez que agregamos o eliminamos una entidad. Al mismo tiempo, si simplificamos el mapa de nuevo cada vez que necesitamos encontrar un camino, entonces podemos perder fácilmente toda la ganancia en rendimiento.
Una de las personas con acceso al código fuente del juego (Allaizn) tuvo una idea. que implementé como resultado. Ahora esta idea parece obvia.
El juego se basa en bloques de fichas de 32x32. El proceso de simplificación reemplaza cada bloque con uno o más
nodos abstractos . Dado que nuestro objetivo es mejorar la búsqueda de un camino alrededor de los lagos, podemos ignorar todas las entidades y considerar solo los mosaicos: no puede moverse en el agua, en la tierra sí puede. Separamos cada bloque en
componentes separados. Un componente es un área de mosaico en el que una unidad puede pasar de un mosaico dentro de un componente a cualquier otro mosaico del mismo componente. En la imagen a continuación, el bloque está dividido en dos componentes separados, rojo y verde. Cada uno de estos componentes se convertirá en un nodo abstracto; de hecho, todo el bloque se reduce a dos "puntos".
El pensamiento más importante de Allaizn fue que no necesitamos almacenar un componente para cada mosaico del mapa; solo recuerde los componentes del mosaico a lo largo del perímetro de cada bloque, porque solo estamos interesados en qué otros componentes están conectados (en bloques vecinos) de cada componente, y esto depende solo de las fichas que están en el borde del bloque.
Búsqueda de ruta jerárquica
Entonces, descubrimos cómo simplificar el mapa, pero ¿cómo usar esto para encontrar caminos? Como dije, hay muchas técnicas de búsqueda de rutas jerárquicas. La idea más simple es encontrar la ruta utilizando nodos abstractos desde el principio hasta el objetivo, es decir, la ruta será una lista de los componentes de los bloques que debe visitar. Luego usamos la serie de buenas búsquedas antiguas A * para descubrir específicamente cómo moverse de un componente del bloque a otro.
El problema aquí es que hemos simplificado demasiado el mapa: ¿qué pasa si es imposible moverse de un bloque a otro, porque algunas entidades (por ejemplo, rocas) bloquean el camino? Al reducir bloques, ignoramos todas las entidades, por lo tanto, solo sabemos que los mosaicos entre los bloques están de alguna manera conectados, pero no sabemos absolutamente nada acerca de si es posible moverse de uno a otro.
La solución es utilizar la simplificación simplemente como una "recomendación" para una búsqueda real. En particular, lo usaremos para crear una versión inteligente de la función de búsqueda heurística.
Como resultado, obtuvimos el siguiente esquema: tenemos dos buscadores de ruta: el
buscador de ruta
base , que encuentra la ruta real, y el
buscador de ruta
abstracto , que proporciona la función heurística al buscador de ruta base. Cada vez que el pathfinder base crea un nuevo nodo base, llama a un pathfinder abstracto para obtener una estimación de la distancia al objetivo. El pathfinder abstracto actúa en el orden opuesto: comienza con el objetivo de búsqueda y allana el camino hacia el principio, pasando de un componente del bloque a otro. Cuando una búsqueda abstracta encuentra el bloque y el componente en el que se crea un nuevo nodo base, utiliza la distancia desde el comienzo de la búsqueda abstracta (que, como dije, es la posición objetivo de toda la búsqueda) para calcular una estimación de la distancia desde el nuevo nodo base al objetivo general.
Sin embargo, ejecutar todo el buscador de ruta para cada nodo individual estará lejos de ser rápido, incluso si el buscador de ruta abstracto se mueve de un bloque a otro. Por lo tanto, en su lugar, utilizamos un esquema llamado "Reverse Resumable A *". "Reversa" significa que, como dije anteriormente, se lleva a cabo desde la meta hasta el principio. "Renovable" significa que después de encontrar un bloque que sea interesante para el pathfinder base, guardamos todos sus nodos en la memoria. La próxima vez que el Pathfinder base cree un nuevo nodo y necesite una estimación de distancia, solo miraremos los nodos abstractos guardados de la búsqueda anterior. Al mismo tiempo, existe una alta probabilidad de que el nodo abstracto requerido todavía esté en la memoria (al final, un nodo abstracto cubre la mayor parte del bloque y, a menudo, todo el bloque).
Incluso si el pathfinder base crea un nodo ubicado en un bloque que no está cubierto por ninguno de los nodos abstractos, no necesitamos realizar la búsqueda abstracta completa nuevamente. Una característica conveniente del algoritmo A * es que incluso después de "terminar el trabajo" y encontrar una ruta, continúa la ejecución, explorando los nodos alrededor de los nodos ya estudiados. Y esto es exactamente lo que hacemos si necesitamos una estimación de distancia para un nodo base ubicado en un bloque que aún no está cubierto por la búsqueda abstracta: reanudamos la búsqueda abstracta desde los nodos almacenados en la memoria hasta que se expande al nodo que necesitamos.
El siguiente video muestra un nuevo sistema de búsqueda de rutas en acción. Los círculos azules son nodos abstractos; puntos blancos - búsqueda básica. El pathfinder en el video es mucho más lento que el juego para mostrar cómo funciona. A velocidad normal, toda la búsqueda solo requiere unos pocos tics. Tenga en cuenta que la búsqueda básica, que todavía usa el antiguo algoritmo que siempre usamos, simplemente mágicamente "sabe" cómo moverse alrededor del lago.
Dado que el pathfinder abstracto se usa solo para obtener una estimación heurística de la distancia, la búsqueda básica puede apartarse fácilmente de la ruta propuesta por la búsqueda abstracta. Esto significa que, aunque el esquema de reducción de bloques ignora todas las entidades, el pathfinder básico puede omitirlas casi sin problemas. Debido a que se ignoran las entidades en el proceso de simplificar el mapa, no necesitamos repetirlo cada vez que se agrega o elimina una entidad, es suficiente para cubrir solo las fichas que se han cambiado (por ejemplo, en el caso de un vertedero de basura), lo que ocurre con mucha menos frecuencia que la colocación de entidades.
Además, esto significa que esencialmente usamos el mismo pathfinder que hemos estado usando durante años, solo que la función heurística se ha actualizado. Es decir, este cambio no afectará a muchos otros sistemas, y solo afectará la velocidad de búsqueda.