Pathfinding con cerradura y llave?

22

Estoy trabajando en un juego con mapas que se parecen a cerraduras y rompecabezas clave . La IA necesita navegar hacia una meta que puede estar detrás de una puerta roja cerrada, pero la llave roja puede estar detrás de una puerta azul cerrada, y así sucesivamente ...

Este rompecabezas es similar a una mazmorra estilo Zelda, como esta imagen:

Mazmorra de Zelda

Para llegar a la Meta, debes derrotar al Jefe, lo que requiere pasar por el pozo, lo que requiere recoger la Pluma, lo que requiere recoger la Llave

Las mazmorras de Zelda tienden a ser lineales. Sin embargo, necesito resolver el problema en el caso general. Asi que:

  • El objetivo podría requerir uno de un conjunto de claves. Entonces quizás necesites obtener la llave roja o la azul. ¡O podría haber una puerta desbloqueada en el largo camino!
  • Podría haber varias puertas y llaves de un tipo. Por ejemplo, podría haber varias llaves rojas en el mapa, y recolectar una otorgará acceso a todas las puertas rojas.
  • El objetivo puede ser inaccesible porque las llaves correctas están detrás de puertas cerradas

¿Cómo realizaría la búsqueda de ruta en dicho mapa? ¿Cómo se vería el gráfico de búsqueda?

Nota: el último punto sobre la detección de objetivos inaccesibles es importante; A *, por ejemplo, es extremadamente ineficiente si el objetivo es inaccesible. Me gustaría tratar esto de manera eficiente.

Suponga que la IA sabe dónde está todo en el mapa.

congusbongus
fuente
44
¿La IA solo conoce y descubre cosas una vez que las desbloquea? Por ejemplo, ¿sabe que la pluma está detrás de la puerta cerrada? ¿La IA comprende conceptos como "Eso es un candado, así que necesito una llave" o es algo más simple como "Tengo algo bloqueando mi camino, así que prueba todas las cosas que he encontrado en él. ¿Pluma en la puerta? No. ¿Llave en la puerta? ¡Sí!
Tim Holt el
1
Hubo una discusión previa sobre este problema en esta pregunta sobre la búsqueda de rutas hacia adelante y hacia atrás , que podría serle útil.
DMGregory
1
Entonces, ¿no estás tratando de simular un jugador, sino que estás tratando de crear una mazmorra optimizada? Mi respuesta fue definitivamente sobre simular el comportamiento de un jugador.
Tim Holt el
44
Desafortunadamente, detectar un objetivo inaccesible es bastante difícil. La única forma de asegurarse de que no hay forma de alcanzar el objetivo es explorar todo el espacio accesible para asegurarse de que ninguno de ellos contenga un objetivo, que es exactamente lo que hace A * que hace que tome tantos pasos adicionales si el objetivo es inaccesible. Cualquier algoritmo que busque menos espacio corre el riesgo de perder una ruta disponible hacia el objetivo porque la ruta se estaba ocultando en parte del espacio que omitió la búsqueda. Puede acelerar esto trabajando en un nivel superior, buscando el gráfico de las conexiones de la sala en lugar de cada mosaico o polígono navmesh.
DMGregory
1
Offtopic, pensé instintivamente en Chip's Challenge en lugar de Zelda :)
Flater

Respuestas:

22

La búsqueda de ruta estándar es suficiente : sus estados son su ubicación actual + su inventario actual. "mudarse" es cambiar de habitación o cambiar el inventario. No está cubierto en esta respuesta, pero no es un esfuerzo adicional, es escribir una buena heurística para A *: realmente puede acelerar la búsqueda al preferir recoger cosas en lugar de alejarse, prefiriendo desbloquear una puerta cerca del objetivo sobre buscar un largo camino, etc.

Esta respuesta ha recibido muchos votos positivos desde que llegó primero y tiene una demostración, pero para una solución mucho más optimizada y especializada, también debe leer la respuesta "Hacerlo al revés es mucho más rápido" /gamedev/ / a / 150155/2624


Prueba de concepto Javascript completamente operativa a continuación. Perdón por la respuesta como un volcado de código: en realidad había implementado esto antes de convencerme de que era una buena respuesta, pero me parece bastante flexible.

Para comenzar cuando piense en la búsqueda de rutas, recuerde que la jerarquía de los algoritmos de búsqueda de rutas simples es:

  • Breadth First Search es lo más simple posible.
  • El algoritmo de Djikstra es como Breadth First Search pero con diferentes "distancias" entre estados
  • A * es Djikstras donde tiene un 'sentido general de la dirección correcta' disponible como heurístico.

En nuestro caso, simplemente codificar un "estado" como "ubicación + inventario" y "distancias" como "movimiento o uso de elementos" nos permite usar Djikstra o A * para resolver nuestro problema.

Aquí hay un código real que demuestra su nivel de ejemplo. El primer fragmento es solo para comparación: salte a la segunda parte si desea ver la solución final. Comenzamos con una implementación de Djikstra que encuentra el camino correcto, pero hemos ignorado todos los obstáculos y claves. (Pruébelo, puede verlo solo para el final, desde la habitación 0 -> 2 -> 3-> 4-> 6-> 5)

function Transition(cost, state) { this.cost = cost, this.state = state; }
// given a current room, return a room of next rooms we can go to. it costs 
// 1 action to move to another room.
function next(n) {
    var moves = []
    // simulate moving to a room
    var move = room => new Transition(1, room)
    if (n == 0) moves.push(move(2))
    else if ( n == 1) moves.push(move(2))
    else if ( n == 2) moves.push(move(0), move(1), move(3))
    else if ( n == 3) moves.push(move(2), move(4), move(6))
    else if ( n == 4) moves.push(move(3))
    else if ( n == 5) moves.push(move(6))
    else if ( n == 6) moves.push(move(5), move(3))
    return moves
}

// Standard Djikstra's algorithm. keep a list of visited and unvisited nodes
// and iteratively find the "cheapest" next node to visit.
function calc_Djikstra(cost, goal, history, nextStates, visited) {

    if (!nextStates.length) return ['did not find goal', history]

    var action = nextStates.pop()
    cost += action.cost
    var cur = action.state

    if (cur == goal) return ['found!', history.concat([cur])]
    if (history.length > 15) return ['we got lost', history]

    var notVisited = (visit) => {
        return visited.filter(v => JSON.stringify(v) == JSON.stringify(visit.state)).length === 0;
    };
    nextStates = nextStates.concat(next(cur).filter(notVisited))
    nextStates.sort()

    visited.push(cur)
    return calc_Djikstra(cost, goal, history.concat([cur]), nextStates, visited)
}

console.log(calc_Djikstra(0, 5, [], [new Transition(0, 0)], []))

Entonces, ¿cómo agregamos elementos y claves a este código? ¡Simple! en lugar de que cada "estado" comience solo con el número de habitación, ahora es una tupla de la habitación y nuestro estado de inventario:

 // Now, each state is a [room, haskey, hasfeather, killedboss] tuple
function State(room, k, f, b) { this.room = room; this.k = k; this.f = f; this.b = b }

Las transiciones ahora cambian de ser una tupla (costo, habitación) a una tupla (costo, estado), por lo que pueden codificar tanto "mudarse a otra habitación" como "recoger un artículo"

// move(3) keeps inventory but sets the room to 3
var move = room => new Transition(1, new State(room, cur.k, cur.f, cur.b))
// pickup("k") keeps room number but increments the key count
var pickup = (cost, item) => {
    var n = Object.assign({}, cur)
    n[item]++;
    return new Transition(cost, new State(cur.room, n.k, n.f, n.b));
};

finalmente, realizamos algunos cambios menores relacionados con el tipo en la función Djikstra (por ejemplo, todavía coincide con un número de sala de meta en lugar de un estado completo), ¡y obtenemos nuestra respuesta completa! Tenga en cuenta que el resultado impreso primero va a la sala 4 para recoger la llave, luego va a la sala 1 para recoger la pluma, luego va a la sala 6, mata al jefe y luego a la sala 5)

// Now, each state is a [room, haskey, hasfeather, killedboss] tuple
function State(room, k, f, b) { this.room = room; this.k = k; this.f = f; this.b = b }
function Transition(cost, state, msg) { this.cost = cost, this.state = state; this.msg = msg; }

function next(cur) {
var moves = []
// simulate moving to a room
var n = cur.room
var move = room => new Transition(1, new State(room, cur.k, cur.f, cur.b), "move to " + room)
var pickup = (cost, item) => {
	var n = Object.assign({}, cur)
	n[item]++;
	return new Transition(cost, new State(cur.room, n.k, n.f, n.b), {
		"k": "pick up key",
		"f": "pick up feather",
		"b": "SLAY BOSS!!!!"}[item]);
};

if (n == 0) moves.push(move(2))
else if ( n == 1) { }
else if ( n == 2) moves.push(move(0), move(3))
else if ( n == 3) moves.push(move(2), move(4))
else if ( n == 4) moves.push(move(3))
else if ( n == 5) { }
else if ( n == 6) { }

// if we have a key, then we can move between rooms 1 and 2
if (cur.k && n == 1) moves.push(move(2));
if (cur.k && n == 2) moves.push(move(1));

// if we have a feather, then we can move between rooms 3 and 6
if (cur.f && n == 3) moves.push(move(6));
if (cur.f && n == 6) moves.push(move(3));

// if killed the boss, then we can move between rooms 5 and 6
if (cur.b && n == 5) moves.push(move(6));
if (cur.b && n == 6) moves.push(move(5));

if (n == 4 && !cur.k) moves.push(pickup(0, 'k'))
if (n == 1 && !cur.f) moves.push(pickup(0, 'f'))
if (n == 6 && !cur.b) moves.push(pickup(100, 'b'))	
return moves
}

var notVisited = (visitedList) => (visit) => {
return visitedList.filter(v => JSON.stringify(v) == JSON.stringify(visit.state)).length === 0;
};

// Standard Djikstra's algorithm. keep a list of visited and unvisited nodes
// and iteratively find the "cheapest" next node to visit.
function calc_Djikstra(cost, goal, history, nextStates, visited) {

if (!nextStates.length) return ['No path exists', history]

var action = nextStates.pop()
cost += action.cost
var cur = action.state

if (cur.room == goal) return history.concat([action.msg])
if (history.length > 15) return ['we got lost', history]

nextStates = nextStates.concat(next(cur).filter(notVisited(visited)))
nextStates.sort()

visited.push(cur)
return calc_Djikstra(cost, goal, history.concat([action.msg]), nextStates, visited)
o}

console.log(calc_Djikstra(0, 5, [], [new Transition(0, new State(0, 0, 0, 0), 'start')], []))

En teoría, esto funciona incluso con BFS y no necesitábamos la función de costo para Djikstra, pero tener el costo nos permite decir "recoger una llave es fácil, pero luchar contra un jefe es realmente difícil, y preferimos retroceder 100 pasos en lugar de luchar contra el jefe, si tuviéramos la opción ":

if (n == 4 && !cur.k) moves.push(pickup(0, 'k'))
if (n == 1 && !cur.f) moves.push(pickup(0, 'f'))
if (n == 6 && !cur.b) moves.push(pickup(100, 'b'))
Palanqueta
fuente
Sí, incluir el inventario / estado clave en el gráfico de búsqueda es una solución. Sin embargo, me preocupa el aumento de los requisitos de espacio: un mapa con 4 teclas requiere 16 veces el espacio de un gráfico sin llave.
congusbongus
8
@congusbongus bienvenido al problema del vendedor ambulante NP-complete. No hay una solución general que lo resuelva en tiempo polinómico.
monstruo de trinquete
1
@congusbongus En general, no creo que su gráfico de búsqueda vaya a estar sobrecargado, pero si le preocupa el espacio, simplemente empaque sus datos; podría usar 24 bits para el indicador de sala (16 millones de habitaciones deberían ser suficiente para cualquier persona) y un poco cada uno para los elementos que le interesan usar como puertas (hasta 8 únicos). Si quieres ponerte elegante, puedes usar dependencias para empacar elementos en bits aún más pequeños, es decir, usar el mismo bit para "clave" y "jefe" ya que hay una dependencia transitiva indirecta
Jimmy
@Jimmy Aunque no es personal, agradezco la mención de mi respuesta :)
Jibb Smart el
13

Atrás A * hará el truco

Como se discutió en esta respuesta a una pregunta sobre la búsqueda de ruta hacia adelante y hacia atrás , la búsqueda de ruta hacia atrás es una solución relativamente simple para este problema. Esto funciona de manera muy similar a GOAP (Planificación de acción orientada a objetivos), planeando soluciones eficientes y minimizando las preguntas sin objetivo.

Al final de esta respuesta, tengo un desglose de cómo maneja el ejemplo que dio.

En detalle

Pathfind desde el destino hasta el inicio. Si, en su búsqueda de caminos, se encuentra con una puerta cerrada, tiene una nueva rama en su búsqueda de caminos que continúa a través de la puerta como si estuviera desbloqueada, y la rama principal continúa buscando otro camino. La rama que continúa a través de la puerta como si estuviera desbloqueada ya no está buscando al agente de IA, ahora está buscando una llave que pueda usar para pasar por la puerta. Con A *, su nueva heurística es la distancia a la tecla + la distancia al agente de IA, en lugar de solo la distancia al agente de IA.

Si la rama de la puerta desbloqueada encuentra la llave, continúa buscando al agente de IA.

Esta solución se hace un poco más complicada cuando hay varias claves viables disponibles, pero puede ramificar en consecuencia. Debido a que las sucursales tienen un destino fijo, aún le permite usar una heurística para optimizar la búsqueda de ruta (A *), y con suerte las rutas imposibles se cortarán rápidamente, si no hay forma de evitar la puerta cerrada, la rama que no No pasar por la puerta se queda sin opciones rápidamente y la rama que atraviesa la puerta y busca la llave continúa por sí sola.

Por supuesto, donde hay una variedad de opciones viables disponibles (múltiples llaves, otros elementos para sortear la puerta, un largo camino alrededor de la puerta), se mantendrán muchas ramas, lo que afectará el rendimiento. Pero también encontrará la opción más rápida y podrá usarla.


En acción

En su ejemplo específico, ruta de acceso desde el objetivo hasta el inicio:

  1. Nos encontramos rápidamente con una puerta de jefe. La rama A continúa por la puerta, ahora buscando un jefe para luchar. La rama B permanece atascada en la habitación y pronto expirará cuando descubra que no hay salida.

  2. La Rama A encuentra al jefe y ahora está buscando el Inicio, pero se encuentra con un pozo.

  3. La rama A continúa sobre el hoyo, pero ahora está buscando la pluma, y ​​en consecuencia hará una línea de abeja hacia la pluma. Se crea la rama C, que trata de encontrar una forma de rodear el pozo, pero caduca tan pronto como no puede. Eso, o se ignora por un tiempo, si su heurístico A * encuentra que la Rama A todavía parece más prometedora.

  4. La rama A se encuentra con la puerta cerrada y continúa a través de la puerta cerrada como si estuviera desbloqueada, pero ahora está buscando la llave. La rama D también continúa a través de la puerta cerrada, todavía buscando la pluma, pero luego buscará la llave. Esto se debe a que no sabemos si necesitamos encontrar la llave o la pluma primero, y en lo que respecta a la búsqueda de caminos, el Inicio podría estar al otro lado de esta puerta. La rama E intenta encontrar un camino alrededor de la puerta cerrada, y falla.

  5. La rama D encuentra rápidamente la pluma y continúa buscando la llave. Se le permite pasar nuevamente por la puerta cerrada, ya que todavía está buscando la llave (y está retrocediendo en el tiempo). Pero una vez que tenga la llave, no podrá pasar por la puerta cerrada (ya que no pudo pasar antes de encontrar la llave).

  6. Las ramas A y D continúan compitiendo, pero cuando la rama A alcanza la llave, está buscando la pluma, y ​​no podrá alcanzarla porque tiene que pasar por la puerta cerrada nuevamente. La Rama D, por otro lado, al alcanzar la tecla, dirige su atención al Inicio y la encuentra sin complicaciones.

  7. La rama D gana. Ha encontrado el camino inverso. La ruta final es: Inicio -> Clave -> Pluma -> Jefe -> Objetivo.

Jibb Smart
fuente
6

Editar : esto está escrito desde el punto de vista de una IA que está buscando explorar y descubrir un objetivo, y no conoce la ubicación de las llaves, cerraduras o destinos con anticipación.

Primero, suponga que la IA tiene algún tipo de objetivo general. Por ejemplo, "Encuentra al jefe" en tu ejemplo. Sí, quieres vencerlo, pero realmente se trata de encontrarlo. Suponga que no tiene idea de cómo llegar a la meta, solo que existe. Y lo sabrá cuando lo encuentre. Una vez que se cumple el objetivo, la IA puede dejar de trabajar para resolver el problema.

Además, voy a usar el término genérico "cerradura" y "llave" aquí, incluso si puede ser un abismo y una pluma. Es decir, la pluma "desbloquea" el abismo "cerradura".

Enfoque de solución

Parece que comenzarías primero con solo una IA que era básicamente un explorador de laberintos (si piensas en tu mapa como un laberinto). Explorar y mapear todos los lugares a los que puede ir sería el foco principal de la IA. Podría basarse únicamente en algo simple como: "Ir siempre al camino más cercano que he visto pero que aún no he visitado".

Sin embargo, algunas reglas entrarían en vigencia al explorar que podrían cambiar la prioridad ...

  • Tomaría cualquier clave que encontrara, a menos que ya tuviera la misma clave
  • Si encontraba una cerradura que nunca antes había visto, probaría todas las llaves que había encontrado en esa cerradura
  • Si una llave funcionara en un nuevo tipo de cerradura, recordaría el tipo de llave y el tipo de cerradura
  • Si encontró una cerradura que había visto antes y tenía la llave, usaría el tipo de llave recordada (por ejemplo, se encontró una segunda cerradura roja, la llave roja funcionó antes en la cerradura roja, así que solo use la llave roja)
  • Recordaría la ubicación de cualquier cerradura que no pudiera desbloquear
  • No necesitaría recordar la ubicación de las cerraduras que había desbloqueado
  • Cada vez que encuentra una llave y sabe de cualquier cerradura previamente desbloqueable, visita inmediatamente cada una de esas cerraduras bloqueadas e intenta desbloquearlas con la nueva llave encontrada
  • Cada vez que desbloqueaba un camino, simplemente volvía a la meta de exploración y mapeo, priorizando entrar en la nueva área

Una nota sobre ese último punto. Si tiene que elegir entre visitar un área inexplorada que se ha visto antes (pero no visitada) versus un área inexplorada detrás de una ruta recién desbloqueada, debe hacer que la ruta recién desbloqueada sea la prioridad. Eso es probablemente donde hay nuevas llaves (o cerraduras) que serán útiles. Esto supone que un camino bloqueado probablemente no será un callejón sin salida sin sentido.

Expandiendo la idea con teclas "bloqueables"

Potencialmente, podría tener claves que no se pueden tomar sin otra clave. O llaves cerradas por así decirlo. Si conoce sus antiguas cuevas colosales, necesita tener la jaula de pájaros para atrapar al pájaro, que luego necesitará para una serpiente. Entonces "desbloqueas" al pájaro con la jaula (que no bloquea el camino pero no se puede levantar sin la jaula), y luego "desbloqueas" la serpiente (que bloquea tu camino) con el pájaro.

Entonces agregando algunas reglas ...

  • Si no se puede tomar una llave (está bloqueada), pruebe con cada llave que ya tenga
  • Si encuentra una llave que no puede desbloquear, recuérdelo para más tarde
  • Si encuentra una nueva clave, pruébela en cada clave bloqueada conocida, así como en la ruta bloqueada

Ni siquiera voy a entrar en todo el asunto acerca de cómo llevar una determinada llave podría negar el efecto de otra llave (Cuevas colosales, la caña asusta al pájaro y debe dejarse caer antes de que el pájaro pueda ser recogido, pero se necesita más tarde para crear un puente mágico) .

Tim Holt
fuente