Can AI SDKs Help?

Contents

Trends Since Last Year Can AI SDKs Help?

The single biggest topic of discussion at the GDC 2000 roundtables was the feasibility of AI SDKs. There are at least three software development kits currently available to AI developers:

• Mathématiques Appliquées' DirectIA, an agent-based toolkit that uses state machines to build up emergent behaviors.
• Louder Than A Bomb's Spark!, a fuzzy-logic editor intended for AI engine developers.
• The Motion Factory's Motivate, which can provide some fairly sophisticated action/reaction state machine capabilities for animating characters. It was used in Red Orb's Prince of Persia 3D, among others.

Many developers (especially those at the "AI for Beginners" session) were relatively unaware of these toolkits and hence were very interested in their capabilities. It didn't seem, however, that many of the more experienced developers thought these toolkits would be all that useful, though a quick poll did reveal that one or two developers were in the process of evaluating the DirectIA toolkit. Most expressed the opinion that one or more SDKs would come to market that would prove them wrong.

Figure 5: Red Orb's Prince of Persia 3D used The Motion Factory's Motivate SDK

In discussing possible features, most felt that an SDK that provided simple flocking or pathfinding functions might best meet their needs. One developer said he'd like to see some kind of standardized "bot-like" language for AI scripts, though there didn't seem to be any widespread enthusiasm for this idea (probably because of fears it would limit creativity). Also discussed briefly in conjunction with this topic was the matter of what developers would be willing to pay for such an SDK, should a useful one actually be available. Most felt that price was not a particular object; developers today are used to paying (or convincing their bosses to pay) thousands of dollars for toolkits, SDKs, models, and the like. This indicates that if somebody can develop an AI SDK flexible enough to meet the demands of developers, they should be able to pay the rent.

Technologies on the Wane

Visibility Graphs

One of the interesting areas that game AI is beginning to explore is the realm of terrain analysis. Terrain analysis takes the relatively simple task of path-finding across a map to its next logical step, which is to get the AI to recognize the strategic and tactical value of various terrain features such as hills, ridges, choke-points, and so on, and incorporate this knowledge into its planning. One tool that offers much promise for dealing with this task is the visibility graph. Visibility graphs are fairly simple constructs originally developed for the field of robotics motion. They work as follows: Assume you are looking down at a map that has a hill in the center and a pasture with clumps of trees all around it. Let appropriately shaped polygons represent the hill and the trees. The visibility graph for this scene uses the vertices of the polygons for the vertices in the graph, and builds the edges of the graph between the vertices wherever there is a clear (unobstructed) path between the corresponding polygon vertices. The weight of each connecting line equals the distance between the two corresponding polygon vertices. This gives you a simplified map against which you can run a pathfinding algorithm to traverse the map while avoiding the obstacles. Visibility graphs were used in Red Storm Entertainment's Force 21 There are some problems with visibility graphs, however. They only give raw connection information, and paths built using them tend to look a little mechanical. Also, the developer needs to do some additional work to prevent all but the smallest units from colliding with polygon (graph) edges as they move, since the path generated from a visibility graph doesn't take into account unit size at all. Still, they're a straightforward way to break down terrain into simplified areas, and they have uses in pathfinding, setting up ambushes (the unobstructed graph edges are natural ambush points), and terrain generation.

It's become clearer since last year's roundtables that the influence of the more "nontraditional" AI techniques, such as neural networks and genetic algorithms (GAs), is continuing to wane. Whereas in previous years developers had many stories to tell of exploring these and other technologies during their design and development efforts, at this year's sessions there was much more focus on making the more traditional approaches (state machines, rules-based AIs, and so on) work better. The reasons for this varied, but essentially boiled down to variations on the fact that these approaches are better understood and work "well enough." Developers seemed to want to focus much more on how to make them work better and leave exploration of theory to the academic field.

Genetic algorithms have taken a particularly hard hit in the past year. There wasn't a single developer at any of the roundtables that reported using them in any current projects, and most felt that their appeal was overrated. While last year's group had expressed some interest in experimenting with using GAs to help with game tuning, the developers who had tried reported this year that they hadn't found this to be very useful. Nobody could think of much use for GAs outside of the well-known "life simulators" such as the Creatures and Petz series.

The one exception to this, as previously noted, is the continued use of A-Life techniques. From flocking algorithms that help guide unit formations (Force 21, Age of Kings, Homeworld) to object-oriented desire/satisfaction approaches (The Sims), developers are finding that these techniques make their games much more lifelike and "predictably unpredictable" than ever before.

Where We're Headed

Always interesting at the roundtables are the inevitable discussions of where the industry in general, and game AI in particular, is headed. As usual, we got almost as many opinions as there were attendees, but some common trends could be seen emerging down the road.

Everybody thought that game AI would continue to be an important part of most games. The recent advances were unlikely to be lost to a new wave of "gee-whiz" 3D graphics engines, and the continued increase in CPU and 3D card capabilities was only going to continue to give AI developers more horsepower. There was the same feeling as last year that the industry would continue to move slowly away from monolithic and rigid rules-based approaches to more purpose-oriented, flexible AIs built using a variety of approaches. It seems safe to assume that extensible AIs will continue to enjoy some popularity and support among developers, mostly in the first-person shooter arena but also in more sophisticated strategy games.

Figure 6: Relic Entertainment's Homeworld used flocking techniques

Academia and the defense establishment continue to influence the game AI field (see John Laird's "Bridging the Gap Between Developers and Researchers" to be published in Part Two next week), though it sometimes seems that the academic world learns more from game developers than the other way around. For the most part, developers seem to feel that the academic study of AI is interesting but won't really help them ship their product, while researchers from the academic field find the rapid progress of the game industry enviable even if the techniques aren't all that well documented.

There can be no doubt that the game AI field continues to be one of the most innovative areas of game development. We know what works and tools are beginning to appear to help us do our jobs. With CPU constraints essentially eliminated and the possibilities of good game AI now part of the design process, AI developers can look forward to a bright future of innovation and experimentation.

For More Information

Web Sites
Far and away the best place to find out more about any aspect of game AI is the Internet. There are more excellent web sites filled with tutorials, information, sample code, and so on, than anybody could possibly list in one place. Some of the recommended ones include:

www.gameai.com
Steven Woodcock's site, dedicated to all things game-AI-related. Provides links to other AI resources, reviews on AI implementations in games already on the market, and archives of various Usenet threads.

www.gamedev.net
Another excellent site dedicated to all aspects of game development, there is an extensive list of resources and an active discussion group on the topic.

www.red.com/cwr.boids.html
This site remains the single best source for any information about flocking and related A-Life technologies.

www.pcai.com/pcai
PC AI magazine has a marvelous web site crammed with all kinds of useful AI resources. From sample applications to research papers, you can find it here.

http://ai.eecs.umich.edu/people/laird/gamesresearch.html
John E. Laird's site

www.aaai.org
American Association for Artificial Intelligence

Newsgroups
Of course Usenet continues to be a great place to do research on a variety of AI-related topics. The best newsgroups for this purpose remain comp.ai.games, comp.ai, and rec.games.programmers.

Papers
Laird, J. E., and M. van Lent. "Interactive Computer Games: Human-Level AI's Killer Application." Proceedings of the AAAI National Conference on Artificial Intelligence, August 2000.

Laird, J. E. "It Knows What You're Going to Do: Adding Anticipation to a Quakebot." Proceedings of the AAAI 2000 Spring Symposium Series: Artificial Intelligence and Interactive Entertainment, March 2000 (AAAI technical report #SS-00-02).

Books
Unfortunately, there really aren't very many books that discuss game AI. Probably the best comprehensive reference remains:

Russell, Stuart J., and Peter Norvig. Artificial Intelligence: A Modern Approach. Upper Saddle River, N. J.: Prentice Hall, 1995.

Discuss this article in Gamasutra's discussion forums

________________________________________________________