Since Isla's seminal article, behavior trees (BT) have become a well recognized framework for designing and managing game AIs.
Even so, a game logic programmer may not immediately perceive their usefulness, and AI engineers may occasionally tell you that they aren't really game AI. Are GOAP, HTN and Utility AI the next big thing?
Shopping for AI solutions, we experimented with state machines, behavior trees and GOAP; this helped crystallize long standing intuitions about game logic and intelligent control. I discuss stateless vs stateful control and the key decisions which informed the design of our BT library.
Why BT?
Behavior Trees partake intelligent control. Compared with AI solutions of like vintage (such as GOAP) BT is more control, less problem solving. You may read Chris Simpson's comprehensive introduction, but I'll give you a quick run-down anyway:
With BT, the unit of work is a task; a task is always running, failing, or complete.
BT composes tasks using sequences and selectors. A sequence iterates children, until the first non-successful task is encountered; a selector iterates until a non-failing task is found.
BT advocates emphasize modularity and responsiveness. This perhaps makes sense when comparing BT with finite state machines (FSMs). To the skeptical game logic programmer, however, that is no selling point: computer programs are modular, update loops are responsive.
In game programming there is a long standing intuition that timely activities may be expressed using imperative forms, much as we write (immediate, functional) conventional program code; this intuition trips game programming hopefuls. Humming to the tune of "hey, my logic is not working" here is a variant of what is commonly seen in game programming forums:
void Snipe(){
Load(gun);
Aim(at: target);
Shoot();
}
Running counter to functional programming does not invalidate this intuition: action queues, co-routines and (syntactic sugars over) event-driven programming, all in some degree answer this. With BT, sequences and the running state address the same problem.
In engaging BT, however, we acknowledge that a better solution to modeling timely activities without pain requires intelligent control. So here's a couple of things BT does implicitly, which are well beyond the grasp of action queues and co-routines:
A task "up the tree" will interrupt lower priority work. In the above example, this could mean avoiding a grenade while aiming, or loading a gun.
Failed tasks re-iterate, complete tasks will skip; this means both resilience and, quite often, the illusion of purposeful, mindful behavior.
BT offers a concise, effective framework for managing timely activities - associating intuitive task descriptions with a flexible (switch/skip/reiterate) execution model
Looking at the big picture, BT stands the middle ground between smarter AIs (HTN, GOAP, Evolutionary, ML) and traditional control; it may be used on its own, or in combination with other techniques.
In all we decided to focus on BT because we wanted to fix, enhance, condense and clarify "everyday game AIs". Game AIs which, being mostly rule based, are not conceptually involved, and a standard fare to game logic programmers.
BT may be implemented as a stateless control strategy; modern iterations, however, have become increasingly stateful. In the next section I discuss the affinity between stateful control and logic hell.
Stateful control is evil
In a dynamic (game/simulation) environment, responsiveness and correctness are not achieved by storing state. Stored state is a by-product of circumstance (world state). Provided world state changes fast enough, caches get out of sync, game logic breaks down.
Wanting a yardstick to evaluate game logic frameworks? Question control strategies that systematically create, store and manage (or require the programmer to manage) control state.
With this yardstick in hand, let's revisit a few well accepted gadgets in the game logic programmer's toolkit:
Event driven programming is stateful: handlers are registered and stored. This style of programming does not scale to complex game AI.
Co-routines are stateful in that program stacks are stored and restored at every frame. The resulting agents commit (blindly) to action courses that a changing environment will soon invalidate (keep reloading, grenade headed your way).
Unity's component architecture is inherently stateful (moving parts), and biases towards parallel execution: running components in parallel is easy (and useful), ensuring they will not is often desirable and it is (too much) work.
Staggering and reducing frame rate requires less control state. As such running sub-systems (such as apperception, or control) at a lower frame rate is a (relatively) safe optimization.
This distinction, between stateless and stateful control, informed the design of our BT library; to put things in perspective, we spent perhaps 80% of development time working on stateful constructs, and recommend their use in perhaps 15% of use cases.
As a rule of thumb, bugs caused by stateful control are caught in QC (including after release). Bugs caused by stateless control are caught by functional testing, and QC aren't going to see them.
Where is the "AI" in Behavior Trees?
Now that we have covered the distinction between stateless and stateful control, let's consider BT from a game AI point of view, as we should like our logic to handle complex, believable agents.
STRIPS orientated approaches (think GOAP) emphasize planning intelligence; this is problem solving. A GOAP agent searches through available action courses; a plan is generated; as with path-finding, frequent re-planning is advised.
With BT, a static plan is manually crafted (or perhaps synthesized - as with ML or evolutionary techniques); thus, in composing tasks the designer specify "good behavior".
This approach isn't altogether restrictive: plans are branching constructs; BT agents are allowed to drop, switch between, and re-iterate tasks.
This is intelligent control closely resembling how humans acquire and utilize knowledge. We share 'recipes' about how to do X. In performing (applying the recipes) we do not mind being interrupted (prioritize tasks) or re-doing failed steps. Also we are not ordinarily bothered by not knowing why or how the recipes actually work.
GOAP, then, partakes planning intelligence; whereas BT provides intelligent control. Atomizing problems into component actions and their expected outcomes (GOAP) is science; encoding "good behavior" (be it a winning strategy, a cooking recipe or the life cycle of dragonflies) is (technical) design.
BT is computationally cheap (no search) and bears a close affinity to how both designers and software engineers approach domain knowledge.
Off the shelf: visual solutions and EDSLs
There is a wealth of BT solutions available. Many focus on visual scripting; others use (embedded) domain specific languages (EDSLs). Finally, some provide ad-hoc scripting languages.
What do these solutions have in common? In all cases developers have determined that integrating with a general purpose language (such as C#, C++ or Python) is unpractical or perhaps undesirable. The development effort then, is on par with building a separate runtime. Conversely users are tied to a proprietary system involving custom constructs and abstractions.
Visual solutions often overlook tools that, from a programmer's point of view, are indispensable - such as being version control, testing or search friendly. Bearing in mind that visual solutions are not without merit, we simply wanted a robust engineering foundation.
With DSLs you are not throwing the host language away: it is more like carrying its corpse in your arms. Less graphically: skimping on the effort of writing a proprietary parser (or forking an existing compiler), DSLs also do not readily interface with the host language. Consistently, BT literature (which mainly covers DSLs and visual solutions) features:
Articles about parameterizing behavior trees (reinvent functions)
Conditional nodes (reinvent control flow)
Custom reuse (such as linking a behavior tree from another)
Across the board, DSLs also lead to confusing compiler errors, confusing debug traces and degraded performance.
Necrophilia aside (put the corpse down).
After reviewing existing solutions (notably for Unity and C#), our overall conclusion was that a library scaling from the nitty gritty details of procedural animation to high level behaviors was missing.
Conceptually we started thinking of behavior trees as a clever, elegant approach to coding update loops (no more, no less) but there was not a library "out there" providing seamless integration with C# or another object language.
Control in OOP languages is relatively inflexible; perhaps this library could not be engineered?
Designing our BT library
Our goal was to avail BT everywhere timely tasks are involved. For this to happen Status needed t
