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.
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.
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.
Notes & Highlights
Notes (and spoilers) from the video:
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.
You can easily reduce branching in the planner by relying on external routines, for example for picking positions or planning tactical paths.
Ordered planner was a requirement for runtime performance, so expanding the actions one by one from the start.
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.
Using HTN, handling "impossible" plans is done as easily as adding a fallback branch into a behavior tree.
Relating to planning in general, be sure to check out the following sources or articles:
- SHOP: Simple Hierarchical Ordered Planner (Blog)
- Assaulting F.E.A.R.'s AI: 29 Tricks to Arm Your Game (Blog)
- An Overview of the AI Architecture Inside the F.E.A.R. SDK (Blog)
- 1,700 AI Units in ArmA 2 (Video)
The slides from the Paris presentation are also available here:
Multi-Unit Planning with HTN and A* William van der Sterren Download PDF
If you have a Premium account, you can of course see the recording of the following presentations:
Planning Multi-Unit Maneuvers Using HTN and A* by William van der Sterren (Premium)
The AI in Killzone 2's Bots: Architecture and HTN Planning by Remco Straatman (Premium)
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!