Árboles de comportamiento preeminente

25

Estoy tratando de entender los árboles de comportamiento, así que estoy agregando un código de prueba. Una cosa con la que estoy luchando es cómo evitar un nodo actualmente en ejecución cuando aparece algo de mayor prioridad.

Considere el siguiente árbol de comportamiento simple y ficticio para un soldado:

ingrese la descripción de la imagen aquí

Supongamos que ha pasado un número de garrapatas y que no había ningún enemigo cerca, el soldado estaba de pie sobre la hierba, por lo que se selecciona el nodo Sentarse para la ejecución:

ingrese la descripción de la imagen aquí

Ahora la acción de sentarse toma tiempo para ejecutarse porque hay una animación para reproducir, por lo que regresa Runningcomo su estado. Pasa una o dos marcas, la animación aún se está ejecutando, pero ¿el enemigo está cerca? desencadenantes de nodo de condición. Ahora tenemos que adelantarnos al nodo Sit down lo antes posible para que podamos ejecutar el nodo Attack . Idealmente, el soldado ni siquiera terminaría de sentarse; en cambio, podría invertir su dirección de animación si solo comenzara a sentarse. Para mayor realismo, si ha pasado algún punto de inflexión en la animación, podríamos optar por dejar que termine de sentarse y luego ponerse de pie nuevamente, o tal vez hacer que se apresure a reaccionar ante la amenaza.

Por más que lo intenté, no he podido encontrar orientación sobre cómo manejar este tipo de situación. Toda la literatura y videos que he consumido en los últimos días (y ha sido mucho) parecen eludir este problema. Lo más cercano que he podido encontrar ha sido este concepto de restablecer los nodos en ejecución, pero eso no le da a los nodos como Sit sentarse la oportunidad de decir "¡hey, aún no he terminado!"

Pensé en quizás definir un método Preempt()o Interrupt()en mi Nodeclase base . Diferentes nodos pueden manejarlo como mejor les parezca, pero en este caso intentaremos que el soldado vuelva a ponerse de pie lo antes posible y luego regrese Success. Creo que este enfoque también requeriría que mi base Nodetenga el concepto de condiciones por separado de otras acciones. De esa forma, el motor solo puede verificar las condiciones y, si pasan, evitar cualquier nodo que se esté ejecutando actualmente antes de comenzar la ejecución de las acciones. Si no se estableciera esta diferenciación, el motor necesitaría ejecutar nodos indiscriminadamente y, por lo tanto, podría desencadenar una nueva acción antes de adelantarse a la ejecución.

Como referencia, a continuación están mis clases base actuales. Nuevamente, esto es un pico, así que he intentado mantener las cosas lo más simples posible y solo agrego complejidad cuando lo necesito, y cuando lo entiendo, que es con lo que estoy luchando en este momento.

public enum ExecuteResult
{
    // node needs more time to run on next tick
    Running,

    // node completed successfully
    Succeeded,

    // node failed to complete
    Failed
}

public abstract class Node<TAgent>
{
    public abstract ExecuteResult Execute(TimeSpan elapsed, TAgent agent, Blackboard blackboard);
}

public abstract class DecoratorNode<TAgent> : Node<TAgent>
{
    private readonly Node<TAgent> child;

    protected DecoratorNode(Node<TAgent> child)
    {
        this.child = child;
    }

    protected Node<TAgent> Child
    {
        get { return this.child; }
    }
}

public abstract class CompositeNode<TAgent> : Node<TAgent>
{
    private readonly Node<TAgent>[] children;

    protected CompositeNode(IEnumerable<Node<TAgent>> children)
    {
        this.children = children.ToArray();
    }

    protected Node<TAgent>[] Children
    {
        get { return this.children; }
    }
}

public abstract class ConditionNode<TAgent> : Node<TAgent>
{
    private readonly bool invert;

    protected ConditionNode()
        : this(false)
    {
    }

    protected ConditionNode(bool invert)
    {
        this.invert = invert;
    }

    public sealed override ExecuteResult Execute(TimeSpan elapsed, TAgent agent, Blackboard blackboard)
    {
        var result = this.CheckCondition(agent, blackboard);

        if (this.invert)
        {
            result = !result;
        }

        return result ? ExecuteResult.Succeeded : ExecuteResult.Failed;
    }

    protected abstract bool CheckCondition(TAgent agent, Blackboard blackboard);
}

public abstract class ActionNode<TAgent> : Node<TAgent>
{
}

¿Alguien tiene alguna idea que pueda guiarme en la dirección correcta? ¿Mi pensamiento está en la línea correcta, o es tan ingenuo como temo?

yo--
fuente
Debe echar un vistazo a este documento: chrishecker.com/My_liner_notes_for_spore/… aquí explica cómo se camina el árbol, no como una máquina de estados, sino desde la RAÍZ en cada tic, que es el verdadero truco para la reactividad. BT no debería necesitar excepciones o eventos. Están agrupando sistemas intrínsecamente y reacciona a todas las situaciones gracias a que siempre fluye desde la raíz. Así es como funciona la preferencia, si una condición externa de controles de mayor prioridad, fluye allí. (llamando a alguna Stop()devolución de llamada antes de salir de los nodos activos)
v.oddou
este aigamedev.com/open/article/popular-behavior-tree-design también está muy bien detallado
v.oddou

Respuestas:

6

Me encontré haciendo la misma pregunta que tú y tuve una gran conversación corta en la sección de comentarios de esta página de blog donde se me proporcionó otra solución al problema.

Lo primero es usar el nodo concurrente. El nodo concurrente es un tipo especial de nodo compuesto. Consiste en una secuencia de comprobaciones previas seguidas de un único nodo de acción. Actualiza todos los nodos secundarios, incluso si su nodo de acción está en estado 'en ejecución'. (A diferencia del nodo de secuencia que debe iniciar su actualización desde el nodo secundario actual en ejecución).

La idea principal es crear dos estados de retorno más para los nodos de acción: "cancelar" y "cancelar".

La falla de la verificación de precondición en el nodo concurrente es un mecanismo que desencadena la cancelación de su nodo de acción en ejecución. Si el nodo de acción no requiere una lógica de cancelación de larga duración, devolverá 'cancelado' inmediatamente. De lo contrario, cambia al estado de 'cancelación' donde puede poner toda la lógica necesaria para la interrupción correcta de la acción.

Rokannon
fuente
Hola y bienvenidos a GDSE. Sería genial si pudieras abrir esa respuesta desde ese blog hasta aquí y al final el enlace a ese blog. Los enlaces tienden a morir, tener una respuesta completa aquí, lo hace más persistente. La pregunta tiene 8 votos ahora, por lo que una buena respuesta sería increíble.
Katu
No creo que nada que devuelva árboles de comportamiento a la máquina de estados finitos sea una buena solución. Su enfoque me parece que necesita visualizar todas las condiciones de salida de cada estado. Cuando esto ES realmente el inconveniente de FSM! BT tiene la ventaja de comenzar de nuevo en la raíz, esto crea un FSM totalmente conectado implícitamente, evitando que escribamos explícitamente las condiciones de salida.
v.oddou
5

Creo que tu soldado puede descomponerse en mente y cuerpo (y cualquier otra cosa). Posteriormente, el cuerpo puede descomponerse en piernas y manos. Luego, cada parte necesita su propio árbol de comportamiento y también una interfaz pública, para solicitudes de partes de nivel superior o inferior.

Por lo tanto, en lugar de administrar micro cada acción, solo envía mensajes instantáneos como "cuerpo, siéntate por un tiempo" o "cuerpo, corre allí", y el cuerpo administrará animaciones, transiciones de estado, retrasos y otras cosas para tú.

Alternativamente, el cuerpo puede manejar comportamientos como este por sí mismo. Si no tiene órdenes, puede preguntar "¿podemos sentarnos aquí?". Más interesante aún, debido a la encapsulación, puede modelar fácilmente características como cansancio o aturdimiento.

Incluso puede intercambiar partes: hacer elefante con intelecto de zombie, agregar alas a humanos (él ni siquiera lo notará), o cualquier otra cosa.

Sin una descomposición como esta, apuesto a que corre el riesgo de encontrarse con una explosión combinatoria, tarde o temprano.

También: http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf

Sombras en la lluvia
fuente
Gracias. Habiendo leído tu respuesta 3 veces, creo que entiendo. Leeré ese PDF este fin de semana.
yo--
1
Habiendo pensado en esto durante la última hora, no estoy seguro de entender la distinción entre tener BT completamente separados para mente y cuerpo versus un solo BT que se descompone en subárboles (referenciado a través de un decorador especial, con scripts de tiempo de construcción atar todo junto en un gran BT). Me parece que esto proporcionaría beneficios de abstracción similares y podría hacer que sea más fácil entender cómo se comporta una entidad dada porque no tiene que mirar a través de múltiples BT separadas. Sin embargo, probablemente estoy siendo ingenuo.
yo--
@ user13414 La diferencia es que necesitará secuencias de comandos especiales para construir el árbol, cuando solo use el acceso indirecto (es decir, cuando el nodo del cuerpo debe preguntarle a su árbol qué objeto representa las piernas) puede ser suficiente y tampoco requerirá ningún ataque mental adicional. Menos código, menos errores. Además, perderá la capacidad de (fácilmente) cambiar el subárbol en tiempo de ejecución. Incluso si no necesita tanta flexibilidad, no perderá nada (incluida la velocidad de ejecución).
Shadows In Rain
3

Anoche, acostada en la cama, tuve una especie de epifanía sobre cómo podría hacer esto sin introducir la complejidad a la que me inclinaba en mi pregunta. Implica el uso del compuesto "paralelo" (mal llamado, en mi humilde opinión). Esto es lo que estoy pensando:

ingrese la descripción de la imagen aquí

Esperemos que todavía sea bastante legible. Los puntos importantes son:

  • La secuencia Sentarse / Retardo / Pararse es una secuencia dentro de una secuencia paralela ( A ). En cada tic, la secuencia paralela también verifica la condición de enemigo cercano (invertida). Si un enemigo está cerca, la condición falla y también lo hace toda la secuencia paralela (inmediatamente, incluso si la secuencia secundaria está a la mitad de Sentarse , Retrasarse o Pararse )
  • en caso de falla, el selector B sobre la secuencia paralela saltará al selector C para manejar la interrupción. Es importante destacar que el selector C no se ejecutará si la secuencia paralela A se completa con éxito
  • el selector C luego intenta ponerse de pie normalmente, pero también puede activar una animación de tropiezo si el soldado está actualmente en una posición demasiado incómoda para simplemente ponerse de pie

Creo que esto funcionará (lo intentaré en mi pico pronto), a pesar de ser un poco más desordenado de lo que había imaginado. Lo bueno es que eventualmente podría encapsular subárboles como piezas lógicas reutilizables y referirme a ellos desde múltiples puntos. Eso aliviará la mayor parte de mi preocupación allí, así que creo que esta es una solución viable.

Por supuesto, me encantaría saber si alguien tiene alguna idea sobre esto.

ACTUALIZAR : aunque este enfoque técnicamente funciona, he decidido que sux. Esto se debe a que los subárboles no relacionados deben "conocer" las condiciones definidas en otras partes del árbol para que puedan desencadenar su propia desaparición. Si bien compartir referencias de subárboles ayudaría a aliviar este dolor, sigue siendo contrario a lo que uno espera al mirar el árbol de comportamiento. De hecho, cometí el mismo error dos veces en un pico muy simple.

Por lo tanto, voy a seguir la otra ruta: soporte explícito para anticiparnos dentro del modelo de objetos, y un compuesto especial que permite que se ejecute un conjunto diferente de acciones cuando se produce la preferencia. Publicaré una respuesta por separado cuando tenga algo funcionando.

yo--
fuente
1
Si realmente desea reutilizar subárboles, entonces la lógica de cuándo interrumpir ("enemigo cerca" aquí) probablemente no debería ser parte del subárbol. En su lugar, tal vez el sistema puede pedirle a cualquier subárbol (por ejemplo, B aquí) que se interrumpa debido a un estímulo de mayor prioridad, y luego saltaría a un nodo de interrupción especialmente marcado (C aquí) que se encargaría de devolver el carácter a un estado estándar , por ejemplo, de pie. Un poco como el árbol de comportamiento equivalente al manejo de excepciones.
Nathan Reed
1
Incluso podría incorporar manejadores de interrupciones múltiples dependiendo de qué estímulo está interrumpiendo. Por ejemplo, si el PNJ está sentado y comienza a disparar, es posible que no desee que se ponga de pie (y presente un objetivo más grande), sino que permanezca bajo y lucha por cubrirse.
Nathan Reed
@Nathan: divertido que mencionas sobre "manejo de excepciones". El primer enfoque posible que pensé anoche fue esta idea de un compuesto Preempt, que tendría dos hijos: uno para ejecución normal y otro para ejecución anticipada. Si el niño normal pasa o falla, ese resultado se propaga. El elemento secundario de preferencia solo se ejecutará si se produce la opción de preferencia. Todos los nodos tendrían un Preempt()método que atravesaría el árbol. Sin embargo, lo único que realmente "manejaría" esto sería el compuesto preventivo, que cambiaría instantáneamente a su nodo secundario preventivo.
yo--
Luego pensé en el enfoque paralelo que describí anteriormente, y que parecía más elegante porque no requiere un cruft extra en toda la API. A su punto de encapsular subárboles, creo que donde sea que surja la complejidad, ese sería un posible punto de sustitución. Eso incluso podría ser donde tienes varias condiciones que se verifican frecuentemente juntas. En ese caso, la raíz de la sustitución sería una secuencia compuesta, con múltiples condiciones como elementos secundarios.
yo--
Creo que Subtrees sabiendo las condiciones que necesitan para "golpear" antes de ejecutar es perfectamente apropiado, ya que los hace independientes y muy explícitos vs implícitos. Si esa es una preocupación mayor, entonces no mantenga las condiciones dentro del subárbol, sino en el "sitio de la llamada".
Seivan
2

Aquí está la solución que he decidido por ahora ...

  • Mi Nodeclase base tiene un Interruptmétodo que, por defecto, no hace nada
  • Las condiciones son construcciones de "primera clase", ya que se requiere que regresen bool(lo que implica que son rápidas de ejecutar y nunca necesitan más de una actualización)
  • Node expone una colección de condiciones por separado a su colección de nodos secundarios
  • Node.Executeejecuta todas las condiciones primero y falla de inmediato si falla alguna condición. Si las condiciones tienen éxito (o no hay ninguna), llamaExecuteCore para que la subclase pueda hacer su trabajo real. Hay un parámetro que permite omitir condiciones, por razones que verá a continuación
  • NodeTambién permite que las condiciones se ejecuten de forma aislada a través de un CheckConditionsmétodo. Por supuesto, en Node.Executerealidad solo llama CheckConditionscuando necesita validar condiciones
  • Mi Selectorcompuesto ahora llama CheckConditionsa cada hijo que considera para la ejecución. Si las condiciones fallan, se mueve directamente hacia el siguiente hijo. Si pasan, verifica si ya hay un niño ejecutor. Si es así, llamaInterrupt y luego falla. Eso es todo lo que puede hacer en este momento, con la esperanza de que el nodo actualmente en ejecución responda a la solicitud de interrupción, lo que puede hacer al ...
  • He agregado un Interruptiblenodo, que es una especie de decorador especial porque tiene el flujo regular de lógica como elemento secundario decorado, y luego un nodo separado para las interrupciones. Ejecuta su hijo regular hasta su finalización o falla siempre que no se interrumpa. Si se interrumpe, cambia inmediatamente a ejecutar su nodo secundario de manejo de interrupciones, que podría ser un subárbol tan complejo como sea necesario

El resultado final es algo como esto, tomado de mi pico:

ingrese la descripción de la imagen aquí

Lo anterior es el árbol de comportamiento para una abeja, que recolecta néctar y lo devuelve a su colmena. Cuando no tiene néctar y no está cerca de una flor que tiene algo, deambula:

ingrese la descripción de la imagen aquí

Si este nodo no fuera interrumpible, nunca fallaría, por lo que la abeja deambularía perpetuamente. Sin embargo, dado que el nodo padre es un selector y tiene hijos de mayor prioridad, su elegibilidad para la ejecución se verifica constantemente. Si sus condiciones pasan, el selector genera una interrupción y el subárbol de arriba cambia inmediatamente a la ruta "interrumpida", que simplemente falla lo antes posible al fallar. Podría, por supuesto, realizar algunas otras acciones primero, pero mi pico realmente no tiene nada que hacer aparte de la fianza.

Sin embargo, para vincular esto con mi pregunta, se podría imaginar que el camino "Interrumpido" podría intentar revertir la animación sentada y, en su defecto, hacer que el soldado tropiece. Todo esto retrasaría la transición al estado de mayor prioridad, y ese era precisamente el objetivo.

Yo creo que estoy feliz con este enfoque - sobre todo las piezas centrales esbozo anterior - pero para ser honesto, que ha recaudado más preguntas sobre la proliferación de las implementaciones específicas de condiciones y acciones, y que atan el árbol de comportamiento en el sistema de animación. Ni siquiera estoy seguro de poder articular estas preguntas todavía, así que seguiré pensando / aumentando.

yo--
fuente
1

Solucioné el mismo problema inventando el decorador "When". Tiene una condición y dos comportamientos infantiles ("entonces" y "de lo contrario"). Cuando se ejecuta "When", verifica la condición y, dependiendo de su resultado, se ejecuta entonces / de otro modo secundario. Si el resultado de la condición cambia, se reinicia el elemento secundario en ejecución y se inicia el elemento secundario correspondiente a otra rama. Si el niño finaliza la ejecución, todo el "Cuándo" finaliza la ejecución.

El punto clave es que, a diferencia de la BT inicial en esta pregunta, donde la condición se verifica solo al inicio de la secuencia, mi "Cuándo" sigue verificando la condición mientras se está ejecutando. Entonces, la parte superior del árbol de comportamiento se reemplaza con:

When[EnemyNear]
  Then
    AttackSequence
  Otherwise
    When[StandingOnGrass]
      Then
        IdleSequence
      Otherwise
        Hum a tune

Para un uso más avanzado de "Cuándo", uno también querría introducir la acción de "Esperar" que simplemente no hace nada durante un período de tiempo específico o de forma indefinida (hasta que se restablece por el comportamiento de los padres). Además, si solo necesita una rama de "Cuándo", la otra puede contener acciones de "Éxito" o "Fracaso", que respectivamente tienen éxito y fallan de inmediato.

Slonopotamus
fuente
Creo que este enfoque está más cerca de lo que los inventores originales de BT tenían en mente. Utiliza un flujo más dinámico, por lo que el estado de "ejecución" en BT es un estado muy peligroso, que debe usarse muy raramente. Debemos diseñar BT siempre teniendo en cuenta la posibilidad de volver a la raíz en cualquier momento.
v.oddou
0

Si bien llego tarde, pero espero que esto pueda ayudar. Principalmente porque quiero asegurarme de que personalmente no me he perdido algo, ya que he estado tratando de resolver esto también. Sobre todo tomé prestada esta idea Unreal, pero sin convertirla en una Decoratorpropiedad sobre una base Nodeo fuertemente vinculada con elBlackboard , es más genérica.

Esto introducirá un nuevo tipo de nodo llamado Guardque es como una combinación de a Decorator, Compositey tiene una condition() -> Resultfirma junto a unupdate() -> Result

Tiene tres modos para indicar cómo debe ocurrir la cancelación cuando Guardregresa Successo Failed, la cancelación depende realmente de la persona que llama. Entonces, para una Selectorllamada a Guard:

  1. Cancelar .self -> Solo cancele el Guard(y su elemento secundario en ejecución) si se está ejecutando y la condición eraFailed
  2. Cancelar .lower-> Solo cancele los nodos de menor prioridad si se están ejecutando y la condición era SuccessoRunning
  3. Cancelar .both -> Ambos .selfy .lowerdependiendo de las condiciones y los nodos en ejecución. Desea cancelar self si se está ejecutando y condicionaría falseo cancelaría el nodo en ejecución si se consideran de menor prioridad según la Compositeregla (Selector en nuestro caso) si la condición es Success. En otras palabras, son básicamente ambos conceptos combinados.

Me gusta Decorator y diferente Compositesolo se necesita un solo hijo.

A pesar de que Guardsólo tienen un solo niño, puede anidar ya que muchos Sequences, Selectorso de otros tipos Nodescomo usted desee, incluyendo otra GuardsoDecorators .

Selector1 Guard.both[Sequence[EnemyNear?]] Sequence1 MoveToEnemy Attack Selector2 Sequence2 StandingOnGrass? Idle HumATune

En el escenario anterior, siempre que se Selector1actualice, siempre ejecutará verificaciones de condición en los guardias asociados con sus hijos. En el caso anterior, Sequence1está guardado y debe verificarse antes de Selector1continuar con elrunning tareas.

Siempre que se ejecute Selector2o Sequence1tan pronto como EnemyNear?regrese successdurante una Guards condition()verificación Selector1, emitirá una interrupción / cancelación alrunning node y luego continuar como de costumbre.

En otras palabras, podemos reaccionar a la rama "inactiva" o "atacante" en función de algunas condiciones que hacen que el comportamiento sea mucho más reactivo que si nos conformamos con Parallel

Esto también le permite proteger a los solteros Nodeque tienen mayor prioridad contra correr Nodesen el mismoComposite

Selector1 Guard.both[Sequence[EnemyNear?]] Sequence1 MoveToEnemy Attack Selector2 Guard.both[StandingOnGrass?] Idle HumATune

Si HumATunees una ejecución larga Node, Selector2siempre verificará esa primero si no fuera por el Guard. Entonces, si el npc se teletransportó a un parche de hierba, la próxima vez que se Selector2ejecute, verificará Guardy cancelaráHumATune para ejecutarIdle

Si se teletransporta fuera del parche de hierba, cancelará el nodo en ejecución (Idle ) y se moverá aHumATune

Como puede ver aquí, la toma de decisiones depende de la persona que llama Guardy no de Guardsí misma. Las reglas de quién se considera lower prioritypermanecen con la persona que llama. En ambos ejemplos, es Selectorquien define lo que constituye comolower priority .

Si tuviera una Compositellamada Random Selector, podría definir las reglas dentro de la implementación de ese específico Composite.

Seivan
fuente