2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Regarding checking vs not checking, you've slightly lost me, as I'm not clear on what you think I don't want to check (or where the idea of events has come into this). It's entirely possible I phrased my question inadequately. The imAs a behaviour tree \$\endgroup\$ – Robominister Nov 6 '13 at 13:51
  • \$\begingroup\$ "I'm interested in behaviour trees that aren't iterated every game tick (but on a set time out, eg every 100ms)." <-- at some level, this is using a loop function of its own. Languages like JS, Java, C# implement these kinds of timer as polling mechanisms (loops) under the hood. The problem is that these loops are discrete from your own game loop, so you will have synchronisation problems if you use them for anything other than rendering logic. When it comes to physics, AI, etc. all timing must be integrated with your own game loop. Let me know if this still isn't clear. \$\endgroup\$ – Engineer Nov 6 '13 at 13:55
  • \$\begingroup\$ If your gameloop is in fact running off one of those mechanisms, OTOH, you may be fine, but that may depends then very much on the order in which the event handlers are called by your 'setTimeOut' (or whatever the name may be). This is why Unity, for instance, has script execution ordering -- to ensure that the various elements of your game logic are running in the correct order, on every single game loop tick. \$\endgroup\$ – Engineer Nov 6 '13 at 13:58
  • \$\begingroup\$ Ah ok! Timeout was a very bad choice of words. No, this would be within the main game loop (a given tree could specify how many frames to wait before updating, eg every 10 frames for a complex tree). \$\endgroup\$ – Robominister Nov 6 '13 at 14:06
  • \$\begingroup\$ OK, so it will check every frame to see if it has zero frames remaining before it must act, then once it hits zero, it acts, and resets its wait counter? That would be the right approach, yes. \$\endgroup\$ – Engineer Nov 6 '13 at 14:08

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.