Angel Studios' Midtown Madness 2 for PC and Midnight Club for Playstation 2 are open racing games in which players have complete freedom to drive where they please. Set in "living cities," these games feature interactive entities that include opponents, cops, traffic, and pedestrians. The role of artificial intelligence is to make the behaviors of these high-level entities convincing and immersive: opponents must be competitive but not insurmountable. Cops who spot you breaking the law must diligently try to slow you down or stop you. Vehicles composing ambient traffic must follow all traffic laws while responding to collisions and other unpredictable circumstances. And pedestrians must go about their routine business, until you swerve towards them and provoke them to run for their lives. This article provides a strategy for programmers who are trying to create AI for open city racing games, which is based on the success of Angel Studios' implementation of AI in Midtown Madness 2 and Midnight Club. The following discussion focuses on the autonomous architecture used by each high-level entity in these games. As gameplay progresses, this autonomy allows each entity to decide for itself how it's going to react to its immediate circumstances. This approach has the benefit of creating lifelike behaviors along with some that were never intended, but add to gameplay in surprising ways.

AI Map: Roads, Intersections, and Open Areas

At the highest level, a city is divided into three primary components for the AI map: roads, intersections, and open areas (see Figure 1). Most of this AI map is composed of roads (line segments) that connect intersections. For our purposes, an intersection is defined as a 2D area in which various roads join. Shortcuts are just like roads, except they are overlaid on top of the three main component types. Shortcuts are used to help the opponents navigate through the various open areas, which by definition have no visible roads or intersections. Each of these physical objects is reflected in a software object.

	Figure 1. The AI map elements appear as green and blue line segments for roads and sidewalks, 2D areas for intersections, and additional line segments for shortcuts across open areas. [Expand Image]

The road object contains all the data representing a street, in terms of lists of 3D vertices. The main definition of the road includes the left/right boundary data, the road's centerline, and orientation vectors defined for each vertex in the definition. Other important road data includes the traffic lane definitions, the pedestrian sidewalk definition, road segment lengths, and lane width data. A minimum of four 3D vertices are used to define a road, and each list of vertices (for example, center vertices, boundary vertices, and so on) has the same number of vertices.

The intersection object contains a pointer to each connected shortcut and road segment. At initialization, these pointers are sorted in clockwise order. The sorting is necessary for helping the ambient traffic decide which is the correct road to turn onto when traversing an intersection. The intersection object also contains a pointer to a "traffic light set" object, which, as you might guess, is responsible for controlling the light's sequence between green and red. Other important tasks for this object include obstacle management and stop-sign control.

Big-city solutions: leveraging the City Tool and GenBAI Tool. Angel's method for creating extremely large cities uses a very sophisticated in-house tool called the City Tool. Not only does this tool create the physical representation of the city, but it also produces the raw data necessary for the AI to work. The City Tool allows the regeneration of the city database on a daily basis. Hence, the city can be customized very quickly to accommodate new gameplay elements that are discovered in prototyping, and to help resolve any issues that may emerge with the AI algorithms.

The GenBAI Tool is a separate tool that processes the raw data generated from the City Tool into the format that the run-time code needs. Other essential tasks that this GenBAI Tool performs include the creation of the ambient and pedestrian population bubbles and the correlation of cull rooms (discrete regions of the city) to the components of the road map.

Based on the available AI performance budget and the immense size of the cities, it's impossible to simulate an entire city at once. The solution is to define a "bubble" that contains a list of all the road components on the city map that are visible from each cull room in the city, for the purpose of culling the simulation of traffic and pedestrians beyond a certain distance. This collection of road components essentially becomes the bubbles for ambient traffic and pedestrians.

The last function of the GenBAI tool is to create a binary version of the data that allows for superfast load times, because binary data can be directly mapped into the structures.

Data files: setting up races. The AI for each race event in the game is defined using one of two files: the city-based AI map data file or the race-based AI map data file. The city file contains defaults to use for all the necessary AI settings at a city level. Each race event in the city includes a race-based AI map data file. This race file contains replacement values to use instead of the city values. This approach turns out to be a powerful design feature, because it allows the game designer to set defaults at a city level, and then easily override these values with new settings for each race.

Some examples of what is defined in these files are the number and definition of the race's opponents, cops, and hook men. Also defined here are the models for the pedestrians and ambient vehicles to use for a specific race event. Finally, exceptions to the road data can be included to change the population fill density and speed limits.