ai-behavior-trees-utility-ai

# Behavior Tree core — Blackboard, nodes, leaves, composites, decorators

Depth for `ai-behavior-trees-utility-ai`. A complete, allocation-conscious C# behavior-tree
runtime. The code targets plain C# (no engine types) so it drops into Unity 6 or Godot 4 C#
unchanged — bind the leaves to your engine's transform/navigation in the concrete actions.

Contract in one line: every node's `Tick` returns `Success`, `Failure`, or `Running`, and a
parent decides what that means. Build the tree once at spawn; keep per-tick work allocation-free.

## Blackboard — the shared state system

The **Blackboard** is the agent's working memory. Leaves read and write it; no node holds a
reference to another. That indirection is what lets the same `MoveTo` action serve chase, patrol,
and flee subtrees, and what makes subtrees reusable across enemy types.

```csharp
using System.Collections.Generic;

// A typed key/value store. Keys are strings (or use enum/int keys to avoid hashing cost).
public sealed class Blackboard
{
    private readonly Dictionary<string, object> _values = new();

    public void Set<T>(string key, T value) => _values[key] = value!;

    public T Get<T>(string key, T fallback = default!)
        => _values.TryGetValue(key, out var v) && v is T t ? t : fallback;

    public bool TryGet<T>(string key, out T value)
    {
        if (_values.TryGetValue(key, out var v) && v is T t) { value = t; return true; }
        value = default!;
        return false;
    }

    public bool Has(string key) => _values.ContainsKey(key);
    public void Remove(string key) => _values.Remove(key);
}
```

For hot agents, prefer a **struct-of-fields blackboard** (public fields on a class) over a string
dictionary — it removes hashing and boxing entirely. Use the dictionary form when designers add
keys at runtime or you serialize the board.

```csharp
// Zero-allocation alternative: a plain data object shared by every node on this agent.
public sealed class AgentContext
{
    public Vector2 Position;
    public Transform Target;      // null when no target
    public Vector2 Home;
    public float LastSeenTime;
    public readonly List<Vector2> Path = new();
}
```

## The node base and status

```csharp
public enum Status { Success, Failure, Running }

// Every node in the tree derives from Node. dt is the decision-step delta (may differ from frame dt).
public abstract class Node
{
    public abstract Status Tick(Blackboard bb, float dt);

    // Called when a parent stops running this node before it finished (aborted branch).
    // Override to release timers, animations, or reservations.
    public virtual void Reset() { }
}
```

`Reset()` is the half of the contract people forget. When a `Selector` switches from a running
low-priority branch to a higher-priority one, it must `Reset()` the abandoned branch so a
half-finished action (a playing attack animation, a reserved cover point) is cleaned up.

## Base classes: leaf, composite, decorator

Three structural node kinds cover every tree:

```csharp
// A leaf does the actual work; it has no children.
public abstract class Leaf : Node { }

// A composite has many children and defines how their statuses combine (see Composites below).
public abstract class Composite : Node
{
    protected readonly List<Node> Children = new();
    protected int Current;                       // resume index for Running composites

    public Composite Add(Node child) { Children.Add(child); return this; }

    public override void Reset()
    {
        Current = 0;
        foreach (var c in Children) c.Reset();
    }
}

// A decorator wraps exactly one child and transforms its status or gates it (see Decorators below).
public abstract class Decorator : Node
{
    protected Node Child = default!;
    public Decorator Wrap(Node child) { Child = child; return this; }
    public override void Reset() => Child.Reset();
}
```

## Condition leaves — instantaneous predicates

A **condition** reads the blackboard and returns `Success` or `Failure` in the same tick. It never
returns `Running` and never mutates game state. Express reusable predicates as one small class with
an injected test, or subclass for named conditions.

```csharp
// Generic condition: succeed when a predicate over the blackboard holds.
public sealed class Condition : Leaf
{
    private readonly System.Func<Blackboard, bool> _predicate;
    public Condition(System.Func<Blackboard, bool> predicate) => _predicate = predicate;

    public override Status Tick(Blackboard bb, float dt)
        => _predicate(bb) ? Status.Success : Status.Failure;
}

// Named condition when the check is non-trivial or reused across trees.
public sealed class CanSeeTarget : Leaf
{
    private readonly float _sightRange;
    public CanSeeTarget(float sightRange) => _sightRange = sightRange;

    public override Status Tick(Blackboard bb, float dt)
    {
        if (!bb.TryGet<Vector2>("targetPos", out var target)) return Status.Failure;
        var self = bb.Get<Vector2>("position");
        // Real games also raycast for line of sight; keep the check cheap and cache the result.
        return (target - self).sqrMagnitude <= _sightRange * _sightRange
            ? Status.Success : Status.Failure;
    }
}
```

Note the pre-allocated `System.Func` delegate: create conditions **once** when the tree is built,
not per tick, so no closure is allocated during evaluation.

## Action leaves — multi-frame work that returns Running

An **action** performs work and returns `Running` until it completes, then `Success` (or `Failure`
if it can't). Returning `Running` is what lets a walk, an animation, or a timed wait span many
ticks without the parent restarting it.

```csharp
// Move toward a blackboard target; Running until within arrive radius, then Success.
public sealed class MoveToTarget : Leaf
{
    private readonly float _speed, _arriveRadius;
    public MoveToTarget(float speed, float arriveRadius)
    { _speed = speed; _arriveRadius = arriveRadius; }

    public override Status Tick(Blackboard bb, float dt)
    {
        if (!bb.TryGet<Vector2>("targetPos", out var target)) return Status.Failure;
        var pos = bb.Get<Vector2>("position");
        var offset = target - pos;
        if (offset.magnitude <= _arriveRadius) return Status.Success;   // arrived

        pos += offset.normalized * _speed * dt;
        bb.Set("position", pos);          // in an engine, drive the NavMeshAgent / CharacterBody here
        return Status.Running;            // keep going next tick
    }
}

// A timed wait — the canonical Running action, useful for patrol pauses and cooldown holds.
public sealed class Wait : Leaf
{
    private readonly float _duration;
    private float _elapsed;
    public Wait(float duration) => _duration = duration;

    public override Status Tick(Blackboard bb, float dt)
    {
        _elapsed += dt;
        if (_elapsed < _duration) return Status.Running;
        return Status.Success;
    }

    public override void Reset() => _elapsed = 0f;   // restart cleanly if the branch is re-entered
}
```

`Wait` shows why `Reset()` matters: its `_elapsed` accumulator must be cleared when the branch is
abandoned and later re-entered, or the second wait finishes instantly.

The `Sequence`/`Selector`/`Parallel` execution logic and the decorator library build directly on
these base classes — see the composites and decorators sections below.

## Composites — how child statuses combine

Composites are the control flow of a tree. The two you use constantly are `Sequence` (AND) and
`Selector` (OR/fallback); `Parallel` covers concurrent branches.

```csharp
// Sequence = AND: tick children in order; stop at the first that is not Success.
// Resumes at the Running child next tick ("memory" variant).
public sealed class Sequence : Composite
{
    public override Status Tick(Blackboard bb, float dt)
    {
        for (; Current < Children.Count; Current++)
        {
            var s = Children[Current].Tick(bb, dt);
            if (s == Status.Running) return Status.Running;   // resume here next tick
            if (s == Status.Failure) { Current = 0; return Status.Failure; }
        }
        Current = 0;
        return Status.Success;                                // every child succeeded
    }
}

// Selector = OR / fallback: return the first child that is not Failure.
public sealed class Selector : Composite
{
    public override Status Tick(Blackboard bb, float dt)
    {
        for (; Current < Children.Count; Current++)
        {
            var s = Children[Current].Tick(bb, dt);
            if (s == Status.Running) return Status.Running;   // resume here next tick
            if (s == Status.Success) { Current = 0; return Status.Success; }
        }
        Current = 0;
        return Status.Failure;                                // every child failed
    }
}
```

**Memory vs reactive.** The versions above *remember* the `Running` child and resume there. That is
efficient but does not let a higher-priority sibling interrupt. For a **reactive** selector — the
common case for combat AI — re-check children from index 0 every tick and abort the running branch
when an earlier child changes its mind:

```csharp
// Reactive selector: earlier (higher-priority) children can preempt a lower running branch.
public sealed class ReactiveSelector : Composite
{
    private int _running = -1;
    public override Status Tick(Blackboard bb, float dt)
    {
        for (int i = 0; i < Children.Count; i++)
        {
            var s = Children[i].Tick(bb, dt);
            if (s == Status.Failure) continue;
            if (_running != -1 && _running != i) Children[_running].Reset();  // abort old branch
            _running = s == Status.Running ? i : -1;
            return s;                                       // Success or Running
        }
        _running = -1;
        return Status.Failure;
    }

    public override void Reset() { base.Reset(); _running = -1; }
}
```

`Parallel` ticks every child each step and resolves with a policy — succeed when *any* (or *all*)
succeed, fail when *any* (or *all*) fail. Use it for "attack while strafing" or "play VFX while
moving".

```csharp
public enum ParallelPolicy { RequireOne, RequireAll }

public sealed class Parallel : Composite
{
    private readonly ParallelPolicy _success, _failure;
    public Parallel(ParallelPolicy success, ParallelPolicy failure)
    { _success = success; _failure = failure; }

    public override Status Tick(Blackboard bb, float dt)
    {
        int successes = 0, failures = 0;
        foreach (var child in Children)
        {
            var s = child.Tick(bb, dt);
            if (s == Status.Success) successes++;
            else if (s == Status.Failure) failures++;
        }
        if (_failure == ParallelPolicy.RequireOne && failures > 0) return Status.Failure;
        if (_failure == ParallelPolicy.RequireAll && failures == Children.Count) return Status.Failure;
        if (_success == ParallelPolicy.RequireOne && successes > 0) return Status.Success;
        if (_success == ParallelPolicy.RequireAll && successes == Children.Count) return Status.Success;
        return Status.Running;
    }
}
```

## Decorators — wrap one child to change its meaning

Decorators add policy without new leaves: invert a result, force a status, gate on a cooldown, or
repeat. Each wraps exactly one child.

```csharp
// Inverter: Success <-> Failure (Running passes through). "NOT".
public sealed class Inverter : Decorator
{
    public override Status Tick(Blackboard bb, float dt) => Child.Tick(bb, dt) switch
    {
        Status.Success => Status.Failure,
        Status.Failure => Status.Success,
        _              => Status.Running,
    };
}

// ForceSuccess: swallow a child's failure so a Sequence keeps going (optional steps).
public sealed class ForceSuccess : Decorator
{
    public override Status Tick(Blackboard bb, float dt)
        => Child.Tick(bb, dt) == Status.Running ? Status.Running : Status.Success;
}

// Repeat: run the child up to n times (n <= 0 = forever), restarting on each Success.
public sealed class Repeat : Decorator
{
    private readonly int _count;
    private int _done;
    public Repeat(int count) => _count = count;

    public override Status Tick(Blackboard bb, float dt)
    {
        var s = Child.Tick(bb, dt);
        if (s == Status.Running) return Status.Running;
        if (s == Status.Failure) { _done = 0; return Status.Failure; }
        _done++;
        if (_count > 0 && _done >= _count) { _done = 0; return Status.Success; }
        Child.Reset();                        // loop again
        return Status.Running;
    }

    public override void Reset() { base.Reset(); _done = 0; }
}

// Cooldown: gate the child so it can only run once per interval (attack/ability rate-limiting).
public sealed class Cooldown : Decorator
{
    private readonly float _seconds;
    private float _readyAt;
    public Cooldown(float seconds) => _seconds = seconds;

    public override Status Tick(Blackboard bb, float dt)
    {
        float now = bb.Get<float>("time");
        if (now < _readyAt) return Status.Failure;     // still cooling down
        var s = Child.Tick(bb, dt);
        if (s == Status.Success) _readyAt = now + _seconds;
        return s;
    }

    public override void Reset() { base.Reset(); _readyAt = 0f; }
}
```

## Running the tree

Wrap the root and tick it on your decision cadence. A behavior tree does **not** need to tick every
render frame — 5–15 Hz is plenty for most NPCs and slashes CPU cost.

```csharp
public sealed class BehaviorTree
{
    private readonly Node _root;
    private readonly Blackboard _bb;
    public BehaviorTree(Node root, Blackboard bb) { _root = root; _bb = bb; }

    public Status Tick(float dt)
    {
        _bb.Set("time", _bb.Get<float>("time") + dt);   // keep a clock for Cooldown/Wait
        return _root.Tick(_bb, dt);
    }
}

// Fluent assembly — build once at spawn, then tick.
var tree = new BehaviorTree(
    new ReactiveSelector()
        .Add(new Sequence()                              // combat branch (highest priority)
            .Add(new CanSeeTarget(sightRange: 12f))
            .Add(new MoveToTarget(speed: 6f, arriveRadius: 1.5f))
            .Add(new Cooldown(0.8f).Wrap(new AttackTarget())))
        .Add(new Patrol(waypoints)),                     // fallback
    blackboard);
```

The `Patrol` and `AttackTarget` leaves, and full agents that assemble these pieces, are in
`references/practical-examples.md`.

# Best practices & pitfalls — performance, memory, hybrid AI

Depth for `ai-behavior-trees-utility-ai`. How to keep a BT/Utility runtime fast, debuggable, and
maintainable at scale (dozens–hundreds of agents), and how to combine the two models well.

## Memory management

- **Build the tree once, at spawn — never per tick.** Node objects, delegates, and consideration
  lists are created during assembly and reused every tick. A tree rebuilt each frame is both a GC
  storm and a correctness bug (it discards `Running` state).
- **Keep `Tick` allocation-free.** No `new`, no LINQ (`Where`/`Select` allocate iterators), no
  closures capturing locals, no boxing. Pre-allocate scratch buffers; iterate with indexed `for`.
- **Prefer a struct-of-fields blackboard** (or `int`/enum keys) over a `Dictionary<string,object>`
  on hot agents — it removes hashing and value-type boxing. Keep the dictionary form for
  designer-authored or serialized boards.
- **Pool agents and their trees.** Reuse a despawned enemy's tree instance on respawn; call
  `Reset()` instead of reallocating.
- **Share immutable data.** Curves and static config are stateless — one instance serves every
  agent. Only per-agent mutable state (the blackboard, `Running` indices) is unique.

## Performance & profiling

- **Profile before optimizing.** Measure AI time in the engine profiler (Unity Profiler, Godot
  Monitors, Unreal `stat game`). The usual cost is not the tree walk — it is what the *leaves* do
  (raycasts, pathfinding, `FindObjectsByType`). Cache perception; pathfind on a timer, not per tick.
- **Tick on a decision cadence, not per frame.** 5–15 Hz is imperceptible for most NPCs and cuts
  cost 4–10×. Drive the tree from an accumulator (see the guard in `practical-examples.md`).
- **Time-slice across frames.** Don't tick every agent on the same frame. Stagger by bucketing
  agents and ticking one bucket per frame, so the cost spreads instead of spiking.

```csharp
// Round-robin: only ~1/N of agents think each frame; the herd cost is flat, not a spike.
_bucket = (_bucket + 1) % Buckets;
for (int i = _bucket; i < agents.Count; i += Buckets)
    agents[i].Think(dt * Buckets);      // scale dt so per-agent cadence is unchanged
```

- **LOD your AI.** Distant or off-screen agents tick slower (or freeze). Tie the cadence to
  distance-from-camera; a guard 200 m away does not need 10 Hz decisions.
- **Utility cost scales with actions × considerations.** Don't score 40 actions × 8 considerations
  every tick. Prune obviously-irrelevant actions first (a cheap gate consideration that early-outs
  at 0), and re-score only when a relevant fact changed.

## Avoiding deep, brittle trees

- **Keep trees shallow and wide.** Deep nesting is hard to read and forces full re-evaluation.
  Factor repeated subtrees into named builder methods and reuse them.
- **Use conditional aborts / a reactive selector** so a high-priority condition (took damage, lost
  the player) interrupts a lower branch, instead of polling a deep tree for the change.
- **Prefer event-driven perception over polling.** Let sensors push `targetPos` onto the blackboard
  when they fire; the tree reads a cached fact instead of raycasting inside a condition every tick.
- **Cache condition results within a tick** if the same expensive check appears in multiple places.

## Combining Utility AI with behavior trees (hybrid)

The two models answer different questions — use each where it is strong:

| Use a **behavior tree** for… | Use **Utility AI** for… |
|---|---|
| Top-level structure & priorities (patrol / engage / flee) | "How much do I want each option right now?" |
| Ordered, interruptible sequences | Target selection, item/ability choice, needs |
| Clear, debuggable, designer-readable flow | Smooth trade-offs with many inputs |

Recommended default: **BT on the outside, Utility on the inside.** The BT decides *engage vs
disengage vs patrol*; a `UtilitySelectorNode` inside the engage branch decides *which target / which
attack* (see `practical-examples.md` §3). Keep the utility set small and local to the branch so
scoring stays cheap, and give the running action hysteresis so the sub-choice doesn't flicker.

Avoid the inverse (utility choosing between whole behavior trees) unless you truly need graded
top-level behavior — it is harder to debug and easy to make thrash.

## Debugging

- **Draw the decision.** Overlay the active BT path (highlight the running leaf) and, for utility,
  a live bar per action score. Most "bad AI" bugs are visible instantly: a stuck `Running` leaf, an
  un-normalized consideration pinning one action to 1.0, or a mis-shaped curve.
- **Log transitions, not ticks.** Print only when the chosen action or active branch *changes*;
  per-tick logs bury the signal.
- **Make randomness reproducible.** Seed the `System.Random` used by softmax/weighted-random per
  agent so a misbehaving agent can be replayed. Never use a shared global RNG across agents.
- **Assert the `Reset()` contract.** A common bug is a `Running` action (`Wait`, `Repeat`, cover
  reservation) that isn't reset when its branch is abandoned. If timed actions "finish instantly"
  after re-entry, a missing `Reset()` is the cause.

## Pitfall quick-reference

- Rebuilding the tree or allocating in `Tick` → GC spikes and lost `Running` state.
- Ticking every agent every frame → CPU spikes; use cadence + time-slicing + LOD.
- Un-normalized considerations (mixed 0..1 and 0..100) → one factor dominates; weights meaningless.
- No hysteresis → jitter on near-ties in both reactive selectors and utility selection.
- Deep trees with polling conditions → wasted work and laggy reactions; use aborts + events.
- Expensive work inside conditions (raycasts, pathfinding) → cache it on the blackboard instead.

# Practical examples — guard AI, villager needs, hybrid agent

Depth for `ai-behavior-trees-utility-ai`. Three drop-in templates that assemble the BT core
(`references/behavior-tree-core.md`) and the Utility system (`references/utility-ai-system.md`) into
real agents. Same plain-C# style — bind the movement/attack leaves to your engine's transform,
navigation, and combat.

## 1. Enemy guard — Patrol → Combat behavior tree

The classic guard: patrol waypoints until it sees the player, then close in and attack on a
cooldown, and fall back to patrol when the player escapes. Two extra leaves complete the set the
core promised:

```csharp
// Patrol: walk a waypoint ring, pausing at each. Always Running (a patrol never "finishes").
public sealed class Patrol : Leaf
{
    private readonly Vector2[] _points;
    private readonly float _speed, _pause;
    private int _i;
    private float _waited;

    public Patrol(Vector2[] points, float speed = 3f, float pause = 1f)
    { _points = points; _speed = speed; _pause = pause; }

    public override Status Tick(Blackboard bb, float dt)
    {
        var pos = bb.Get<Vector2>("position");
        var goal = _points[_i];
        if ((goal - pos).magnitude > 0.2f)
        {
            bb.Set("position", pos + (goal - pos).normalized * _speed * dt);
            return Status.Running;
        }
        _waited += dt;                                  // reached a waypoint: pause, then advance
        if (_waited >= _pause) { _waited = 0f; _i = (_i + 1) % _points.Length; }
        return Status.Running;
    }

    public override void Reset() => _waited = 0f;
}

// AttackTarget: one swing. Wrap in a Cooldown decorator to rate-limit (see the assembly below).
public sealed class AttackTarget : Leaf
{
    public override Status Tick(Blackboard bb, float dt)
    {
        if (!bb.TryGet<IDamageable>("target", out var target)) return Status.Failure;
        target.ApplyDamage(10f);
        return Status.Success;
    }
}
```

Assemble and drive it. Perception writes `targetPos`/`target` onto the blackboard; the tree only
*decides*:

```csharp
public sealed class GuardAgent
{
    private readonly BehaviorTree _tree;
    private readonly Blackboard _bb = new();
    private float _decisionTimer;
    private const float TickRate = 1f / 10f;             // decide at 10 Hz, not every frame

    public GuardAgent(Vector2[] patrolRoute)
    {
        _tree = new BehaviorTree(
            new ReactiveSelector()                       // reactive: seeing the player preempts patrol
                .Add(new Sequence()                      // --- combat branch (higher priority) ---
                    .Add(new CanSeeTarget(sightRange: 12f))
                    .Add(new MoveToTarget(speed: 6f, arriveRadius: 1.5f))
                    .Add(new Cooldown(0.8f).Wrap(new AttackTarget())))
                .Add(new Patrol(patrolRoute)),           // --- fallback ---
            _bb);
    }

    // Call every frame; the tree itself only ticks on the decision cadence.
    public void Update(float dt, PerceptionResult perception)
    {
        _bb.Set("position", perception.SelfPos);
        if (perception.SeesPlayer) { _bb.Set("targetPos", perception.PlayerPos); _bb.Set("target", perception.Player); }
        else _bb.Remove("targetPos");

        _decisionTimer += dt;
        if (_decisionTimer < TickRate) return;
        _tree.Tick(_decisionTimer);
        _decisionTimer = 0f;
    }
}
```

## 2. Villager needs — Utility AI

When behavior is driven by competing *needs* rather than a fixed priority order, Utility AI is the
better fit. A villager weighs hunger, fatigue, and social need against opportunity, and does the
most-wanted thing:

```csharp
UtilityEvaluator BuildVillagerBrain()
{
    // Each action: weight * combined considerations (all 0..1). Curves shape the "want".
    var eat = new UtilityAction("Eat") { Weight = 1.2f }
        .With(new Consideration("hunger", bb => bb.Get<float>("hunger01"),
                                 t => Curves.Sigmoid(t, k: 10f, mid: 0.5f)))     // want food as hunger rises
        .With(new Consideration("hasFood", bb => bb.Get<float>("food01"), Curves.Linear));

    var sleep = new UtilityAction("Sleep") { Weight = 1f }
        .With(new Consideration("fatigue", bb => bb.Get<float>("fatigue01"),
                                 t => Curves.Quadratic(t)))                       // only strong when very tired
        .With(new Consideration("isNight", bb => bb.Get<float>("night01"), Curves.Smoothstep));

    var socialize = new UtilityAction("Socialize") { Weight = 0.8f }
        .With(new Consideration("lonely", bb => bb.Get<float>("loneliness01"), Curves.Linear))
        .With(new Consideration("friendsNear", bb => bb.Get<float>("friendsNear01"), Curves.Smoothstep));

    var work = new UtilityAction("Work") { Weight = 0.7f }
        .With(new Consideration("daytime", bb => bb.Get<float>("day01"), Curves.Smoothstep))
        .With(new Consideration("notTooTired",
              bb => 1f - bb.Get<float>("fatigue01"), Curves.Linear));            // inverted fact

    return new UtilityEvaluator().Add(eat).Add(sleep).Add(socialize).Add(work);
}

// Per decision step: pick and dispatch. Hysteresis stops the villager thrashing between near-ties.
void UpdateVillager(UtilityEvaluator brain, Blackboard bb)
{
    var choice = brain.SelectBest(bb, inertiaBonus: 0.05f);
    Dispatch(choice.Name);      // route "Eat"/"Sleep"/... to your gameplay handlers
}
```

## 3. Hybrid — a BT that delegates a choice to Utility AI

The best of both: a behavior tree gives the top-level *structure and priorities*; a utility node
makes a *graded sub-choice* (which target, which attack) inside a branch. Bridge them with a leaf
that owns a `UtilityEvaluator` and runs the winner's `Behavior` subtree.

```csharp
// A BT leaf that scores utility actions and ticks the chosen action's Behavior subtree.
public sealed class UtilitySelectorNode : Leaf
{
    private readonly UtilityEvaluator _evaluator;
    private readonly float _inertia;
    private UtilityAction _running;

    public UtilitySelectorNode(UtilityEvaluator evaluator, float inertia = 0.05f)
    { _evaluator = evaluator; _inertia = inertia; }

    public override Status Tick(Blackboard bb, float dt)
    {
        var choice = _evaluator.SelectBest(bb, _inertia);
        if (choice != _running) { _running?.Behavior?.Reset(); _running = choice; }  // switched: clean up
        return _running?.Behavior?.Tick(bb, dt) ?? Status.Failure;
    }

    public override void Reset() { _running?.Behavior?.Reset(); _running = null; }
}
```

```csharp
// Combat structured by a BT; "which attack" chosen by utility each tick.
var attackChoice = new UtilityEvaluator()
    .Add(new UtilityAction("Melee")  { Weight = 1f, Behavior = new MeleeCombo() }
        .With(new Consideration("close", bb => Curves.InverseLerp01(bb.Get<float>("distToPlayer"), 6f, 1f), Curves.Smoothstep)))
    .Add(new UtilityAction("Ranged") { Weight = 1f, Behavior = new FireVolley() }
        .With(new Consideration("far",  bb => Curves.InverseLerp01(bb.Get<float>("distToPlayer"), 2f, 14f), Curves.Smoothstep))
        .With(new Consideration("ammo", bb => bb.Get<float>("ammo01"), Curves.Linear)));

var hybrid = new BehaviorTree(
    new ReactiveSelector()
        .Add(new Sequence()
            .Add(new CanSeeTarget(12f))
            .Add(new UtilitySelectorNode(attackChoice)))   // BT picks "engage"; utility picks how
        .Add(new Patrol(route)),
    blackboard);
```

This layering is the recommended default for combat AI: keep the readable, debuggable BT for
"engage vs disengage vs patrol", and let utility handle the continuous trade-offs. The performance
and architecture trade-offs of the hybrid are in `references/best-practices-and-pitfalls.md`.

# Utility AI system — curves, considerations, evaluator

Depth for `ai-behavior-trees-utility-ai`. Utility AI turns *"which action do I want most right
now?"* into arithmetic: describe each candidate action with a few **considerations**, map each raw
fact through a **normalized response curve** to 0..1, combine them into a score, and select. Same
C#-only style as the BT core, so it composes with it (see the hybrid section in
`references/practical-examples.md`).

Golden rule: **every consideration outputs 0..1.** Mixing ranges (one 0..1, one 0..100) lets the
big one dominate and makes weights meaningless.

## Response-curve library

Curves shape *how* a fact translates to desire. `t` is a normalized 0..1 input (use
`InverseLerp01` to normalize a raw fact first). All outputs are clamped to 0..1.

```csharp
public static class Curves
{
    public static float Clamp01(float x) => x < 0f ? 0f : x > 1f ? 1f : x;

    // Normalize a raw fact into 0..1 (a==0 output, b==1 output). Handles inverted ranges (a>b).
    public static float InverseLerp01(float x, float a, float b)
        => a == b ? (x >= b ? 1f : 0f) : Clamp01((x - a) / (b - a));

    // Linear: desire tracks the fact directly.
    public static float Linear(float t, float slope = 1f, float yIntercept = 0f)
        => Clamp01(slope * t + yIntercept);

    // Polynomial: exponent>1 = ease-in (low until high t); exponent<1 = ease-out (rises fast early).
    public static float Polynomial(float t, float exponent)
        => Clamp01((float)System.Math.Pow(Clamp01(t), exponent));

    public static float Quadratic(float t) => Polynomial(t, 2f);      // slow start, sharp finish
    public static float InverseQuadratic(float t)                     // fast start, gentle finish
        => Clamp01(1f - (1f - Clamp01(t)) * (1f - Clamp01(t)));

    // Exponential: k>0 grows steeply near 1; useful for "only care when nearly full/empty".
    public static float Exponential(float t, float k = 4f)
        => Clamp01(((float)System.Math.Exp(k * Clamp01(t)) - 1f) / (System.MathF.Exp(k) - 1f));

    // Logistic / sigmoid: a smooth S-curve with an adjustable threshold. k = steepness, mid = 0.5 crossing.
    public static float Sigmoid(float t, float k = 8f, float mid = 0.5f)
        => Clamp01(1f / (1f + System.MathF.Exp(-k * (Clamp01(t) - mid))));

    // Smoothstep: eased 0..1 with zero slope at both ends; good default for "soft threshold".
    public static float Smoothstep(float t) { t = Clamp01(t); return t * t * (3f - 2f * t); }
}
```

Pick by intent: **Linear** for proportional wants; **Quadratic/Exponential** for "only matters at
the extreme"; **Sigmoid/Smoothstep** for a soft threshold (flee when health crosses ~40%); invert
any curve with `1 - curve(t)` (e.g. desire-to-heal rises as health falls).

## Considerations — one fact, one curve

A **consideration** binds a fact reader to a curve and yields a 0..1 factor. Build them once and
reuse; they hold no per-tick state.

```csharp
public sealed class Consideration
{
    public readonly string Name;
    private readonly System.Func<Blackboard, float> _fact;   // raw or pre-normalized fact
    private readonly System.Func<float, float> _curve;       // maps the fact to 0..1

    public Consideration(string name, System.Func<Blackboard, float> fact,
                         System.Func<float, float> curve)
    { Name = name; _fact = fact; _curve = curve; }

    public float Evaluate(Blackboard bb) => Curves.Clamp01(_curve(_fact(bb)));
}
```

```csharp
// Example considerations for a "attack the player" action.
var proximity = new Consideration("proximity",
    bb => Curves.InverseLerp01(bb.Get<float>("distToPlayer"), 20f, 2f),  // near -> 1
    Curves.Smoothstep);

var myHealth = new Consideration("myHealth",
    bb => bb.Get<float>("health01"),
    t => Curves.Sigmoid(t, k: 8f, mid: 0.35f));                          // low health -> low desire
```

## Scored actions and the compensation factor

A `UtilityAction` scores as its `weight` times the **combined** considerations. Multiplying factors
is standard (a single near-zero consideration should veto the action), but naive multiplication
over-punishes as you add considerations. Apply Dave Mark's **compensation factor** so more
considerations don't unfairly drag the score down.

```csharp
public sealed class UtilityAction
{
    public readonly string Name;
    public float Weight = 1f;
    public readonly List<Consideration> Considerations = new();
    public Node Behavior;                         // optional BT subtree to run when chosen (hybrid)

    public UtilityAction(string name) => Name = name;
    public UtilityAction With(Consideration c) { Considerations.Add(c); return this; }

    public float Score(Blackboard bb)
    {
        int n = Considerations.Count;
        if (n == 0) return Weight;

        float product = 1f;
        for (int i = 0; i < n; i++) product *= Considerations[i].Evaluate(bb);

        // Compensation: add back some of what extra factors removed. modFactor -> 0 as n grows.
        float modFactor = 1f - 1f / n;
        float makeUp = (1f - product) * modFactor;
        float compensated = product + makeUp * product;

        return Weight * Curves.Clamp01(compensated);
    }
}
```

## The evaluator — scoring and selection

The evaluator scores every action and selects one. Offer three strategies: **argmax** (best),
**softmax** (probabilistic, weighted by score — variety without dumb choices), and
**weighted-random** over raw scores. Add **hysteresis** (an inertia bonus for the current action)
so agents commit instead of flip-flopping on near-ties.

```csharp
public sealed class UtilityEvaluator
{
    private readonly List<UtilityAction> _actions = new();
    private UtilityAction _current;

    public UtilityEvaluator Add(UtilityAction a) { _actions.Add(a); return this; }

    // Argmax with hysteresis: the currently-committed action gets a small bonus.
    public UtilityAction SelectBest(Blackboard bb, float inertiaBonus = 0.05f)
    {
        UtilityAction best = null; float bestScore = float.NegativeInfinity;
        foreach (var a in _actions)
        {
            float s = a.Score(bb);
            if (a == _current) s += inertiaBonus;      // stickiness to avoid jitter
            if (s > bestScore) { bestScore = s; best = a; }
        }
        _current = best;
        return best;
    }

    // Softmax: choose proportionally to exp(score/temperature). Higher temp = more random.
    public UtilityAction SelectSoftmax(Blackboard bb, System.Random rng, float temperature = 0.2f)
    {
        float sum = 0f;
        var weights = new float[_actions.Count];
        for (int i = 0; i < _actions.Count; i++)
        {
            weights[i] = System.MathF.Exp(_actions[i].Score(bb) / System.MathF.Max(temperature, 1e-4f));
            sum += weights[i];
        }
        float roll = (float)rng.NextDouble() * sum;
        for (int i = 0; i < weights.Length; i++)
            if ((roll -= weights[i]) <= 0f) { _current = _actions[i]; return _actions[i]; }
        _current = _actions[^1];
        return _current;
    }
}
```

Usage: score every decision step, then run the winner's `Behavior` (hybrid) or call its handler
directly. Verify by drawing each action's live score as a debug bar while tuning — utility bugs are
almost always a mis-shaped curve or an un-normalized fact, and both are obvious on screen. The
worked villager-needs evaluator and the BT+Utility hybrid are in
`references/practical-examples.md`.

---
name: ai-behavior-trees-utility-ai
description: >
  Build a production behavior-tree runtime (Blackboard, action/condition leaves,
  sequence/selector/parallel composites, decorators) and a Utility AI system (response
  curves — linear, exponential, sigmoid, quadratic — considerations, and action evaluators),
  plus hybrid BT-drives-Utility agents. Use when implementing a reusable behavior-tree or
  utility-based decision system, or tuning enemy/NPC decisions beyond a simple FSM, or when
  the user mentions behavior tree, blackboard, decorator, selector, sequence, tick status,
  utility AI, response/scoring curve, or consideration. For choosing between FSM/BT/steering
  or for pathfinding, use game-ai; for Unreal's BehaviorTree/Blackboard assets, use
  unreal-behavior-trees.
---

# Behavior Trees & Utility AI

Two complementary ways to structure NPC decision-making, plus how to combine them. A
**behavior tree (BT)** expresses *structured, prioritized, reactive* logic as a tree that is
"ticked" each step. **Utility AI** answers *"how much do I want each option right now?"* by
scoring actions with normalized curves and picking the best. Ship believable agents by using a
BT for structure and Utility AI where graded trade-offs matter.

This skill is the **implementation** companion to `game-ai` (which helps you *choose* between
FSM / BT / steering / pathfinding). Read `game-ai` to pick a model; read this to build the
runtime.

## When to use

- Use to build a **reusable BT runtime**: a `Blackboard`, `Node` base, action/condition leaves,
  `Sequence`/`Selector`/`Parallel` composites, and decorators (Inverter, Cooldown, Repeat).
- Use to build a **Utility AI** decider: response curves, considerations, and an evaluator that
  scores and selects actions (max, softmax, or weighted-random for variety).
- Use to build **hybrid AI** — a BT whose leaf delegates the "which attack / which target"
  choice to a utility evaluator.

**When *not* to use:** to *choose* between FSM, BT, steering, or pathfinding, and for A*/navmesh
routing, use `game-ai`. For Unreal's asset-based `BehaviorTree`/`Blackboard`, `BTTask`/`BTService`
and `AIController`, use `unreal-behavior-trees`. For the navmesh agent that *moves* the NPC, use
`unity-navmesh` or the engine's navigation node.

## Core workflow

1. **Pick the model.** Structured, prioritized, interruptible behavior → **BT**. Continuous
   "score every option" decisions (targeting, needs, item choice) → **Utility**. Both → **hybrid**.
2. **Design the Blackboard first.** One typed key/value store per agent is the shared memory that
   decouples nodes; leaves read/write it and never hold references to each other.
3. **Write leaves.** *Conditions* return `Success`/`Failure` immediately; *actions* return
   `Running` across frames until they finish. Keep leaves small and side-effect-explicit.
4. **Compose.** `Selector` = OR/fallback (first non-failure wins); `Sequence` = AND (stop at first
   non-success); `Parallel` for concurrent branches. Wrap with decorators for policy (invert,
   cooldown, repeat, force-success).
5. **For Utility:** enumerate considerations, map each raw fact through a **normalized 0..1 curve**,
   combine (weighted product with compensation, or weighted sum), then select the max — add
   hysteresis so agents don't flip-flop on ties.
6. **Tick deliberately.** Tick the tree/evaluator once per *decision step* (often slower than
   render). Preserve `Running` state between ticks; verify by drawing the active path and the
   per-action scores on screen while tuning.

## Architecture at a glance

A behavior tree evaluates top-down, left-to-right; each node returns a status up to its parent:

```mermaid
flowchart TD
    Root["Selector (root)"] --> Combat["Sequence: Combat"]
    Root --> Patrol["Action: Patrol"]
    Combat --> See["Condition: CanSeePlayer?"]
    Combat --> InRange{"Selector: Reach"}
    Combat --> Attack["Action: Attack (Running)"]
    InRange --> Close["Condition: InAttackRange?"]
    InRange --> MoveTo["Action: MoveToPlayer (Running)"]
```

Utility AI is a scoring pipeline — every candidate action is scored, then one is selected:

```text
facts (distance, health, ammo…)
      │  each fact → a normalized 0..1 response curve (consideration)
      ▼
score(action) = weight · combine(consideration_1 … consideration_n)   # product+compensation or sum
      ▼
select: argmax  ·  or softmax / weighted-random for variety  ·  + hysteresis to avoid jitter
```

**Status is a three-value enum** shared by every node — this is the contract that makes the tree
composable:

```csharp
public enum Status { Success, Failure, Running }

public abstract class Node
{
    public abstract Status Tick(Blackboard bb, float dt);
    public virtual void Reset() { }   // called when a parent abandons this subtree
}
```

```csharp
// Selector = fallback/OR: return the first child that is not Failure.
public sealed class Selector : Composite
{
    public override Status Tick(Blackboard bb, float dt)
    {
        for (; _current < Children.Count; _current++)
        {
            var s = Children[_current].Tick(bb, dt);
            if (s != Status.Failure) return s;   // Success or Running stops the scan
        }
        _current = 0;
        return Status.Failure;                    // every child failed
    }
}
```

The reciprocal `Sequence` (AND — stop at first non-`Success`), `Parallel`, the `Blackboard`, the
leaf base classes, and every decorator are in `references/behavior-tree-core.md`.

## Utility scoring in one snippet

```csharp
// A consideration maps one raw fact to 0..1 through a response curve.
float Score(Blackboard bb)
{
    float distance01 = Curves.InverseLerp01(bb.Get<float>("distToPlayer"), 20f, 2f); // near = 1
    float health01   = Curves.Sigmoid(bb.Get<float>("health01"), k: 8f, mid: 0.4f);  // hurt = low
    // Product + compensation keeps a single 0 from vetoing while low values still dampen.
    return Curves.CompensatedProduct(new[] { distance01, health01 });
}
```

The full curve library (linear, quadratic, exponential, logistic/sigmoid, smoothstep), the
`Consideration`/`UtilityAction` types, and the `UtilityEvaluator` selection strategies are in
`references/utility-ai-system.md`.

## Pitfalls

- **Re-ticking a `Running` action from the root every frame restarts it.** Return `Running` and
  resume where you left off; only `Reset()` a subtree when a parent actually abandons it.
- **Deep trees re-evaluated wholesale each tick** waste time and cause thrash. Prefer shallow
  trees and *conditional aborts* (a higher-priority condition can interrupt a lower branch).
- **Un-normalized considerations.** If one curve outputs 0..100 and another 0..1, the big one
  dominates. Every consideration must return 0..1.
- **Utility jitter on near-ties.** Add hysteresis: give the currently-running action a small bonus
  so the agent commits instead of oscillating.
- **Allocating nodes, closures, or arrays every tick** creates GC spikes. Build the tree once at
  spawn; keep per-tick work allocation-free.

## References

- `references/behavior-tree-core.md` — Blackboard, `Node`/leaf base classes, action & condition
  leaves, `Sequence`/`Selector`/`Parallel`, and the decorator library (full C#).
- `references/utility-ai-system.md` — response-curve library, `Consideration`, `UtilityAction`,
  and the `UtilityEvaluator` (argmax, softmax, weighted-random, hysteresis).
- `references/practical-examples.md` — a guard Patrol→Combat BT, a villager needs-based Utility
  AI, and a hybrid agent, as drop-in templates.
- `references/best-practices-and-pitfalls.md` — memory management, profiling, avoiding deep trees,
  event-driven aborts, and combining Utility AI with BTs (hybrid architecture).

## Related skills

- `game-ai` — choose between FSM / BT / steering; A* and navmesh pathfinding.
- `unreal-behavior-trees` — Unreal's asset-based BT/Blackboard, tasks, decorators, services.
- `unity-navmesh` — the `NavMeshAgent` that carries out "move to" intents.
- `physics-tuning` — agent radius, movement, and collision response for the motion layer.
- `tower-defense`, `fps-shooter`, `rpg` — genres that compose this decision layer.