It's hard to ignore the potential of planning techniques for Game AI, and over the years they've drawn much attention from developers and researchers alike. In theory, planners could help build more intelligent non-player characters, and (indirectly) more believable and entertaining NPCs. Better still, planners as game directors or story generators could help craft unique experiences for each player.
In practice, planning technology has made notable inroads in the past 8-10 years since being introduced in the games industry. There are certainly a lot of open problems to solve and many more questions left to answer, but much has been achieved already...
In this article and its accompanying video, I'll dig into the history of planning in games, look at games that use planning as well as related techniques that have had an impact, and present the biggest lessons we've learned as a result of all this.
Video Presentation (26m)
STRIPS is a planning algorithm that searches through possible situations (or world states) by applying operators (or actions). Typically with STRIPS, this search is done backward from the goal state rather than forward from the current world state; the first is faster, but the second is more flexible when you have complex goals. Using A* to drive the search with simple heuristics can help make the planning process relatively efficient. (This is only a short overview, but obviously it's a topic that has been studied for decades over hundreds of white papers.)
F.E.A.R. is the first game known to use planning techniques, based on the work of Jeff Orkin. The enemy AI relies on a STRIPS-style planner to search through possible actions to find a world state that matches with the goal criteria. Monolith's title went on to spawn a franchise of sequels and expansions, and inspired many other games to use STRIPS-style planning too — in particular the S.T.A.L.K.E.R. series, CONDEMNED, and JUST CAUSE 2.
There aren't very many games that use such planners in comparison to other techniques, but the AI in those games has been well received by players and reviewers. The most successful games to use planning have featured more open worlds and emergent gameplay, whereas more heavily scripted or linear story-driven characters have conversely received poor reviews when implemented with STRIPS-style planners. In the past few years, we've seen an incremental shift away from STRIPS-style implementations towards more hierarchical approaches, either HTN planners or their reactive cousins behavior trees.
HTN planners are based on hierarchies of tasks that can be broken down recursively, like a plan that starts with the big picture and gets refined into actionable steps. Different HTN algorithms take different approaches to expanding the plan, for example starting from the current point in time and progressing one step at a time (a.k.a. ordered HTN). The ordered approach is more efficient though less flexible; partial order approaches are proven capable of emulating STRIPS for example.
HTN-based planners inspired by SHOP (an ordered planner) are becoming increasingly popular over the STRIPS-based ones. Guerrilla Games implemented a planner inspired by SHOP into KILLZONE 2, and continues to use the technology in sequels including KILLZONE 3 and presumably 4. The bots in the series have continuously received praise from players and reviewers alike, thanks in part to the planning technology but also the richness of the domain. Recently, in TRANSFORMERS: WAR FOR CYBERTRON, High Moon also switched from using a STRIPS-based planner to a hierarchical approach also inspired by Guerrilla's work and SHOP.
It's often difficult to draw the line between hierarchical planners and behavior trees, since SHOP-inspired planners often include implementation tricks or design patterns to make them more reactive for the sake of performance. In practice, this makes them very similar to the industry-standard behavior trees, which have been in heavy use since ~2004 (with ideas inspired from robotics and virtual agents from decades before).
In practice, the AI in games like TOTAL WAR (e.g. EMPIRE or NAPOLEON) has been dubbed a planner but follows implementations traits of "reactive planners" and "belief-desire intention" architectures (both are misleading terms, despite having been used often in academic research). Similarly, games like METRO 2033 switched from STRIPS-style planners, and Avalanche studios is also currently favoring its behavior tree implementation despite having a production-quality STRIPS planner available.
A utility system is the term used to describe a voting/scoring system, and they are often applied to sub-systems of games like selecting objects/positions based on the results of a spread-sheet like calculation. It's interesting to establish parallels between STRIPS-based planners and utility-based systems, since both have a strong emphasis on emergent behavior that's not intended to be controlled top-down by designers.
DEMIGOD in particular uses a form of action search that's not a planner in the traditional sense, trying to satisfy clear dependencies and meet Boolean conditions in the goal state, but instead trying to evaluate the benefit of short sequences of actions and pick the best one. This approach bridges the gap between utility systems and non-hierarchical planner, making utility systems more deliberate in the process.
Another notable implementation is the one in the SIMS 3. The SIMS franchise is famous for its use of utility systems, but in the 3rd major iteration, the game puts more focus on a top-level hierarchy and keeps the utility-based decisions more isolated. This was necessary for performance reasons, but also makes the characters more purposeful.
Based on the applications in all these games, we've developed a much better understanding of planning in games:
- Technology has not been much of a problem. Applying STRIPS into a game in real-time certainly required many engineering and optimizations tricks, likewise speeding up HTN implementations. However, with additional processing power available and with much better knowledge of the problem since then, planning performance hasn't been as big of an issue as you'd expect it to be...
- The biggest open questions are about design. The most significant problems to solve have been finding ways to tweak and tune the behaviors resulting from planners, optionally integrating them with level scripts, and teaching designers to think more systematically and work with emergent AIs. This has required significantly more effort than the pure algorithmic aspects of planning, and is responsible for the incremental transition towards hierarchical approaches.
- In well understood domains, other techniques work best. In the cases of action/combat games, we can easily build robust AI that looks deliberate using simple reactive techniques like behavior trees. In fact, it's difficult to tell the difference for such applications between the behavior generated by a planner compared to more reactive approaches, yet the planning process will be noticeably slower at runtime and require more development time.
- Planning has most benefits in unknown domains. Jeff Orkin mentioned in his publications that one of the benefits of planning was in prototyping, creating new behaviors quickly by letting the planner generate behavior given new actions or goals to work with. Planners also have shown to be more beneficial in open worlds, where the sandbox simulation has significantly more complexity.
- Goal-based architectures are great! Regardless of whether developers use planning techniques or not, an architecture that separates the AI's goals (or WHAT to do) and the AI's decision making (or HOW to do it), has proven to be very effective. Planning research has helped crystallize this insight, and even when using reactive techniques this is arguably a best practice for AI architecture in games today.
We've barely scratched the surface of what planners have to offer for game development. We've certainly learned a lot, but at the same time there's such a small amount of research on topics that are problematic in games (e.g. design and workflow questions) that progress is slower than you'd expect for such a mature field as automated planning.
Perhaps the most exciting prospect of planners, however, is their application to create new types of gameplay that would otherwise not be possible using any other approach. This part has proven to be more of a challenge, as few designers have the background in systems thinking that's required to come up with such ambitious and innovative designs.
What interests you about planning in games? What lesson do you take out of our last 8-10 years of applying planning to the game development process? Post a comment below or in the forums.