Notes from the “AI for Dummies” Session

AI Roundtable Moderator’s Report

2003 Game Developer’s Conference, March 6 - 8

Steven Woodcock

NoSpam_ferretman@gameai.com

Background

For seven years I have had the honor of moderating a series of AI roundtables at the Game Developer’s Conference with fellow developers Neil Kirby (Lucent Technologies) and Eric Dybsand (Glacier Edge Technologies). These roundtables began when the three of us became extremely frustrated at the 1996 GDC as we found ourselves shut out of AI session after AI session. The sessions that we could get into were packed to standing room only capacity and were just plain uncomfortable, often too noisy with just sheer mass to even be al that useful. We felt that there seemed to be a crying need for more AI sessions and so we submitted a proposal to the GDC folks for a series of three simultaneous roundtables over each of the three days of the conference. The idea was that with these sessions we would both accommodate the massive numbers of developers who seemed to want to talk about the topic and be able to focus the sessions on those problems that developers were facing in their day to day efforts. GDC agreed, and the GDC AI Roundtables were born.

We focused the 2002 sessions on essentially the same topics as we did with the 2001 sessions, and tried to follow the same format since that seemed successful. Our Day One sessions focused on general AI topics, flowing from topic to topic as the attendees wished. Our Day Two roundtables covered specific areas of game AI—my session was focused on role-playing and online games, Eric talked about real- and turn-based strategy games, and Neil covered first person shooters. The breakout of specific game AI topics was something we’d done at the request of various attendees who often had questions or comments specific to a current project which might otherwise not come up in the more general sessions.

Day Three used a format that we’ve found fairly successful in the past, combining the three individual roundtables into a single session that we’ve dubbed "AI for Newbies". In this session we tried to answer the questions of developers new to the field of game AI who often didn’t know where to start. Many more experienced AI developers attended and helped us in answering questions and providing examples of why a particular technology or problem was good or bad based on their real world experiences.

Almost embarrassingly the sessions seemed to go wonderfully. There was an excellent "give and take" flow to the discussions and it seemed as if developers were eager to explore what others were doing. What follows are notes from the sessions that I moderated. Eric and Neil’s moderators reports can be found online wherever the reader found this report.

Thursday, March 6th

My first session began quickly, starting with 28 people and then rapidly filling up to the room’s capacity of 40. Attendees came from across the spectrum of games and experience and included at least three researchers from the academic field. There was also at least one AI middleware vendor present. Three quarters of the attendees were actively working on a current project, with two developers noting that they were building an in-house AI engine for future projects.

I tried to kick off the session with a basic poll regarding the resources developers had for game AI and the number of developers they tended to have on each project, but this was quickly changed to a discussion on CPU resources in general. Astonishingly every PC developer in attendance said that they had "enough CPU to do the job"….nobody felt particularly constrained anymore. (This did not hold for PS2 and X-Box developers; to them framerate was king and all else was secondary.) Estimates regarding how much CPU developers actually used varied all over the map (see chart below), with a fair number reporting that they got anywhere from 10 to 15%. Most developers said that they sized their AI’s CPU usage based on available resources, using more when they needed it or when they found (through testing) that they were on a faster machine.

Average CPU Utilization	Number of Attendees
1 - 5%	2
5 – 10%	4
10 - 15%	7
15 – 40%	3
50%	3
5 – 60% (varied by game need)	12
100% (turned based games)	2
Didn’t Know	4

Everybody reported that they had plenty of programmers dedicated to working game AI, though not everybody could give a hard number:

Number of AI Developers	Number of Attendees
1	8
1 1/2	8
2	6
3	2

The numbers were interesting though they didn’t spark much discussion. They’re up slightly from previous years but nothing terribly significant. As usual the turn-based strategy developers noted that they had both more CPU (100%) and more dedicated developers (anywhere from 1 to 3) than other developers did. Interestingly enough, one turn-based team said that they were only building a turn-based game because their team was small and none of them really understood real-time requirements well.

The roundtable quickly moved on to cover a variety of issues:

GDC Sessions – I opened with a question as to why the number of AI-related sessions at the 2003 GDC were down—did anybody have an opinion? Generally nobody did. Some thought that perhaps there had just been fewer submissions in general this time around, while others thought that the layoffs that that hit the industry had had an effect.

Collision Detection – One developer asked if others were having problems handling collision detection and a surprising number agreed. This was of particular interest to me since historically collision detection hasn’t always been considered a part of game AI. While most developers still didn’t have to deal with collision detection a surprising number of attendees (seven) said that it was indeed part of their job. These developers noted that they were spending up to 2/3 of their AI budget on collision detection of one kind or another, split between line-of-sight checks (for things like stealthy movement) and true collision and/or avoiding same.

Knowledge Resources – Developers in general seemed to have a much better handle on where to gather information than in previous years. 80% noted that they had used something that they’d found in the various Game Programming Gems and AI Wisdom books (this made me happy) and everybody had their favorite web site.

Pathfinding – This seems to crop up every year and this session did not disappoint. As before, developers pretty much considered the basics of the issue solved and were only interested in how pathfinding could be done more efficiently (most games use up to 50% of their AI budget on pathfinding). Most seemed to have tried to approach what inefficiencies they could by breaking out their basic pathfinding functionality into its own "engine" that ran in parallel with the AI engine itself. This allowed that thread to constantly be evaluating paths and answering the needs of various game agents, making use of whatever "spare" CPU it could. Most agreed that it was otherwise only interesting in the context of AI middleware and noted that this might provide middleware with their "killer app".

Emergent Behavior – Everybody who was working any kind of game with multiple agents thought that emergent behavior was a wonderful thing to have, but difficult to test if it was very complex. Nearly everybody was using the example of The Sims to try to build "smart terrain" or "smart objects" into their game, thus encapsulating behavior into smaller chunks (and incidentally making expansion easier). The example of the AI behind the Battle of Helms Deep in The Return of the King was cited as the kind of thing developers sometimes ran into. (In the session covering the movie the animators revealed that most of the battle used AI agents whose behavior was computer controlled. They had a very simple AI to essentially attack the nearest enemy in their field of view. However, when the developers "turned them on" many of the Orcs and Elves on the fringes of the battle didn’t see any enemies, so they ran away into the woods. A simple change to have them turn around if they didn’t see anybody was added, and all was well.) Another developer noted that he used a training ‘bot to test his AIs, but every modification he made to his AI required changes to the test ‘bot as well.

Testing – The discussion of emergent behavior led fairly quickly into a discussion of testing in general. Everybody was looking for ways to do this more efficiently and reliably, since games are now growing so complex that it was nearly impossible to test all possibilities. On problem developers reported is understanding their creation--while an AI was clearly doing something it wasn’t always clear why an AI was doing what it was doing…and that made fixing (if that was called for) very difficult. One developer (of a first-person shooter) noted that he was greatly assisted by simply building what he called a "test level" in which he could run his agents through new situations as he developed them. Another used a playback system to generate situations and observe the results. At least one developer said he just cheated if he ran into any problems, and this elicited quite a laugh from around the room.

Prototyping – Most developers were very happy that they were being included much earlier in the design process, though to some extent this led to unrealistic expectations on the part of the producer (who expected to see things moving and fighting before the basic game engine was done). Reusing game engines from project to project was helping to mitigate this a bit, but that didn’t help the new projects much.

Languages/Scripting – Over 80% of developers were using some kind of scripting language. While virtually all developers were writing their tools in c or C++, a few were investigating using C# or Python for their basic game engine. Only a few were leaving scripting hooks in the AI engine to allow users to build their own AI mods however; most felt it just wasn’t worth the effort. The biggest exception to this was the first-person shooter genre, where ‘bot programming has become an expected feature for any major game.

Learning – This topic was discussed to some degree during the 2002 sessions but there wasn’t much optimism at the time. This year there seemed to be more interest, particularly in light of the AI successes shown in Black and White. The role-playing developers in particular felt that they could build their AIs to study the player’s actions and learn to emulate them or craft their conversations based on the player’s demonstrated knowledge.

One developer was particularly interested in this topic since he was trying to build a learning system for a fighting game; he got several suggestions from others about things to try (neural networks,, changing the weights on FSMs based on player actions, feedback ala Black and White). He asked if there were any middleware packages that might provide such functionality. As it turned out this provided a natural opening for the final subject of discussion.

Middleware – There was quite a bit of discussion about the potential of AI middleware towards the end of the session, and the vendor present really perked up when we began to cover it. A quick show of hands indicated that nobody present was using or planning to use any of the middleware packages available. There were a variety of reasons given, which broke down into two or three fundamental objections:

Control – Most developers felt that any AI middleware package (or at least the ones they were familiar with) wouldn’t give them the kind of basic control over unit AI that they needed to have. There was broad discussion over whether a defined API or an API that allowed developer extensions would be more useful; everybody who had an opinion thought they ought to be able to extend or modify the API as needed.

Design Issues – Many developers also thought that any AI middleware would inevitably drive the design of their game and that was essentially unacceptable. Examples were cited of how there had to be tradeoffs between design of the game proper and the design of its AI, and developers overall believed that any middleware had the potential to drive them in directions they didn’t want to go. (This is in keeping with the findings from both last year and this, showing that many developers are reusing or extending existing AI engines from game project to game project.)

Functionality – Fundamentally, most developers just didn’t think that the existing middleware provided sufficient functionality for their needs. Without knowing exactly what they wanted, they felt that existing packages just didn’t provide enough power and features to make them worthwhile. To some extent this is similar to what developers felt at the dawn of the 3D APIs; many were far more comfortable with "rolling their own" than depending on APIs that (at the time) weren’t very well known.

The final portion of the AI middleware discussion flowed naturally from talking about functionality to talking about what the middleware vendors could do to make their products more appealing. Some developers felt that the middleware vendors needed to build in features that developers were having trouble with (such as learning). Others thought that their best contribution would be to help standardize AI interfaces, or to provide pathfinding functionality that was faster and more efficient than anything the developers themselves could come up with. (The vendor took some serious notes at this point, I thought.)

The session ran about 10 minutes long. There were numerous side topics but it was difficult for this moderator to jot it all down while trying to keep the discussion flowing. Many thanks to Dave Mark (InnocuousFox on GameDev.Net) for his notes on this session; they were very helpful.

Friday, March 7th

The sessions on the second day focused in on specific areas of game AI. My session covered role-playing and online games.

We had only 28 people attending (the second day is typically down) but we started early. We started quickly and interestingly enough the roundtable leapt to themes discussed the day before:

Learning – Developers were keenly interested in trying to build AIs that might learn, both from the player and the environment around them. (Developers of role-playing games were more interested in this than those building online games, since most online developers seemed to feel that the NPCs were mostly "window dressing", existing to give the players something to do when they weren’t talking to each other.)

All agreed that this was a difficult proposition though there had been some advances. The example of Black and White was brought up again and there was discussion over whether or not the "slap/praise" paradigm in that game could be generalized to other games. Most developers thought it could through conversation trees, though they didn’t want the choices to be blindingly obvious (as some games have been). Developers thought that this kind of interaction would make games far more interesting for players, as well as providing more realistic environments. This in turn got the interest of the online game folks, since they’re always interested in making the playing environment more interactive and realistic.

Resources – The online game developers were quick to offer up the next major topic, that being their utter lack of resources. They were facing problems very different from those discussed in the previous day’s session, since they often had to provide AI for hundreds or thousands of NPCs (creatures, villagers, companions) across a dozen servers, all in realtime, with no more communication than the average 28.8K modem. They were dying for any techniques that might help them do things more efficiently.

There were a number of techniques suggested by members of the roundtable, mostly modeled on experiences with real-time strategy games and first-person shooters. These included:

Running the AI handler in a separate thread so it could be more easily managed;
Prioritizing the AI to give priority to those agents the player was directly interacting with in some fashion;
Using some kind of Level of Detail (LoD) AI to simply agents that were "out of sight" while making sure they didn’t do anything illegal or stupid.

These two topics ran heavily throughout the hour and took up virtually all of the available time. Towards the end of the session we had some brief discussion of AI middleware and its possibilities, but there were no issues that hadn’t been brought up in the previous day’s session.

Saturday, March 8th

As mentioned earlier 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. There were 28 attendees at the session, somewhat fewer than the year before but in keeping with the general numbers from the other roundtables.

As usual, Eric and Neil moderated while I took notes on the whiteboard (much 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: I heard you say "pathfinding was solved" in the first session. What did you mean by that?

Basically we meant that this is something that pretty much every game developer has worked through and agreed that A* and variants are the best answer for relatively static environments. There are always individual games with different needs, but A* is breathtakingly capable of handling a huge number of possible game designs.

For more dynamic environments there are several possibilities. One is a more robust version of A* that has hooks into your engine to handle changes in terrain, obstacles, etc. The other is to implement Dynamic A* (known as D*), which automatically handles path re-planning as conditions change. What you want to use really depends on your game and your needs.

Question #2: What are other possible pathfinding approaches?

There are several solutions that various developers use depending on their game. Putting directional cues into the terrain is one possibility, and is often done in conjunction with A* just to help an AI get around a difficult problem without much CPU expense. Another is to use the basic steering behaviors (a subset of flocking behaviors) set forth by Craig Reynolds.

Question #3: How can I handle pathfinding over very large areas?

Do it a piece at a time. Break up the terrain into really big chunks and use A* to build a path from one to the other. You can then hand off just these areas to the pathfinding for a finer solution. In the meantime you can start your unit moving and it will have the effect of slowly refining its path, rather like most people moving across a large area.

Question #4: What do most RPGs use for AI?

Scripted responses tied with scripted missions. There hasn’t been much advancement of RPG AIs over the years, mostly because it’s very hard to write a free form novel.

Question #5: What are some big areas of interest in future AI?

Developers in general are keen to come up with AIs that are cooperative, that can learn, and which can handle reputations. Learning AIs in particular are a of great interest now that developers have seen what has been done with games like Black and White.

Question #6: What are some examples of games that provide open-ended environments with changing storylines?

These have come and gone over the years but there are some. Grand Theft Auto, Freelancer, and BC3K all provide relatively open-ended universes in which one can ignore the storyline as much as one wishes. Many of them don’t really change the storyline in response to the player’s activities as much as they either "make it ignorable" or "color it somewhat".

Note that these kinds of games can be more difficult for your QA to test, and you could end up with a lot of wasted development if a player never sees your alternate storylines and extra content. This will annoy your producer no end.

Question #7: Can you build an AI to dynamically generate content?

Well, it’s theoretically possible but certainly not easy. Nobody has really done it yet, though The Sims dynamically generates the "speech" of a given Sim based on what he’s doing. Two big problems are how you test this kind of thing, and figuring out whether or not the player actually likes the content you’re generating.

There are some interesting potential tools in the old MUD ‘bots since they can respond dynamically to situations as they occur. Somebody has to write all the responses though, and this kind of database can be difficult to localize.

Question #8: What do I need to help sell an AI idea to my producer?

Show him how it will help the player’s "suspension of disbelief". A designer-driven tool that can easily show the possibilities would also be helpful but that takes time and resources to create.

Question #9: How can I make a role-playing or online game more interesting?

It’s very easy to make these games seem repetitive or boring. The online games are particularly hard since everybody wants to be the hero. Side quests help a lot, as do drafting other players to become content creators (dungeon masters).

It also helps to give players the ability to build their own game mods and/or adventures.

Question #10: Is anybody using any kind of AI technologies like Neural Networks or Genetic Algorithms?

Short answer: No.

Longer answer: NNs and GAs cost $$$ both in testing and development costs. You probably won’t understand how they work, you can’t guarantee reproducibility (just like with biological life), and you won’t know how to change them to do something the producer is demanding.

Question #11: How can we make AIs better?

Lots of ways. You must remember that you’re not building an AI to beat the player, you’re building an AI to make an enjoyable opponent.

Find a game with an AI that you admire, and try to emulate it. FPS games are starting to make greater use of squad-based behavior and that can look very good. Real-time strategy games are tying specific goals to levels, and that gives you something to focus the AI and the player on. HALO has a wonderful mission-based structure that there’s much to learn from.

Give NPCs their own agendas, and have them act accordingly. Better yet try to let them negotiate with the players to satisfy multiple goals (but stay away from the "Bring me the Golden Thingie and I’ll give you the Silver Whatnot" nonsense of many RPGs).

Cheat smarter. Give enemies more information if that’s what it takes.

Above all, do what makes the game more fun.