Дерева поведінки для ШІ NPC — проєктування, тик і дошка

1. Чому FSM не справляються

Скінченний автомат (FSM) моделює ШІ як граф: вузли — це стани, ребра — переходи. Це працює для простих персонажів, але швидко погіршується:

• Вибух станів: N видів поведінки потребують O(N²) переходів, щоб охопити кожен шлях від стану до стану.
• Жодного повторного використання: не можна легко поділитися логікою «відступити до укриття за низького здоров'я» між піхотинцем і магом — кожен FSM кодує її окремо.
• Важко розставляти пріоритети: що має робити NPC, коли одночасно «мало набоїв» І «помічено ворога» І «поранений»? Пріоритет FSM неявно закладений у порядку ребер, його важко проаналізувати.

2. Чотири основні типи вузлів

3. Протокол тику та потік статусів

4. Дошка — спільна пам'ять

Дошка (Blackboard) — це спільне сховище ключ-значення, яке роз'єднує сприйняття, міркування та дію. Вузли читають і записують дошку замість того, щоб викликати одне одного безпосередньо.

5. Декоратори та повторне використання піддерев

6. BT проти FSM — компроміси проєктування

7. Рушій дерева поведінки на JavaScript

// Мінімальний синхронний рушій дерева поведінки
const Status = Object.freeze({ SUCCESS: 'S', FAILURE: 'F', RUNNING: 'R' });

class Sequence {
  constructor(...children) { this.children = children; }
  tick(bb) {
    for (const c of this.children) {
      const s = c.tick(bb);
      if (s !== Status.SUCCESS) return s;
    }
    return Status.SUCCESS;
  }
}

class Selector {
  constructor(...children) { this.children = children; }
  tick(bb) {
    for (const c of this.children) {
      const s = c.tick(bb);
      if (s !== Status.FAILURE) return s;
    }
    return Status.FAILURE;
  }
}

class Action {
  constructor(fn) { this.fn = fn; }
  tick(bb) { return this.fn(bb); }
}

class Condition {
  constructor(pred) { this.pred = pred; }
  tick(bb) { return this.pred(bb) ? Status.SUCCESS : Status.FAILURE; }
}

class Inverter {
  constructor(child) { this.child = child; }
  tick(bb) {
    const s = this.child.tick(bb);
    if (s === Status.SUCCESS) return Status.FAILURE;
    if (s === Status.FAILURE) return Status.SUCCESS;
    return Status.RUNNING;
  }
}

class Blackboard {
  constructor() { this.data = {}; }
  set(k, v) { this.data[k] = v; }
  get(k) { return this.data[k]; }
  has(k) { return k in this.data; }
}

// Приклад: дерево NPC-вартового
const tree = new Selector(
  new Sequence(
    new Condition(bb => bb.get('enemy_visible')),
    new Action(bb => { console.log('Chasing enemy'); return Status.RUNNING; })
  ),
  new Sequence(
    new Condition(bb => bb.get('noise_heard')),
    new Action(bb => { console.log('Investigating'); return Status.SUCCESS; })
  ),
  new Action(bb => { console.log('Patrolling'); return Status.RUNNING; })
);

const bb = new Blackboard();
bb.set('enemy_visible', false);
bb.set('noise_heard', true);
tree.tick(bb);  // → "Investigating" (Розслідування)

8. Паралельні вузли, подієво-орієнтовані BT та гібриди HFSM

• Паралельний вузол: тикає всіх нащадків одночасно. Параметризується порогами успіху/невдачі — наприклад, успіх, якщо ≥1 нащадок успішний, невдача, якщо всі зазнають невдачі. Корисний для одночасної перевірки здоров'я та близькості під час руху.
• Подієво-орієнтовані BT: замість опитування умов щотику спостерігачі підписуються на події світу. Коли подія спрацьовує, дерево переоцінюється від ураженого вузла вгору. Halo використовує подієво-орієнтовані BT, щоб миттєво переривати поточну поведінку за подіями сприйняття ШІ.
• Селектори, зважені за корисністю: замість фіксованого пріоритету зліва направо нащадки оцінюються функцією корисності, і обирається нащадок із найвищою оцінкою. Поєднує BT та утилітарний ШІ (The Sims).
• Гібриди BT + FSM: використовуйте автомат для перемикання між високорівневими режимами (Мирний/Насторожі/Бій), з виділеним підграфом BT для кожного стану. Поширено в RPG з відкритим світом, де NPC також виконують небойові щоденні рутини.
• Інструменти: AI Module в Unreal Engine, Behavior Designer в Unity, ROS2 BehaviorTree.CPP, додаток BeehaveTree для Godot.