Conciencia situacional en la búsqueda de caminos

Suponga que tiene que encontrar el camino más corto a través de una mazmorra, donde ciertos pasajes solo se abren después de que se recolectan ciertos artículos, como puertas y llaves cerradas, por ejemplo.

La reacción intestinal normal a las palabras "camino más corto" obviamente sería A *. Pero A * fallaría en dicho entorno, ya que veo muchos problemas que definen una heurística confiable y, además, es muy probable que un nodo tenga que ser visitado varias veces, lo que tampoco es posible en A * convencional y también hacer la heurística más difícil.

Lo que pensé es simplemente buscar un camino desde el comienzo de la mazmorra hasta el final, ignorando las puertas bloqueadas. Después de encontrar este camino, para cada una de las puertas que bloquean nuestro camino, se buscaría y atravesaría un camino adicional en busca de la llave adecuada y de regreso a la puerta, incluso antes de llegar a la puerta. El mismo sistema se usaría para manejar una situación en la que el camino hacia una llave necesaria para abrir una puerta es nuevamente bloqueado por otra puerta, que debe abrirse primero.

Un gran problema que veo con mi solución es que después de encontrar todas las rutas, incluidas las de adquisición de artículos, la distancia total recorrida por el agente podría no ser la más pequeña posible, ya que podría haber otras puertas bloqueadas que están más lejos del objetivo pero tienen su clave apropiada mucho más fácilmente disponible. A * habría descuidado estas puertas en la primera pasada donde las puertas bloqueadas simplemente se ignoran.

Estoy seguro de que no soy el primero en tratar de resolver esto y agradecería alguna información sobre el problema.

La forma de manejar esta situación de manera óptima utilizando A * directo es expandir el espacio de búsqueda. Es decir, imagine que existe una copia separada de la mazmorra para cada combinación de elementos que su personaje podría llevar.

En cada copia de la mazmorra, las puertas que son transitables son exactamente las que se pueden pasar utilizando el conjunto de elementos correspondiente. La única forma de pasar de una copia de mazmorra a otra es pararse en la ubicación de un elemento y recogerlo.

Puede ampliar este truco para incluir otros cambios de estado, como interruptores que pueden abrir y / o cerrar puertas. Incluso podría permitir que el jugador suelte elementos, aunque esto puede complicarse ya que el estado debe incluir la ubicación de cada elemento soltado, aumentando enormemente el espacio de búsqueda potencial.

Una optimización muy útil es precalcular los caminos más cortos desde cada puerta (en realidad, cada lado de cada puerta) y cada elemento a cualquier otra puerta / elemento accesible, suponiendo que todas las puertas estén bloqueadas . Una vez que tenga esas rutas, puede tratar cada una de ellas como un borde ponderado en un gráfico que conecta estas ubicaciones significativas entre sí e ignorar todas las demás ubicaciones.

Por ejemplo, suponga que su mazmorra tiene diez puertas y cinco llaves. Luego habrá 2 * 10 + 5 = 25 ubicaciones significativas, y 2 ^ 5 = 32 combinaciones posibles de elementos, para un total de 25 * 32 = 800 nodos en el espacio de búsqueda completo. Este es un número muy modesto, especialmente dado que es probable que gran parte del espacio de búsqueda sea inalcanzable.

Desde un punto de vista del mundo real: si se dirigía de A a B y encontraba una puerta D en su camino que estaba cerrada, se daría cuenta de que debe encontrar la llave D. Entonces, si su IA es tan desconocida como lo es el humano típico , eso implicaría explorar la clave, que es un conjunto de pequeños pasos de búsqueda de ruta en sí mismo. Por otro lado, es posible que desee que su IA sepa, antes de intentar un camino, que hay una puerta cerrada en esa ruta, y en ese caso probablemente también sepa dónde encontrar la llave.

De cualquier manera, el problema es uno de conectividad en dos niveles. En el nivel "en el suelo", sabes que siempre puedes moverte con seguridad dentro de una zona no dividida ... es decir, sin puertas cerradas. Aquí es donde puede usar su implementación actual de pathfinding A * libremente. (En un ejemplo simplista, podrías ver una zona como una habitación individual. No puedes llegar a ninguna otra habitación sin abrir una puerta. En realidad, podría ser una región completa de tu mazmorra). Esta es la base de tu movimiento de la entidad, pero es un poco como caminar con los ojos bajos, en lugar de inspeccionar el área a su alrededor primero, es probable que camine hacia una farola. O en este caso, una puerta cerrada. Por lo tanto, los mapas a nivel del suelo en los que se ejecuta tu A * deben restringir al jugador al movimiento solo dentro de la zona actual.

A continuación, hay un mapa de nivel superior, que es más de naturaleza topológica que topográfica. Realmente no le importan los detalles sobre el terreno de los obstáculos, etc., solo le importa la conectividad entre zonas. Este mapa topológico tiene conexiones entre zonas pares que actualmente tienen una puerta cerrada entre ellas, ya que muestra la conectividad ideal de todas las zonas en tu mazmorra. En sus bordes, cada uno representando una puerta entre zonas, almacena la llave que aún se necesita, si la hay, para abrir esa puerta, de lo contrario, se considera abierta. Por lo tanto, al buscar en este gráfico la ruta más corta, debe limitar esa ruta encontrada solo a las rutas que ya están abiertas , al verificar los datos en los bordes a medida que se ejecuta la búsqueda. La conectividad aquí no implica apertura, sino que implica apertura potencial.

Cuando desee moverse a un punto que se encuentre dentro de una zona separada, primero busque su mapa de nivel superior para encontrar un camino. (A * o cualquier otro algoritmo de ruta más corta se puede usar en este nivel). Una vez que encuentre una ruta, ese mapa de nivel superior también debe proporcionar información sobre qué puerta debe usar para llegar desde su zona actual a la otra zona. Ahora, en la zona local, puedes hacer IA a nivel del suelo para navegar hacia esa puerta. Una vez que se ha alcanzado la puerta, tu personaje puede pasar por esa puerta / portal. Ahora está en la zona B. Si esta es la zona objetivo, puede usar la navegación a nivel del suelo para ir a la tecla. Si no es así, debe repetir el paso uno hasta llegar a la zona objetivo.

Existe la posibilidad de que una llave que se busca esté detrás de una puerta cerrada ... y que la llave de esa puerta sea también ... y así hasta la saciedad. Esto es esencialmente un problema de resolución de dependencias, y hay algunas formas de abordarlo, una de las cuales son las Redes de Petri. Ver este excelente artículo.

PD. Si está creando su mazmorra de manera procesal, a medida que lo hace, puede almacenar información sobre el orden de dependencia, siempre que ya conozca la posición inicial del jugador.

La reacción intestinal normal a las palabras "camino más corto" obviamente sería A *. Pero A * fallaría en dicho entorno, ya que veo muchos problemas que definen una heurística confiable y, además, es muy probable que un nodo tenga que ser visitado varias veces, lo que tampoco es posible en A * convencional y también hacer la heurística más difícil.

En primer lugar, una heurística admisible no tiene que ser perfecta. Simplemente tiene que ser subestimado y tiene que ser mejor que nada. Dado que está trabajando con distancias reales, parece probable que A * al menos sería de alguna ayuda, e incluso si la heurística no mejorara mucho la búsqueda, probablemente aún sería mejor que una búsqueda estándar de amplitud o similar.

En segundo lugar, A * puede visitar un nodo tantas veces como desee. Recuerde que A * no es un algoritmo de búsqueda de ruta sino un algoritmo de búsqueda. Busca a través de los estados. En los juegos, a menudo equiparamos un estado con una posición, porque no nos importa cómo llegaste a ese estado, sino cuán corto fue el camino para llegar allí. Sin embargo, en un problema como este, el estado es una combinación de la posición más cualquier otro estado relevante, como las teclas mantenidas.

Sin embargo, es cierto que estas complicaciones moverán A * de los reinos de 'muy eficiente' a 'tendrá éxito, pero probablemente no en la escala de tiempo que requiero'. ¿Cuál es el calendario que necesita? De hecho, ¿por qué necesita hacer esto? ¿Realmente necesita el camino más corto o sería suficiente un camino razonable?

Lo que pensé es simplemente buscar un camino desde el comienzo de la mazmorra hasta el final, ignorando las puertas bloqueadas. Después de encontrar este camino, para cada una de las puertas que bloquean nuestro camino, se buscaría y atravesaría un camino adicional en busca de la llave adecuada y de regreso a la puerta, incluso antes de llegar a la puerta.

Es fácil demostrar que dicho sistema sería subóptimo. ¿Desde dónde comenzarías el camino adicional? Si desde el principio, ha perdido su tiempo trazando el camino original hacia la puerta. Si desde el final, colocar una llave cerca del inicio significa que la ruta atraviesa el mapa dos veces cuando una vez sería suficiente. Si intenta calcular los puntos de fusión óptimos para las rutas hacia y desde la puerta y la ruta original, obtendrá un resultado óptimo pero requerirá muchos recursos debido a la cantidad de permutaciones y la dificultad para formar una heurística para simplificar la búsqueda. Si agrega varias claves al problema, entonces tiene el problema del vendedor ambulante que no es fácil de resolver de manera eficiente.

Lo que intentaría, si es posible relajar el criterio del 'camino más corto', es este:

• Cree un gráfico de alto nivel que solo contenga ubicaciones importantes: posiciones clave, posiciones de puertas, posiciones dentro de áreas bloqueadas, y observe las distancias en línea recta entre ellas. Si su mapa ya se divide en habitaciones u otras ubicaciones discretas, eso es genial.
• Use A * para encontrar una ruta a través de este gráfico, desde el principio hasta el final. La heurística cartesiana de distancia normal debería ser suficiente para mantenerla manejable.
• Ahora, con esta ruta simplificada entre estos puntos de ruta, use A * nuevamente para trazar una ruta de bajo nivel de un punto de ruta al siguiente.
• Únete a estos caminos de bajo nivel para formar todo tu camino.

Una vez que eso funcionara, consideraría algunas optimizaciones menores, por ejemplo. ponderando las áreas con claves de manera más indulgente para que la ruta de nivel bajo sea más probable que haga pequeños desvíos para recoger las claves.

con la información que proporcionó, creo que puede usar A * con solo una pequeña modificación. en un algoritmo A * normal, marca todos los nodos a medida que los pasa para asegurarse de no volver a pasarlos nunca más. Esa es la parte exacta que causa problemas con los artículos. El cambio clave es recordar cuáles eran sus artículos cuando previamente pasó de un nodo. Aquí hay un código sudo que explica lo que quiero decir:

if (nodestoCheck.notempty())
    newNode = nodeToCheck.first;
    if (notpassed(newNode.pos, newNode.items))
        if (room(newNode).containItem)
            add NewNode + room(NewNode).items 
        else
            do normal A* algorithm for new Node

Con este algoritmo, primero comienza a verificar todos los nodos sin ningún elemento. existe una alta posibilidad de que su primer grupo de búsqueda termine bloqueado por algunas puertas. pero encontrará una llave para esa puerta antes de buscar en todas las habitaciones. a partir de esa clave, comienza una nueva búsqueda con esa clave específica. esta vez cuando llegue a la puerta puede pasarla. la misma rutina continúa hasta que encuentres la salida de la mazmorra. El único problema puede ser el consumo de memoria siempre que haya muchas puertas y llaves. aunque no será un problema para al menos 10 o 15 teclas.

¿Por qué no usas A * normal y modelas puertas cerradas como regiones intransitables? una vez que recoja la llave (¿caminar sobre el mosaico de la llave?), eso convierte esa puerta cerrada en particular en una región transitable.

Lo que esto significa es que su buscador de ruta irá por la ruta más corta sin llave , y si encuentra claves en el camino, lo incorporará a su ruta si eso ayuda.

Eso me parece bastante razonable. No es perfecto, pero es una solución simple al problema.