Intelligence for Changing Worlds: Real-time Generation of AI Data in Dynamic MMO Environments
The emergence of in-game physics and user-generated content is making MMO worlds much more dynamic than in the past. NPCs must now interact with a physically-changing environment, rather than merely navigating through a static world. This dramatically increases the complexity and sophistication required of the AI subsystem and makes some of the current methodologies obsolete. This lecture reviews and clarifies the major problems in handling movement and position planning that arise in such scenes. A new algorithmic solution is presented, as well as useful GPU programming techniques for implementing the solution.
PROBLEM DESCRIPTION
The talk begins by a short survey of the differences between planning in dynamic scenarios and more conservative games. A game-like prototype is used to illustrate key aspects of the problem, as well as to quantify the complexity of AI graph generation in real-time.
CURRENT TECHNIQUES
The talk covers some current techniques for handling dynamic changes, their advantages and drawbacks (e.g. D*, steering, using tiered approach for coarse planning).
PROPOSED SOLUTION
The discussion of the proposed solution includes the following steps:
- Choosing the Right World Representation: Selecting an effective game graph format to represent the game world.
- Coping with Change: Starting with raw geometry (“polygon soup”), fast detection of areas that have changed.
- Building the Graph: Using rendering-like techniques to create an initial (approximate) game graph.
- Fine-tuning the Graph: Correcting problematic locations in the initial graph using collision-based techniques. This includes querying the game or physics engine for “virtual collision tests”: will a particular NPC, in a certain spatial location, facing in a certain direction, and performing a particular NPC action collide with anything?
FASTER IS ALWAYS BETTER: Dealing with computational aspects
A particular challenge posed by dynamic environments is the raw CPU power needed to generate and update the game graph. Fortunately, some techniques requiring a lot of computational power map well on to the GPU. The lecture covers several adaptations of previous work to the problem at hand. An example of these includes creating grid maps. Since the scene changes dramatically in relatively short time, the GPU can be used for the creation and maintenance of a grid map for pathfinding by “rendering” the entire scene from above to a texture which is then read back to main memory. The talk presents the basic idea of how this is done and some of the key steps including:
- Using the rendering “color” for setting weights.
- Performing lightning-fast influence and uncertainty maps by drawing textures.
Intended Audience: AI programmers
Prerequisites: Attendees should have experience with standard game AI programming techniques.
Format: Lecture
Date/Time: Friday, 10:00 AM
Room: Parliament
