|
|
 |
 |
 | | | | |
 |
|||
 |
||||||
          |
 |
 |
||||
|
Technologies in the Limelight Exploring the AI technologies used by other developers in games has been a popular topic at past CGDC roundtables. Developers are increasingly turning to military and academic sources for new ideas and technologies (and those disciplines are turning their eyes on the game industry as well). Discussions with developers at the roundtables and at demo booths in the exposition hall yielded some interesting information about what technologies are in use today. Rules-Based AI. Rules-based approaches to game AI, led by the Finite State Machine (FSM) and the Fuzzy State Machine (FuSM), continue to lead the pack as the most popular technologies among AI developers. The reasons for this remain the same:
While every game shipped in the past year makes use of rules-based AIs to one degree or another, there were a couple that seemed to stand out in developer's minds as particularly interesting implementations. One of these was Epic Games' Unreal, a first-person 3D shooter that provided some excellent examples of the complexity of behaviors available using FSMs and FuSMs. Taking the advances of Valve Software's Half-Life one step further, the AI in Unreal also makes heavy use of FSMs to control the behavior of the player's opponents to an often amazingly realistic degree. At higher levels, there is evidence of considerable intelligence on the part of monsters, which run away, hide when wounded, summon reinforcements, and can even lead the player into ambushes when possible. Herds of miscellaneous critters scuttle about the game levels using a fairly nice flocking algorithm, adding to the overall effect of the living world that the player has been thrust. All of this was done by the developers by layering FSMs, which were built on top of an extensible scripting system called UnrealScript (more on that below).
A game making heavy use of FSMs is Activision's Call to Power. Billed as using "over-arching potentialities" to guide its strategic thinking, Call to Power's AI actually makes heavy use of cascaded FuSMs throughout its design. The primary reason for this was straightforward enough, in that a number of different civilization personalities had to be accommodated in the design in order to reflect the differing governmental and militaristic bents of the various civilizations portrayed in the game. If the developers had used a strictly rules-based design to accomplish this, there would have been a considerable amount of special code to handle each civilization. Using FuSM technology allowed the developers to build on core AI engine in which its various decision-making thresholds could be modified by each civilization's unique personality and philosophical leanings. This approach allows the game to accommodate a variety of different playing styles and technological research trees without bogging down the design in too many special cases. Every decision that a given civilization can make is based partly on the strategic situation, partly on that civilization's personality, and on the decisions it had made previously. Anytime something isn't terribly obvious, or not covered by a specific rule of some kind, the AI uses fuzzy logic (in the form of the FuSMs) to make a decision. This, in turn, results in an AI whose decisions are internally consistent and plausible, yet still leaves the chance for a surprise or two. Extensible AIs. A number of recently-released games have featured Extensible AIs (ExAIs) in one form or another, building on a trend that began a couple of years ago with the release of Quake. The success of that game's QuakeC scripting language, which permitted players to build their own computer opponents, assistants, and companions (known as "bots") and trade them over the web, has inspired a number of other developers to build similar capabilities into their releases. Several developers at the 1999 roundtables mentioned that they were at least exploring the possibility of ExAIs in their projects. To date, most ExAIs have cropped up in the first-person 3D shooter genre. Last year's Unreal and Half-Life provided players with interfaces through which they could devise their own rules for computer opponents. However, there were differences in implementation. Unreal went with a general "directive-like" interface through which AI behavior is controlled using relatively simple commands, such as "Move forward until you see an enemy, then throw grenades." Half-Life used a more traditional "programming-like" approach that somewhat resembles Perl or JavaScript. Both approaches have proven extremely popular with players and led to legions of users trading scripts and bots online for games based on both engines. More recently, however, ExAI technology has been finding its way into other genres of games. Interplay's Baldur's Gate, a role-playing game (RPG) based in part on the Advanced Dungeons & Dragons paper RPG, uses scripts to control non-player characters (NPCs) within the game — including those that can be in the player's own party. These scripts allow players to specify the basic reactions of their NPCs to a variety of combat situations, permitting them to adjust behavior either to accommodate a player's particular style (making mages more cautious than they are by default, for example) or to create entirely new NPC classes. Several aficionados of the game have already seized on this last capability to develop a number of NPC classes not present in the original game, creating thieves, warrior-mage combinations, elven archers, and so on.
The AI scripts themselves are heavily rules-based in the Half-Life vein, operating in a strictly linear fashion from top to bottom within the script. Thus, rules "later" in a given script might or might not ever "fire" depending on the circumstances of the game and whether or not the player overrides any particular NPC action (an option always available). Responses can be weighted to control their probability of occurrence, though there is no provision for being able to modify the internals of the game's AI engine itself. There are some pre-defined, basic strategies available for the player-cum-AI-designer to use, and, of course, the existing NPC scripts are readily available as examples of what can be done. Documentation shipping with the game is necessarily sparse (probably to help avoid too many support hassles), but a few web sites have sprung up on which tinkerers can exchange information. Listing 1 shows a snippet of a script, which was kindly provided by Baldur's Gate enthusiast Sean Carley for my game AI web page. It's from a warrior AI he developed, and as you can see, the scripting system is very English-like in syntax.
However, adding ExAI capabilities to a game isn't at all easy, and most developers at the 1999 AI roundtables agreed with the opinion from previous years that the trend wasn't likely to become widespread. There are significant design considerations that have to be worked out if one desires to add the ability for players to modify a game AI to suit their tastes, not to mention the problem of after-sale support. Developers have to decide how they're going to provide these hooks (code interface? scripts?), how they're going to document them (in the manual? online? HTML on the CD? not at all?), and just how far they should go to bullet-proof the whole interface in the first place. (Whose fault is it if some player distributes an AI script that erases somebody's hard drive?) These very issues were, in part, the reason why Activision somewhat de-emphasized its much-touted interface to the AI engine in Call to Power. Originally, the development team had planned to provide full and total access to Call to Power's AI in such a fashion that players could have hypothetically replaced the game's AI with their own. The AI is completely encapsulated within a .DLL file, and it was planned to have players access it via header files that would have provided an interface to many of the internal functions (though the source itself was not going to have been released to the public). Users would have been completely on their own while using this interface — the support issues could have been nightmarish otherwise — and this approach would have allowed anybody who had the time and patience to replace Call to Power's AI completely with their own — a first in the industry.
Unfortunately for budding developers, the pressure of shipping on time and the design complications encountered while trying to implement this rather unique feature made that goal unrealistic. Activision was forced to drop that part of the plan (oddly though, you can still find a .MAP file listing the various function interfaces on the CD). Still, a number of extensible features made their way into the game, enough so that, although Activision isn't advertising the fact much, a number of players have begun making variations and trading them online. Players can modify unit attributes (all maintained in flat text files) and have access to the fuzzy logic rules sets used by the AI to set priorities for the strategic-level AI. This allows you to create new unit types and civilizations, in much the same fashion as UnrealScript permits new bots. In a similar vein, Microsoft's Age of Empires provides much the same level of customization of units and civilizations, though emphasis is more on customization of the various personalities of each civilization type than on actual modification of their rules sets. Learning and Strategic Thinking. Another trend that bubbled to the surface at the 1999 AI roundtables was experimentation with learning AIs in various games. While it was definitely a widely-held opinion that most games featuring learning AIs haven't really done a very good job of delivering, several developers had high hopes that they'd be able to incorporate some level of learning into their next round of releases. Developers seem to be exploring a number of different approaches to simulate learning, most involve comparing the current strategic or tactical situation to similar past situations. Mythos Games, in their recently released Magic & Mayhem, noted that they were doing localized assault planning by continually building a data file that describes how attacks had fared historically in previous scenarios. A proposed attack is compared to this database, and if it succeeded most of the time, it's actually carried out (the threshold is determined in part randomly and in part by the personality of the AI player). A "winnowing" algorithm discards "old" lessons so the learning file doesn't become too large. The developer reported that this approach resulted in an AI that gradually tailored itself to the player's style of play — a feature that is certainly something of a Holy Grail to AI developers.
Interestingly enough, some developers (roughly 20 percent of attendees) were experimenting with Artificial Neural Networks (ANNs) as a learning technology. ANNs have cropped up often in the AI roundtables as a potential solution to the learning-AI problem, but there are some interesting challenges in using the technology in games that have discouraged most developers to date. Historically, using ANNs within a game presents the developer with two particularly thorny problems: First, it can be very difficult to identify meaningful inputs and match them to outputs that make sense within the context of the game; and second, most ANNs learn through a technique called "supervised learning," which requires constant developer feedback. While it is possible to build ANNs that can learn unsupervised, there's no guarantee that they won't "go stupid" and become completely helpless players. Most developers are trying to avoid these problems by training their ANNs exclusively during the development phase, then freezing them before the game actually ships. This allows them to let the AIs learn while playing against the development team and play testers without the risk that a shipping AI might wander off into some Rain Man universe of perception. The downside to this, of course, is that the game doesn't learn anything from the player, and so the whole effort boils down to an automated form of AI tuning (ultimately similar to using genetic algorithm to try to tune various game AI parameters). A developer of an upcoming sports game announced that he was working on a way to integrate unsupervised learning ANNs into his game, although he planned to include an option to reset the AI should the player feel it had become feeble-minded (or too strong a player, as the case may be). One big problem with learning AIs that caused much amused discussion at the roundtables was the fact that a learning AI is, by definition, unpredictable. This leads to huge problems when it comes time to do quality assurance testing on your game — how can anything be tested reliably if it behaves differently from game to game? How can a developer fix a bug if it's impossible to recreate the conditions that led to a certain behavior? On a closely related vein, several developers noted that they were attempting to find AI technologies that would do a better job at strategic-level thinking and planning. To date, most strategy games do an adequate job at the tactical level — identifying cities or units to attack, taking advantage of unprotected assets, and so on — but do a lousy job at developing and implementing grand strategy. The problem, from a programmer's point of view, is basically one of optimization. Most war games (ignoring for the moment most first-person shooters and RPGs, since they are primarily tactical in the extreme), whether real-time strategy or turn-based, do a much better job of optimizing small, tactical situations over larger, strategic ones. This leads to AIs that fight battles well but still manage to lose the war, often because they overlook solutions glaringly obvious to the human player. A large part of this situation is simply the result of the historical inclination of developers to build AIs at the unit level; for example, in a Civil War game, a cavalry unit might decide to attack an artillery unit without the presence of any other support. This in turn leads to an AI that often overlooks obvious attacks in favor of frittering away its forces. Adding in an ability for a unit to call for help balances things out somewhat, but that's still a far cry from strategic-level thinking. Additionally, there's the problem that strategic-level planning may be very good for the war effort overall, but very bad for the individual unit. One example of this might be a brigade ordered to hold a vital mountain pass in the face of overwhelming enemy attack — the war might be won because the delaying action bought the time necessary to get reinforcements to the area, but the unit itself isn't likely to survive. An AI built to handle only unit-level thinking is going to have a hard time making this kind of trade-off. Chess game AIs are perhaps the one exception to this rule, but they're cheating, since most chess programs draw upon databases of thousands of games and simply pick the highest-scoring move available at that moment. Many developers present felt that the time had come to redress this imbalance and were looking to a number of AI-related technologies for help. Some were building on the same techniques used for learning algorithms by using databases of previously-successful moves to develop plans for similar future moves. Others were looking at tools such as Influence Maps (see sidebar "Influence Maps in a Nutshell") to provide ways for their AIs to "see" the grand strategic picture. A few were hoping simply to solve the problem the same way most chess programs do, which is to build large databases of opening strategic moves based on feedback from play testers and the development team.
Interestingly enough, a vocal minority of developers felt the move towards developing better strategic AIs was primarily a waste of time, particularly in games in which players can't easily see the other side's forces. The theory they put forth was that if the player can't see what the computer is doing, why waste time on elaborate strategic AIs in the first place? A few well-placed but thoroughly plausible unit placements (via judicious cheating on the part of the AI) would go a long way towards providing the player with an enjoyable gaming experience. Many of this group felt that the mere appearance of a tank deep behind enemy lines would be ascribed a meaning by the player if the attack came at a particularly vulnerable time. They based this opinion on the reams of e-mail they had received from players that raved about the intelligence of the AIs in their games, when the AI was, in fact, cheating outrageously just to keep up. Pathfinding. Pathfinding is a perennial favorite topic at the roundtables, but most developers this year were far more interested in finding ways to solve unusual pathfinding situations than in learning "how to." The A* algorithm (for more details, see Bryan Stout's excellent article, "Smart Moves: Intelligent Pathfinding," Game Developer, October/November 1996) has become the de facto solution to this problem for one very simple reason: It works, and it works well. A* has the added benefit of scaling well into newer games that feature 3D terrain, and it requires few tweaks and modifications. The 3D pathfinding issues presented by the latest generations of first-person 3D shooters were generally felt to be nowhere near the problem most developers were afraid it might be. The early implementations of A* for 2D games had been adapted easily by most developers for the 3D environment, with most developers coming up with variations of the same solution of overlaying a system of nodes within the 3D environment against which paths were found. Some games generate the nodal network when the game map is loaded, while others simply load a pre-defined network as a part of the map data itself. At least one upcoming first-person-shooter style game, The War In Heaven from Eternal Warriors, features an AI that uses a pre-defined node map for its basic pathfinding, but goes one better by dynamically generating new nodes for finer control based on the tactical situation.
Developers at the roundtables were very interested in exploring ways to handle special case pathfinding problems. Identifying and dealing with highly-restrictive terrain (such as bridges or mountain passes) was a hot topic, since these terrain types can lead to traffic jams that make an AI look extremely stupid to the player. Most developers simply marked these terrain features by hand in some fashion in order to make them easy for the AI to identify — although this greatly complicated things when the AI had to deal with randomly generated maps. Many developers said that they solved the problem in part by assigning a special AI agent to play traffic cop, thus side-stepping the issue of bogging down individual unit AIs with the details of crossing a bridge politely. Another problem of keen interest to developers was how to handle the issue of changing terrain gracefully. One of the failings of the A* algorithm is that it assumes the terrain over which it has calculated a path doesn't change — this is a bad side effect should the bridge you were planning to cross get blown up by an artillery round. To solve this problem, some developers were using D*, a dynamic A* variant tuned to handle changeable terrain, but none were happy with it due to the CPU hit required to recalculate paths. Others simply ignored the change until the unit in question reached the point where it couldn't move, but this approach leads to behavior that most players find objectionable. A few confessed that they didn't bother trying to fix it — if a unit got stuck, they just jumped it a few squares to get it going again. |
|
|
Features
