Article
i/2008/05/strawman

Chasing Strawmen Out of Game AI Research

Alex J. Champandard on May 2, 2008

The call for papers for the AIIDE ‘08 conference has just expired. This year I’m on the Program Committee, so today I got my hands on four papers to review based on my selected topics. There are some pretty great research projects this year…

However, I find the opening paragraphs that describe the motivation of the paper very frustrating. While many of the arguments presented may have been valid quite a few years ago, technology is moving very quickly these days. Most of the papers cited written by people in industry are already a few years out of date, and as such, don’t really represent a valid basis for research anymore.

So, until I write a paper documenting the typical techniques used in industry these days, here’s an article dismissing the four most common fallacies that you shouldn’t base your arguments on.

FALLACY #1
Developers Use Scripts Because They Don’t Know Better

Based on the behaviors you see in games, it’s easy to assume that developers don’t stay up-to-date with progress made in the field of AI… However, the problems you notice are a side-effect of the sheer complexity of the task rather than the technology used.

FACT #1
Scripts Are Irreplaceable

Game AI developers are fully aware of the many limitations of scripted behaviors. Yet they are still widespread in industry because they serve a purpose that no other technology can match:

  • Scripts are the best way to specify sequential behaviors. All AI needs sequences to some degree, but this is especially true for story-driven games.

  • Scripts are the simplest way to prototype AI logic. Scrips provide a direct channel from the brain of the designer into the game.

No amount of research will change the usefulness of scripts. There’s certainly room for improving workflow — but conceptually scripts are here to stay. When developers need adaptive behaviors, they use different techniques that work particularly well…

FALLACY #2
Game AI Is Stupid Because It Doesn’t Adapt

Nobody’s arguing that game AI doesn’t have a certain level of stupidity to it, but it’s not adaptive technology that’s missing…

FACT #2
Game AI Already Supports Runtime Adaptation

The job of a game AI developer is primarily to build adaptive behaviors. If you don’t have adaptive behaviors, then you can’t really build a game at all — let alone make it fun. For already a few generations of games, NPCs have been built from behaviors that are more or less autonomous (depending on the requirements).

  • Autonomous behaviors are designed to adapt to situations dynamically already.

  • Finite-state machines, among others, can be used to build adaptable behaviors by taking into account more information.

The thing to notice here is that this traditional adaptation has a cost. It takes time for the designer to figure out what information about the player or world requires adaptation, then the programmer must implement the correct behavior. The overhead of this workflow is an acceptable argument, and there’s certainly lots of research to be done here.

FALLACY #3
Developers Typically Use Scripts to Build Game AI

Scripts are still used very often to describe the logic in levels, but individual characters typically use a different approach.

FACT #3
Goal-Directed Systems are the Reference Implementation

Many researchers approach the process of creating behaviors automatically (either online or offline) from the machine learning angle. There’s nothing wrong with that, but the most common mistake is to compare these ML techniques to hand scripting. As discussed in #1, scripting is only used where necessary…

These days, the most common implementation choice for AI logic is a hierarchical goal-driven system, for example Behavior Trees (BT) or Hierarchical Tasks Networks (HTN). Such systems also do a great job of automatically generating context sensitive behaviors that adapt to their environment. As such, you should be comparing your machine learning to these techniques, which have much more benefits in pretty much every department.

FALLACY #4
STRIPS Planners Represent the State-of-the-Art

If you assume that A* planners are the cutting edge of game AI, you’re on the right track — and way ahead of the curve. However, there’s even better technology being used these days…

FACT #4
Non-Hierarchical Planners are a Stepping Stone

The flat STRIPS planner used in the game F.E.A.R. is being replaced by hierarchical planners just like A* pathfinding has taken second place to hierarchical pathfinders for large worlds. It’s not only more efficient, but it’s easier for your designers to control the outcome also.

Three (yes, 3!) AI middleware solutions will release hierarchical planners within the year, or have already done so. A few more commercial games are in development using such forms of hierarchical planners. As a developer, you’d need to have a really good excuse not to use this approach for building commercial game AI. As a researcher, you should be comparing your technology to this approach.

Conclusion

There’s lots of research still to be done in applying artificial intelligence to games, but let’s see it done for the right reasons. Research based on current concerns of studios is much more likely to make it into a real game.

It’s true that techniques used in commercial games are poorly documented, but the situation is improving. Among other things, you can sign up to the AiGameDev.com forums and ask for feedback from professionals, and also don’t forget to attend the many mixed conferences between academics and developers from industry (e.g. in Paris on the 25th of June).

Discussion 3 Comments

alexjc on May 4th, 2008

[B]Jeff,[/B] Actually, come to think of it, there are [U]four[/U] middleware companies with projects relating to hierarchical planners. There's the one you mentioned, there's [URL="http://www.ekione.com/"]EKI One[/URL] which isn't out yet, but lists hierarchical planners as a feature based on my article :-) Also, ex-middleware company [URL="http://en.wikipedia.org/wiki/Mad_Doc_Software"]Mad Doc[/URL] definitely had HTN compiler technology (based on a paper at AIIDE I think) before they got bought by Rockstar -- but now it'll never see the light of day. There's another one too, but I must check for public sources on that one. Stay tuned! As for shipped titles that used HTN, look towards [URL="http://www.gamasutra.com/features/20070412/wilcox_01.shtml"]Radical[/URL] possibly. Also, based on our many discussions in the forums, I would also point out that the difference between a goal-directed behavior tree and a HTN are minor. There are tradeoffs to be made when picking one over the other, but either way the resulting tree & implementation is extremely similar. [B]Anonymous,[/B] You're absolutely right that large numbers of mainstream developers have more ad-hoc implementations. There are many games to be built with really simple AI, and these companies will keep doing so -- or start improving technology. However, there are many high-tech companies that are really pushing the boundaries beyond what middleware provides. I guess somehow I gravitate around these more, but this kind of knowledge is spreading quickly to projects who need it. Anyway, my point is that if you're going to be doing research you should be compared to the best practices -- not the average implementation. There's always been a gap between those two! Alex

RyanP on May 5th, 2008

Alex, I do agree that people should obviously do some more research before they write a paper or just not generalize as to why something is done if they do not know. However I do have some questions if you do not mind. You mentioned "hierarchical pathfinders" and HTN. I am confused what exactly is "hierarchical pathfinders"? I logical guesstimated that it is a form of scripted pathfinding, however I could be wrong. As for an HTN, upon reading your previous article back in January it does appear that it is a behavior based FSM. Is my understanding of that correct? Thanks, Ryan

alexjc on May 6th, 2008

[B]Ryan,[/B] Hierarchical pathfinding is basically applying the search algorithm onto a less detailed graph. So you'd search a bunch of rooms or sectors before searching individual steps in a grid. Read about [URL="http://aigamedev.com/forums/aigamedev.com/theory/near-optimal-hierarchical-pathfinding"]HPA*[/URL] for example. A planner is different from Hierarchical Finite State Machines (HFSM) since it thinks about "concepts" and doesn't actually execute anything. You have to take the resulting plan and then apply it. Read more about the [URL="http://aigamedev.com/theory/shop-htn"]SHOP HTN[/URL] planner on the blog too. If you have any more questions, sign-up to the [URL="http://aigamedev.com/forums/"]forums[/URL] :-) Alex

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!