Open Review
PIG_JustCause2

Planning in Games: An Overview and Lessons Learned

Alex J. Champandard on March 8, 2013

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-based Planners

PIG_ActionPlanners

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-based Planners

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.

Behavior Trees

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.

Utility Systems

PIG_UtilityGames

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.

Lessons Learned

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.

Final Words

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.

Discussion 12 Comments

urosidoki on March 8th, 2013

It was really interesting. I am still trying to figuring out how do you assign the cost for every action on the STRIPS. If A* uses floats for that I dont know which criteria would take you to decide what is the best cost for every action. Will you tell me if you know anything about that? I have seen the FEAR sdk and the code is using A* as you said but all of those "cost" per actionNode are not visible. Any idea?

bram on March 9th, 2013

Thanks for sharing, it's a great topic. "Planning doesn't make or break a game." Yeah, I would guess you are right, but it sounds like a challenge! I wonder if AI-Planning could somehow be made central in the core-gameplay. What if you let the player control a planner, e.g. by selecting/buying action sets to solve problems? SoldierA can do actions X,Y,Z and MarineB can do actions U,V,W. Player assembles a squad to tackle GOAL G? @urosidoki If you want to see how action-cost is used in a planner: I open sourced a G.O.A.P. which is very concise and easy to read. [url]https://github.com/stolk/GPGOAP[/url]

urosidoki on March 9th, 2013

Thanks bram, I will take a look today :D

fzambetta on March 9th, 2013

Excellent post Alex! :) One thing I'd like to point out though is that there is a huge amount of academic research that is very related to utility systems and that also often uses (factored) state-based representations. One only needs to consider the plethora of work on Markov Decision Processes (MDP) and Reinforcement Learning (RL). In RL in particular, we have several approaches to solving probabilistic planning problems as well as hybrid architectures that allow planning, acting and learning (e.g., Sutton's Dyna see http://webdocs.cs.ualberta.ca/~sutton/book/ebook/node96.html). Essentially an RL problem revolves around finding a policy (a sequence of actions) to maximise some form of utility (very often a so called "discounted return"). Besides, some work has been devoted to having STRIPS-based representations inform an RL method http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=4670492&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F4662488%2F4670488%2F04670492.pdf%3Farnumber%3D4670492 ). Finally, scalability issues in MDPs have been proposed to be solved via hybridisation with BDI architectures (http://dl.acm.org/citation.cfm?id=1160818&dl=ACM&coll=DL&CFID=188589557&CFTOKEN=84964637).

shafranov on March 10th, 2013

@urosidoki: Action cost is a value >= 1 (chosen with a balck magic ;) Heuristic is a current number of unsatisfied goal state properties (i.e. an upper bound on the number of actions still needed to satisfy a goal state) I believe that's what they did in Fear.

theqweaker on March 13th, 2013

Here are the action costs in F.E.A.R., as you can find them in the game data base, which you get with the SDK (sorted in increasing cost); as you can see, the first action cost is 0.5 (strictly less than 1): EscapeDanger-0.5, UseSmartObjectNodeMounted-1, TraverseLinkUncloaked-1, TraverseBlockedDoor-1, SurveyArea-1, SuppressionFireFromCover-1, ReloadCovered-1, ReactToDanger-1, MountVehicle-1, MountNodeUncloaked-1, IdleOnVehicle-1, GotoValidPosition-1, GotoNodeOfType-1, GotoNode-1, FaceNode-1, DodgeCovered-1, DismountVehicle-1, DismountNodeUncloaked-1, Charge-1, AttackLungeUncloaked-1, Animate-1, LookAtDisturbance-1.5, TraverseLink-2, SuppressionFire-2, KnockDownExplosive-2, KnockDownBullet-2, InspectDisturbance-2, IdleTurret-2, Idle-2, FollowPlayer-2, DodgeRollParanoid-2, BlindFireFromCover-2, AttackGrenadeFromCover-2, UseSmartObjectNode-3, LookAtDisturbanceFromView-3, LongRecoilHelmetPiercing-3, LongRecoilExplosive-3, LongRecoilBullet-3, Follow-3, FlushOutWithGrenade-3, DodgeShuffle-3, AttackMeleeUncloaked-3, AttackMelee-3, GotoTarget-4, AttackFromCover-4, AttackFromArmoredBounded-4, AttackFromArmored-4, AttackFromAmbush-4, AttackFromView-4.5, ReloadCrouch-5, AttackCrouch-5, AttackTurretCeiling-6, Attack-6, AttackReady-7, GotoTargetLost-8 -- TheQweaker.

andreatux on March 23rd, 2013

I'm attending "Planning in Artificial Intelligence" at TU wien and I'm going to do a seminar in ai focused on Hierarchical Planning (HTN). Very Veeeery interesting topic!

andreatux on March 23rd, 2013

Oh and another thing, I'm basing the seminar presentation also on a paper called : Hierarchical Plan Representations for Encoding Strategic Game AI (2005 - Hai Hoang, Stephen L. Urban, Hector M. Avila). Can anyone suggest me a more recent white paper (if exists) on Hierarchical Planning applied to videogames? Thanks :)

theqweaker on March 25th, 2013

I don't know about a white paper about HTN in games. There are other papers, however ; google them with "HTN planning video-games" or something like it. But instead I suggest you watch AIGameDev.com's broadcasts, for instance: Planning for the FALL OF CYBERTRON: AI in TRANSFORMERS or Inside Hierarchical Task Network Planners. Enjoy! -- TheQweaker.

andreatux on March 25th, 2013

I need a white paper because it is required by University! But many thanks for your advices :)

urosidoki on March 28th, 2013

Ey guys, thanks for the info! :)

tombatsford on April 25th, 2013

Hey, I really enjoyed this article, it has helped me out while writing my final year dissertation. However, I think you got Fall of and War for Cybertron mixed up. Fall of Cybertron (2012) was the sequal, and the game that used HTN planning, where as the original War of Cybertron (2010) used STRIPS planning.

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!