AI Madness: Using AI to Bring Open-City Racing to Life
Simulating Vehicles with Full Physics
The full physics simulation object, VehiclePhysics, is a base class with the logic for navigating the city. The different entities in the city are derived from this base class, including the RouteRacer object (some of the opponents) and the PoliceOfficer object (cops). These child classes supply the additional logic necessary for performing higher-level behaviors. We use the term "full-physics vehicles" because the car being controlled for this category behaves within the laws of physics. These cars have code for simulating the engine, transmission, and wheels, and are controlled by setting values for steering, brake, and throttle. Additionally, the VehiclePhysics class contains two key public methods, RegisterRoute and DriveRoute.
Registering a route. The first thing that the navigation algorithm needs is a route. The route can either be created dynamically in real time or defined in a file as a list of intersection IDs. The real-time method always returns the shortest route. The file method is created by the Race Editor, another proprietary in-house tool that allows the game designer to look down on the city in 2D and select the intersections that make up the route. The game designer can thereby create very specific routes for opponents. Also, the file method eliminates the need for some of the AI entities to calculate their routes in real time, which in turn saves processing time.
Planning the route. Once a route to a final destination has been specified, a little bit more detailed planning is needed for handling immediate situations. We used a road cache for this purpose, which stores the most immediate three roads the vehicle is on or needs to drive down next (see Figure 6).
![]() |
|
![]() | ||
![]() | ||||
![]() |
Figure 6. The route is defined by the roads connecting
intersections 1 to 5, in order. Vehicle A is on road 2-3, which is
the "hint road." Vehicle B has accidentally been knocked onto road
6-2. The immediate target is intersection 3 for both vehicles. Thus,
Vehicle A's cache consists of roads 2-3, 3-4, and 4-5. Vehicle B's
cache consists of roads 6-2, 2-3, and
3-4. |
At any given moment, the vehicle knows the next intersection it is trying to get to (the immediate target), so the vehicle can identify the road connecting this target intersection with the intersection immediately before the target. If the vehicle is already on this "hint road," then the cache is filled with the hint road and the next two roads in the route.
If the vehicle isn't on the hint road, it has gotten knocked off course. In this situation, the vehicle looks at all the roads that connect with the intersection immediately before the target. If the vehicle is on one of these roads, then the cache is filled with this road and the next two roads the vehicle needs to take in order to get back on track. If the vehicle isn't on any of these roads, then it dynamically plots a new route to the target intersection.
Determining multiple routes. If there are no ambient vehicles in the city, then there is only one route necessary to give to an opponent (the computer-controlled player, or CCP), the best route. In general, however, there is ambient traffic everywhere that must be avoided if the CCP is to remain competitive. The choice then becomes which path to pick to avoid the obstacles. At any given moment, this choice comes down to going left or right to avoid an upcoming obstacle. As the CCP plans ahead, it determines two additional routes for each and every obstacle, until it reaches the required planning distance. This process produces a tree of routes to choose from (see Figure 7).
![]() |
|
![]() | ||
![]() | ||||
![]() |
Figure 7. The purple lines on the road show the tree of
possible routes that this opponent vehicle is considering. The
orange line shows the best route -- which is typically the one that
isn't blocked, stays on the road, and goes as straight as
possible. |
Choosing the best route. When all the possible routes have been enumerated, the best route for the CCP can be determined. Sometimes one or more of the routes will take the vehicle onto the sidewalk. Taking the sidewalk is a negative, so these routes are less attractive than those which stay on the road. Also, some routes will become completely blocked, with no way around the obstacles present, making those less attractive as well. The last criterion is minimizing the amount of turning required to drive a path. Taking all these criteria into account, the best route is usually the one that isn't blocked, stays on the road, and goes as straight as possible.
Setting the steering. The CCP vehicle simulated with full physics uses the same driving model that the player's vehicle uses. For example, both vehicles take a steering parameter between -1.0 and 1.0. This parameter is input from the control pad for the player's vehicle, but the CCP must calculate its steering parameter in real time to avoid obstacles and reach its final destination. Rather than planning its entire route in advance, the CCP simplifies the problem by calculating a series of Steering Target Points (STPs), one per frame in real time as gameplay progresses. Each STP is simply the next point the CCP needs to steer towards to get one frame closer to its final destination. Each point is calculated with due consideration to navigating the road, navigating sharp turns, and avoiding obstacles.
Setting the throttle. Most of the time a CCP wants to go as fast as possible. There are two exceptions to this rule: traversing sharp turns and reaching the end of a race. Sharp turns are defined as those in which the angle between two road subsegments is greater than 45 degrees, and can occur anywhere along the road or when traversing an intersection. Since the route through a sharp turn is circular, it is easy to calculate the maximum velocity through the turn by the formula
where V is equal to the velocity, u is the coefficient of friction for the road surface, g is the value of gravity, and R is the radius of our turn. Once the velocity is known, all that the CCP has to do is slow down to the correct speed before entering the turn.
Getting stuck. Unfortunately, even the best CCP can occasionally get stuck, just like the player does. When a CCP gets stuck, it throws its car into reverse, realigns with the road target, and then goes back into drive and resumes the race.
The Road Ahead
In the wake of the original Midtown Madness, we wanted open city racing to give players much more than the ability to drive on any street and across any open area. In order for a city to feel and play in the most immersive and fun way possible, many interactive entities of real cities need to be simulated convincingly. These entities include racing opponents, tenacious cops, ambient traffic, and pedestrians, all of which require powerful and adaptive AI to bring them to life. Midtown Madness 2 and Midnight Club expand on the capabilities of these entities, which in turn raises the bar of players' expectations even further.
The future of open city racing is wide open -- literally. Angel Studios and I are planning even more enhancements to the AI in any future games of this type that we do. Some ideas I'm planning to investigate in the future include enhancing the opponent navigation skills of all AI entities, and creating AI opponents that learn from the players. Additionally, I'd like to create more player interaction with the city pedestrians, and have more interaction between AI entities. Anyone wanna race?
Joe Azdima has been an AI programmer at Angel Studios for three years. During that time, he architected and implemented the entire AI system for Midtown Madness 1 and 2 for PC and Midnight Club for Playstation 2. Joe thanks Robert Bacon, Angel Studios' technical writer, for the exceptional editorial efforts Robert has applied to this article.
Discuss this article in Gamasutra's discussion forums