The Challenge for Planning Techniques: Responsive Behaviors in Dynamic Worlds

Alex J. Champandard on February 15, 2008

Planners are certainly getting more popular in game studios these days, but there’s still a very long way to go before developers reach the same level of understanding as for traditional scripted systems. One area in particular that causes problems is dealing with dynamic situations.

Tobe Mayr, a former colleague and designer at Rockstar, wrote a very interesting comment [1] about the use of planners yesterday on the post about SHOP:

“This approach seems very useful in a deterministic or stable environment, say, a slow-evolving strategy game. How about games that feature radical changes in short time spans? E.g. shooters with multiple objectives that need to be re-evaluated whenever conditions change dramatically?”

Since that last article was rather academic, it’s a good opportunity to balance it out with something more practical…

Dynamic Worlds GTA 4

Screenshot 1: Highly dynamic situations in Grand Theft Auto 4.

Sometimes It’s Black and White

Anyway, Tobe is absolutely right on two counts in his comments about hierarchical task network (HTN) planners:

  • Hierarchical planners are perfectly suited to static worlds where the AI has long term goals. However, those types of problems are very rare in games; the player interaction makes everything dynamic!

  • On the other hand, such planners are not necessary for problems where you want the AI actors to behave in a purely reactive fashion. You might as well be using a state machine.

That covers the black and white cases… but in practice, most often you’ll end up somewhere in the middle.

What About the Other Cases?

Assuming you want your AI to solve context-sensitive problems in a purposeful way, then I’m going to make the argument that both hierarchies and planners can still be very useful to build reactive AI.

A hierarchy helps design responsive AI because they’re a simple yet powerful way to express behaviors. You can break down the top level combat behaviors into sub-behaviors for attacking, and easily specify when each of them should be interrupted. This is why HFSM work so well. These same ideas make hierarchical planners equally useful for complex dynamic problems too.
Planners help because they allow you to reduce the amount of work necessary to connect states. Instead of building a large spaghetti state machine, you build modular parts and let an automated algorithm plug together the blocks to solve problems dynamically.
As a matter of fact, Jeff Orkin who created the planner for F.E.A.R. mentioned in his GDC talk that his use of the planner mainly helped generate reactive behaviors in a much simpler way. The soldier behaviors were a little more complex than games before, but they were primarily much easier to edit and build up modularly.

Grand Theft Auto 4 Rockstar

Screenshot 2: Worlds in GTA 4 require adaptive behaviors from player and AI.

Planners In Practice

Effectively, a hierarchical planner can be applied to situations in games where responsive behaviors are required, and it’ll generally help maintain the codebase and keep things simple.

However, there are a few things to watch out for compared to building a normal state machine: You’ll need to:

  1. Keep running your planner very regular basis (multiple times per second, e.g. 5 Hz) to compute new plans.

  2. Use logic to prevent unnecessary work by trying to detecting relevant changes, and using level of detail for different characters.

  3. Detect redundant plans (or duplicates) and don’t execute them from scratch every time.

  4. Add simple logic to prevent oscillations in the behaviors and commit to a particular course of action when appropriate.

This part of applying planners is harder than the actual theory itself. Start simple, then as you need more logic to manage the planner, start building simple state machines to deal with changes in the world and feed the data to the planner appropriately. Also be sure to see how the code in the F.E.A.R. SDK handles these problems.

Do you think planners can and should be applied to problems where responsive behaviors are required? If not, why not?

Discussion 4 Comments

Ian Morrison on February 16th, 2008

It seems to me that you might be able to get some more reactive behaviours at less cost by limiting how far ahead you search. My current project uses a smart object approach, but the way I've implemented it has it act almost like a planner that only considers one move ahead (the weightings on the smart objects are educated guesses as to how the action will achieve the AI's goals). Perhaps you could use an A* planner that progressively looks further and further ahead into the search, and simply chooses the most likely path from each iteration, as opposed to a hierarchal one that designs the big picture and then fills out the details as it goes (though either could work quite handily).

3emeType on February 18th, 2008

A planner requires to describe the effects of actions on variables. What if these effects are not deterministic ?

3emeType on February 18th, 2008

Ok, a planner could "search a fuzzy state machine (or similar) and still determine the best course of action", but at what cost ? Is it applicable to game AI ? Edit : This is a reply to the message of "The Recursion King" which appear at the end of the discussion (bug ?).

alexjc on February 18th, 2008

[B]3emeType, [/B]Doing full blown probabilistic search of all possible options is much more expensive for sure, and probably not feasible for games yet. What's interesting is that normal hierarchical planners can do very well by only taking into account the most likely outcome (as specified by the designer). The only catch is that you have to replan often, but if you have a dynamic world you'd need to do that anyway. I'll schedule a future post on the blog about this subject. Alex

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!