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.
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.
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.
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
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.
Modulo, I cannot get on with the Inform7 approach; yes, I think you are right.
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
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:
-
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?
-
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.
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.
Why not simply have your begin-dialogue action fail if the player is already in a conversation?
It makes sense, but dragons are lurking.
That task doesn’t directly trigger a scene change & conversation because I’m not running one tree but potentially a dozen trees when an action is performed.
Now you’re right that the task could look to see if a previous version of that task has already been queued and failed there. But that makes it a first-come, first-served approach, and the author doesn’t have a way of saying, “this actor is more important than that actor.” (I don’t think that approach can work because it will always be context specific).
I could add a “speech priority” attribute to the task so that one task will win out, but if the last task has the highest priority… well, other tasks will have already succeeded when they shouldn’t have.
Perhaps I could run all the behaviour trees in parallel and specific tasks can block waiting for all other tasks of the same type to have completed, and only one can succeed, and the rest fail. That feels like a recipe for deadlocks and painful debugging sessions.
It’s messy, and I haven’t thought of a clean solution.
I feel that tying this to plot & plot clocks while making the author structure things a little differently could end up being more straightforward in the end.
It’s definitely an interesting idea but I’ve not conjured any formulation of “merging” trees that is conceptually easy enough for me to follow and think I could live with over time.
I’ve considered just having one behaviour tree, but it creates a significant authoring challenge as it quickly becomes unwieldy.
In fact I like your idea of subdividing the tree even further along functional lines. I’ll think about that.
I think this is the big issue - you need something that is easy to understand and to follow in six months!
1 Like
NPCs can do different things, but you can represent them as large-scale branches in the big tree. Patrollers take this branch until they sight the player. Rabbits have a whole other branch involve looking for lettuces.
The point, as Matt implies, is that you’re really answering exactly one question: what does this NPC do right now? One tree can handle that.
Breaking it up (actor, location, faction, time-of-day?) sounds tempting to me because I’m used to I7! But it’s tricky all right. I7 groups distinct rules into rulebooks, and the only question is what order to check them in. (And that’s already fraught.) Grouping distinct micro-trees into… what? A big composite tree? Interesting problem. Which I don’t have a solution for. :)
Don’t tempt me to add time-of-day! 
While working on Rez, I came across the RPG “Blades in the Dark” by John Harper. I haven’t played Blades, although I have read the rulebook several times. Something cool it introduces is “progress clocks”:
“Sneaking into the Bluecoat Watch Tower? Make a clock to track the alert level of the patrolling guards. When the PCs suffer consequences from partial successes or missed rolls, fill in segments of the clock until the alarm is raised.”
There are all different kinds of progress clocks that can be operating at the same time in a Blades game.
So I have borrowed them, and Rez has a @plot element to define a plot with a clock and, crucially, a priority, i.e. one plot can be more important than another.
So what I am thinking is that narratively an NPC engaging with a player to initiate dialogue (rather than a player initiating dialogue with an NPC) must be part of advancing a plot. So the behaviour tree task advances the plot and potentially triggers dialogue.
We can use the plot priority to queue the encounters if two plots have advanced in this way in the same “tick”.
I’m still playing with it in my mind. But by gating this kind of thing through a plot, I think (I mean, I hope) it keeps it simple for the author to reason about why things are happening (including later on when they have forgotten everything!).
I recently played Citizen Sleeper, which directly adapts this mechanic to a computer game.
1 Like
I’m just looking at it now on Steam. Interesting that they even call out these mechanisms on the store page. I guess I should give this one a go and see how they implement things. Thanks for the pointer.
There’s also…I’ve been hesitating to mention it since it’s a little distinct from behavior trees, but there has been a bunch of work in things like HTN (Hierarchical Task Network) planners and such in the narrative space: in particular Ian Horswill’s Step language can handle most things in the “tree-search with backtracking and unification” family. Max Kreminski’s page might also be interesting to you (maybe starting with the papers about StoryAssembler or Felt)?
3 Likes
Interesting stuff. Thanks for the pointers.
1 Like