(This is a slightly edited copy of the feature article I wrote for Game Developer Magazine that appeared in their August, 2012 issue.)
A question that seems to come up regularly from students, designers, and even from veteran programmers is âwhat AI architecture should I use?â Itâs a query that is sprinkled across internet message boards, comes up at GDC dinners, and Iâm sure is a frequent topic in pre-production meetings at game studios â indie and AAA alike. As a game AI consultant, I certainly field it from my clients on a regular basis. More often than not, the less-than-satisfying answer to this question is a resounding, âIt depends.â What follows resembles something more along the lines of an interrogation than an answer.
It puts me in mind of the days long ago when I was a waiter. (I suppose they call them âserversâ now.) People would often ask me, âwhat do you recommend?â or the even vaguer, âwhatâs good here?â For those that havenât had the opportunity to work in the restaurant business, you may not realize that this can be a horribly uncomfortable question to be presented with. After all, most people are well aware that tastes differâŚ so why would a waiter server be able to ascertain what it is you have a proverbial hankerinâ for? The way out of this situation would be to ask return questions. âWell, how hungry are you? Are you in a hurry? What are you in the mood for? Steak? Chicken? Allergic to peanuts? Oh… youâre vegan? And you need gluten-free, eh? Well that certainly redirects things.â The result of this Q&A is not that I tell them what they want, but rather I help them discover for themselves what it is they really want.
Much the same falls out of the conversations surrounding AI architectures. After all, there isnât necessarily one best way of doing things. Often, as I mentioned before, it simply depends. What is it you are trying to do? What are your technical limitations? What is your experience? What is your time frame? How much authorial control do your designers need? Really, it is something that you as the developer need to ascertain for yourself. As a waiter, I can only help you ask the right questions of yourself and point you in the right direction once we have the answers.
Unfortunately, many of the available books, articles, and web sites only tell you how the different architectures work. They often donât tell you the pros and cons of each. That often leads to misguided enthusiasts proclaiming with exuberant confidence, âI will create my [incredible AI] with a [not even remotely appropriate technology]!!â Donât get me wrongâŚ those resources are often very good at telling you how to work on a technical level with the different methods. What is missing is why you would do so.
At the 2010 GDC AI Summit, we presented a panel-based session entitled âDeciding on an AI Architecture: Which Tool for the Job?â The premise of the panel pitted four different technologies against each other to see which of them was most appropriate to use in four different game AI situations. Each architecture was represented by a person whose job it was to argue for our own and against the others. (Spoiler alert: the 4 game highly-contrived situations were specifically chosen so that each architecture was shown to have a strong point.) Even with the pre-written outcomes designed to steer toward a âbestâ answer, the three âlosingâ panelists managed to make the point that their method could work but simply was not the best tool for that job.
But thatâs part of the problem, isnât it? Certainly most AI architectures could manage to muddle through most any AI situation. However, that often leads people to a false sense of security. AI is often complicated enough that some amount of hair-pulling is expected. This often obscures the fact that an inappropriateâor, shall we say, âless than optimalââmethod is making things more difficult than it should be. All of this brings us back to our initial questionââwhat AI architecture should I use?â And, once again, I respond, âit depends.â
Same StuffâDifferent Shapes
|Itâs the same stuffâŚ just different shapes.
If I may tap once again into my food metaphor, selecting an AI architecture is often like selecting Mexican foodâfor most intents and purposes, itâs the same stuffâŚ just different shapes. Allow me to expound. The contents of most Mexican food can be reduced to some combination of a fairly succinct list of possibilities: tomato, cheese, beans, lettuce, onionsâŚ you know the drill. Additionally, the non-vegan among us often elect to include some form of meat (real or faux). Think of these ingredients as the behavior content of our AI. This is the stuff the gives all the flavor and âsubstanceâ to the dish. But what about the outside? Often we order our Mexican food in terms of its shape or formâa tacoâŚ a burritoâŚ etc. Why do we think in terms of the outside form when it is the stuff that is on the inside that is pretty much the point of the order in the first place?
The answer lies in the fact that the outsideâthat is, the shell or wrapper of some sortâis merely a content delivery mechanism. For the most part, it exists only as a way of keeping those internals together long enough for consumption. In this way, these âdelivery mechanismsâ compare to AI architectures. They only serve to package and deliver the tasty behavioral content that we want our players to experience. But why are there so many different forms for such a utilitarian function? And which form do I use? Well, it depends.
The same holds true when we talk about our AI systems. We often speak in terms of the mechanism rather than the content. We are writing a finite state machine, a behavior tree, or a planner, just like we are filling a taco, a burrito, or an enchilada. Once we have decided on that packaging, we can put any (or all!) of the tasty stuff into it that we want to. HoweverâŚ there are pros and cons to each.
The TostadaâJust a Pile of Stuff
Starting simple, letâs look at the tostada. It is, quite literally, about as simple a delivery platform that you can use for our Mexican food. Everything just sits on top of it right where you can see it. You can add and remove ingredients with ease. Of course, you are somewhat limited on how much you can put on since eventually it will start to fall off the sides. Although it is a little difficult to grab initially, if you pick it up correctly, everything stays put. However, itâs not a terribly stable platform. If you tip it in the slightest, you run the risk of sending things tumbling. Whatâs more, as soon as you start biting into it, you run the risk of having the whole thing break in unpredictable ways at which point, your entire pile of content falls apart. For all intents and purposes, the tostada really isnât a container at all once you start using itâitâs just a hard flat object that you pile stuff on top of and hope it stays put.
|You never know when the entire platform is going to simply fall apart.
From an AI standpoint, the equivalent isnât even really an architecture. This would be similar to simply adding rules here or there around our code that change the direction of things in a fairly haphazard manner. Obviously, the problem with that is, like the tostada, you can only get so much content before things become unstable. Itâs a bit unwieldy as well. Most importantly, every time you take a bite of your content, you never know when the entire platform is going to simply fall apart.
Adding a Little StructureâThe State Machine Taco
Our tostada suffered from not having enough structure to hold the content stable before it started to fall offâor fall apart entirely. However, by just being a little more organized about how we arrange things, we can make sure our content is a lot more self-contained. In the Mexican food world, we can simply bend our tostada shell into a curve and, behold, it becomes a taco! The result is that we can not only hold a lot more content, but we can also pick it up, manipulate it, and move it around to where we can get some good use out of it.
Adding a little bit of structure to a bunch of otherwise disjointed rules maps over somewhat to the most basic of AI architecturesâthe finite state machine (FSM). The most basic part of a FSM is a state. That is, an AI agent is doing or being something at a given point in time. It is said to be âinâ a state. Theoretically, an agent can only be in one state at a time. (This is only partially correct because more advanced agents can run multiple FSMs in parallelâŚ never mind that for now. Suffice to say, each FSM can only be in one state.)
The reason this organizes the agent behavior better is because everything the agent needs to know about what it is doing is contained in the code for the state that it is in. The animations it needs to play to act out a certain state, for example, are listed in the body of that state. The other part of the state machine is the logic for what to do next. This may involve switching to another state or even simply continuing to stay in the current one.
The transition logic in any given state may be as simple or as complex as needed. For example, it may simply involve a countdown timer that says to switch to a new state after a designated amount of time. It may be a simple random chance that a new state should be entered. For example, State A might say that, every time we check, there is a 10% chance of transitioning to State B. We could even elect to make the new state that we will transition to a result of a random selection as wellâsay a 1/3 chance of State B and a 2/3 chance of State C.
More commonly, state machines employ elaborate trigger mechanisms that involve the game logic and situation. For instance our âguardâ state may have the logic, âif [the player enters the room] and [is holding the Taco of Power] and [I have the Salsa of Smiting], then attack the playerâ at which point my state changes from âguardâ to âattackâ. Note the three individual criteria in the statement. We could certainly have a different statement that says, âif [the player enters the room] and [is holding the Taco of Power] and [I DO NOT have the Salsa of Smiting], then flee.â Obviously, the result of this is that I would transition from âguardâ to âfleeâ instead.
So each state has the code for what to do while in that state and, more notably, when, if, and what to do next. While some of the criteria can access some of the same external checks, in the end each state has its own set of transition logic that is used solely for that state. Unfortunately, this comes with some drawbacks.
Figure 1 â As we add states to a finite state machine, the number of transitions rapidly.
First, as the number of states increases, the number of potential transitions increases as wellâat an alarming rate. If you assume for the moment that any given state could potentially transition to any of the other states, the number of transitions increases fairly quickly. Specifically, the number of transitions would be the [number of states] Ă ([number of states] â 1). In Figure 1, there are 4 states each of which can transition to 3 others for a total of 12 transitions. If we were to add a 5th state, this would increase to 20 transitions. 6 states would merit 30, etc. When you consider that games could potentially have dozens of states transitioning back and forth, you begin to appreciate the complexity.
What really drives that issue home, however, is the realization of the workload that is involved in adding a new state to the mix. In order to have that state accessible, you have to go and touch every single other state that could potentially transition to it. Looking back at Figure 1, if we were to add a State E, we would have to edit states A-D to add the transitions to E. Editing a stateâs logic invokes the same problem. You have to remember what other states may be involved and revisit each one.
|And the bigger it gets, the more opportunity for disaster.
Additionally, any logic that would be involved in that transition must also be interworked into the other state-specific logic that may already be there. With the sheer numbers of states in which to put the transition logic and the possible complexity of the integration into each one, we realize that our FSM taco suffers from some of the same fragility of the ad hoc tostada we mentioned earlier. Sure, because of its shape, we can pile a little more on and even handle it a little better. One bite, however, could shatter the shell and drop everything into our lap. And the bigger it gets, the more opportunity for disaster.
A Softer ApproachâThe Behavior Tree
So the problem with the taco is that it can hold a fair bit of content (more than the tostada anyway), but is a bit brittle. It is not the shape of the taco that is at fault as much as it is a result of using the hard shell. If only we could hold the same content delivered in much the same manner, but have our container be less prone to shattering when we put some pressure on it. The answer, of course, is the soft taco. And the analogue in the AI architecture could very well be the behavior tree.
At this point, it is useful to point out the different between an action and a decision. In the FSM above, our agents were in one state at a timeâthat is, they were âdoing somethingâ at any given moment (even if that something was âdoing nothingâ). Inside each state was decision logic that told them if they should change to something else and, in fact, what they should change to. That logic often has very little to do with the state that it is contained in and more to do with what is going on outside the state or even outside the agent itself. For example, if I hear a gunshot, it really doesnât matter what Iâm doing at the timeâIâm going to flinch, duck for cover, wet myself, or any number of other appropriate responses. Therefore, why would I need to have the decision logic for âReact to Gunshotâ in each and every other state I could have been in at the time?
Figure 2 â In a behavior tree, the decision logic is separate from the actual state code.
This is the strength of the behavior tree. It separates the states from the decision logic. Both still exist in the AI code, but they are not arranged so that the decision logic is in the actual state code. Instead, the decision logic is removed to a stand-alone architecture (Figure 2). This allows it to run by itselfâeither continuously or as neededâwhere it selects what state the agent should be in. All the state code is responsible for is doing things that are specific to that state such as animating, changing values in the world, etc.
The main advantage to this is that all the decision logic is in a single place. We can make it as complicated as we need to without worrying about how to keep it all synchronized between different states. If we add a new behavior, we add the code to call it in one place rather than having to revisit all of the existing states. If we need to edit the transition logic for a particular behavior, we can edit it in one place rather than many.
Figure 3 — A simple behavior tree. At the moment the agent has decided to do a ranged attack.
Another advantage of behavior trees is that there is a far more formal method of building behaviors. Through a collection of tools, templates, and structures, very expressive behaviors can be writtenâeven sequencing behaviors together that are meant to go together (Figure 3). This is one of the reasons that Behavior Trees have become one of the more âgo-toâ AI architectures in games having been notably used in titles ranging from Halo 2 and 3, to Spore.
A detailed explanation of what makes behavior trees work, how they are organized, and how the code is written is beyond the scope of this article. Suffice to say, however, that they are far less prone to breaking their shell and spilling their contents all over your lap. Because the risk of breaking is far less, and the structure is so much more organized, you can also pack in a lot more behavioral content.
For an excellent primer on behavior trees, see Bjoern Knaflaâs Introduction to Behavior Trees on #AltDevBlogADay
A Hybrid TacoâThe Hierarchical Finite State Machine
Figure 4 â In a hierarchical finite state machine, some states contain other related states making the organization moreÂ manageable.
A brief note before we leave the land of tacos behind. One the advantages of the behavior treeânamely the tree-like structureâis sometimes applied to the finite state machine. In the hierarchical finite state machine (HFSM), there are multiple levels of states. Higher-level states will only be concerned with transitioning to other states on the same level. On the other hand, lower-level states insideÂ the parent state can only transition to each other. This tiered separation of responsibility helps to provide a little structural organization to a flat FSM and helps to keep some of the complexity under control.
If we were to place the HFSM into our Mexican metaphor, it would be similar to one of those nifty hard tacos wrapped in a soft taco shell. Thereâs still only so much you can pile into it before it gets unwieldy, but at least it doesnât tend to shatter and make as big of a mess.
Building it from ScratchâPlanning your Fajita
If you are anything like my wife, you want to be able to choose exactly what is in your Mexican dishânot just overall, but in each bite. Thatâs why she orders fajitas. While the fajita looks and acts a lot like a taco (specifically, a soft shell one), the method of construction is a little different. Rather than coming as an already assembled construction, the typical method of serving it is to bring you the tortillas and having the content in a couple of separate piles. You then construct your own on the spot like a personal mini buffet. You can choose what you want to put in the first one and then even change it up for the subsequent ones. It all depends on what you deem appropriate for your tastes at that moment.
The AI equivalent of this is the planner. While the end result of a planner is a state (just like the FSM and behavior tree above), how it gets to that state is significantly different.
Like a behavior tree, the reasoning architecture behind a planner is separate from the code that âdoes stuffâ. A planner compares its situationâthe state of the world at the momentâand compares it to a collection of individual atomic actions that it could do. It then assembles one or more of these tasks into a sequence (the âplanâ) so that its current goal is met.
|A planner actually works backwards from its goal.
Unlike other architectures that start at its current state and look forward, a planner actually works backwards from its goal (Figure 5). For example, if the goal is âkill playerâ, a planner might discover that one method of satisfying that goal is to âshoot playerâ. Of course, this requires having a gun. If the agent doesnât have a gun, it would have to pick one up. If one is not nearby, it would have to move to one it knows exists. If it doesnât know where one is, it may have to search for one. The result of searching backwards is a plan that can be executed forwards. Of course, if another method of satisfying the âkill playerâ goal is to throw a Taco of Power at it, and the agent already has one in hand, it would likely elect to take the shorter plan and just hurl said taco.
Figure 5 â The planner has found two different methods of achieving âkill playerâ and selected the shorter one.
The planner diverges from the FSM and BT in that it isnât specifically hand-authored. Therein lies the difference in plannersâthey actually solve situations based on what is available to do and how those available actions can be chained together. One of the benefits of this sort of structure is that it can often come up with solutions to novel situations that the designer or programmer didnât necessarily account for and handle directly in code.
From an implementation standpoint, a major plus of the planner is that a new action can be dropped into the game and the planner architecture will know how to use it. This speeds up development time markedly. All the author says is, âhere are the potential things you could doâŚ go forth and do things.â
Of course, a drawback of this is that authorial control is diminished. In a FSM or BT, creative, âoutside the boxâ solutions were the exception from the predictable, hand-authored systems. In a planner, the scripted, predictable moments are the exception; you must specifically override or trick the planning system to say, ânoâŚ I really want you to do this exact thing at this moment.â
While planner-based architectures are less common than behavior trees, there are notable titles that used some form of planners. Most famously, Jeff Orkin used them in Monolithâs creepy shooter, F.E.A.R. His variant was referred to as Goal-Oriented Action Planning or GOAP. For more information on GOAP, see Jeffâs page, http://web.media.mit.edu/~jorkin/goap.html
A more recent flavor of planner is the hierarchical task network (or HTN) planner such as was used to great effect in Guerillaâs Killzone 2. For more information on HTN planning in Killzone 2, visit http://aigamedev.com/open/coverage/htn-planning-discussion/
Putting It All in a BowlâA Utility-Based Salad
Another architecture that is less structured than the FSM or behavior tree is what has been called in recent years simply âutility-basedâ method. Much like the planner, a utility-based system doesnât have a pre-determined arrangement of what to do when. Instead, potential actions are considered by weighing a variety of factorsâwhat is good and bad about this?âand selecting the most appropriate thing to do. As you can see, this is similar to the planner in that the AI gets to choose whatâs best at the time.
|The action with the highest score wins.
Instead of assemblinga plan like the fajita-like planner, however, the utility-based system simply selects the single next bite. This is why it is more comparable to a taco salad in a huge bowl. All the ingredients are in the mix and available at all times. However, you simply select what it is that would like to poke at and eat. Do you want that piece of chicken in there? A tomato, perhaps? An olive? A big wad of lettuce? You can select it based on what you have a taste for or what is most accessible at the moment.
Figure 6 â A typical utility-based system rates all the potential actions on a variety of criteria and selects the best.
One of the more apparent examples of a utility-based AI system is in The Sims. In fact, the considerations are largely shown in the interface itself. The progression of AI architectures throughout The Sims franchise is well documented and I recommend reading up on it. The short version is that each potential action in the game is scored based on a combination of an agentâs current needs and the ability of that action or item to satisfy that need. The agent then uses an approach common in utility-based methods and constructs a weighted sum of the considerations to determine which action is âthe bestâ at that moment. The action with the highest score wins (Figure 6).
While utility-based systems can be used in many types of games, they are more appropriate in situations where there are a large number of potentially competing actions the AI can takeâoften with no obvious âright answer.â In those times, the mathematical approach that utility-based systems employ is necessary to ferret out what the most reasonable action to take is. Aside from The Sims, other common areas where utility-based systems are appropriate are in RPGs, RTS, and simulations.
Like behavior trees and planners, the utility-based AI code is a reasoner. Once an action is decided up, the agent still must transition to a state. The utility system simply is selecting what state to go to next. In the same way, then, just like those other systems, the reasoning code is all in a single place. This makes building, editing, tuning and tweaking the system much more compartmentalized. Also, like a planner, adding actions to the system is fairly straight forward. By simply adding the action with the appropriate weights, the AI will automatically take it into account and being using it in relevant situations. This is one of the reasons that games such as The Sims were as expandable as they wereâthe agents simply included any new object into their decision system without any changes to the underlying code.
|The system is providing suggestions as to what might be a good idea.
On the other hand, one drawback of a utility system is that there isnât always a good way to intuit what will happen in a given situation. In a behavior tree, for example, it is a relatively simple exercise to traverse the tree and find the branches and nodes that would be active in a particular situation. Because a utility system is inherently more fuzzy than binary, determining how the actions stack up is often more opaque. Thatâs not to say that a utility-based AI is not controllable or configurable. In fact, utility systems offer a deep level of control. The difference is that rather than telling the system exactly what to do in a situation, the system is providing suggestions as to what might be a good idea. In that respect, a utility system shares some of the adaptable aspects of plannersâthe AI simply looks at its available options and then decides what is most appropriate.
For more reading on utility-based systems, please check out my book, Behavioral Mathematics for Game AI or, if you have GDC Vault access, you can view my AI Summit lectures (with Kevin Dill) from 2010 and 2012 entitled, âImproving AI Decision Modeling through Utility Theoryâ and âEmbracing the Dark Art of Mathematical Modelingâ respectively.
Wrap it UpâA Neural Network Burrito
The last entry in my (extremely strained) metaphorical cornucopia is the burrito. In the other examples, all the content that was being delivered was open and available for inspection. In the case of the fajita, you (the AI users) were able to assemble what you wanted in each iteration. In the taco salad, the hard and soft tacos, and even the tostada you were able to, as the clichĂŠ says, âseason to tasteâ. Perhaps a little extra cheese over the top? Maybe a few extra tomatoes? Even if you didnât edit the content of your dish, you were at least able to see what you were getting into before you took a bite. There was no mystery about what made up your dinner; everything was open and available for your inspection.
The burrito is different in this respect. You are often told, in general terms, what the burrito is supposed to be packing but the details are often hidden from view. To paraphrase Winston Churchill, âit is a riddle, wrapped in a mystery, inside a soft flour shell.â While the burrito (and for that matter, the neural network) is extremely flexible, you have absolutely no idea what is inside or what you are going to get in the next bite. Donât like sour cream? Olives? Tough. If itâs in there, you wonât know until you take that bite. At that point, it is too late. There is no editing without completely unwrapping the package and, for all intents and purposes, starting from scratch.
This is the caveat emptor of the NN-based AI solution. As a type of âlearningâ AI, neural nets need to be trained with test or live performance data. At some point you have to wrap up the training and say, âThis is what I haveâ. If a designer wanders in, looks over your shoulder and says, âIt looks pretty cool, but in [this situation] I would like it to do [this action] a little a little more often,â thereâs really nothing you can do to change it. Youâve already closed your burrito up. About all you can do is try to retrain the NN and hope for the best.
So while the NN offers some advantages in being able to pile a lot of things into a huge concoction of possibilities, there are huge disadvantages in a lack of designer control after the fact. Unfortunately, this tends to disqualify NNs and other machine-learning solutions from consideration in the game AI environment where that level of control is not only valuable but often a requirement.
That said, there have been a few successful implementations of NNs in gamesâfor example, Michael Robbins used NNs to improve the tactical AI of Supreme Commander 2 from Gas Powered Games. (For those with GDC Vault access, you can see more about his implementation of this in the AI Summit session, âOff the Beaten Path: Non-Traditional Uses of AIâ.)
Browsing the Buffet
So weâve covered a variety of architectures and, for what its worth, equated them with our Mexican delights. Going back to our premise, as far as the content goes, itâs all the same stuff. The difference is simply the delivery mechanismâthat is, the shape of the wrappingâand the associated pros and cons of each. This has by no means been an exhaustive treatment of AI architectures. The purpose was simply to expose you to the options that are out there and why you may or may not want to select each for the particular tastes and needs of your project. To sum up, though, letâs go through the dishes once againâŚ
You can certainly just throw the occasional rule into your code that controls behaviorâbut thatâs not really an âarchitectureâ. By organizing your AI into logical chunks, you can create a finite state machine. A FSM is relatively easy to construct and for non-programmers to understand. While this is good for simple agents with a limited number behaviors, it gets brittle quickly as the number of states increases. By organizing the states into the logical tiers of a hierarchical finite state machine (HFSM), you can mitigate some of this complexity.
By removing the reasoning code from the states themselves, you can gain a lot more flexibility. By organizing behaviors into logically similar branches, you can construct a behavior tree. BTs are also fairly easy for designers and other non-programmers to understand. The main advantages, however, are not only the ease with which they can be constructed but how well they scale without the need for a lot of extra programming. Once the BT structure is in place, new branches and nodes can be added easily. However, despite how robust BT implementations can get, it is still a form of hand-authored of scriptingââwhen X, do Yâ.
Figure 7 — The type of architecture you select needs to be based on YOUR needs.
Like the behavior tree, a planner allows for very extensible creation. However, where the BT is more hand-authored by designers, a planner simply âsolvesâ situations using whatever it feels is best for the situation. This can be powerful, but also leads to a very scary lack of control for designers.
Similarly, utility-based systems depart from the specific script approach and allow the characters to decide freely what to do and, as above, might unsettle some designers. They are incredibly expandable to large numbers of complex factors and possible decisions. However, they are slightly more difficult to intuit at times although tools can be easily built that aid that process.
The ultimate hands-off black box in the neural network. Even the programmers donât know whatâs going on inside their little neurons at times. The good news is that they can often be trained to âdo what human players would do.â That aspect itself holds a lot of appeal in some genres. They are also a little easier to build since you only have to construct the training mechanism and thenâŚ wellâŚ train it.
|There is no âone size fits allâ solution to AI architectures.
The point is, there is no âone size fits allâ solution to AI architectures. (You also donât have to limit yourself to a single architecture in a game.) Depending on your needs, your team, and your prior experience, any of the above may be The Right Way for you to organize your AI. As with any technical decision, the secret is to research what you can, even try a few things out, and decide what you like. If I am your waiter AI consultant, I can help you outâŚ but the decision is ultimately going to be what you have a hankerinâ for.
Now letâs eat!
(The author would like to dedicate this article to all the GDC, Gamasutra, and GDMag staff who are still lamenting the departure of the beloved Mexican restaurant that used to be located in their building. I mourn with you, my friends.)