Open Coverage
Arma2_BattleFires.large

Hierarchical Task Networks for Mission Generation and Real-time Behavior

Alex J. Champandard on April 20, 2010

Certainly one of my biggest take aways from the Paris Game AI Conference 2009 was the rise of hierarchical task network (HTN) planning techniques for games. The potential is huge, from helping reduce behavior modelling overheads when creating purposeful behaviors and automatically generating large missions for the player to take part in, both these domains can benefit from HTN planners.

During a panel discussion on the subject, when I asked Remco Straatman (Lead AI Programmer at Guerrilla Games) and William van der Sterren (Consultant at CGF-AI) whether the technique had broken in to industry, here's the reply I got:

“If Remco and the KILLZONE 2 team can do 500 plans per second, then it's definitely ready for the industry. Some of the industry is simply not ready for HTN.” — William van der Sterren

This statement was followed by laughter from the audience, but the point is certainly worth considering — and now's your chance to listen in to the discussion and ponder the situation. In this article you'll find the full video recording of this session from Paris, as well as some background on the use of hierarchical task network planners in games, and finally references on the subject.

Background

There were two projects presented in Paris last year that used HTN Planners intensively, in particular:

  • Remco Straatman talked about the work of the Guerrilla Games team on applying an ordered HTN planner into KILLZONE 2. The game uses planning for both individuals and the squads, and manages to do so at interactive rates.

  • William van der Sterren presented his work called “Planned Assault” which is a mission generator for ARMED ASSAULT (ArmA 1). He uses a full HTN plan representation combined with an A* heuristic search to find plans that make sense from a military perspective.

For reference, the panel discussion in the video recording below took place immediately after William's presentation.

Audio/Video Recording

The following video is being released for the first time here. There were minor technical issues with the recording towards the end, but the content of the panel forced us to publish it despite it being not up to the usual AiGameDev.com standards! All the other high-quality videos from the Paris Game AI Conference 2009 are of course available in our Premium area.


This full audio / video session recording from the Paris Game AI Conference 2009 was brought to you thanks to the sponsorship of Spir.Ops, a game AI middleware company based in Paris.

Notes & Highlights

Notes (and spoilers) from the video:

  1. While planning, most of the time is actually spent pathfinding! So it's the same performance bottlenecks you find in traditional and more reactive game AI.

  2. You can easily reduce branching in the planner by relying on external routines, for example for picking positions or planning tactical paths.

  3. Ordered planner was a requirement for runtime performance, so expanding the actions one by one from the start.

  4. It's important (but challenging) to explain why plans fail, so having a tool or debug view to list reasons for failure is very useful.

  5. Using HTN, handling "impossible" plans is done as easily as adding a fallback branch into a behavior tree.

References

Relating to planning in general, be sure to check out the following sources or articles:

The slides from the Paris presentation are also available here:

Multi-Unit Planning with HTN and A*
William van der Sterren
Download PDF
Killzone 2 Multiplayer Bots
Remco Straatman, Tim Verweij, Alex Champandard
Download PPT or PDF

If you have a Premium account, you can of course see the recording of the following presentations:

If you have any questions or comments on the topic of hierarchical task networks, or planners in general for games, don't hesitate to post them below!

IMPORTANT: If you'd like to join us in Paris for the Game AI Conference 2010 and hear about the artificial intelligence in BATTLEFIELD: BAD COMPANY 2, you need to move very quickly and secure your seats. There are less than a dozen tickets left for the event!

Discussion 0 Comments

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!