Game AI. Behavior Trees struggles

Question

I'm writing a bot for a MOBA game as final project. Game status is read directly from the screen (that's the requirement).

Now I have come to the AI part. On the first steps it started as some basic IFs, then I tried using a state machine, but there were too many jumps between states. Google lead me into Behavior Trees.

My current tree looks like this

It looks like it would work... And it does mostly... Except for the fleeing part. The fleeing part consists of setting a "safe point" as the current target for the navigator... But because of it being SUCCESSFUL (it has to flee), the selector does not traverse to the Navigation Behavior.

Solutions i'm thinking of

1. I could make it return FALSE when it's not successful, but then it would check the combat behavior even though it's already fleeing.
2. I could make a fleeing behavior. Really, that seems like the most logical thing, but it would be some redundant navigation code. I could extract the a branch from the Nav Behavior into a separate object. I'm not sure that's the right way though.

P.S. I'm using apocdev's Tree Sharp as the base for the tree. I don't think it really matters(it acts as it should), but just in case.

Answer 1

In my experience, navigation should not be handled explicitly in the behavior tree. BTs are great at stateless reactive behavior, while navigation is inherently stateful: you find your path, than you follow it, check whether you should replan... If you need to handle jumps, elevators etc. thnigs get crazy and are difficult to handle in a BT. In all games I worked on, navigation was written in native code.

I see two ways you may implement navigation outside your BTs:

1) Current navigation target and navigation state may be part of the character's "body". The BT has action node to set current navigation target (succeeds immediately) and possibly also senses to query the navigation state (DestinationReached, PathFindingFailed,...). After every update to the BT, the navigation is updated, possibly replanning path, if the target has changed.

Solution 1 allows you to react quickly to any change in the world state - your BT is constantly reevaluated and if you realize you want to advance instead of fleeing, the change happens immediately. This however leads to higher risk of oscillations and things like random navigation target selection need special care to not reset the navigation on every update.

2) You may have a navigate node that handles the navigation for you and contains all navigation-related state. In this case, the target location is a parameter of the node or is prepared by another node. To implement this, your BT needs to support nodes that not only "Fail" and "Succeed" but may also be "Running" and maintain a little state for you. Tree Sharp is unknown to me, so I do not know what is the BT variant you are dealing with and whether this is an option. The idea is that both composite nodes (Selectors and Sequences) return "Running" when any of the children return "Running". Decorators also remember which node was "Running" in the last update. Sequences resume their update with the running node on the next tick. Selectors on the other hand reevaluate their children from the left, but if different branch than what ran the last time should be updated, the branch running previously is notified with a "End" signal which lets them cleanup whatever is necessary -e.g. stop movement.

The latter solution is IMHO more versatile but more difficult to implement and with higher requirements on your BT implementation. However, keep in mind, that you might need longer running nodes anyway if you plan to do anything more complex in your BTs. If you do so, remember that your BT engine should enforce a Init - Work - End lifecycle on all your nodes or you will just go crazy debugging the mess.

If you have not yet seen AIGameDev.com coverage of BTs (this one has free access, and hopefully covers the topics I discussed here: http://aigamedev.com/insider/presentation/behavior-trees/) you should check it out.

Some ideas are also nicely put in answer by Byte56: Behavior Trees :: Actions That Take Longer Than One Tick

Answer 2

A solution could be dealing differently with the Navigator Behavior; if its only purpose is telling your bot where to go if its current status is "flee", then you could incorporate it in the Flee Behavior and remove the Navigator Sequence. Otherwise, if Navigator Behavior is used to achieve different results, you could incorporate its functions in the same Selector as Flee and Fight Behaviors.

In "Handling Complexity in the Halo 2 AI, GDC 2005" (link), Bungie shows how they dealt with multiple gameplay behaviors in the same sub-tree of Root. I am suggesting a similar solution, incorporating Navigation within the "what shall I do now?" part of behavior tree.