Behaviour Trees with irregular updates

Question

I'm interested in behaviour trees that aren't iterated every game tick, but every so often. (Edit: the tree could specify how many frames within the main game loop to wait before running its tick function again).

Every theoretical implementation I have seen of behaviour trees talks of the tree search being carried out every game update - which seems necessary, because a leaf node (eg a behaviour, like 'return to base') needs to be constantly checked to see if is still running, failed or completed.

Can anyone suggest how I might start implementing a tree that isnt run every tick, or point me in the direction of good material specific to this case (I am struggling to find anything)?

My thoughts so far:

• action leaf nodes (when they start) must only push some kind of action object onto a list for an entity, rather than directly calling any code that makes the entity do something. The list of actions for the entity would be run every frame (update any that need to run, pop any that have completed from the list).
• the return state from a given action must be fed back into the tree, so that when we run the tree iteration again (and reach the same action leaf node - so the tree has so far determined that we ought to still be trying this action) - that the action has completed, or is still running etc.
• If my actual action code is running from an action list on an entity, then I possibly need to cancel previously running actions in the list - i am thinking that I can just delete the entire stack of queued up actions. I've seen the idea of ActionLists which block lower priority actions when a higher priority one is added, but this seems like very close logic to behaviour trees, and I dont want to be duplicating behaviour.

This leaves me with some questions

1) How would I feed the action return state back into the tree? Its obvious I need to store some information relating to 'currently executing actions' on the entity, and check that in the tree tick, but I can't imagine how.

2) Does having a seperate behaviour tree (for deciding behaviour) and action list (for carrying out actual queued up actions) sound like a reasonable approach?

3) Is the approach of updating a behaviour tree irregularly actually used by anyone? It seems like a nice idea for budgeting ai search time when you have a lot of ai entities to process.

(Edit) - I am also thinking about storing a single instance of a given behaviour tree in memory, and providing it by reference to any entity that uses it. So any information about what action was last selected for execution on an entity must be stored in a data context relative to the entity (which the tree can check). (I am probably answering my own questions as i go!)

I hope I have expressed my questions adequately! Thanks in advance for any help :)

Answer 1

Feed back the action return state

I'm not quite clear on what you mean here, but I see this as fairly simple. The action returns are going to come back at some point -- on some game loop tick, during the action execution phase. You can do these as either method returns, as gamestate changes, or as both (method returns from action methods writing into global state which is held for later examination). Then, the next time you run the tree tick / AI "thought" phase, you're going to examine those results, whether that's on the same game loop tick or a later tick. Do clarify if this is not what you mean.

Periodic AI updates

Absolutely. Periodic updates are by no means limited to behaviour tree AI. Periodic AI updates (which may be selective, based on what category of AI) are a standard approach to reducing AI processing costs over time. All you need is to implement some interface that cleanly encapsulates the concept of frequency of update per AI instance or category. I would suggest something like the strategy pattern, perhaps, called periodically. This would decouple the actual AI update logic from the idea of its being called. It's kind of like saying, "I don't know whether water or mud will come out when I turn that tap handle over there, but I know that it's a tap handle, and when I turn it, something will come out of the nozzle." Likewise, you don't know what a given AI will do, you only want to make sure it does its job. For this reason, the strategy pattern has a standard zero-args execute method which allows you to apply some action generically, without worrying about different function names or arguments. It's a "one size fits all" method call.

Actions vs. Behaviours

Your current thoughts on this are sound, particularly separating out the action list to maintain the necessary conceptual distinction.