Prevenção de árvores de comportamento

Estou tentando entender as árvores de comportamento, então estou criando um código de teste. Uma coisa com a qual estou lutando é como antecipar um nó em execução no momento quando surgir algo de maior prioridade.

Considere a seguinte árvore de comportamento simples e fictícia para um soldado:

Suponha que um número de tiques tenha passado e que não havia nenhum inimigo por perto, o soldado estava de pé na grama, portanto o nó Sentar-se é selecionado para execução:

Agora, a ação Sentar leva tempo para ser executada porque há uma animação a ser reproduzida; portanto, ela retorna Runningcomo seu status. Um carrapato ou dois passam, a animação ainda está em execução, mas o Inimigo está próximo? disparos do nó de condição. Agora, precisamos antecipar o nó Sentar o mais rápido possível, para que possamos executar o nó Ataque . Idealmente, o soldado nem terminaria de sentar - ele poderia reverter sua direção de animação se apenas começasse a sentar. Para aumentar o realismo, se ele passou de algum ponto crítico na animação, poderíamos optar por deixá-lo terminar de sentar e ficar de pé novamente, ou talvez fazê-lo tropeçar na pressa de reagir à ameaça.

Por mais que eu tente, não consegui encontrar orientações sobre como lidar com esse tipo de situação. Toda a literatura e vídeos que eu consumi nos últimos dias (e tem sido muito) parecem contornar esse problema. A coisa mais próxima que pude encontrar foi esse conceito de redefinir nós em execução, mas isso não dá a nós como o Sit a chance de dizer "ei, ainda não terminei!"

Pensei em talvez definindo um Preempt()ou Interrupt()método em minha base de Nodeclasse. Nós diferentes podem lidar com isso da maneira que acharem melhor, mas, neste caso, tentaríamos colocar o soldado de pé o mais rápido possível e depois voltar Success. Eu acho que essa abordagem também exigiria que minha base Nodetenha o conceito de condições separadamente para outras ações. Dessa forma, o mecanismo pode verificar apenas as condições e, se elas passarem, antecipar qualquer nó em execução no momento antes de iniciar a execução das ações. Se essa diferenciação não fosse estabelecida, o mecanismo precisaria executar nós indiscriminadamente e, portanto, poderia disparar uma nova ação antes de antecipar a execução.

Para referência, abaixo estão minhas classes base atuais. Novamente, este é um pico, por isso tentei manter as coisas o mais simples possível e adicionar complexidade apenas quando eu precisar e quando eu entender, e é com isso que estou lutando agora.

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>
{
}

Alguém tem alguma idéia que possa me orientar na direção certa? O meu pensamento está na linha certa, ou é tão ingênuo quanto eu temo?

Eu me encontrei fazendo a mesma pergunta que você e tive uma ótima conversa curta na seção de comentários desta página do blog, onde me foi fornecida outra solução do problema.

A primeira coisa é usar o nó simultâneo. Nó simultâneo é um tipo especial de nó composto. Consiste na sequência de verificações de pré-condição seguidas por um único nó de ação. Ele atualiza todos os nós filhos, mesmo que seu nó de ação esteja no estado 'running'. (Diferentemente do nó de sequência, que deve iniciar a atualização do nó filho em execução atual.)

A idéia principal é criar mais dois estados de retorno para nós de ação: "canceling" e "canceled".

A falha na verificação de pré-condição no nó simultâneo é um mecanismo que aciona o cancelamento do nó de ação em execução. Se o nó de ação não exigir lógica de cancelamento de longa execução, ele retornará 'cancelado' imediatamente. Caso contrário, ele muda para o estado 'cancelando', onde você pode colocar toda a lógica necessária para a interrupção correta da ação.

Eu acho que seu soldado pode ser decomposto em mente e corpo (e o que mais). Posteriormente, o corpo pode ser decomposto em pernas e mãos. Então, cada parte precisa de sua própria árvore de comportamento e também de uma interface pública - para solicitações de partes de nível superior ou inferior.

Então, em vez de gerenciar todas as ações, basta enviar mensagens instantâneas como "corpo, sente-se por algum tempo" ou "corpo, corra para lá", e o corpo gerenciará animações, transições de estado, atrasos e outras coisas para vocês.

Como alternativa, o corpo pode gerenciar comportamentos como esse por conta própria. Se não tiver ordens, pode perguntar "podemos sentar aqui?". Mais interessante, por causa do encapsulamento, você pode modelar facilmente recursos como cansaço ou atordoamento.

Você pode até trocar partes - fazer elefante com intelecto de zumbi, adicionar asas a humanos (ele nem notará), ou qualquer outra coisa.

Sem uma decomposição como essa, aposto que você corre o risco de encontrar uma explosão combinatória, mais cedo ou mais tarde.

Também: http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf

Deitada na cama ontem à noite, tive uma espécie de epifania sobre como eu poderia fazer isso sem introduzir a complexidade que eu estava inclinando na minha pergunta. Envolve o uso do composto "paralelo" (mal nomeado, IMHO). Aqui está o que estou pensando:

Espero que ainda seja bastante legível. Os pontos importantes são:

• a sequência Sit / Delay / Stand up é uma sequência dentro de uma sequência paralela ( A ). Em cada tick, a sequência paralela também verifica a condição de inimigo próximo (invertida). Se um inimigo estiver próximo, a condição falhará e também a sequência paralela inteira (imediatamente, mesmo se a sequência filho estiver no meio de Sentar , Atraso ou Levantar )
• em caso de falha, o seletor B acima da sequência paralela pula para dentro do seletor C para lidar com a interrupção. Importante, o seletor C não seria executado se a sequência paralela A fosse concluída com êxito
• o seletor C tenta se levantar normalmente, mas também pode acionar uma animação de tropeço se o soldado estiver atualmente em uma posição muito embaraçosa para simplesmente se levantar

Eu acho que isso vai funcionar (vou tentar em breve), apesar de ser um pouco mais confuso do que eu imaginava. O bom é que eu seria capaz de encapsular subárvores como peças reutilizáveis ​​da lógica e me referir a elas a partir de vários pontos. Isso aliviará a maior parte da minha preocupação lá, então acho que essa é uma solução viável.

Claro, eu ainda adoraria saber se alguém tem alguma opinião sobre isso.

ATUALIZAÇÃO : embora essa abordagem funcione tecnicamente, eu decidi que é sux. Isso ocorre porque as subárvores não relacionadas precisam "conhecer" as condições definidas em outras partes da árvore para que possam desencadear sua própria morte. Embora o compartilhamento de referências de subárvore possa ajudar a aliviar essa dor, ainda é contrário ao que se espera quando se olha para a árvore de comportamento. De fato, cometi o mesmo erro duas vezes em um pico muito simples.

Portanto, vou seguir a outra rota: suporte explícito para a antecipação dentro do modelo de objeto e um composto especial que permite que um conjunto diferente de ações seja executado quando ocorrer a preempção. Vou postar uma resposta separada quando houver algo funcionando.

Aqui está a solução que eu decidi por enquanto ...

• Minha Nodeclasse base possui um Interruptmétodo que, por padrão, não faz nada
• As condições são construções de "primeira classe", na medida em que precisam retornar bool(implicando que são rápidas de executar e nunca precisam de mais de uma atualização)
• Node expõe uma coleção de condições separadamente à sua coleção de nós filhos
• Node.Executeexecuta todas as condições primeiro e falha imediatamente se alguma condição falhar. Se as condições forem bem-sucedidas (ou não houverem), ele será chamado ExecuteCorepara que a subclasse possa fazer seu trabalho real. Há um parâmetro que permite ignorar condições, por razões que você verá abaixo
• Nodetambém permite que as condições sejam executadas isoladamente por meio de um CheckConditionsmétodo Obviamente, Node.Executena verdade , apenas chama CheckConditionsquando é necessário validar condições
• Meu Selectorcomposto agora chama CheckConditionscada filho que considera para execução. Se as condições falharem, ele se move diretamente para o próximo filho. Se eles passarem, verifica se já existe um filho em execução. Nesse caso, ele chama Interrupte depois falha. É tudo o que pode fazer neste momento, na esperança de que o nó atualmente em execução responda à solicitação de interrupção, o que pode ser feito ...
• Eu adicionei um Interruptiblenó, que é um tipo de decorador especial porque ele tem o fluxo regular da lógica como filho decorado e, em seguida, um nó separado para interrupções. Ele executa seu filho normal até a conclusão ou falha, desde que não seja interrompido. Se for interrompido, ele imediatamente muda para a execução de seu nó filho de manipulação de interrupções, que pode ser uma subárvore tão complexa quanto necessário

O resultado final é algo assim, tirado do meu pico:

A descrição acima é a árvore de comportamento de uma abelha, que coleta o néctar e o retorna à sua colméia. Quando não tem néctar e não está perto de uma flor que tem algum, vagueia:

Se esse nó não fosse interrompível, nunca falharia, portanto a abelha vagaria perpetuamente. No entanto, como o nó pai é um seletor e possui filhos de prioridade mais alta, sua elegibilidade para execução é constantemente verificada. Se as condições deles passarem, o seletor gera uma interrupção e a subárvore acima muda imediatamente para o caminho "Interrompido", que simplesmente falha o mais rápido possível. É claro que ele poderia executar algumas outras ações primeiro, mas meu pico realmente não tem nada a fazer além de fiança.

Para ligar isso de volta à minha pergunta, no entanto, você pode imaginar que o caminho "Interrompido" poderia tentar reverter a animação de sentar e, na sua falta, fazer o soldado tropeçar. Tudo isso atrasaria a transição para o estado de maior prioridade, e era exatamente esse o objetivo.

Eu acho que eu estou feliz com esta abordagem - especialmente as peças do núcleo I esquema acima - mas para ser honesto, é levantadas dúvidas sobre a proliferação de implementações específicas de condições e ações, e amarrar a árvore de comportamento no sistema de animação. Ainda não tenho certeza de que posso articular essas perguntas, por isso continuarei pensando.

Corrigi o mesmo problema inventando o decorador "When". Tem uma condição e dois comportamentos filhos ("then" e "else"). Quando "Quando" é executado, ele verifica a condição e, dependendo do resultado, executa então / caso contrário, filho. Se o resultado da condição for alterado, o filho em execução será redefinido e o filho correspondente a outra ramificação será iniciado. Se o filho concluir a execução, todo o "Quando" concluirá a execução.

O ponto principal é que, diferentemente do BT inicial nesta questão, em que a condição é verificada apenas no início da sequência, meu "Quando" continua verificando a condição enquanto está em execução. Portanto, a parte superior da árvore de comportamento é substituída por:

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

Para um uso mais avançado do "When", também é recomendável introduzir a ação "Wait" que simplesmente não faz nada por um período de tempo especificado ou indefinidamente (até redefinir pelo comportamento dos pais). Além disso, se você precisar de apenas um ramo de "Quando", outro poderá conter as ações "Sucesso" ou "Falha", que respeitem bem-sucedidos e falhem imediatamente.

Enquanto estou atrasado, mas espero que isso possa ajudar. Principalmente porque eu quero ter certeza de que pessoalmente não perdi algo, pois tenho tentado descobrir isso também. Eu emprestei essa ideia principalmente Unreal, mas sem torná-la uma Decoratorpropriedade em uma base Nodeou fortemente ligada à Blackboard, é mais genérica.

Isto irá introduzir um novo tipo de nó chamado Guardque é como uma combinação de um Decorator, e Compositee tem uma condition() -> Resultassinatura ao lado de umupdate() -> Result

Ele possui três modos para indicar como o cancelamento deve ocorrer quando o Guardretorno é retornado Successou Failed, na verdade, o cancelamento depende do chamador. Portanto, para uma Selectorchamada a Guard:

1. Cancelar .self -> Cancele apenas o Guard(e seu filho em execução) se estiver em execução e a condição foiFailed
2. Cancelar .lower-> Cancele apenas os nós de prioridade mais baixa se estiverem em execução e a condição foi SuccessouRunning
3. Cancelar .both -> Ambos .selfe .lowerdependendo das condições e dos nós em execução. Você deseja cancelar a si mesmo se estiver em execução e condicionar falseou cancelar o nó em execução se eles forem considerados de menor prioridade com base na Compositeregra ( Selectorno nosso caso) se a condição for Success. Em outras palavras, são basicamente os dois conceitos combinados.

Como Decoratore ao contrário, Compositeé preciso apenas um filho.

Apesar de Guardter apenas um filho único, você pode aninhar como muitos Sequences, Selectorsou outros tipos Nodescomo você desejar, incluindo outro Guardsou Decorators.

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

No cenário acima, sempre que houver Selector1atualizações, ele sempre executará verificações de condições nos protetores associados a seus filhos. No caso acima, Sequence1é Guardado e precisa ser verificado antes de Selector1continuar com as runningtarefas.

Sempre que Selector2ou Sequence1está em execução, logo que EnemyNear?retorna successdurante uma Guards condition()verificação, em seguida, Selector1irá emitir uma interrupção / cancelar a running nodee depois continuar como de costume.

Em outras palavras, podemos reagir a ramificações "inativas" ou "atacadas" com base em algumas condições, tornando o comportamento muito mais reativo do que se decidíssemos Parallel

Isso também permite proteger as pessoas Nodecom prioridade mais alta contra a execução Nodesno mesmoComposite

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

Se HumATunea execução for longa Node, Selector2sempre a verificará primeiro, se não fosse pela Guard. Portanto, se o npc for teleportado para um trecho de grama, da próxima vez que for Selector2executado, ele verificará Guarde cancelará HumATunepara executarIdle

Se for teleportado para fora da grama, ele cancelará o nó em execução ( Idle) e passará paraHumATune

Como você vê aqui, a tomada de decisão depende do chamador Guarde não do Guardpróprio. As regras de quem é considerado lower prioritypermanecem com o chamador. Nos dois exemplos, é Selectorquem define o que constitui como a lower priority.

Se você tivesse Compositechamado Random Selector, então você definiria as regras na implementação desse específico Composite.