Дерева поведінки: ШІ для NPC

Скінченний автомат (FSM) добре працює для невеликої кількості станів — Idle, Patrol, Chase, Attack — з явними переходами між кожною парою. Проблема в тому, що кількість переходів росте комбінаторно: додайте стан Flee та CallForHelp, і раптом доведеться продумати десяток нових ребер, багато з яких мали б спільно використовувати одну й ту саму перевірку "чи я в небезпеці?".

Дерево поведінки (behavior tree, BT) замінює заплутаний граф переходів деревом невеликих, повторно використовних вузлів, які обчислюються ("тікаються") згори вниз, зліва направо, щокадру. Складна поведінка виникає з композиції простих вузлів, а не з ручного прокладання переходів, і гілки можна повторно використовувати для багатьох різних NPC, просто переприв'язавши їх.

Кожен вузол дерева, будь то листова дія чи композит, реалізує один метод: tick(blackboard). Він повертає один із трьох статусів. Цей крихітний контракт — увесь рушій; будь-який інший тип вузла будується виключно комбінуванням викликів tick() у своїх дочірніх вузлах.

const Status = Object.freeze({
  SUCCESS: 'SUCCESS', // вузол досяг мети цього тіку
  FAILURE: 'FAILURE', // вузол не зміг досягти мети
  RUNNING: 'RUNNING', // ще в процесі, викликати tick() знову наступного кадру
});

class Node {
  // Перевизначається в підкласах. Має повертати значення Status.
  tick(blackboard) {
    throw new Error('tick() not implemented');
  }
}

Композити мають дочірні вузли й вирішують, які з них тікати та як комбінувати результати. Два робочі коні покривають майже все, що вам знадобиться:

• Sequence — логіка "І". Тікає дочірні вузли зліва направо; зупиняється й повертає FAILURE, щойно один з них провалюється; повертає SUCCESS тільки якщо всі дочірні вузли успішні. Представляє план — список кроків, які всі мають спрацювати.
• Selector — логіка "АБО". Тікає дочірні вузли зліва направо; зупиняється й повертає SUCCESS, щойно один з них успішний; повертає FAILURE тільки якщо всі провалилися. Представляє список альтернативних стратегій за пріоритетом.

class Composite extends Node {
  constructor(children = []) {
    super();
    this.children = children;
  }
}

class Sequence extends Composite {
  tick(bb) {
    for (const child of this.children) {
      const status = child.tick(bb);
      if (status !== Status.SUCCESS) return status; // FAILURE або RUNNING
    }
    return Status.SUCCESS; // усі дочірні вузли успішні
  }
}

class Selector extends Composite {
  tick(bb) {
    for (const child of this.children) {
      const status = child.tick(bb);
      if (status !== Status.FAILURE) return status; // SUCCESS або RUNNING
    }
    return Status.FAILURE; // усі дочірні вузли провалились
  }
}

Читання дерева перетворюється на читання звичайного тексту: Selector зі списком [Attack, Chase, Patrol] означає "атакуй, якщо можеш, інакше переслідуй, якщо можеш, інакше патрулюй". Кожен із них сам є Sequence з умов і дій, наприклад Attack = Sequence[InRange?, SwingWeapon].

Декоратор огортає рівно один дочірній вузол і модифікує його результат або частоту виклику. Саме тут живе значна частина повторно використовної "клеючої" логіки:

class Decorator extends Node {
  constructor(child) {
    super();
    this.child = child;
  }
}

// Перевертає SUCCESS <-> FAILURE. Корисно для перевірок "НЕ видно".
class Inverter extends Decorator {
  tick(bb) {
    const status = this.child.tick(bb);
    if (status === Status.SUCCESS) return Status.FAILURE;
    if (status === Status.FAILURE) return Status.SUCCESS;
    return status; // RUNNING проходить без змін
  }
}

// Забороняє повторний запуск дочірнього вузла, доки не мине `seconds`
// секунд відколи він востаннє повернув щось відмінне від RUNNING.
class Cooldown extends Decorator {
  constructor(child, seconds) {
    super(child);
    this.seconds = seconds;
    this.readyAt = 0;
  }
  tick(bb) {
    if (bb.time < this.readyAt) return Status.FAILURE;
    const status = this.child.tick(bb);
    if (status !== Status.RUNNING) this.readyAt = bb.time + this.seconds;
    return status;
  }
}

// Продовжує тікати дочірній вузол, доки він не провалиться `n` разів,
// або нескінченно, якщо n не задано. Зручно для циклів "озирнутись довкола".
class Repeater extends Decorator {
  constructor(child, times = Infinity) {
    super(child);
    this.times = times;
    this.count = 0;
  }
  tick(bb) {
    if (this.count >= this.times) return Status.SUCCESS;
    const status = this.child.tick(bb);
    if (status === Status.FAILURE) { this.count++; return Status.RUNNING; }
    return Status.RUNNING;
  }
}

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

class Blackboard {
  constructor(agent) {
    this.agent = agent;         // NPC, яким керує це дерево
    this.time = 0;              // оновлюється раз на кадр ігровим циклом
    this.playerPos = null;      // остання відома позиція гравця, або null
    this.lastSeenAt = -Infinity;
    this.patrolIndex = 0;
    this.homePos = agent.position.clone();
  }
}

Листові вузли виконують фактичну роботу — це єдині вузли, що безпосередньо торкаються ігрового стану. Умови — це листи, які ніколи не повертають RUNNING; дії ж зазвичай повертають, поки анімують чи рухають NPC протягом кількох кадрів.

class Condition extends Node {
  constructor(predicate) { super(); this.predicate = predicate; }
  tick(bb) { return this.predicate(bb) ? Status.SUCCESS : Status.FAILURE; }
}

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

const SEE_RANGE = 12;
const ATTACK_RANGE = 1.6;
const LOW_HEALTH = 0.25;

const canSeePlayer = new Condition((bb) => {
  const dist = bb.agent.position.distanceTo(bb.world.player.position);
  if (dist > SEE_RANGE) return false;
  const blocked = bb.world.raycastBlocked(bb.agent.position, bb.world.player.position);
  if (!blocked) { bb.playerPos = bb.world.player.position.clone(); bb.lastSeenAt = bb.time; }
  return !blocked;
});

const inAttackRange = new Condition((bb) =>
  bb.playerPos && bb.agent.position.distanceTo(bb.playerPos) <= ATTACK_RANGE
);

const isLowHealth = new Condition((bb) => bb.agent.health / bb.agent.maxHealth < LOW_HEALTH);

const attack = new Action((bb) => {
  bb.agent.swingWeapon();
  return bb.agent.attackFinished ? Status.SUCCESS : Status.RUNNING;
});

const chaseToPlayer = new Action((bb) => {
  if (!bb.playerPos) return Status.FAILURE;
  const reached = bb.agent.moveToward(bb.playerPos, bb.agent.runSpeed);
  return reached ? Status.SUCCESS : Status.RUNNING;
});

const fleeToHome = new Action((bb) => {
  const reached = bb.agent.moveToward(bb.homePos, bb.agent.runSpeed * 1.2);
  return reached ? Status.SUCCESS : Status.RUNNING;
});

const patrolNextWaypoint = new Action((bb) => {
  const target = bb.world.patrolRoute[bb.patrolIndex];
  const reached = bb.agent.moveToward(target, bb.agent.walkSpeed);
  if (reached) bb.patrolIndex = (bb.patrolIndex + 1) % bb.world.patrolRoute.length;
  return Status.RUNNING; // патруль ніколи не "завершується" — завжди RUNNING
});

З'єднайте листи в композити, найвищий пріоритет — першим. Корінь Selector спершу пробує втечу, потім атаку, потім переслідування, і повертається до патрулювання, якщо нічого інше не підходить:

const guardTree = new Selector([
  // 1. Найвищий пріоритет: бігти додому й лікуватись при серйозній травмі
  new Sequence([ isLowHealth, fleeToHome ]),

  // 2. Якщо гравець достатньо близько — атакувати
  new Sequence([ canSeePlayer, inAttackRange, new Cooldown(attack, 0.8) ]),

  // 3. Якщо гравця помічено, але він поза дистанцією — переслідувати
  new Sequence([ canSeePlayer, chaseToPlayer ]),

  // 4. Пам'ятати гравця 4с після втрати з поля зору, переслідувати останню відому точку
  new Sequence([
    new Condition((bb) => bb.time - bb.lastSeenAt < 4),
    chaseToPlayer,
  ]),

  // 5. За замовчуванням: нескінченно йти маршрутом патрулювання
  new Repeater(patrolNextWaypoint),
]);

Оскільки корінь — Selector, порядок пріоритету і є дизайном ШІ: поміняйте два рядки місцями, і характер охоронця повністю зміниться — поставте chase вище за flee, і отримаєте безрозсудного охоронця, що б'ється до смерті замість відступу.

Один тік на кадр на кожного NPC — це вся інтеграція. Тікання дешеве — це лише кілька викликів функцій уздовж активної гілки — тож сотні NPC можуть спільно використовувати одне визначення guardTree, кожен зі своїм власним екземпляром Blackboard:

const guards = world.npcs.map((agent) => ({
  agent,
  bb: new Blackboard(agent),
}));

function update(dt) {
  world.time += dt;
  for (const { agent, bb } of guards) {
    bb.time = world.time;
    bb.world = world;
    guardTree.tick(bb); // один виклик керує цілим рішенням цього кадру
  }
}

Найбільший приріст продуктивності при побудові дерев поведінки — дебаг-накладка, що показує останній статус кожного вузла. Огорніть tick() один раз, щоб записувати його, а потім обійдіть дерево, щоб намалювати кольорову схему:

function instrument(node) {
  const original = node.tick.bind(node);
  node.tick = (bb) => {
    const status = original(bb);
    node.lastStatus = status; // зелений=SUCCESS, червоний=FAILURE, жовтий=RUNNING
    return status;
  };
  if (node.children) node.children.forEach(instrument);
  if (node.child) instrument(node.child);
  return node;
}

instrument(guardTree);

// У вашому дебаг-HUD:
function drawNode(node, depth = 0) {
  const color = { SUCCESS: '#22c55e', FAILURE: '#ef4444', RUNNING: '#facc15' }[node.lastStatus] || '#555';
  console.log('  '.repeat(depth) + node.constructor.name, color);
  (node.children || (node.child ? [node.child] : [])).forEach((c) => drawNode(c, depth + 1));
}

Спостереження за тим, як активна гілка загорається жовтим у режимі реального часу, робить одразу зрозумілим, чому NPC "не атакує" — зазвичай це застарілий lastSeenAt або промінь, заблокований власним колайдером агента.

Дерева поведінки чудові, коли пріоритети переважно фіксовані й прописані вручну — саме як приклад охоронця вище. Вони починають напружуватись, коли потрібно багато конкуруючих цілей, оцінюваних за неперервними змінними (голод, боєприпаси, рівень загрози, згуртованість загону), що обмінюються між собою; це найкраще місце для utility AI, яка оцінює кожну можливу дію функцією й вибирає найвищий бал щотіку замість фіксованого порядку пріоритетів.

Для NPC, яким потрібно планувати багатокрокову тактику (обхід з флангу, потім кидок гранати, потім штурм), планувальник Ієрархічної мережі завдань (HTN) — який шукає серед послідовностей завдань, щоб задовольнити мету — підходить краще за обидва варіанти. Багато випущених ігор поєднують усі три: BT для реактивного бою, оцінку utility для вибору гілки BT чи цілі з пріоритетом, і планування HTN на рівні загону над обома.