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:
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.
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.
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...
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.
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.
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.