Arbres de comportement préemptifs

J'essaie de me familiariser avec les arbres de comportement, alors j'enrichis du code de test. Une chose avec laquelle je me bats est de savoir comment préempter un nœud en cours d'exécution lorsque quelque chose de priorité plus élevée se présente.

Considérez l'arbre de comportement simple et fictif suivant pour un soldat:

Supposons qu'un certain nombre de tiques se soient écoulées et qu'il n'y avait pas d'ennemi à proximité, le soldat se tenait sur l'herbe, donc le nœud S'asseoir est sélectionné pour l'exécution:

L' action S'asseoir prend maintenant du temps à exécuter car il y a une animation à jouer, elle revient donc Runningcomme son statut. Une ou deux tiques passent, l'animation est toujours en cours, mais l' ennemi est-il proche? déclencheurs de noeud de condition. Maintenant, nous devons préempter le nœud Sit as ASAP afin que nous puissions exécuter le nœud Attack . Idéalement, le soldat ne finirait même pas de s'asseoir - il pourrait plutôt inverser sa direction d'animation s'il commençait juste à s'asseoir. Pour plus de réalisme, s'il a dépassé un certain point de basculement dans l'animation, nous pourrions plutôt choisir de le laisser finir de s'asseoir puis de se relever, ou peut-être de le faire trébucher dans sa hâte de réagir à la menace.

J'ai beau essayer, je n'ai pas pu trouver de conseils sur la façon de gérer ce genre de situation. Toute la littérature et les vidéos que j'ai consommées ces derniers jours (et ça fait beaucoup) semblent contourner ce problème. La chose la plus proche que j'ai pu trouver est ce concept de réinitialisation des nœuds en cours d'exécution, mais cela ne donne pas aux nœuds comme Sit Down une chance de dire "hé, je n'ai pas encore fini!"

J'ai pensé à définir peut-être une méthode Preempt()ou Interrupt()sur ma Nodeclasse de base . Différents nœuds peuvent le gérer comme bon leur semble, mais dans ce cas, nous essayons de remettre le soldat sur ses pieds dès que possible, puis de revenir Success. Je pense que cette approche exigerait également que ma base Nodeait le concept de conditions séparément des autres actions. De cette façon, le moteur ne peut vérifier que les conditions et, si elles réussissent, préempter tout nœud en cours d'exécution avant de démarrer l'exécution des actions. Si cette différenciation n'était pas établie, le moteur devrait exécuter les nœuds sans discernement et pourrait donc déclencher une nouvelle action avant de préempter celle en cours d'exécution.

Pour référence, voici mes classes de base actuelles. Encore une fois, c'est un pic, j'ai donc essayé de garder les choses aussi simples que possible et d'ajouter de la complexité uniquement lorsque j'en ai besoin et quand je le comprends, ce avec quoi je me bats en ce moment.

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

Quelqu'un at-il une idée qui pourrait m'orienter dans la bonne direction? Est-ce que ma pensée va dans le bon sens, ou est-ce aussi naïf que je le crains?

Je me suis retrouvé à poser la même question que vous et j'ai eu une très courte conversation dans la section des commentaires de cette page de blog où on m'a proposé une autre solution du problème.

La première chose est d'utiliser un nœud simultané. Le nœud simultané est un type spécial de nœud composite. Il consiste en une séquence de vérifications de précondition suivie d'un nœud d'action unique. Il met à jour tous les nœuds enfants même si son nœud d'action est en état «en cours d'exécution». (Contrairement au nœud de séquence qui doit démarrer sa mise à jour à partir du nœud enfant en cours d'exécution.)

L'idée principale est de créer deux autres états de retour pour les nœuds d'action: "annuler" et "annulé".

L'échec de la vérification des conditions préalables dans le nœud simultané est un mécanisme qui déclenche l'annulation de son nœud d'action en cours d'exécution. Si le nœud d'action ne nécessite pas de logique d'annulation de longue durée, il retournera immédiatement «annulé». Sinon, il passe à l'état «d'annulation» où vous pouvez mettre toute la logique nécessaire pour une interruption correcte de l'action.

Je pense que votre soldat peut être décomposé dans l'esprit et le corps (et quoi que ce soit d'autre). Par la suite, le corps peut être décomposé en jambes et mains. Ensuite, chaque partie a besoin de son propre arbre de comportement, ainsi que d'une interface publique - pour les demandes des parties de niveau supérieur ou inférieur.

Donc, au lieu de micro-gérer chaque action, vous envoyez simplement des messages instantanés comme "corps, asseyez-vous pendant un certain temps" ou "corps, courez là", et le corps gérera les animations, les transitions d'état, les retards et autres choses pour toi.

Alternativement, le corps peut gérer lui-même des comportements comme celui-ci. S'il n'a pas d'ordre, il peut se demander: «pouvons-nous nous asseoir ici?». Plus intéressant, en raison de l'encapsulation, vous pouvez facilement modéliser des fonctionnalités telles que la fatigue ou l'étourdissement.

Vous pouvez même échanger des pièces - faire un éléphant avec l'intellect d'un zombie, ajouter des ailes à l'homme (il ne le remarquera même pas), ou autre chose.

Sans une telle décomposition, je parie que vous risquez de rencontrer tôt ou tard une explosion combinatoire.

Aussi: http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf

Couché dans mon lit la nuit dernière, j'ai eu une sorte d'épiphanie sur la façon dont je pourrais procéder sans introduire la complexité vers laquelle je me penchais dans ma question. Elle implique l'utilisation du composite (mal nommé, à mon humble avis) "parallèle". Voici ce que je pense:

J'espère que c'est encore assez lisible. Les points importants sont:

• la séquence assis / retard / debout est une séquence dans une séquence parallèle ( A ). À chaque tick, la séquence parallèle vérifie également l' état proche de l' ennemi (inversé). Si un ennemi est proche, la condition échoue, de même que toute la séquence parallèle (immédiatement, même si la séquence enfant est à mi-chemin de la position assise , retardée ou debout ).
• en cas d'échec, le sélecteur B au-dessus de la séquence parallèle sautera dans le sélecteur C pour gérer l'interruption. Surtout, le sélecteur C ne s'exécuterait pas si la séquence parallèle A se terminait avec succès
• le sélecteur C essaie alors de se lever normalement, mais peut également déclencher une animation de trébuchement si le soldat est actuellement dans une position trop maladroite pour simplement se lever

Je pense que cela fonctionnera (je vais l'essayer dans mon pic bientôt), malgré le fait qu'il soit un peu plus compliqué que ce que j'avais prévu. La bonne chose est que je serais finalement en mesure d'encapsuler des sous-arbres comme des éléments de logique réutilisables et de les référencer à partir de plusieurs points. Cela apaisera la plupart de mes préoccupations là-bas, donc je pense que c'est une solution viable.

Bien sûr, j'aimerais toujours savoir si quelqu'un a des idées à ce sujet.

MISE À JOUR : bien que cette approche fonctionne techniquement, je l'ai décidé sux. En effet, les sous-arbres indépendants doivent "connaître" les conditions définies dans d'autres parties de l'arbre pour pouvoir déclencher leur propre disparition. Bien que le partage de références de sous-arbre permettrait de soulager cette douleur, c'est toujours contraire à ce que l'on attend en regardant l'arbre de comportement. En effet, j'ai fait deux fois la même erreur sur un pic très simple.

Par conséquent, je vais emprunter l'autre voie: la prise en charge explicite de la préemption dans le modèle objet et un composite spécial qui permet à un ensemble différent d'actions de s'exécuter lorsque la préemption se produit. Je posterai une réponse séparée lorsque j'aurai quelque chose qui fonctionne.

Voici la solution sur laquelle je me suis installé pour l'instant ...

• Ma Nodeclasse de base a une Interruptméthode qui, par défaut, ne fait rien
• Les conditions sont des constructions de "première classe", en ce sens qu'elles doivent être retournées bool(ce qui implique qu'elles sont rapides à exécuter et n'ont jamais besoin de plus d'une mise à jour)
• Node expose une collection de conditions séparément à sa collection de nœuds enfants
• Node.Executeexécute toutes les conditions en premier et échoue immédiatement si une condition échoue. Si les conditions réussissent (ou s'il n'y en a pas), il appelleExecuteCore pour que la sous-classe puisse faire son travail réel. Il y a un paramètre qui permet de sauter des conditions, pour les raisons que vous verrez ci-dessous
• Nodepermet également d'exécuter des conditions de manière isolée via une CheckConditionsméthode. Bien sûr, en Node.Executefait, il appelle juste CheckConditionsquand il a besoin de valider les conditions
• Mon Selectorcomposite appelle désormais CheckConditionschaque enfant qu'il envisage d'exécuter. Si les conditions échouent, il se déplace directement vers l'enfant suivant. S'ils réussissent, il vérifie s'il existe déjà un enfant en cours d'exécution. Si c'est le cas, il appelle Interruptpuis échoue. C'est tout ce qu'il peut faire à ce stade, dans l'espoir que le nœud en cours d'exécution répondra à la demande d'interruption, ce qu'il peut faire en ...
• J'ai ajouté un Interruptiblenœud, qui est une sorte de décorateur spécial car il a le flux de logique régulier en tant qu'enfant décoré, puis un nœud séparé pour les interruptions. Il exécute son enfant normal jusqu'à la fin ou l'échec tant qu'il n'est pas interrompu. S'il est interrompu, il passe immédiatement à l'exécution de son nœud enfant de gestion des interruptions, qui pourrait être une sous-arborescence aussi complexe que nécessaire.

Le résultat final est quelque chose comme ça, tiré de mon pic:

Ce qui précède est l'arbre de comportement d'une abeille, qui recueille le nectar et le retourne dans sa ruche. Quand il n'a pas de nectar et n'est pas près d'une fleur qui en a, il erre:

Si ce nœud n'était pas interruptible, il n'échouerait jamais, donc l'abeille errerait perpétuellement. Cependant, comme le nœud parent est un sélecteur et qu'il a des enfants de priorité plus élevée, leur éligibilité à l'exécution est constamment vérifiée. Si leurs conditions sont remplies, le sélecteur déclenche une interruption et la sous-arborescence ci-dessus bascule immédiatement sur le chemin "Interrompu", qui purge simplement ASAP en échouant. Il pourrait, bien sûr, effectuer d'autres actions en premier, mais ma pointe n'a vraiment rien d'autre à faire que la mise en liberté sous caution.

Pour relier cela à ma question, cependant, vous pourriez imaginer que le chemin "Interrompu" pourrait tenter d'inverser l'animation assise et, à défaut, faire trébucher le soldat. Tout cela retarderait la transition vers l'état de priorité plus élevée, et c'est précisément l'objectif recherché.

Je pense que je suis satisfait de cette approche - en particulier les éléments de base que je décris ci-dessus - mais pour être honnête, cela a soulevé de nouvelles questions sur la prolifération de mises en œuvre spécifiques de conditions et d'actions, et de lier l'arbre de comportement au système d'animation. Je ne suis même pas sûr de pouvoir articuler ces questions pour le moment, alors je continuerai à penser / à augmenter.

J'ai corrigé le même problème en inventant le décorateur "Quand". Il a une condition et deux comportements enfant ("alors" et "sinon"). Lorsque "Quand" est exécuté, il vérifie la condition et en fonction de son résultat, s'exécute alors / sinon enfant. Si le résultat de la condition change, l'enfant en cours d'exécution est réinitialisé et l'enfant correspondant à une autre branche est démarré. Si l'enfant termine l'exécution, "Quand" entier termine l'exécution.

Le point clé est que, contrairement au BT initial dans cette question où la condition est vérifiée uniquement au début de la séquence, mon "Quand" continue de vérifier la condition pendant son exécution. Ainsi, le haut de l'arbre de comportement est remplacé par:

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

Pour une utilisation plus avancée de «Quand», on voudrait également introduire une action «Attendre» qui ne fait tout simplement rien pendant une durée spécifiée ou indéfiniment (jusqu'à ce qu'elle soit réinitialisée par le comportement parent). De plus, si vous n'avez besoin que d'une branche de "Quand", une autre peut contenir des actions "Succès" ou "Echec", qui respectivement réussissent et échouent immédiatement.

Bien que je sois en retard, mais j'espère que cela peut vous aider. Surtout parce que je veux m'assurer que je n'ai personnellement pas raté quelque chose moi-même, car j'ai également essayé de comprendre cela. J'ai principalement emprunté cette idée à Unreal, mais sans en faire une Decoratorpropriété sur une base Nodeou fortement liée à la Blackboard, c'est plus générique.

Cela introduira un nouveau type de nœud appelé Guardqui est comme une combinaison de a Decorator, Compositeet a une condition() -> Resultsignature à côté d'unupdate() -> Result

Il a trois modes pour indiquer comment l'annulation doit se produire lors du Guardretour Successou Failed, l'annulation réelle dépend de l'appelant. Donc pour un Selectorappel Guard:

1. Annuler .self -> Annuler uniquement le Guard(et son enfant en cours d'exécution) s'il est en cours d'exécution et que la condition étaitFailed
2. Annuler .lower-> Annuler uniquement les nœuds de priorité inférieure s'ils sont en cours d'exécution et que la condition était SuccessouRunning
3. Annuler .both -> Les deux .selfet .lowerselon les conditions et les nœuds en cours d'exécution. Vous souhaitez vous annuler si son fonctionnement est en cours et conditionner falseou annuler le nœud en cours d'exécution s'il est considéré comme une priorité inférieure en fonction de la Compositerègle ( Selectordans notre cas) si la condition est Success. En d'autres termes, il s'agit essentiellement des deux concepts combinés.

Comme Decoratoret contrairement à Compositecela, il ne prend qu'un seul enfant.

Bien Guardprendre qu'un seul enfant, vous pouvez imbriquer autant Sequences, Selectorsou d' autres types Nodesque vous voulez, y compris d' autres Guardsou Decorators.

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

Dans le scénario ci-dessus, chaque fois qu'il est mis à Selector1jour, il exécute toujours des vérifications de condition sur les gardes associés à ses enfants. Dans le cas ci-dessus, Sequence1est Gardé et doit être vérifié avant de Selector1poursuivre les runningtâches.

Chaque fois que Selector2ou Sequence1est en cours d'exécution dès les EnemyNear?retours successlors d'un Guards condition()contrôle, puis Selector1émettra une interruption / annulation à la running nodepuis continuer comme d'habitude.

En d'autres termes, nous pouvons réagir à une branche "inactive" ou "d'attaque" en fonction de quelques conditions, ce qui rend le comportement beaucoup plus réactif que si nous nous installions Parallel

Cela vous permet également de protéger les personnes Nodequi ont une priorité plus élevée contre l'exécution Nodesdans le mêmeComposite

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

Si HumATunec'est un long terme Node, Selector2vérifiera toujours celui-ci en premier si ce n'était pas pour le Guard. Donc, si le PNJ s'est téléporté sur une parcelle d'herbe, la prochaine fois Selector2, il vérifiera Guardet annulera HumATunepour fonctionnerIdle

S'il se téléporte hors de l'herbe, il annulera le nœud en cours d'exécution ( Idle) et se déplaceraHumATune

Comme vous le voyez ici, la prise de décision repose sur l'appelant Guardet non sur Guardlui - même. Les règles de qui est considéré comme étant lower priorityrestent avec l'appelant. Dans les deux exemples, c'est Selectorqui définit ce qui constitue un lower priority.

Si vous aviez un Compositeappelé Random Selector, alors vous auriez à définir les règles dans la mise en œuvre de ce spécifique Composite.