Вытесняющие Поведенческие Деревья

Я пытаюсь разобраться с деревьями поведения, поэтому выкручиваю тестовый код. Одна вещь, с которой я борюсь, это как выгрузить текущий работающий узел, когда появляется что-то с более высоким приоритетом.

Рассмотрим следующее простое, вымышленное дерево поведения для солдата:

Предположим, что какое-то количество тиков прошло, а поблизости нет врагов, солдат стоял на траве, поэтому для выполнения выбран узел Sit down :

Теперь для выполнения действия Sit down требуется время, поскольку анимация воспроизводится, поэтому она возвращается в Runningкачестве своего состояния. Проходит один или два тика, анимация все еще работает, но Враг рядом? условие узла срабатывает. Теперь нам нужно выгрузить узел Sit down как можно скорее, чтобы мы могли выполнить узел Attack . В идеале солдат даже не успел бы сесть - вместо этого он мог бы изменить направление анимации, если бы только начал сидеть. Для дополнительного реализма, если он преодолел какой-то переломный момент в анимации, мы могли бы вместо этого выбрать, чтобы он закончил сесть, а затем снова встал, или, возможно, он споткнулся в своей спешке, чтобы отреагировать на угрозу.

Как ни старайся, мне не удалось найти руководство, как справиться с такой ситуацией. Вся литература и видео, которые я употреблял за последние несколько дней (и их было много), кажется, обошли вокруг этой проблемы. Самая близкая вещь, которую я смог найти, - это концепция сброса работающих узлов, но это не дает таким узлам, как Sit down, возможность сказать «эй, я еще не закончил!»

Я подумал о том, чтобы определить метод Preempt()или Interrupt()в моем базовом Nodeклассе. Разные узлы могут справиться с этим так, как считают нужным, но в этом случае мы попытаемся вернуть солдата на ноги как можно скорее, а затем вернуться Success. Я думаю, что этот подход также потребовал бы, чтобы моя база Nodeимела концепцию условий отдельно от других действий. Таким образом, механизм может проверять только условия и, если они пройдут, выгрузить любой выполняющийся в данный момент узел перед началом выполнения действий. Если это разграничение не было установлено, движок должен будет выполнять узлы без разбора и, следовательно, может инициировать новое действие, прежде чем прервать работающее.

Для справки ниже приведены мои текущие базовые классы. Опять же, это всплеск, поэтому я попытался сделать вещи максимально простыми и добавить сложность только тогда, когда мне это нужно, и когда я это понимаю, с чем я сейчас борюсь.

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

Есть ли у кого-нибудь понимание, которое может направить меня в правильном направлении? Мое мышление в правильном направлении, или это так наивно, как я боюсь?

Я обнаружил, что задаю тот же вопрос, что и вы, и у меня был отличный короткий разговор в разделе комментариев на этой странице блога, где мне было предоставлено другое решение проблемы.

Первое, что нужно использовать параллельный узел. Параллельный узел - это особый тип составного узла. Он состоит из последовательности проверок предварительных условий, за которыми следует один узел действия. Он обновляет все дочерние узлы, даже если его узел действия находится в состоянии «выполняется». (В отличие от узла последовательности, который должен начать обновление с текущего запущенного дочернего узла.)

Основная идея заключается в создании еще двух возвращаемых состояний для узлов действия: «отмена» и «отмена».

Отказ проверки предварительных условий в параллельном узле - это механизм, который инициирует отмену запущенного узла действия. Если узел действия не требует длительной логики отмены, он немедленно вернет «отменено». В противном случае он переключается в состояние «отмены», где вы можете поместить всю необходимую логику для правильного прерывания действия.

Я думаю, что ваш солдат может быть разложен на разум и тело (и все остальное). Впоследствии тело может быть разложено на ноги и руки. Затем каждая часть нуждается в своем собственном дереве поведения, а также в открытом интерфейсе - для запросов от частей более высокого или более низкого уровня.

Таким образом, вместо микроуправления каждым действием вы просто отправляете мгновенные сообщения типа «тело, сядьте на некоторое время» или «тело, бегите туда», а тело будет управлять анимацией, переходами состояний, задержками и другими вещами для ты.

Кроме того, тело может управлять таким поведением самостоятельно. Если у него нет заказов, он может спросить ум: «Можем ли мы сидеть здесь?». Что еще интереснее, из-за инкапсуляции вы можете легко моделировать такие функции, как усталость или оглушение.

Вы можете даже поменяться частями - сделать слона с интеллектом зомби, добавить крылья человеку (он даже не заметит) или что-то еще.

Без такого разложения, держу пари, вы рискуете встретить комбинаторный взрыв, рано или поздно.

Также: http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf

Лежа в постели прошлой ночью, у меня было что-то вроде прозрения о том, как я могу это сделать, не представляя сложности, к которой я склонялся в своем вопросе. Он предполагает использование (плохо названного, IMHO) «параллельного» композита. Вот что я думаю:

Надеюсь, это все еще довольно читабельно. Важными моментами являются:

• Сядьте / Delay / Stand-up - это последовательность в параллельной последовательности ( A ). На каждом тике параллельная последовательность также проверяет состояние ближнего врага (инвертировано). Если враг находится рядом, то условие не выполняется и поэтому тоже делает всю последовательность параллельной (немедленно, даже если последовательность ребенка в середине присесть , задержка или Встаньте )
• в случае неудачи селектор B над параллельной последовательностью переместится в селектор C для обработки прерывания. Важно отметить, что селектор C не будет работать, если параллельная последовательность A завершена успешно
• Затем селектор C пытается встать в обычном режиме, но может также запустить анимацию спотыкания, если солдат в настоящее время находится в слишком неудобном положении, чтобы просто встать

Я думаю, что это сработает (я собираюсь попробовать это в моем спайке в ближайшее время), несмотря на то, что это было немного более грязно, чем я предполагал. Хорошо, что в конечном итоге я смог бы инкапсулировать поддеревья как куски логики многократного использования и ссылаться на них из разных точек. Это снимет большую часть моей озабоченности, поэтому я думаю, что это жизнеспособное решение.

Конечно, я все еще хотел бы услышать, есть ли у кого-нибудь какие-либо мысли по этому поводу.

ОБНОВЛЕНИЕ : хотя этот подход технически работает, я решил, что это достаточно. Это потому, что несвязанные поддеревья должны «знать» об условиях, определенных в других частях дерева, чтобы они могли инициировать свою гибель. Хотя обмен ссылками на поддеревья мог бы облегчить эту боль, он все равно противоречит тому, что можно ожидать, глядя на дерево поведения. Действительно, я дважды совершил одну и ту же ошибку на очень простом скачке.

Поэтому я собираюсь пойти по другому пути: явная поддержка вытеснения внутри объектной модели и специальный композит, который позволяет выполнять другой набор действий при выполнении вытеснения. Я выложу отдельный ответ, когда у меня что-то будет работать.

Вот решение, на котором я остановился сейчас ...

• В моем базовом Nodeклассе есть Interruptметод, который по умолчанию ничего не делает
• Условия являются конструкциями «первого класса» в том смысле, что они должны возвращаться bool(что означает, что они выполняются быстро и никогда не требуют более одного обновления)
• Node выставляет коллекцию условий отдельно к своей коллекции дочерних узлов
• Node.Executeсначала выполняет все условия и сразу завершается неудачей, если какое-либо условие не выполняется. Если условия успешны (или их нет), он вызывает, ExecuteCoreчтобы подкласс мог выполнять свою реальную работу. Существует параметр, позволяющий пропускать условия по причинам, которые вы увидите ниже.
• Nodeтакже позволяет выполнять условия изолированно с помощью CheckConditionsметода. Конечно, на Node.Executeсамом деле просто звонки, CheckConditionsкогда нужно проверить условия
• Мой Selectorкомпозит сейчас звонитCheckConditions к каждому дочернему элементу, которого считает нужным. Если условия не выполняются, он перемещается прямо к следующему ребенку. Если они проходят, он проверяет, есть ли уже исполняющий дочерний элемент. Если это так, он звонит, Interruptа затем терпит неудачу. Это все, что он может сделать на данный момент, в надежде, что текущий работающий узел ответит на запрос прерывания, что он может сделать с помощью ...
• Я добавил Interruptibleузел, который является своего рода специальным декоратором, потому что он имеет регулярный поток логики в качестве своего оформленного потомка, а затем отдельный узел для прерываний. Он выполняет свой обычный дочерний элемент до завершения или сбоя, если он не прерывается. Если он прерван, он немедленно переключается на выполнение дочернего узла обработки прерываний, который может быть настолько сложным поддеревом, насколько требуется

Конечный результат примерно такой, взятый из моего спайка:

Выше приведено дерево поведения для пчелы, которая собирает нектар и возвращает его в улей. Когда он не имеет нектара и не находится рядом с цветком, он бродит:

Если этот узел не будет прерываемым, он никогда не выйдет из строя, поэтому пчела будет постоянно блуждать. Однако, поскольку родительский узел является селектором и имеет дочерние объекты с более высоким приоритетом, их право на выполнение постоянно проверяется. Если их условия выполняются, селектор вызывает прерывание, и поддерево выше сразу переключается на путь «Прерванный», который просто сбрасывает ASAP в случае сбоя. Конечно, он мог бы сначала выполнить некоторые другие действия, но мой шип на самом деле не имеет ничего общего, кроме залога.

Чтобы связать это с моим вопросом, вы можете себе представить, что «прерванный» путь может попытаться обратить вспять сидячую анимацию и, если это не удастся, заставить солдата спотыкаться. Все это задержало бы переход к более высокоприоритетному состоянию, и именно это и было целью.

Я думаю, что я доволен этим подходом - особенно основными частями, которые я обрисовал выше - но, честно говоря, он поднимает дополнительные вопросы о распространении конкретных реализаций условий и действий и привязке дерева поведения к системе анимации. Я даже не уверен, что смогу сформулировать эти вопросы еще, поэтому я буду продолжать думать.

Я исправил эту проблему, придумав декоратор «Когда». У него есть условие и два дочерних поведения («тогда» и «иначе»). Когда выполняется «Когда», он проверяет условие и, в зависимости от своего результата, запускает то / иное потомство. Если результат условия изменяется, работающий дочерний элемент сбрасывается, и дочерний элемент, соответствующий другой ветви, запускается. Если дочерний элемент заканчивает выполнение, целое «Когда» завершает выполнение.

Ключевым моментом является то, что в отличие от исходного BT в этом вопросе, где условие проверяется только в начале последовательности, мое «Когда» продолжает проверять условие, пока оно выполняется. Итак, вершина дерева поведения заменяется на:

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

Для более сложного использования «Когда», можно также ввести действие «Ожидание», которое просто ничего не делает в течение определенного периода времени или неопределенно (до сброса родительским поведением). Кроме того, если вам нужна только одна ветвь «Когда», другая может содержать действия «Успешно» или «Неудачно», которые соответственно завершаются успешно и сразу же завершаются неудачей.

Пока я опаздываю, но надеюсь, это поможет. Главным образом потому, что я хочу удостовериться, что лично я что-то не пропустил, поскольку я тоже пытался это выяснить. Я по большей части заимствовал эту идею Unreal, но не сделал ее Decoratorсобственностью на базе Nodeили сильно привязанной кBlackboard ней, она более общая.

Это введет новый тип узла с именем, Guardкоторый похож на комбинацию Decorator, и Compositeи имеетcondition() -> Result подпись рядом сupdate() -> Result

Он имеет три режима, чтобы указать, как отмена должна происходить, когда Guard возврате Successили Failed, фактически, отмена зависит от звонящего. Итак, для Selectorвызова Guard:

1. Отмена .self -> Только отменитьGuard (и его работающий дочерний элемент), только если он работает и условие былоFailed
2. Отмена .lower-> Отменить узлы с более низким приоритетом, только если они работают и условие былоSuccess илиRunning
3. Отмена .both -> Оба .selfи в .lowerзависимости от условий и запущенных узлов. Вы хотите отменить себя, если он работает и будет условие дляfalse что он работает или будет отменен, если они считаются более низкими приоритетами на основе Compositeправила ( Selectorв нашем случае), если условие выполнено Success. Другими словами, это в основном обе концепции вместе взятые.

Как Decoratorи в отличиеComposite него требуется только один ребенок.

Несмотря Guardна то, что вы берете только одного ребенка, вы можете вкладывать столько Sequences, сколько хотите, Selectorsили другие типы Nodes, включая другие GuardsилиDecorators .

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

В приведенном выше сценарии при каждом Selector1обновлении он всегда запускает проверки состояния на элементах защиты, связанных с его потомками. В случае выше, Sequence1охраняется и должен быть проверен, прежде чем Selector1продолжить сrunning задачами.

Всякий раз, когда Selector2или Sequence1работает, как только EnemyNear?вернется successво время Guards condition()проверки, Selector1будет выдавать прерывание / отмена дляrunning node и затем продолжит как обычно.

Другими словами, мы можем реагировать на ветку «бездействия» или «атаки», основываясь на нескольких условиях, что делает поведение гораздо более реактивным, чем если бы мы остановились на Parallel

Это также позволяет вам защищать одиночные, Nodeкоторые имеют более высокий приоритет, от запуска Nodesв том жеComposite

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

Если HumATuneэто длительный период Node, Selector2всегда сначала проверяйте его, если не для Guard. Так что, если NPC телепортируется на патч травы, при следующем Selector2запуске он проверитGuard и отменитHumATune запуске для запускаIdle

Если он телепортируется из патча травы, он отменяет работающий узел (Idle ) и перемещается вHumATune

Как вы видите здесь, принятие решений зависит от вызывающего, Guardа не от Guardсамого себя. Правила того, кем считается, lower priorityостается с вызывающей стороной. В обоих примерах это Selectorкто определяет, что представляет собойlower priority .

Если бы у вас был Compositeвызов Random Selector, то вы могли бы определить правила в рамках реализации этого конкретного Composite.