Are you familiar with behaviour trees?

Authoring General Design Discussions
1

In working on my own IF projects, I am making use of behaviour trees (I think this is a good article that describes them conceptually and in-depth). In a nutshell, they are a way of combining queries (that ask questions about the game state) and actions (that alter the game state) into a structure that has a clever trick. They are programming without a lot of programming.

TLDR? Okay, a few key concepts:

We are going to talk about “tasks”, which are either composites (that structure other tasks), queries (that succeed or fail based on the game state), or actions (that alter the game state). And tasks “succeed” or “fail”. Let’s introduce a couple of composite tasks:

SELECT A, B, C, D

SELECT is an example of a task and is a composite task because it has “child” tasks that it operates on. In this case, it executes the tasks A, B, C, and D. If any of them succeeds, it stops there, and SELECT is considered to have succeeded. If A, B, C, and D all fail, then SELECT fails also.

SEQUENCE A, B, C, D

This executes tasks A, B, C, and D in turn. If any of them fails, it stops, and SEQUENCE fails. If they all succeed, SEQUENCE succeeds.

So, SELECT picks the first task that succeeds, and SEQUENCE ensures that all tasks succeeded. We can use just these two concepts to build quite sophisticated behaviours.

Here are a couple of simple SEQUENCE examples:

SEQUENCE
  BOB_IS_THIRSTY
  BOB_HAS_WATER
  BOB_DRINKS
  1. If Bob isn’t thirsty, this sequence will fail.
  2. If Bob is thirsty but has no water, the sequence will fail.
  3. If Bob is thirsty & has water, he takes a drink.

A likely consequence of BOB_DRINKS is that he’s no longer thirsty and has less or no water.

SEQUENCE
  BOB_SEES_WATER
  BOBS_FLASK_ISNT_FULL
  BOB_FILLS_FLASK
  1. If Bob doesn’t see water, this sequence will fail
  2. If Bob’s flask is full, this sequence will fail
  3. If Bob bob sees water & his flask isn’t full, he’ll fill the flask.

Here’s a slightly more complex example arising out of a game I am building that uses SELECT to combine SEQUENCES and build an NPC behaviour:

SELECT
  SEQUENCE
    BLACK_RONIN_IS_WOUNDED
    SELECT
      SEQUENCE
        BLACK_RONIN_IS_IN_MONASTERY
        BLACK_RONIN_HEALS
      BLACK_RONIN_MOVES_TOWARDS_NEAREST_MONASTERY
  SEQUENCE
    BLACK_RONIN_SEES_PLAYER_TRAIL
    BLACK_RONIN_MOVES_IN_PLAYER_DIRECTION
  SEQUENCE
    BLACK_RONIN_SEES_PLAYER
    BLACK_RONIN_AMBUSHES
  BLACK_RONIN_MOVES_IN_RANDOM_DIRECTION

In my game, the Black Ronin hunts the player unless he’s wounded, in which case he heads for a monastery and, when he reaches one, heals. If he catches up with the player, he will attempt to ambush them; otherwise, he heads in a random direction hoping to pick up the player’s trail.

Something interesting about this is that the person building these behaviours doesn’t have to be the person implementing the queries (like BLACK_RONIN_IS_WOUNDED) and actions (BLACK_RONIN_HEALS). As long as they can master the concepts of SELECT and SEQUENCE, they can use them to build relatively complex behaviours.

It’s programming, but with a built-in structure and a relatively limited set of concepts you need to understand/use (there are more than SEQUENCE and SELECT, but these are fundamental). I wonder if people who are more authors than programmers might succeed with this where they wouldn’t cope with, for example, an equivalent Javascript function (or building this in something like TADS or Inform).

In practice, instead of BLACK_RONIN_IS_WOUNDED, I have a query task ACTOR_TEST actor=black_ronin attribute=health test=LT value=75. This is a little more verbose but allows me to apply tests to different attributes of different actors with one type of query. But if you wanted, you could build per-actor queries that directly modelled what you wanted to know.

Does anyone else find this approach interesting for creating NPCs with their own agency & motivation?*

Matt

  • In fact, I use them beyond this in terms of how things like items & even locations can respond to/modify the game state.
4 Likes
2

Is what you describe above a tree? The link you provide certainly is; there is a branching structure. What you have seems more like a list. That is not to say what you are doing is wrong, only that it may not be quite what you say it is. And does that matter? Well, yes. Because my daughter is doing a project and will get extra marks if she includes a behavior tree, so it is important to ME exactly what that would be.

Besides the (possibly trivial) labelling issue, I absolutely do use this design. Not in anything I have released yet, but it is a part of QuestJS, and I have looked at implementing reactive NPCs in this way. I am doing it entirely in JavaScript; QuestJS provides the infrastructure, the author provides the data in a big list. There is an example in the documentation:

1 Like
3

It is a tree. The branching structure is described by indentation. You can always go back and forth between a tree and an indented list this way.

I haven’t used behavior trees, but I’ve seen them. (My current day job game makes use of them, so I see them go by in code reviews.)

The idea of a behavior tree is startlingly similar to the way you might write branching behavior in Ink or a similar language:

"What's that?" my master asked.
*	"I am somewhat tired[."]," I repeated.
	"Really," he responded. "How deleterious."
*	"Nothing, Monsieur!"[] I replied.
	"Very good, then."
*	"I said, this journey is appalling[."] and I want no more of it."
	"Ah," he replied, not unkindly.
	"I see you are feeling frustrated. Tomorrow, things will improve."

In Ink, * marks branches of a SELECT (a player choice); otherwise a group of lines is implicitly a SEQUENCE. Queries are { conditions }. This isn’t an exact parallel but it shows a similar approach.

Behavior trees as they’re generally described add two key ideas to the basic approach:

  • A SELECT has some degree of backtracking. A condition failure down in the depths of a SELECT branch can kill the whole branch, and then the SELECT considers the next one. (It’s a bit Prolog-like if you want to think about it that way.)

  • The tree is constantly being re-evaluated, so that it describes the NPC’s behavior moment by moment. In parser terms, this is “every turn”. (In real-time games, there’s some notion of pausing in a single “running” node for N seconds while an animation plays out. I don’t have a good sense of how that works though.)

This is interesting stuff, but as I say, I haven’t played with it. People who are more familiar with (say) I7 extensions will have to say if there are already ways to do this in the I7 world.

4 Likes
4

If I’m understanding correctly, I believe this is the way pretty much everything is done in Dialog, which is a Prolog-like language designed for IF purposes. In particular, its fundamental query structure gives you SELECT and SEQUENCE.

1 Like
5

Are these trees? Yes. They have a root node and nodes branching from the root. The first two examples are elementary trees but still trees. Perhaps my use of indentation to show structure isn’t clear? I’m not sure there is a better way in a post, but perhaps a diagram will help.

BTExample
BTExample3528×1620 170 KB

6

This is fascinating; I have looked at Ink but didn’t make this connection.

Inks dialogues seem perhaps more immediate and about constructing player output text. Maybe that’s why I didn’t see it. I wonder how well they scale and how well the implicit connections work in a big tree.

Thanks for sharing.

7

Most interesting.

Here’s how it would work in Strand. Strand doesn’t have behaviour trees per se, but you’d construct them from terms

The main difference is that Strand doesn’t use white-space indentation to mean anything, so consequently the “indented” parts have to be given their own names. In this case RON1, RON2, RON3 (say).

RONLOOP<   // this runs every turn for ronin
* RON1

RON1=
*?BLACK_RONIN_IS_WOUNDED RON2
* RON3

RON2=
*?BLACK_RONIN_IS_IN_MONASTERY BLACK_RONIN_HEALS
* BLACK_RONIN_MOVES_TOWARDS_NEAREST_MONASTERY

RON3=
*?BLACK_RONIN_SEES_PLAYER_TRAIL BLACK_RONIN_MOVES_IN_PLAYER_DIRECTION
*?BLACK_RONIN_SEES_PLAYER  BLACK_RONIN_AMBUSHES
* BLACK_RONIN_MOVES_IN_RANDOM_DIRECTION


// example definitions of some of these

BLACK_RONIN_IS_WOUNDED > is ronin health wounded

BLACK_RONIN_IS_IN_MONASTERY > is ronin in monastery

BLACK_RONIN_HEALS
> set ronin health good

BLACK_RONIN_SEES_PLAYER > is ronin in here
8

Rez doesn’t use whitespace either but I felt adding the real syntax might obscure the point. What it actually looks like:

@actor black_ronin begin
  behaviours: ^[SELECT [
                 [SEQUENCE [
                   [BLACK_RONIN_IS_WOUNDED]
                   [SELECT [
                     [SEQUENCE [
                       [BLACK_RONIN_IS_IN_MONASTERY]
                       [BLACK_RONIN_HEALS]
                     [BLACK_RONIN_MOVES_TOWARDS_NEAREST_MONASTERY]]
                 [SEQUENCE [
                   [BLACK_RONIN_SEES_PLAYER_TRAIL]
                   [BLACK_RONIN_MOVES_IN_PLAYER_DIRECTION]]
                 [SEQUENCE [
                   [BLACK_RONIN_SEES_PLAYER]
                   [BLACK_RONIN_AMBUSHES]]
                 [BLACK_RONIN_MOVES_IN_RANDOM_DIRECTION]]]
end

I mean, it doesn’t look like this either because the specific tasks are different, but structurally this is what I am writing. Also, yes, I have written a lot of Lisp code :slight_smile:

9

Very interesting. I spent a little time looking at Dialog and saw much that I liked. If I had been building parser-based games or targeting the Z-machine, I am sure I would have tried it.

10

One way this can be managed for real-time games is by using a threadpool for agent decisons (which is also a sensible approach for things like route-finding since you need some control over your scope-in-time to make the next frame reliably, anyway). An animation playing takes the agent out of the queue for a thread.

11

I based my behaviour trees on the Crysis implementation though I didn’t copy the ability to return a “running” status which is how this typically seems to be handled.

For example, a path-finding task node might do some work and then return “running” rather than “success” or “failure”. On the next tick, when the tree is executed again, it starts with the running node allowing it to continue.

It didn’t seem to make sense in the context of a non-realtime game, so I didn’t bother to implement it.

12

Behaviour trees look very powerful to me, so long as story state is not a consideration. Like pathfinding, a sort of figuring-out of how to achieve an outcome in a story-consistent way.

Managing guard conditions across trees might be a challenge though. When an NPC smashes a door to enter a room, he denies any further opportunity of unlocking the door. Hence no need for keys. So some puzzles become unnecessary. And because clever puzzles have significant side effects, that means those side-effects won’t happen. Interesting variations become unavailable, etc.

13

But this implies that a behaviour tree allows an NPC to smash a door down, which you, as the author, decide. Why can’t the NPC have their own key and relock the door after them? The behaviour tree mechanism doesn’t create these situations or have any inherent implication on the type of puzzle you can create.

1 Like
14

Yes indeed, I think maybe you have re-stated the point I made above. NPC behaviour ought to enhance, not diminish the player experience. Therefore cannot trespass into puzzle space.

15

This I7 Event Chains extension seems similar.

2 Likes
16

Modulo, I cannot get on with the Inform7 approach; yes, I think you are right.

17

Perhaps. I agree with you player experience is, ultimately, what is essential.

But you are setting up a dichotomy between NPC behaviour & puzzles that feels arbitrary to me. Both are elements of a game’s design. I would agree that NPC design without consideration of puzzle structure could present problems for both. But I don’t see why an author would set out to do this rather than integrate them.

Then again, I neither enjoy nor want to create such puzzles, so perhaps I miss something important.

1 Like
18

I am heartened to see that this concept is in play in several IF systems.

A challenge I am thinking about is what I call the “integration and sequencing” challenge.

I get the impression that in most BT-based games (here, I am talking about FP/shooter-type games where this technique grew up), there is one big behaviour tree, and the range of actions available is relatively low, and the tree is looped at high-frequency.

I have found it more natural to break things up so that, e.g., an actor has a behaviour tree, a faction has a behaviour tree, a plot has a behaviour tree, a location has a behaviour tree and so on.

In the “one big tree” situation, there is always precisely one action that can result (the success or “running” path of the tree). But you’re running the tree so fast that it appears simultaneous actions can occur.

But I have many trees and are run with much greater intervals in between (e.g. after a player has taken an action). Using Rez, a game is designed in terms of Scenes into which Cards (the primary content presenting mechanism) get played. Dialogue with an actor, for example, could be its own scene and present different layouts and interactions to other parts of the game.

So perhaps an NPC wants to trigger a dialogue with the player, so a task in their tree might be [actor/begin-player-dialogue actor=black_ronin scene=issue_challenge], but if two NPCs happen to do this at the same time, now I have a problem.

Two possible approaches I am considering, although I would welcome other suggestions, are:

  1. Instead of an NPC being able to trigger an engagement, we collect together all such side effects of the tree and present a menu to the player. So if the Black Ronin & Master Shu want to speak to the player, the player decides what to do. This makes the event loop more complicated and has two apparent side-effects: (a) the player could set up an advantageous order of events that we don’t want, and a scene may branch out; how do we get back to the choice point?

  2. Drive all such interactions through plots. I borrowed the “plot clock” notion from Blades in the Dark. My plots have an inherent priority. So the side-effect would trigger a plot that then drives the interaction. If two plots want to advance, there is a straightforward way (through the plot priority) of breaking deadlocks.

I’d be interested to hear what any of you folks think about all this.

19

I suspect the one big tree approach works well for FPS games because all the NPCs are doing the same thing - looking for and then attacking the player. I would guess the tree has nodes that allows for differentiation between NPC types - if the NPC has a sword, go down this branch, etc.

Whether that works for a particular IF game depends on the degree of commonality between NPCs. For interesting NPCs the player can talk to, probably not a lot, and i would give each NPC its own.

Can you define a branch that all NPCs would use, that can be defined somewhere and then grafted on to the individual trees?

I further split trees between roles for an individual NPC, so potentially one for conversations, and another for giving the NPC something, and a third that gets used every turn to decide what she is actually doing.

20

Why not simply have your begin-dialogue action fail if the player is already in a conversation?