Notes from the “AI for Dummies” Session

AI Roundtable Moderator’s Report

2001 Game Developer’s Conference, March 22-24

Steven Woodcock

ferretman@gameai.com

Background

For the last five years, Neil Kirby, Eric Dybsand, and I have moderated a series of AI roundtables at the Game Developer’s Conference. These roundtables grew out of a sense of frustration at the 1996 GDC, when we found ourselves unable to get into several game AI sessions that were packed to standing-room only capacity. We submitted a proposal to the GDC folks for a series of three simultaneous roundtables, which would both accommodate the massive numbers of people any AI session seemed to attract and allow us to focus sessions on problems developers were facing—something not really doable in a lecture format. They agreed, and the GDC AI Roundtables were born.

This year’s sessions followed essentially the same format as the 2000 roundtables did. Day One focused on general AI topics—whatever the attendees wanted to discuss. Day Two broke up the roundtables into specific topical areas. My session focused on RPGs and FPS games, while Eric’s was aimed at wargames and strategy games of all kinds. Neil took on the very difficult topic of sports game AIs. This devotion of sessions to specific arenas of game development were intended to help satisfy attendees who had questions or comments specific to a current project, which might otherwise not come up in a more general discussion.

Day Three continued a format we first experimented with in the 1999 roundtables, in that this session was a combined roundtable focusing on "AI for Newbies". In this session, we attempted to address the needs of developers new to the field of game AI who often didn’t know where to start. We also tried to reach out to artists, producers, and others involved in the game development process who were interested in the field of game AI but who really didn’t know much about it. Our hope with this session was that we would be able to both help developers new to the field and aid in bridging the "understanding gap" that can crop up between AI developers and others on their team.

Overall the sessions seemed to go very well and it is my hope that much information was traded and absorbed. What follows are specific notes from each of the sessions I moderated; Neil and Eric's moderator’s reports can be found online wherever this report was, or by following the links.

Thursday, March 22^nd

My first session had a total of 15 attendees, the same as with last year’s session but still feeling a bit "light". We later attributed the lower turnout to the fact that my particular session was located on the far side of the bundle of rooms in which all of our roundtables were located; most folks looking for a roundtable found Neil or Eric’s room first and stayed there. I was quite lucky in having the esteemed Will Wright (creator of The Sims) in my session, however, and he provided some excellent insights as the roundtable discussions proceeded.

We began with our standard questions concerning the number of developers present and how many resources they were getting in their projects. Every attendee was an AI developer involved in an active project, and they reported an average CPU usage of 51% or so for the bulk of their projects. Two developers were working on turn-based games and could legitimately claim 100% CPU availability, while one indicated he’d never really measured his CPU budget but assumed it was 10% or less. Another poll revealed that the developers had plenty of manpower to get their job done—12 indicated that they had at least one full-time AI developer, and two indicated there were two developers devoted to the AI.

Highlights from the roundtable discussions included:

Genetic Algorithms – Everybody thought Genetic Algorithms (GAs) had potential but hardly anybody was willing to use them for their next project. The inherent unpredictability of evolutionary computing turned off many developers, if only because nobody could ensure that a "dumb AI" wouldn’t evolve when they weren’t looking. One developer indicated that he was investigating using GAs for an upcoming MassMOG (Massively Multi-player Online Game), using them to help craft the "story" the players interacted with in real-time.

Viruses Infecting the AI – As a follow-up to the discussion of using individual user’s machines to "breed" better AIs for a MassMOG, one attendee brought up the potential problem of viruses being introduced into the AI engine via this route. All agreed that for this to work there would need to be some kind of verification of the gene’s intent and authenticity, but that ultimately the Game Master for the game would have to simply keep a watchful eye.

Level of Detail AI was a popular topic of discussion, no doubt in part because many attendees (including this moderator) had just come from an excellent presentation by Demis Hassabis on his approach to the problem in his upcoming game Republic. LoDAI is essentially the problem of tuning one’s AI processing so that agents near to and heavily influenced by the player get priority over those far away and in the background. A variety of approaches were discussed by the attendees on how they were handling LoDAI in their projects, including upping the priority of individual AI threads and building the AI in an event-based fashion so that agents far from the player didn’t get as much processing time. Most developers felt that LoDAI was ultimately a tuning issue and one they didn’t worry about too much during development proper.

Group AI was also a favorite topic of discussion, given the current popularity of games featuring teams of NPCs working with or assisting the player’s avatar. There was general consensus that it just wasn’t easy, and that getting it right depended heavily on the specifics of the game itself. There was much unhappiness that players often didn’t see how clever the team AIs in a given game were—a player wouldn’t always know, for example, that a teammate AI had just taken out an enemy soldier that had nearly ambushed the player’s avatar. Feedback of some sort between the NPCs and the player is vital.
Influence Maps (IMs) were brought up by a developer who was wondering if they might prove a suitable technology for his RPG. He envisioned using these to attract certain NPCs to the player, or to repel them in the event the player had a bad reputation. Will Wright jumped in to share that he’d considered IMs in The Sims to handle certain social interactions (such as bad body odor) but hadn’t been able to implement them for that game.

The session ended with the discussion going strong on several fronts.

Friday, March 23^rd

As mentioned above the second day sessions were focused on specific areas of game AI. My session covered RPGs and FPS games which, in hindsight, proved not to be the best combination as the needs to the two kinds of AI appear to be significantly different from each other.

A total of 35 people attended the RPG/FPS AI roundtable, and the room filled up so quickly that we shut the doors and got started 15 minutes early. The conversation was quick to get started and covered a lot of topics, despite it being obvious from the start that the two kinds of games were prompted entirely different kinds of questions.

Resources – As with the first day’s session, the bulk of the 35 attendees felt that they had more than enough CPU resources to get their job done. Fully 32 of the 35 were AI developers themselves, and reported an average of 1 dedicated AI developer per project. Fourteen were working on a first-person shooter project, while 6 were involved in an RPG of some kind. CPU resource estimates ranged from 5% to 25%, with the overall average around 15% by my estimate. Generally the only problems developers felt they were facing were making their AI "smart" and avoiding the inevitable schedule crunch.

Motivation vs. scripting was a topic quickly embraced by both groups, since both have the problem of building AIs which are believable without being so complex that they detract from gameplay. The FPS crowd seemed to feel that most good AI interactions could be handled directly in the game engine proper via a good scripting engine, similar to the methods established already by Quake and Half-Life. The RPG developers, on the other hand, were looking for "organic" solutions more along the lines of the AI in The Sims (indeed, The Sims was mentioned several times throughout the session as an inspiration for what AI could be). It was generally agreed that The Sims had raised the bar in terms of what was expected from a game AI, and every developer present was seeking a way to build that level of believability into their game.

3D Path-finding cropped up as a perennial problem, just as in previous year’s roundtables. Nearly everybody used some form of A*, though one developer was fairly proud of a detailed waypoint system he’d built for his console FPS that seemed to work very well. Developers were keen on discussing ways to speed up path-finding in 3D space, and a few ideas were tossed out. Most developers reported that they simply collapsed the problem into a 2D one, marking ladders, sniper positions, and other 3D terrain as especially desirable in some fashion. One developer, working on an online RPG, was planning to avoid the problem entirely by using a form of "bread crumbs" laid down by the players to build intelligent paths for his NPCs to traverse. All agreed that path-finding and line-of-sight (LOS) calculations were far and away the most expensive components of their AI in terms of CPU usage and general maintenance.

Companion AIs, that is AIs which assist the player in some fashion, were one of the few topic areas in which both FPS and RPG developers felt their problems overlapped. Nobody felt that they were doing a very good job of building "believable" companion AIs. Various companion AIs from previous games were discussed, as well as some of the older MUD (Multi-User Dungeon) AIs such as Julia. The most common solution currently in use seems to be to craft these NPCs along generic lines, but to back them up with scripts that would trigger under various circumstances. Nobody much liked this approach, though it seemed to have the virtue of being easy to debug and modify as a game approached the final tuning phase.

Game AI SDKs cropped up as a popular topic from previous years, with nearly every attendee wondering if anybody else had used or was considering using one. It turned out that nobody was using any kind of AI SDK or middleware, for pretty much the same reason—they didn’t feel they were practical, or that they currently offered sufficient benefits. We discussed the various AI SDKs currently available (Mathematiques Appliquees DirectIA, LouderThanABomb’s Spark!, and Biographic Technologies’ ACE plug-in for Maya) and their potential benefits, but beyond the basic information nobody in the room had used or considered using them. It was quite apparent that if AI middleware is to gain widespread acceptance the developers of these toolkits still have a lot of convincing to do.

Exotic AI Technologies – As always, many of the attendees were exploring the use of the more exotic AI technologies—neural networks, genetic algorithms, etc.—as potential a potential solution to building better AIs. They didn’t get a great deal of encouragement from other developers who had already explored these technologies, however. There was general agreement among the "old hands" that the fuzzier AI technologies sounded really great, but couldn’t deliver the kind of predictable, understandable, and (most importantly) tunable control over a games’ AI that developers really needed. The humble Finite State Machine (FSM) and its cousin the Fuzzy State Machine (FuSM) were far and away the most popular approaches to building any kind of AI, with newer tools such as scripting simply providing more flexible ways to build and tune them.

Unfortunately our session ran out of time before we ran out of things to discuss, to the great disappointment of all concerned. A quick closing survey indicated that attendees felt that RPGs would be better lumped with adventure games in future sessions, and that FPS games could probably carry a session by themselves.

Saturday, March 24^th

Day Three was another "AI for Newbies" session, following up on the popular format we began in 1999. Neil, Eric, and myself combined our separate AI roundtables into one large session devoted to helping folks new to game AI get answers to their questions. The session had a total of 34 attendees—down from the similar 2000 session, but in line with the convention averages. The room had just the right amount of people for a good "give and take" session.

In order to help facilitate the discussion we put together a handout with pointers to references on a variety of the most common game AI topics. This seemed to go over fairly well with the attendees and we’ll probably do it again for the 2002 sessions.

Neil and Eric moderated while I took notes on the whiteboard (thanks to the GDC staff for providing that!). What follows are the questions I got onto paper together with the best summation of our answers (and related discussion) I could get down:

Question #1: Are there good references for Game AI?

There are few references for game AI itself as a topic. While there are several books in various stages of production (most notably Bryan Stout’s Game AI: Pathfinding, due out late this year with any luck), the field is pretty sparse. We recommend Russell and Norvig’s AI: A Modern Approach as a basic reference. We also recommend the Game Programming Gems series (which both Eric and Steve have done articles for) as having excellent sections on game AI.

Beyond that, the Web is the single best source for all game AI information. Steve’s site, www.gameai.com, is highly recommended, as is www.gamedev.net.

Question #2: How do I do path-finding? I keep hearing about "A-star" but I don’t know what that means.

The web is, again, your best single source for path-finding information, mostly notably the "A*" (pronounced "A-star") algorithm. A* is the most common solution used by game developers because it works.

There are a ton of good sites out there that will both explain the A* algorithm and provide source code—again, www.gameai.com is a good place to start. Forums on the various game development web sites are also great places to ask questions if you’re having trouble implementing A*--both www.gamedev.net and www.gamasutra.com have excellent forums on game AI. The Game Programming Gems series has several chapters devoted to A* and how to adapt it for the needs of your particular game—no single A* solution is right for everybody.

One note: Good data structures make all the difference for efficient path-finding. Do some design work first.

Question #3: What is "dynamic path-finding"?

Dynamic path-finding is essentially the adapting of your path to new information in near-real time, such as recognizing that a bridge you were planning to cross has blown up and so you’ve got to find another path. It’s amazing how many games don’t do this.

A* will handle this if you approach the path-finding problem piecemeal, time-slicing the full path-finding solution across several CPU cycles. Not only does this lessen the load of path-finding on your overall game engine, but it allows the algorithm to recognize potential changes in the environment between steps.

Another approach is to establish waypoints, solving the full path in smaller sections. The unit in question gets to Point A, then figures out how to get to Point B, then looks at getting to Point C, doing all of this stepwise rather than in one big lump.

Yet another approach is to have the game send some kind of triggering event to any unit crossing terrain that has been/might be changed. There can be some "fog of war" issues here (in Command and Conquer, for example, units knew about terrain changes they couldn’t technically see) so tread carefully and design well.

Question #4: How do I create good NPCs (Non Player Characters)?

This is often called the "smart bartender" problem—you want to make a bartender who isn’t a blithering idiot and who can actually hold a "bartender like" conversation with the player, but whom also isn’t going to leap over the counter and run off on a quest with you. An awful lot of RPGs seem to have either one variety or the other, and holding a real conversation is almost impossible.

Branching conversation trees are the pretty common ways to handle this, but they can quickly get boring and predictable. There’s nearly always some selection that’s clearly stupid, plus one that’s clearly provocative—leaving the "middle way" as the obvious solution.

Conversational AI is hard, but there are some resources. The best examples come from the old MUD (Multi User Dungeon) ‘bots, such as Julia and Debbie. You can find more information and code at here.

Remember that you’re building a game, so nothing’s going to be perfect. You can get pretty good though, especially if you look beyond the conventional branching conversation tree. You’ll always get criticism whatever you do, so do what works for the game.

Question #5: How do I build my AI within budget?

This question was prompted by one poor guy who was six weeks away from game delivery and hadn’t started his AI yet. There was general consensus that he was screwed, but that the conversation that followed would help him on his next project.

The best way to make sure your AI is within budget and does what your producer wants is to be involved from the very beginning. Be part of the game’s design, and ask AI questions as important design elements are discussed—"Will you be wanting me to implement that behavior in some kind of scripted fashion, or should I build an AI that will try to figure things out on the fly?".

Next, make sure that everybody involved has realistic expectations. Good AI is hard—you don’t have to worry whether or not you’re going to build an AI so good that it can’t be beaten. Make sure you’ve got a reasonable slice of the CPU resources dedicated to the AI proper—don’t let the graphics guys run the show. Establish definite, testable milestones on the schedule and stick to ‘em. Outline the features the producer wants and work those first—don’t experiment unless you’re oozing spare time.

Focus on the "big payoff" AI features first—prioritization is key. It’s much more important that your NPCs can shoot intelligently than that they can find a power-up quickly.

Enforce your interface. Define a common set of methods for the other game folks to invoke your AI and make them stick to it! You can’t manage your AI if you’re not in control of it. Similarly, your AI should interface with the game at as close to the same level as the player as possible—this helps to avoid cheating and makes the whole AI design more modular and extensible.

Question #6: How do I get my AIs to behave intelligently?

This is really a subset of other topics already discussed, but there is a bit more to say. Don’t dismiss the magic of the random number. Good random actions can easily be mistaken for intelligent actions by the user, especially if the environment encourages them to think that way. Make sure your AIs choose from a good set of random actions if they must choose randomly.

Question #7: Is anybody using new AI technologies?

Not much, no. Genetic Algorithms and Neural Networks are very popular in academic circles but have found little use in the game industry. For the most part they’re considered both too unpredictable and too difficult to understand once they are working—it’s tough to tune what you don’t understand.

There are some exceptions…games such as Dogs, Creatures, and Cloak, Dagger, and DNA all use these technologies to some degree. Arguably these are less games than they are toys, however. The Sims is sometimes offered as an example of cutting-edge AI, but really at its heart its true innovation was the idea of "smart terrain" that satisfied "needs" of the various game agents.

There are other dangers in using Genetic Algorithms. It’s appealing to think that one might build a game that learns from the user as it plays, but evolution is essentially a blind search—it’s entirely possible to breed a "dumb" AI. You’ll also have all kinds of problems with your QA and Tech people—try explaining to them that your AI will never play the game the same way each time, and that you can’t necessarily recreate any problems the user might report.

Question #8: How can I control player perception of my AI?

The bottom line is you can’t, really, but you can influence his experience.

As mentioned before, good random choices often receive the benefit of the doubt from the player; he will often attribute intelligence to a random event if it makes some sense. Humans by their nature impose patterns on what they see, so you’ve got basic human nature working for you right off the bat.

When in doubt, a "fuzzy" decision seems more "human" than a "crisp" one. A tank that always attacks infantry over another tank is "crisp"; a tank that selects targets randomly but reasonably will seem much more "realistic" to the player.

Question #9: What languages are people using for their AIs?

C and C++ are pretty much the languages of choice. You can do AI in any language but that’s the reality of the business.

Question #10: How do I keep my State Machines from getting too big?

Combinatorial explosion of state machine options is a big problem and not an easy one to address. You can minimize it a bit by randomizing parts of your state machine and by breaking your machines into smaller "layers" of decisions.

When all else fails, revisit your design. You’ll probably find that you’re using some decision making elements which really aren’t big players and which can be removed with little affect on your AI’s overall performance.

Question #11: Is there any kind of AI "middleware", and is anybody using it?

The short answer is that there are some SDKs available, but nobody is using any of them heavily just yet. A couple of companies are exploring them in limited projects; DirectIA is being used in an RTS called Peacekeepers, for example.

A big issue with AI middleware is the "Not Invented Here" syndrome—few AI developers believe that a tool can help them build what they’ve always known to be a carefully crafted AI for their game.

Part of the problem too is that middleware as a software class is only just gaining acceptance. When AI middleware provides sufficient functionality to be worthwhile, and when game schedules compress to the point that developers will actually consider outside solutions rather than building their own (such as with the physics middleware), AI middleware will probably gain more widespread use.