Article
i/2007/07/allocator

Using Resource Allocators to Synchronize Behaviors

Alex J. Champandard on July 11, 2007

If your low-level behaviors are designed to run concurrently, and you’re using parallels to fork control inside hierarchies, whole subtrees of behaviors can run at the same time. Now you can generate many interesting concurrent behaviors, but the problem is that most of them are just not realistic. For example, it’s probably possible (thanks to your audio engine) for your actor to say two things at the same time — but it’s not ideal!

Resource Allocation

A resource allocator managing access for two parallel trees.

So you need a way to synchronize trees, in order to prevent these unrealistic behaviors from occurring. To do this, you can use a resource allocation strategy, which is just another node in the tree. Put one of these allocators around each resource that needs special treatment to handle concurrent behaviors, like the voice of your actors.

Types of Allocators

The most simple strategy for resource allocation is a first-come-first-served system. There’s a queue which stores the behaviors as they request the resource. Only the first is allowed to access the resource, and all others are paused until it’s their turn.

This simple strategy resolves most synchronization problems, but often you’ll need more control over the scheduling of the behaviors that need to access the resource. The next step is to use priorities for each behavior, and order the queue using their priority level. So the most important behaviors would get access to the resource first.

Finally, your allocators could be much more complex, and attempt to arbitrate between the different behaviors in the queue. This is possible, for example, if you have a path-planner than supports multiple goals. The “destination” resource would be chosen by the arbitrator as a compromise between the requests of the individual behaviors. (This approach is rarely currently in games.)

Common Configuration Options

The main decision you face when creating resource allocators is to decide the scope. Which behaviors in the whole game share that allocator? It could be on a per-actor basis (like the voice), a per-group basis (the right to fire at the player), or even a global basis.

Also, you may decide how many behaviors are allowed to access the resource at the same time. For things like limb animation, it’s wise to limit the number to one in most cases. But other cases it may be a higher limit, for example the total number of actors speaking at the same time may be set to two or three in a large crowd.

When using priorities, it may also be necessary to add an option whether the resource should support interrupts or not. So a low priority behavior using animation would be kicked out by a high-priority reaction. Then, you also have extra options whether to allow certain behaviors to queue-up or not…

Words of Advice

As you can tell, resource allocation strategies can get pretty complex. The best advice is to start simple! Once you’ve identified which additional features you need, separate them into options for the resource itself (like scope) and options for the behaviors using it (like priorities).

As you add features, make sure you unit test everything as it could backfire otherwise. Priorities and interruptions are pretty tricky to implement, so avoid them if the design permits you to do so.

Generally, try to keep the behaviors very short so there’s not much need for interruptions. You can do this by making behaviors that change the state of the resource and then terminate; for example, a behavior for SitDown rather than StaySitting which would lock up the whole body resource for much longer.

Discussion 6 Comments

gware on July 12th, 2007

Is the parallel between this ressource allocator scheme and critical sections correct? If it is, I think we can get a lot of information about the scalability of this solution. Although it IS good to have such a mechanism, it is also good practice to try to avoid using it too much otherwise you'll find yourself waiting for data. IMO, most of the time, behaviors that are modifying the same data / context should not be run in parallel. To reuse the example at the begining of the post : "it’s probably possible (thanks to your audio engine) for your actor to say two things at the same time — but it’s not ideal" I do not think that behaviors acting both on the same character and it's voice actions should be run in parallel. Predicates should be used to filter this behavior tree. I understand that it is a very simple example, and you may end up in some case where you just need to use critical sections. As you say : "Priorities and interruptions are pretty tricky to implement, so avoid them if the design permits you to do so." Not only tricky to implement, they can be deathtrap if not designed very carefully. A good test to run, is to create few behavior trees and search for possible ressource collision. As you said a very good pratice is to use atomic behaviors in order to avoid locking data for too long. Also it may help you detect what behaviors are mutualy exclusive. Is it a good design to ask your scheduler to prevent to run behaviors that affects the same ressource ? (Or should it be done when designing each behavior trees ?)

alexjc on July 12th, 2007

Hi Gabriel, Wow, very insightful comments! And you're absolutely right about the analogy to [B]critical sections[/B]. You really get my creative juices flowing; there's so much to explain, as I approach the problem from a different angle :-) A few comments to get started: [LIST] [*]In game AI, it's not about optimal usage of resources; it's about realism. In fact, using the resources optimally may be unrealistic. [*]For most behaviors, if you design the trees well with many fallbacks, they will never block unless you want them to (set an option). So the system is always "scalable" in that sense; it doesn't fail like linear computations. [/LIST] From my perspective, most behaviors trees should be task oriented, designed separately and run concurrently. The reason for this is that the alternative is not modular enough to scale. Here are the two options: [LIST] [*]You can either design one control system per resource (head, voice) and everytime you want to add a goal-oriented behavior you have to extend all the control systems — which potentially touches all the other behaviors. [*]Alternatively, you can have one control system per behavior, and just have allocators for each resource. Adding new behaviors is trivial since you don't touch any other behaviors; you only rely on the resource itself. [/LIST] The only down side is that implementing priorities, interruptions and quality of service for behaviors is hard... (I've planned [TT]Game:AI++[/TT] to handle this better than my previous systems.) But even without those, and without a queue you can get awesome behaviors. An example: your enemy guard is patrolling using the main [TT]BEHAVE[/TT] tree. He can look around, sigh, mumble using his voice, head, and torso resources. Then an event happens and you want him to react. This is a separate [TT]REACT[/TT] tree which tries to turn towards the explosion with the torso, look at it with the head, and shout in surprise. Even if only one of those resources is available, it's perfectly fine to just fallback to do the others and wait in the queue for a few seconds. With a monolithic control system, you'd have to build your main behaviors together with all the possible reactions... Does that make sense?

gware on July 12th, 2007

I totally agree with your two comments. The way it differs from cirtical section comes from the way you will handle fallbacks from your behaviors. I'm not sure about what you meant by "behaviors trees should be task oriented". Does it mean that tasks are atomic, and behavior trees are composed (only?) by tasks (and other behaviors) ? About the two possibilities you are talking about : I don't think designing a control system per ressource is a good way to go. In fact I believe it's not possible if you have a lot ressource (which you will have). By doing this, you will quickly fall in the infinite state machine trap :) Designer will end up doing trees for each ressource and this will grow out of hand. Designing a control system per behavior with locking just seems to be fine. Again, I totally agree with your points. But, I think a good thing should be to avoid locking. You could do this by using preconditions excluding two control system to be run in parallel. using your example, i'd say that BEHAVIOR_NORMAL and BEHAVIOR_ALERT are exclusive, they will lock for (nearly) each ressource. IMO, you will first end BEHAVIOR_NORMAL then go to a BEHAVIOR_ALERT. This, because you probably don't want your character turning his torso toward the explosion while mumbling ('til the ressource end ... which can be long depending on your assets). By ending a control system you may feel that your engine is too responsive (another option would be to wait for its "normal" ending). Adding postconditions can also help you defining smoother transitions (let's say "normal" to "astonished" to "alert"). (but you may end up having too much preconditions, and a very complicated graph if you have a lot of control systems, it may be something to work on:). To summarize my thoughts: Do not have a control system per ressource. Have something to control the transitions between control systems checking : - valid transitions between behaviors - not to run mutually exclusive tasks in parallel (and thus mutually exclusive behaviors). (so that youe character won't start to freak out while whistling ;)) This way you do not have scripted behavior sequencement (you will end with one if your post conditions are too strict), but still you won't have exclusive behaviors running in parallel and waiting for each others. Anyway, I'm not sure if this is a good way to design a behavior system but I hope it makes some sense. (Also I hope I did not go off topic :P )

alexjc on July 12th, 2007

Ok, I see your points. My personal opinion on the subject is two fold: [LIST] [*]Locking or clashing on resources can be avoided by falling back, and even queuing for a resource is still very realistic. [*]Designing behaviors specifically to run with other behaviors is an [TT]N^2[/TT] problem, so there's lots of work — like with FSM. [/LIST] That's why I love resource allocators. It's worth spending a constant amount of time getting them right, so you can then scale linearly with the behaviors and not worry about anything else. You do have to think about two things though: [LIST] [*]Think wisely about how resources handle behaviors, all the options discussed above. [*]Think wisely about how each behavior interacts with the resources, depending on its role. [/LIST] Then just let it happen! For me, an ecology of multitudes of behaviors is always better than a few that are micro-managed... Alex PS: By "task-oriented" I mean a behavior than does NOT manage stuff (like a resource control system), but actually achieves a goal in the world then terminates.

Sergio on July 15th, 2007

The problem I see with resource management is that you can't assume that resources are truly independent. Realistic behavior is built upon subtle dependencies, and we fully use our whole body when expressing ourselves. If a behavior tries to use the 'voice' resource to shout in surprise, but a previous behavior has a lock on the 'facial animation' to show the character is bored, it's not going to work. If the character turns his face to look at an explosion, but his torso and legs are still facing his patrol route, the player won't be able to understand what's happening (people can't turn their heads that much). I guess that's why people tend to end up with monolithic behaviors that manage all resources. The problem with solving dependencies between behaviors being O(n^2) can be alleviated if we approach the transition from one behavior to the next as a problem this new behavior has to solve. Basically, we don't provide any guarantees as for the state of the resources when the new behavior starts, and it's responsible to make sense of all that and provide believable results. If the behavior REACT realizes that the character has a sore throat and can't use his voice, it will adjust appropriately to handle the situation. If the character is lying on the ground, the behavior will do something different than if the character is looking straight at the source of the reaction. Also, a system this emergent will never provide the same degree of control that designers and animators have come to expect, to create an experience that closely resembles that of movies (which, of course, are not interactive). As anecdotal evidence, at work we were looking at some animations created using Natural Motion's Endorphin. While they looked okay, and they were fully procedural, they weren't "the same" as what a skilled animator may have created manually. So sadly, eventually they will look worse to the player. The only way to get the maximum quality for your game is then through full control like in current (gasp) FSMs. Many people are going to have a lot of resistance accepting a solution technologically superior, but that yields inferior results even though it's at a substantially lower cost.

alexjc on July 16th, 2007

Great points Sergio. It's certainly the case that both creating modular emergent behaviors, and monolithic control systems have problems. But ultimately, there's no way designers are/will be able to create large quantities of data for one big state machine or behavior tree. I agree, designers have come to expect a level of control, but they're also rather bored with "baby-sitting" these monolithic systems. When I was at Rockstar, it was amazing to see my designer colleagues creating modular behaviors and plug them together. As long as you have good tools, and a highly interactive pipeline that can reload changes dynamically, the designers can really use their creativity. Also, with regards to resources, it's true they are not entirely independent. Most often they are modeled hierarchically (in a non-strict way), which is good enough. But even if you don't think in terms of resources, they are still there! Ignore them at your own peril...

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!