0
\$\begingroup\$

Let's say I have a condition node which has to spend a lot of time calculating something to finally return a bool to the behavior tree.
But in the following action, we need this information again. I now have a few options:

  • I could just calculate the information again. That could unnecessarily take a lot of time and may result in redundant code.

  • I could save the information into some kind of state data dictionary but now the action depends on calling the condition first.

  • I could make it a single action that would just fail if the resulting calculation would end up being False. I would possibly end up with a bunch of very similar, very complex actions. Again possibly a lot of unnecessary redundancy.

How do I tackle something like that?
Is there a pattern that I could apply to the action/condition design (or whatever) or inside the behavior tree implementation that solves this?
Or am I using behavior trees wrong entirely?

\$\endgroup\$
2
\$\begingroup\$

Handling conditions

Let's say I have a condition node which has to spend a lot of time calculating something to finally return a bool to the behavior tree. But in the following action, we need this information again.

I worry about why you have to check the condition multiple times. Perhaps you could refactor your tree, so that you don't?

These are the options you have to apply conditions:

  1. That could either be accomplished by having multiple identical condition nodes, or by adding the conditions to the action. In the later, if the condition fails then the action fails. And you already know that's not what you want.

  2. You make a sequence, and inside the sequence you place a condition node (if conditions are decoration to action nodes in your implementation, you make a node with the condition but no action) if the condition fails, then the sequence fails, that prevents the other nodes in the sequence from running.

  3. You make condition node, and have the actions be children of the condition. If the condition is true, you expand the subtree.

Using the second and third way I mention, you can have actions that run if the condition is true and actions that run if the condition is false.


Avoiding redundant computation

Under the assumption that you can't create a behavior tree that avoid using the same condition in multiple places, there are still things you can do to avoid computing the result multiple times...


Reuse subtrees

it is a common practice to have a dictionary of subtrees, and have nodes call subtrees from the dictionary, this allows you to reuse subtrees (or it could be just single condition nodes) in various places of your tree.


Use Memoization

It is totally ok to use Memoization in your conditions. That is, you can let the condition store use an encapsulated backing storage※, if there is no value stored you compute the condition and store it, if there is a value stored... you check if it is valid※※ and decide if you use it or compute again.

※: If your conditions are lambda predicates, then you can just use a closure on some variable. No need for fancy data dictionary.

※※: you may also store the data needed to compute and compare it to check if it have changed. If the data is too complex you may use a version variable that you change every time the data needed changes... and then you can compare that. You may also use elapsed time as an heuristic to guess if it is worth to check or compute again.


Agent memory

Depending on your language/platform it may not be possible or it may not be convinient to encasulate the information used for memoization. There is no need to worry about that. It is valid to use an storage for information that the agent knows about. In fact, it is often needed to have some form of knowledge representation in your AI.

I wonder why people always go for the dictionary... perhaps it is the easier model to grasp. Yet, knowledge representation is a broad topic, and there are many datastructures that you can use for it.

In your behavior tree, the agent memory allows you to write more abstract actions, by having them pull informtion from it. With that said, using agent memory for flow control in your behavior tree makes it harder to maintain. It is coupling it to the knowledge representation, use sparsely.


Handling long computations

If you need to handle processes that will take a while to compute in your behavior tree, there two other tools you need to know:

  • Sending signals and waiting for signals.
  • Parallel nodes.

Sending and waiting signals are action nodes. They can be used to interface between the behavior trees of various agents, or in this case, you can use them to post requests and wait for results. That should be simple to implement.

Parallel nodes on the other hand can be tricky: you need nodes that will expand their children in parallel. To decide if the node succeeds, it will have parameters telling it that it succeeds if X amount of children succeed and that it fails if Y amount of children fail. Furthermore, the parallel node should abort pending children once it reaches success or failure. That implies race conditions and actions you can abort.

To see how they can be of value, I'll present a use case from a real game and how to solve it with behavior trees.

Real game use case

The game Prototype needs to handle pathfinding for a large number of units (every person in the city), but pathfinding is expensive, so they restrict the CPU time dedicated for pathfinding as not to hurt FPS. However, that means that the game will not get all the pathfinding done in time.

The developers used two pathfinding methods... the first one is quick and dirty: it only checks for the general direction to where the person has to go and avoids nearby obstacles. The second one if a full-blown pathfinding algorithm.

Now, you see, the idea is to have units use the quick and dirty method until the pathfinding algorithm have a response. Therefore, they queue pathfinding requests in a queue. The pathfinding subsystem will takes those requests one by one. Meanwhile the unit is running the quick and dirty method... but when the pathfinding subsystem responds the system aborts the quick and dirty method and follow the found path instead.

Implementing it with parallel nodes in a behavior tree

Use a parallel node that expects one child to succeed. As children have: 1) an action that queues the pathfinding request, wait for it and store it on the agent memory, then succeed (triggering the parallel node to abort the other action) – Aborting this action means to un-queue the request and no longer wait. 2) Another action node that uses the quick and dirty method until abortion or reaches the goal, where it succeeds.

After that parallel node is node, you know that either the unit reached destination or the path it has to follow is stored in memory. To use it, you could make a sequence with that parallel node I described before, followed by a condition that checks if the path is in memory, and have that condition expand into an action that follows the path and then remove it from memory.


Using that technique, you can handle long computations in your behavior tree. Of course, there are other uses of these tools. For example, you can see how you could have the behavior be interrupted by signals (instead of writing pooling behaviors).


Addendum: Will the agent know it?

For example, the AI agent has to handle a unit that will go to the other side of a Drawbridge. Perhaps the Drawbridge is currently up, meaning that the unit cannot go there. However, will the unit know?

If the Drawbridge is outside of view, it makes sense that the unit doesn't know if it is currently up, and so it makes sense to implement a behavior that don't check for it... instead walk up to it, and let it fail. The same goes for obstructions in the way that the AI agent cannot foresee.

On the other hand, if the AI agent should know because something else gave it that information. Then you need to model information given to the AI agent, the agent memory is the go to solution. In fact, if it is responsibility of another AI agent to tell, you can use an action to send the signal ("Drawbridge up" or "Drawbridge down") from one agent to the other that could be waiting for it.

For abstract, consider what would the AI actually know and how would know it.

\$\endgroup\$
  • \$\begingroup\$ wow, that's quiet the answer, i will need some time to read it all but I prematurely want to clarify something with a small example. Lets say the condition checks if a path to coordinates x is available. you can use it as bool condition but if you want to actually go there you will have to recalculate the path again because you dont have a way to store it without weird unintended stuff. \$\endgroup\$ – BluBb_mADe Feb 26 '17 at 5:06
  • \$\begingroup\$ A quick note about the language.I am currently using python to prototype individual modules for a project to tackle the hard problems first and if I can get it to work dirty I'm gonna decide on a language (probably c# or c++). That's the reason for my current tendency to dictionaries and I ment to say memoization but forgot the behavior-tree term. \$\endgroup\$ – BluBb_mADe Feb 26 '17 at 5:11
  • \$\begingroup\$ I've gone through it all now and in the end option two is the way to go. I also thought about doing a lazy evaluation like you recommended if the information isn't calculated yet but that would make the whole condition unnecessary in the first place and I end up with option 3. Does that sound reasonable? I guess I just kinda have to go with it and accept the imperfection of the solution. \$\endgroup\$ – BluBb_mADe Feb 26 '17 at 5:22
  • 1
    \$\begingroup\$ @BluBb_mADe memoization is not a behavior-tree term, it just means storing the result of functions to avoid computing them again. A common example is storing fibbonaci results, so you don't have to go over all the series again if you need more numbers (Edit: factorial works too, the linked wiki article shows factorial). These are tools combine them as need, AI is not a solved problem, you know? there is plenty of room to improve. Also, see addendum. You may not need a perfect AI if you don't have to implement an all knowng agent. \$\endgroup\$ – Theraot Feb 26 '17 at 5:28
  • \$\begingroup\$ Your logicin the addendum makes sense from the outsiders perspective but on the inside it only holds if you use something like LPA* or IDA* or D* or whatnot. I just hoped someone would've already found a trick for the missing "return values" in behavior trees or some kind of rule-of-thumb. I expected that many people already ran into this problem and worked out some kind of best practice. \$\endgroup\$ – BluBb_mADe Feb 26 '17 at 5:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.