Behaviour trees that decide what game characters do, with optional utility scores to pick the best choice.
Import blitz.decisions As AI gives your program these, with AI. in front. Each name leads to its part of the reference.
CreateTree:Tree()AddSequence:Node(tree:Tree, parent:Node)AddSelector:Node(tree:Tree, parent:Node)AddAction:Node(tree:Tree, parent:Node, behaviour:Action)AddCondition:Node(tree:Tree, parent:Node, condition:Condition)AddWait:Node(tree:Tree, parent:Node, seconds:Double)UpdateTree:Int(tree:Tree, seconds:Double, work:Int = 64)TreeSuspended:Int(tree:Tree)ResetTree(tree:Tree)ActiveNode:Node(tree:Tree)ResultSuccess, Failure, RunningAn optional part. Import blitz.decisions.utility As Utility as well to use these.
CreateUtility:UtilitySelector(options:UtilityOptions)AddOption(selector:UtilitySelector, name:Str, evaluator:Evaluator)UpdateUtility:Str(selector:UtilitySelector, seconds:Double)UtilityOptionsswitchMargin:Double = 0.1D, minimumHold:Double = 0.25DUtilitySelectorEvaluatorScore:Double()Decisions helps the characters in your game decide what to do. You give a character a few things it can do, such as patrol, chase or rest, and a few questions it can ask, such as "Can I see the player?". Then you arrange them in a tree that says what to try first, and what to do instead when that doesn't work. Each frame the tree picks what the character should be doing, and keeps it doing that until something more important comes along. Game makers call this a behaviour tree.
Open patrol.bb and run it. The guard walks to and fro, resting for two seconds at each end. Move the yellow ball into its ring with the arrow keys and it chases you. Get far enough away and it gives up and goes back to its patrol.
; A guard patrols to and fro, resting at each end, and chases you when you
; come inside its ring. Arrow keys move the yellow ball. Escape quits.
Dialect "modern"
Import blitz.decisions As AI
Global guard:Int, you:Int, post:Int ; The entities the guard's actions use.
; An action: walk to the end of the patrol. It succeeds on getting there.
Type Patrol Implements AI.Action
Field x:Float = 5 ; Where the end is.
Method Tick:Int(seconds:Double)
PositionEntity post, Self.x, 0, 0
PointEntity guard, post
MoveEntity guard, 0, 0, 2 * seconds
If EntityDistance(guard, post) > 0.1 Then Return AI.Result.Running
Self.x = -Self.x ; Next time, go to the other end.
Return AI.Result.Success
End Method
Method Abort() ; It stopped early. There's nothing to tidy up.
End Method
End Type
; An action: run after you. It fails, so the guard gives up, if you get away.
Type ChaseYou Implements AI.Action
Method Tick:Int(seconds:Double)
If EntityDistance(guard, you) > 6 Then Return AI.Result.Failure
PointEntity guard, you
If EntityDistance(guard, you) > 1 Then MoveEntity guard, 0, 0, 3 * seconds
Return AI.Result.Running
End Method
Method Abort()
End Method
End Type
; A condition: is the guard close enough to see you?
Type CanSeeYou Implements AI.Condition
Method Test:Int()
Return EntityDistance(guard, you) < 4
End Method
End Type
Graphics3D 800, 480, 0, 2
SetBuffer BackBuffer()
Local camera:Int = CreateCamera()
CameraClsColor camera, 18, 52, 79
CameraZoom camera, 1.6
PositionEntity camera, 0, 14, -14
RotateEntity camera, 45, 0, 0
Local light:Int = CreateLight()
RotateEntity light, 50, 30, 0
Local ground:Int = CreateCube()
ScaleEntity ground, 9, 0.1, 6
PositionEntity ground, 0, -0.1, 0
EntityColor ground, 40, 100, 140
guard = CreateCylinder(16)
ScaleMesh guard, 0.4, 0.8, 0.4
PositionMesh guard, 0, 0.8, 0 ; So that it stands on the ground.
EntityColor guard, 230, 90, 70
Local ring:Int = CreateCylinder(32, True, guard) ; How far the guard can see.
ScaleEntity ring, 4, 0.05, 4
EntityAlpha ring, 0.3
you = CreateSphere(12)
ScaleMesh you, 0.4, 0.4, 0.4
PositionMesh you, 0, 0.4, 0
EntityColor you, 255, 220, 0
PositionEntity you, 0, 0, -5
post = CreatePivot()
; The guard's mind. A selector tries its branches in order, and takes the first
; that works: chase you if it can see you, or else patrol. A sequence does its
; steps one after another.
Local tree:AI.Tree = AI.CreateTree()
Local root:AI.Node = AI.AddSelector(tree, Null)
Local hunt:AI.Node = AI.AddSequence(tree, root)
Local sight:CanSeeYou = New CanSeeYou
AI.AddCondition tree, hunt, sight
Local chase:ChaseYou = New ChaseYou
Local chasing:AI.Node = AI.AddAction(tree, hunt, chase)
Local rounds:AI.Node = AI.AddSequence(tree, root)
Local patrol:Patrol = New Patrol
AI.AddAction tree, rounds, patrol
Local resting:AI.Node = AI.AddWait(tree, rounds, 2D) ; Rest for two seconds.
Local previous:Int = MilliSecs()
While Not KeyDown(1)
; Move yourself, then tell the guard how much time has passed. It decides
; what to do, and does it.
Local now:Int = MilliSecs()
Local seconds:Double = Double(now - previous) / 1000D
previous = now
MoveEntity you, (KeyDown(205) - KeyDown(203)) * 5 * seconds, 0, (KeyDown(200) - KeyDown(208)) * 5 * seconds
AI.UpdateTree tree, seconds
; Ask which action or wait is running, to show what the guard is doing.
Local doing:Str = "Patrolling"
If AI.ActiveNode(tree) = chasing Then doing = "Chasing you!"
If AI.ActiveNode(tree) = resting Then doing = "Resting"
RenderWorld
CameraProject camera, EntityX(guard), 2.6, EntityZ(guard)
Text ProjectedX(), ProjectedY(), doing, True, True
Text 10, 10, "Arrow keys move the yellow ball. Don't let the guard see you!"
Flip
Wend
Delete tree ; Delete the tree first, then the actions and the condition.
Delete sight
Delete chase
Delete patrol
End
The tree has two branches. The first is a sequence: a question, "Can it see you?", and then an action, chasing you. When the answer is no, that branch fails, and the selector tries the next one: walk to the end of the patrol, then wait. The actions and the question are Types of your own, and your actions do the moving. The module only decides which of them runs, and passes on the seconds you give it.
Make a Type that Implements AI.Action, with two methods. Tick does one
frame's worth of the action and says how it's going: Running until it's
finished, then Success, or Failure if it can't be done. Abort is called
if the tree stops it part way through, because something more important came
along.
Type Eat Implements AI.Action
Field eaten:Double
Method Tick:Int(seconds:Double)
Self.eaten = Self.eaten + seconds
If Self.eaten < 3D Then Return AI.Result.Running
Self.eaten = 0D
Return AI.Result.Success ; Three seconds later, dinner's over.
End Method
Method Abort()
Self.eaten = 0D ; Stopped early, so start afresh next time.
End Method
End Type
A condition is a Type that Implements AI.Condition, with a Test method that
returns True or False. Put it first in a sequence, and the steps after it
only happen when it says True.
Type Hungry Implements AI.Condition
Method Test:Int()
Return hunger > 50 ; hunger is a Global of the game's.
End Method
End Type
Local hungry:Hungry = New Hungry
Local eat:Eat = New Eat
Local dinner:AI.Node = AI.AddSequence(tree, root)
AI.AddCondition tree, dinner, hungry
Local eating:AI.Node = AI.AddAction(tree, dinner, eat)
AddWait adds a step that does nothing for a number of seconds, so there's no
action to write. Here the pet has a nap after its dinner:
AI.AddWait tree, dinner, 1.5D
ActiveNode gives you the action or wait that's running, or Null. Keep the
nodes you want to check when you build the tree, as eating is above, and
compare:
If AI.ActiveNode(tree) = eating Then Text 10, 10, "Eating"
ResetTree stops whatever is running, calling its Abort, and the next
update starts again from the top, as when a character respawns.
AI.ResetTree tree
An update does at most 64 small steps of work, so that a big tree can't stall
your game. A selector with eleven or more branches that each start with a
question can run out of steps before it decides, and then it carries on in the
next frame. If TreeSuspended often says so, allow it more:
AI.UpdateTree tree, seconds, 256 If AI.TreeSuspended(tree) Then DebugLog "Still deciding"
Some choices are a matter of degree: a pet that is very hungry and a little
sleepy should eat first. blitz.decisions.utility asks each option for a score
from 0 to 1, and picks the highest. It doesn't flip-flop: it keeps its choice
for at least a quarter of a second, and after that another option has to score
more than 0.1 higher to take over. A score of 0 means "not now", and a choice
whose score drops to 0 gives way at once.
; At the top of the program:
Import blitz.decisions.utility As Utility
Type Need Implements Utility.Evaluator
Field amount:Double ; From 0 to 1. The game changes it.
Method Score:Double()
Return Self.amount
End Method
End Type
Local appetite:Need = New Need
Local sleepiness:Need = New Need
Local needs:Utility.UtilitySelector = Utility.CreateUtility(Null)
Utility.AddOption needs, "eat", appetite
Utility.AddOption needs, "sleep", sleepiness
; Then, each frame:
Select Utility.UpdateUtility(needs, seconds)
Case "eat"
; Head for the food bowl.
Case "sleep"
; Head for the basket.
End Select
It gives back the name of its choice, or "" when every score is 0.
UtilityOptions changes the quarter of a second and the 0.1. Delete the
selector before the Need objects it uses.
Blip's tip
A selector asks its questions again every frame, so a more important branch can always take over. A sequence doesn't: once one of its actions is running, it goes straight back to that action each frame, without asking its question again. So an action has to notice for itself when it should stop, as
ChaseYoudoes when you get away.
Null as its parent.UpdateTree, so you're in charge of
pausing and slow motion.ActiveNode, but never delete them.eaten does above.Four more complete programs come with the module:
The reference below has every function and rule.
blitz.decisions.utilityUnpublished 0.1.0 preview. Extended object-lifecycle-v1 (runtime 1114,
module ABI 5 or newer) is required. No package dependencies. Main-thread only.
Blitz3D+ comes with this module, so any Extended program can
Import blitz.decisions. Open an example and run it. No binary assets or
network connection is needed.
examples/quick_start.bb: a wait followed by an opening gate. R resets it.examples/guard.bb: danger, pursuit, patrol and idle; input changes the world,
and the selected behaviour moves the guard. Shows the active node and Abort.examples/budgeted_agents.bb: independent agents with tiny traversal budgets,
queued reset from Tick, delayed preemption and explicit teardown.Each has a finite --verify mode that checks the advertised interaction. The
application captures input, updates decisions with seconds, applies movement
inside its own Action, then draws. The library never polls input or clocks.
Result.Success, Result.Failure, Result.Running are Int enum constants.
Action supplies Tick(seconds:Double):Int and Abort(); Condition supplies
Test():Int (zero is false, nonzero true). Callbacks must return promptly.
Actions and conditions are borrowed and must outlive their trees. Per-agent
state belongs in per-agent behaviour instances; explicitly stateless behaviours
can be shared. Neither navigation nor movement is built into the library.
CreateTree():Tree returns an owned tree. Build it with AddSequence(tree,parent),
AddSelector(tree,parent), AddAction(tree,parent,behaviour),
AddCondition(tree,parent,condition) and AddWait(tree,parent,seconds).
All return borrowed Nodes. Pass explicit Null for the single root: object
optional defaults are not supported by the compiler. Only sequences/selectors
accept children. Each addition creates a fresh node, so cycles/moves are not
representable. Maximum depth is 4096 nodes including the root. Empty composites
are rejected at first Update. Structure freezes permanently at that Update.
TreeSuspended(tree):Int is True when the latest UpdateTree used its whole work
budget before reaching a decision; its Running result then means "not decided
yet" rather than "an action is running". A guarded branch Seq[Cond, Action]
that fails costs about six steps, so a selector with eleven or more such branches
exceeds the default budget of 64; raise work if TreeSuspended is True every frame.
UpdateTree(tree,seconds,work=64):Int returns Result. A completed traversal can
start again on the next call; a game may stop calling after Success/Failure.
ActiveNode(tree):Node returns the currently selected running action/wait or
Null. Compare identity with your stored nodes; there is no mutable public graph.
ResetTree(tree) aborts running work and clears execution/time, keeping the
frozen definition. Delete tree aborts and releases owned nodes/collections.
Never delete a borrowed node. Delete behaviours after the tree. Null/deleted
tree operations, invalid input and callback misuse report contextual RuntimeError.
There is no fallible I/O, LastError, Save or Commit API. Reset is an execution
operation, not a disposal alias; cleanup never completes gameplay actions.
Sequences remember their running child, including when budget suspension occurs while returning through ancestors. Selectors start at their highest priority child on each new traversal. A suspended traversal resumes before starting a new one: a tiny budget does not repeatedly test the first condition forever.
The old running leaf stays selected while a candidate's conditions are tested. Reaching a different action/wait commits replacement: detach the old leaf, deliver its single Abort if it was an action, unwind its abandoned memory path, then tick the replacement. A condition-only terminal traversal commits at its root. Candidates containing an action commit before that action's Tick even if it immediately fails. There is no rollback of callback side effects.
Work counts interpreter steps (entry, child dispatch, return propagation and
abandoned-path unwind), so deep traversal/unwind can suspend. It excludes the
callback's own work. No recursive traversal or per-visit frame objects. The Stack
grows to the maximum visited depth and reuses that capacity.
Initial structural validation and explicit Reset/Delete cost O(nodes). A normal
update uses at most work interpreter steps and O(depth) retained stack space.
Conditions sample the world when called; suspension does not snapshot game state.
Finite nonnegative seconds accumulate while traversal is suspended. Waits consume only their remaining duration and pass overshoot onward. An Action consumes all pending seconds because Tick does not report unused time. Successor actions in that same call receive zero seconds. New calls accumulate new time even when finishing the prior traversal. Completion discards unconsumed time; Reset intentionally discards it. Budget suspension never discards time. An accumulated-time overflow is a programming error rather than infinity. Binary64 rounding applies to time; fixed exactly representable deltas are useful in tests.
Recursive Update and owner Delete during Tick/Test/Abort are errors. Reset may be queued from Tick; it is applied after that callback returns and Update returns Running. Reset during Test/Abort is an error. Final Abort runs with the tree inactive and cannot restart/reset it. Read-only ActiveNode is available during callbacks; it reports Null during Abort. No callback runs while deleting nodes.
Import blitz.decisions.utility As Utility. It is independently usable, adds no
dependency and does not import the tree core. Selection never invokes game actions.
Type Desire Implements Utility.Evaluator
Field value:Double
Method Score:Double()
Return Self.value
End Method
End Type
Local desire:Desire = New Desire
desire.value = 0.8D
Local selector:Utility.UtilitySelector = Utility.CreateUtility(Null)
Utility.AddOption selector, "heal", desire
Print Utility.UpdateUtility(selector, 0D) ; heal
Delete selector
Delete desire
| Declaration | Contract |
|---|---|
Evaluator.Score():Double | Borrowed callback, finite 0..1; zero means unavailable. Called once per update in registration order. |
UtilityOptions | Caller-owned value record. switchMargin:Double=0.1D, finite 0..1; minimumHold:Double=0.25D, finite nonnegative seconds. |
CreateUtility(options:UtilityOptions):UtilitySelector | Explicit Null selects defaults; validates and copies options. Caller owns the result. |
AddOption(selector,name:Str,evaluator:Evaluator) | Borrows evaluator; copies a nonempty, case-sensitive unique name. Add before the first update. |
UpdateUtility(selector,seconds:Double):Str | Finite nonnegative seconds. Returns a registered name or empty string when none is available. O(options); the only allocation is the returned name string. |
UtilitySelector | Private factory construction and state. Delete releases registrations without Score calls or deleting evaluators. |
The greatest positive score wins initially; equal scores use registration order.
An available current option stays until its minimum hold has elapsed and a
challenger strictly exceeds its score plus the switch margin. Equality retains
the current option. Scores are capped at 1, so while the current option scores
above 1 - switchMargin no challenger can displace it; it changes only when its
own score falls. Use a smaller margin if top-scoring options must stay contestable. If the current score becomes zero, both rules are bypassed.
All-zero scores clear selection. A new selection starts hold at zero; time before
that selection does not count. Hold accumulation saturates, avoiding overflow.
No random state or wall clock is involved. Very small positive scores remain
available; all arithmetic follows binary64 precision.
Registration freezes at the first update, including an empty update. Evaluators can read changing game-owned state; they cannot add options, recursively update or delete their selector during Score. Score has no queued mutation facility. Return from the outer update before deleting. Share evaluators only when their state/lifetime contract makes that safe. Delete selectors before evaluators. See utility choices: H changes health, D changes danger, Space reloads the target, and the returned choice drives real state changes.
No parallel/concurrent nodes, decorators, generic blackboard, worker execution, graphical authoring, persistence or navigation/state adapters in v1. See licence, provenance and changelog.