BehaviourTree - простая реализация деревьев поведений

Размещено

Деревья поведений (BehaviourTree) - довольно часто используемый подход для построения логики поведения ботов. Существует много комплексных решений, предоставляющих визуальное построение, отладку, плотную интеграцию в какой-то движок. Но что, если все это излишне и требуется минимальный размер, простота сборки, скорость работы и возможность работать на сервере без движка?

В общем случае Деревья состоят из узлов (Node), собирающихся в иерархию по определенным правилам. В каждый момент времени выполняется только один узел, затем происходит переход к следующему на основе результатов работы текущего - Дерево является по сути конечным автоматом (FSM - Finite State Machine), способным обрабатывать входящие данные и переключать внутренние состояния на их основе. Можно рассматривать Дерево как блок-схему работы какого-то алгоритма обработки данных.

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

Примеры типов узлов, встречающихся практически во всех реализациях Деревьев:

  • Пользовательский код - обертка над кодом, который должен выполниться в определенном месте работы Дерева.
  • Условное ветвление - аналог “if A then B else C” - если условие A верно - можно переходить к B, иначе к C.
  • Отрицание - инверсия результата работы: был успех, станет провал и наоборот.
  • Альтернативный выбор - аналог “switch { case A then B; case C then D; }” - набор пар “условие”/“обработчик”, выполняющегося в случае срабатывания условия.
  • Последовательность - цепочка-список узлов, выполняющихся последовательно друг за другом.
  • Цикл - аналог “while A do B” - повторять выполнение B пока условие A верно.

Пакет Leopotam.Ai.Bt реализует все перечисленное и предлагает сборку Дерева из кода. Давайте соберем следующее дерево:

1
2
3
4
5
6
7
sequence:
    action1
    action2
    if condition:
        action3
    else:
        action4

Его реализация может выглядеть примерно так:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// Данные, которые будем обрабатывать.
class Data {
    public int Counter;
}
// Вспомогательный тип, сокращающий
// количество кода для описания дерева.
BtNodes<Data> bt;

// Собираем дерево. Корневым элементом
// будет Seq - "последовательность".
var root = bt.Seq (
    // Пользовательский код
    // может быть в виде лямбд.
    bt.Act ((d) => {
        d.Counter = 12;
        return BtResult.True;
    }),
    // А может и в виде внешних методов.
    bt.Act (OnAct1)
    // "Условие" принимает 3 узла.
    bt.If (
        // Узел проверки условия.
        bt.Act (OnIfCheck),
        // Узел успеха проверки.
        bt.Act (OnIfTrue),
        // Узел провала проверки.
        bt.Act (OnIfFalse)
    )
);
// Дерево собрано, можно его запускать.
Data data = new ();
BtResult res = root.Run (data);
// Результаты:
// res = BtResult.True.
// data.Counter = 78.

// Обработчики.
BtResult OnAct1 (Data d) {
    d.Counter = 34;
    return BtResult.True;
}
BtResult OnIfCheck (Data d) {
    return d.Counter > 123 ? BtResult.True : BtResult.False;
}
BtResult OnIfTrue (Data d) {
    d.Counter = 56;
    return BtResult.True;
}
BtResult OnIfFalse(Data d) {
    d.Counter = 78;
    return BtResult.True;
}

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

Реализация в пакете Leopotam.Ai.Bt дает возможность разделения обработки узла на несколько кадров с автоматическим продолжением с места остановки, а так же поддерживает реализацию своих типов узлов в случае необходимости.

Актуальные версии пакетов доступны в GitVerse.