Finally Modularized My BT Library

TEV-w-INTLord

My behaviour tree library now exists as a git subtree in my game’s repo!

This means any updates I make to the library from other endeavors can easily be incorporated to this project. Likewise, any updates to the BT library from this game can be applied to the BT library’s own repo.

One such update is the Parallel Composite. I realize they’re really needed for real-time games, so I added them in. For example, when you need your A.I.’s moving, to act independently from shooting, allowing a run-and-gun behaviour (shooting while evading, shooting while charging in, etc.).

It’s not multi-threaded though (with this being in Unity), and I haven’t added completion policy or failure policy to it yet.

The way I made my Parallel, I think is different from the one explained in AIGameDev.com. It’s far more rudimentary since I’m still not finished with it.

  • The Parallel executes all its children once in sequence, but does no early-out aborts.
  • It waits for all of them to finish executing, then deliberate what its return value should be, based on the return value of its children.
  • Even if a child returns “Running” (a request to suspend tree traversal), we still wait for all children to complete.

There would be two types of deliberation policies:

  1. At least one failure from any child will make the parallel return failure. The parallel will return success only if all children returned success.
  2. At least one success from any child will make the parallel return success. The parallel will return failure only if all children returned failure.

Essentially, one is strict, and the other isn’t.

What if two children of a Parallel return “Running”? I haven’t taken this into account but I imagine it would be like this:

  1. Traversal should continue at the very first one that signaled “Running”.
  2. Even if one of them finished successfully, if the other one is still in “Running”, the whole tree should still return “Running”.
  3. This means the traversal should keep track of all “Running” actions.
  4. Essentially what we want to prevent here is resetting execution of a “Running” action, when what it should really do is attempt to continue where it left off instead.

Thankfully I already made code where the traversal stack is saved when we suspend traversal. However, the idea of keeping track of two or more “Running” actions complicate things. Could be I need to store more than one traversal stack.

Real parallel nodes I believe, will keep on running its children. If one child finishes too early while the others haven’t finished yet, it gets run again.

Since my BT library runs on Unity which is hampered by restrictions on multi-threading, I’d have to do some sort of job scheduling like operating systems do.

This was one thing I thought of before: an interleaved parallel.

  • This will disrupt the normal flow of traversal. The interleave will look at its first child, let it execute one of its children, then suspend that traversal. The interleave will then move on to its next child, also only allowing it to execute one of its children only. And so on.
  • It’s a constant cycle of suspension and continuation of the children’s own traversals.
  • When should the interleave stop? When all children have completed their traversal at least once (remember, they repeat traversal if possible). Then the return value of the interleave will be chosen from the deliberation policies mentioned earlier.

For my scenario though, I’ve yet to need this. My behaviour tree actions and conditions are very lightweight, in that they don’t actually do the actions themselves. They just send requests to the other sub-systems in the game to do the work for them. The behaviour tree only handles the deciding part, not the doing part. As such, traversal is relatively fast, that I (so far) don’t need a job scheduler for a parallel. I just traverse them linearly.

Assertion checks, on the other hand, makes sense to be checked only after resuming traversal of the whole tree (back from a “Running” state).

Why? Because most, if not all, actions always return a “Running” signal. As mentioned, actions only fire off requests to the other sub-systems in the game to do the actual work. Once that request has been sent, the tree has no choice but to wait for that to finish. For example, an attack action sends a request to play the attack animation (among other things). And only once the animation is finished do we resume traversal of the tree.

So I made a special composite just for that. It’ll automatically traverse its “assertion” child when the resuming of traversal continues from its “main” child. I called it Auditor.

The BT library by the way, is now tentatively named “INTLord”. I’m not sure if that should be INTLord, or INT Lord, or Int Lord.

Auditor Nodes

btxAuditor2

 

Here’s my answer for not having true concurrent/parallel nodes for my behaviour tree plugin for Unity: Auditor nodes.

Actually Alex Champandard already explained before, if for some reason you can’t implement true multi-threaded traversals you can fake it by using the same concept that operating systems do: job schedulers.

Which I still didn’t do. At least for now. Auditor nodes merely make sure their assertion branch gets evaluated when you resume from a previously suspended (a.k.a. “Running”) state of the tree traversal.

It didn’t justify peppering a subtree with back-and-forth checking of assert nodes and normal traversal (as how a job scheduler might do), because traversal is fast, or at least, meant to be fast.

Actions never process their behaviour immediately upon being traversed. They merely request other parts of the game code to initiate an activity for them (please start moving to this location, please attack this enemy, etc.) and such Actions that rely on something to finish first before sending Success or Fail would suspend the traversal (a.k.a. “Running” state). Which is why the Auditor’s asserts are checked only when resuming from a traversal suspend.

For cases where the Action/Condition is doing something computationally heavy, it should spread that computation over several frames (a bit like coroutines), hence another use of the “Running” state.

The only reason why I can’t make real multi-threaded traversals is because Unity doesn’t play well with multi-threading. For example, checking line-of-sight, as in raycasting, cannot be done in new threads, it has to be done in the main thread, even though raycasts are a very read-only affair.

Of the 100 nobles watching, 100 were impressed.

nonrecursive

Ah… Smell that? That is the smell of 0 unit tests failing on my non-recursive, brute-forced traversal of behaviour trees.

Thanks to Bjoern Knafla for the tutorials!

This is part of an effort to improve my behaviour tree plugin. Hopefully I can make a demo game out of it and sell it on the Unity Asset Store.

I lately haven’t been able to make any considerable progress with Tactics Ensemble as day job work is taking up a lot of my attention. I’m still working on it though.

W.U. 15: Another update on the Behaviour Tree Editor

This Behaviour Tree Editor is really taking up much of my time. Its the “Editor” part, to be more precise.

  1. Traversals can now be watched in the Editor. That is to say, the Traversals Display Window and the Editor now show the same thing.
  2. This also means proper editing of Behaviour Trees can now be done in-game.
  3. The Editor can now be used to add new nodes to the tree.

Roadmap:

  1. The rest of operations for nodes: deleting, duplicating.
  2. Tabbed interface: more than one behaviour tree open at a time.
  3. Make it work for the Player class in addition to the Unit class (for editing victory/defeat conditions)
  4. Minor enhancements: add feedback on where node gets placed when dragged.

W.U. 14: Behaviour Tree Editor Update

Sorry for the voice and volume, this was done in a hurry. I’m really busy.

Here I demonstrate how my Behaviour Tree Editor works so far.

If you don’t know what that is, basically, it’s what powers the A.I. system. Here I have a tool to make these A.I. systems and tweak them while playing the game.

I got some updates on it, and I may release it as open-source if anyone wants.

So far, the editor can now be used to edit the properties of actions and conditions (even while the game is running), drag nodes around, and load/save Behaviour Tree files. Files are saved in JSON format.

I was surprised and annoyed there was no ready made free code to draw a color picker dialog box in runtime for Unity, so I made one. But it was surprisingly easy, thanks to the HSBColor code in the Unity wiki site. I can also release it in open-source if anyone wants.

Also quite nice is the file dialog box code in ImprovedFileBrowser. If anyone is looking into making a runtime file dialog box, that’s a good place to start.

W.U. 12: Victory/Defeat Conditions

I was tackling on implementing the checking of victory/defeat conditions to check if the player won already or not, and I realized, “Why not use behaviour trees for this?” Is this really going to help, or is it a case of “when you have a shiny new hammer, everything looks like a nail”?

What I have are these so far:

Types of Victory Conditions:

  1. All enemies defeated
  2. Kill certain units
  3. Survive for N turns
  4. Default: Only player left who is not defeated

Types of Defeat Conditions:

  1. All my units defeated
  2. Certain units of mine are dead
  3. N number of turns passed
  4. A (non-ally) player is victorious

(There’s a lot of redundancy there, like “all enemies defeated” would also trigger “all my units defeated” for the opposing player, but for cases where there are more than two players, defeat of one player won’t automatically mean victory because there would be at least two players left.)

Usually there’d be a list of victory conditions and another list for defeat conditions, for each player.

The question is, does triggering at least only one condition in the list constitute an automatic victory (for that player), or do you need all conditions in the list to trigger true to mean victory? Basically, are the conditions in the list strung together in an AND operation or an OR operation?

And the answer is, it depends on each mission the designer creates. So why not allow the designer the flexibility to specify how he wants it? And with my goal of allowing mods, this does need to be flexible.

So I was thinking, why not structure it as a behaviour tree? One behaviour tree for checking victory, and another for checking defeat. And each player will have one of those pairs (there shouldn’t be only one meant for all players since the AI can have different victory conditions than the human player, for example).

So there it is. Right now it’s just a simple message saying “YOU WON” or “YOU LOST”.

W.U. 11: Behaviour Tree Traversal Display

Here’s a video where the A.I.’s behaviour tree traversal is inspected. I decided against watching a traversal as it happens because of performance reasons and instead, the game records traversals and you can watch them after they are recorded.

W.U. 10.1: Behaviour Tree Decorators

I’ve properly changed the HasSufficientStamina hack into decorators instead:

The “enough stamina to” decorator essentially turns the action it decorates into a condition, stifling it from actually doing the action and just querying the amount of stamina it costs to do. It then accumulates that stamina cost (among siblings in the sequence) in another variable and check if the unit has enough stamina to match the accumulated cost. If not, it returns failure.

I wanted the decorator shapes to look nice when stacked on top of each other, so this is how I designed them to look like:

Here, a bunch of (test dummy) decorators are in the Retreat sequence, and a few more are in the health check condition.