The following blog post, unless otherwise noted, was written by a member of Gamasutras community.
The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.
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.
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.
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.
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.
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?
Our goal was to avail BT everywhere timely tasks are involved. For this to happen Status needed to be small and mighty (as the Mighty Bool) and our composites more nimble than if-elses.
Core library
The smallest unit of work in our library is a status expression (not an object, function reference or lambda). Where expressions go, anything goes:
- Parameterisation is built-in (use functions),
- Statefulness is possible (use objects)
- Conventional programming is okay (conversions from bools, statements, traditional control flow)
The library does not centralize control; we can use our own, dedicated update loops and tickers or MonoBehaviour‘s Update() – even the upstream ticker built into a pre-existing visual solution.
To make this possible, we designed a calculus:
- Sequences overload the conditional logical AND (&&)
- Selectors overload the conditional logical OR (||)
- Parallel execution is implemented via PLUS (+) and MUL (*).
Implementing sequences and selectors in this way is possible in C# because overloading preserves the short-circuiting behavior of the conditional operators (three cheers to SQL, 3VL and enterprise computing).
An example using a sequence:
status Snipe() => Load(gun) && Aim(at: target) && Shoot();
And another using a selector:
status Step() => Attack() || Defend() || Retreat();
Although we often abuse the expression bodied notation (=>), this of course is optional since any function returning status may partake the behavior tree(s):
status Grab(){
if(!inProgress){
if(!target) return fail(log && "No target");
if(isGrabbing) return done();
}
return MoveTo(target)
&& Play("Grab", Effect, delay)
&& isGrabbing;
}
NOTE: A perceptive reader might question why fail() and done() are functions. This hides debugging information injected at compile time, and provides a hook for logging/tracing APIs.
In all, the library core fits 100 loc, and is MIT-licensed.
Decorators and stateful composites
With all reservations about stateful control, there are situations where you want a cooldown or timer; stateful composites are also useful, notably when steps are performative (such as a ritual or dance) or later steps appear to undo prior steps.
Similar to co-routines, stateful composites impose an ordering on tasks – the idea here is once done is done (whereas stateless composites go by if undone, do it over again).
The next example implements the main controller in a simple shooting game using a stateful sequence. In this case the controller fully owns the flow of interaction so there is no interference and stateful control is safe.
The same example also demonstrates decorator syntax (After inserts a two seconds delay) and shows mixing stateful and stateless composites:
override public status Step() => Sequence()[
and ? DisplayMenu
: and ? (Exit || StartPlay)
: and ? Play
: and ? After(2)?[ DisplayScore && Reset ]
: loop // "end" if you'd rather not loop over.
];
NOTE: the ternary switch pattern is less elegant than conditional operators, however we do need hooks for tracking state, and we still avoid computationally expensive alternatives (var-args and closures allocate on the heap).
Finally, a self contained example to emphasize the decorator syntax:
Shoot() => Button("Fire1") && Cooldown(0.1f)?[ Fire() ] )
Under the hood, decorators leverage the null conditional operators and abuse the diagnostics API (works on iOS too) to create site bound objects (so you can, but need not declare a field for every cooldown/timer).
With a year of hindsight and some, Active Logic is a fairly stable library. It is tightly integrated with the C# language, features visual tracing/logging and does not dictate how an engineer should organize their code or generate significant overheads.
My purpose in writing this article was part introducing the library, part encouraging others to more seriously consider BT’s benefits.
Object oriented and functional languages have not been designed with intelligent control in mind. In this sense our library perhaps should not exist. In C#, we relied on a dependable, yet unlikely combination of obscure, newer and accidental language features.
Compared with conditional operators, the ternary syntax is lesser. It is portable (think C++, Python) but may only support stateful composites(*).
The take home message here, is that intelligent control matters; by-passing DSLs, it may be implemented today in object oriented and functional languages; with minor, non breaking changes to the target lingo, small performance overheads and syntactic quizziness may be smoothed over; concerted efforts will make this happen.
(*) Edit: I previously wrote that the ternary switch notation could support stateless composites. Although I keep my eyes on the prize, that is very probably a no.
Designing and implementing Active Logic has been a peculiar journey, and I am hoping to see delightfully crafted AIs utilizing this tool.
The core library is engine agnostic, available on Github (AGPL), and there is also a commercial license (via the Unity Asset Store).
Dramatic improvements to the library would require extensive usage, extensive feedback, or groundbreaking improvements to the C# language; with this in mind I am interested in hearing from (and perhaps contributing to) projects that may take advantage of this technology.
This has been a fairly top-down overview; I may follow up with a hands-on article.
The Active Logic library stemmed from our independant game project, Antistar. Antistar is a real time adventure game, and the range of applications we originally envisionned includes ecosystem behavior, squad AIs and less rigid approaches to conversation management. While the game’s codebase largely predates our BT library, not crediting the darling project that started it all may be a bit uncouth. Antistar will be presented at Tapei Game Show in 2021.
Until then. My encouragement goes to the skeptical game logic programmer: behaviors tree are a silver bullet – here’s a gun, go shoot werewolves.
