AI Madness: Using AI to Bring Open-City Racing to Life

Curves Ahead: Creating Traffic

Following rails and cubic spline curves. During normal driving conditions, all the ambient vehicles are positioned and oriented by a 2D spline curve. This curve defines the exact route the ambient traffic will drive in the XZ-plane. We used Hermite curves because the defining parameters, the start and end positions, and the directional vectors are easy to calculate and readily available.

Since the lanes for ambient vehicles on each road are defined by a list of vertices, a road subsegment can easily be created between each vertex in the list. When the ambient vehicle moves from one segment to the next, a new spline is calculated to define the path the vehicle will take. Splines are also used for creating recovery routes back to the main rail data. These recovery routes are necessary for recovering the path after a collision or a player-avoidance action sent the ambient vehicle off the rail. Using splines enables the ambient vehicles to drive smoothly through curves typically made up of many small road segments and intersections.

Setting the road velocity: the need for speed. Each road in the AI map has a speed-limit parameter for determining how fast ambient vehicles are allowed to drive on that road. In addition, each ambient vehicle has a random value for determining the amount it will drive over or under the road's speed limit. This value can be negative or positive to allow the ambient vehicles to travel at different speeds relative to each other.

When a vehicle needs to accelerate, it uses a randomly selected value between 5 and 8 m/s2. At other times, when an ambient vehicle needs to decelerate, perhaps because of a stop sign or red light, then the vehicle calculates a deceleration value based on attaining the desired speed in 1 second. The deceleration is calculated by

(V2 - V02) / 2(X - X0)

where V is the target velocity, V0 is the current velocity, and (X - X0) is the distance required to perform the deceleration.

Detecting collisions. With performance times being so critical, each ambient vehicle can't test all the other ambient vehicles in its obstacle grid cell. As a compromise between speed and comprehensiveness, each ambient vehicle contains only a pointer to the next ambient vehicle directly in front of it in the same lane. On each frame, the ambient checks if the distance between itself and the next ambient vehicle is too close. If it is, the ambient in back will slow down to the speed of the ambient in front. Later, when the ambient in front becomes far enough away, the one in back will try to resume a different speed based on the current road's speed limit.

By itself, this simplification creates a problem with multi-car pileups. The problem can be solved by stopping the ambient vehicles at the intersections preceding the crash scene.

Crossing the intersection. Once an ambient vehicle reaches the end of a road, it must traverse an intersection. To do this, each vehicle needs to successfully gain approval from the following four functional groups.

First, the ambient vehicle must get approval from the intersection governing that road's "traffic control." Each road entering an intersection contains information that describes the traffic control for that road. Applicable control types are NoStop, AllwaysStop, TrafficLight, and StopSign (see Figure 2). If NoStop is set, then the ambient vehicle gets immediate approval to proceed through the intersection. If AllwaysStop is set, the ambient never gets approval to enter the intersection. If TrafficLight is set, the ambient is given approval whenever its direction has a green light. If StopSign is set, the ambient vehicle that has been waiting the longest time is approved to traverse the intersection.

Figure 2. In this case, the TrafficLight class is set to red for some vehicles, which stop and wait. The other vehicles with green/yellow lights get permission to cross the intersection. The vehicle crossing in the left lane decides to turn left, while the vehicle in the right lane goes straight.

The second approval group is the accident manager. The accident manager keeps track of all the ambient vehicles in the intersection and the next upcoming road segment. If there are any accidents present in these AI map components, then approval to traverse the intersection is denied. Otherwise, the ambient vehicle is approved and moves on to the third stage.

The third stage requires that the road which the ambient is going to be on after traversing the intersection has the road capacity to accept the ambient vehicle's entire length, with no part of the vehicle sticking into the intersection.

The fourth and final approval comes from a check to see if there are any other ambient vehicles trying to cross at the same time. An example of why this check is necessary is when an ambient vehicle is turning from a road controlled by a stop sign onto a main road controlled by a traffic light. Since the approval of the stop sign is based on the wait time at the intersection, the vehicle that's been waiting longest would have permission to cross the intersection -- but in reality that vehicle needs to wait until the cars that have been given permission by the traffic light get out of the way.

Selecting the next road. When an ambient vehicle reaches the end of the intersection, the next decision the vehicle must make is which direction to take. Depending on its current lane assignment, the ambient vehicle selects the next road based on the following rules (see Figure 2):

Since the roads are sorted in clockwise order, this simplifies selection of the correct road. For example, to select the road to the left, just add 1 to the current road's intersection index value (the ID number of that road in the intersection road array). To pick the straight road, add 2. To go right, just subtract 1 from the road's intersection index value.

Changing lanes. On roads that are long enough, the ambient vehicles will change lanes in order to load an equal number of vehicles into each lane of the road. When the vehicle has traveled to the point that triggers the lane change (usually set at 25 percent of the total road length), the vehicle will calculate a spline that will take it smoothly from its current lane to the destination lane.

The difficulty here is in setting the next-vehicle pointer for collision detection. The solution is to have a next-vehicle pointer for each possible lane of the road. During this state, the vehicle is assigned to two separate lanes and therefore is actually able to detect collision for both traffic lanes.

Once a vehicle completes the lane change, it makes another decision as to which road it wants to turn onto after traversing the upcoming intersection. This decision is necessary because the vehicle is in a new lane and may not be able to get to the previously selected road from its new lane assignment.

Orienting the car. As the ambient traffic vehicles drive around the city, they are constantly driving over an arbitrary set of polygons forming the roads and intersections. One of the challenges for the AI is orienting the ambient vehicles to match the contour of the road and surfaces of open areas. Because there are hills, banked road surfaces, curbs separating roads and sidewalks, and uneven open terrain, the obvious way to orient the vehicles is to shoot a probe straight down the Y-axis from the front-left, front-right, and rear-left corners of the vehicle. First, get the XZ position of the vehicle from the calculated spline position and determine the three corner positions in respect to the center point of the vehicle. Then, shoot probes at the three corners to get their Y positions.

Once you know the three corner positions, you can calculate the car's orientation vectors. This approach works very well, but even caching the last polygon isn't fast enough to do all the time for every car in the traffic bubble. One way to enhance performance is to mark every road as being either flat or not. If an ambient vehicle drives on a flat road, it doesn't need to do the full probe method. Instead, this vehicle could use just the Y value from the road's rail data. Another performance enhancement is to orient the vehicles that are far enough from the player using only the road's rail-orientation vectors. This approach works well when small vehicle-orientation pops are not noticeable.

Managing the collision state. When an ambient vehicle collides with the player, or with a dynamic or static obstacle in the city, the ambient vehicle switches from using a partially simulated physics model to a fully simulated physics model. The fully simulated model allows the ambient vehicle to act correctly in collisions.

A vehicle manager controls the activities of all the vehicles transitioning between physics models. A collision manager handles the collision itself. For example, once a vehicle has come to rest, the vehicle manager resets it back to the partially simulated physics model. At this point, the ambient vehicle attempts to plot a spline back to the road rail. As it proceeds along the rail, the vehicle will not perform any obstacle detection, and will collide with anything in its way. A collision then sends the vehicle back to the collision manager. This loop will repeat for a definable number of tries. If the maximum number of tries is reached, the ambient vehicle gives up and remains in its current location until the population manager places it back into the active bubble of the ambient vehicle pool.

Using an obstacle-avoidance grid. Every AI entity in the game is assigned to a cell in the obstacle-avoidance grid. This assignment allows fully simulated physics vehicles to perform faster obstacle avoidance.

Since the road is defined by a list of vertices, these vertices make natural separation points between obstacle-avoidance buckets. Together, these buckets divide the city into a grid that limits the scope of collision detection. As an ambient vehicle moves along its rail, crossing a boundary between buckets causes the vehicle to be removed from the previous bucket and added to the new bucket. The intersection is also considered an obstacle bucket.

Simulation bubbles for ambient traffic. A run-time parameter specifies the total number of ambient vehicles to create in the city. After being created, each ambient vehicle is placed into an ambient pool from which the ambients around the player are populated. This fully simulated region around the player is the simulation bubble. Relative to the locations of the player, remote regions of the city are outside of the simulation bubble, and are not fully simulated.

When a player moves from one cull room to another, the population manager compares the vertex list of the new cull room against the list for the old one. From these two lists, three new lists are created: New Roads, Obsolete Roads, and No Change Roads. First, the obsolete roads are removed from the active road list, and the ambient vehicles on them are placed into the ambient pool. Next, the new roads are populated with a vehicle density equal to the total vehicle length divided by the total road length. The vehicle density value is set to the default value based on the road type, or an exception value set through the definition of the race AI map file.

As the ambient vehicles randomly drive around the city, they sometimes come to the edge of the simulation bubble. When this happens, the ambient vehicles have two choices. First, if the road type is two-way (that is, ambient vehicles can drive in both directions), then the vehicle is repositioned at the beginning of the current road's opposite direction. Alternatively, if the ambient vehicle reaches the end of a one-way road, the vehicle is removed from the road and placed into the pool and thereby becomes available to populate other bubbles.

Driving in London: left becomes right. London drivers use the left side of the road instead of the right. To accommodate this situation, some changes have to be made to the raw road data. First, all of the right lane data must be copied to the left lane data, and vice versa. The order of each lane's vertex data must then be reversed so that the first vertex becomes the last, and the lane order reversed so that what was the lane closest to the road's centerline becomes the lane farthest from the center.

Given these changes, the rest of the AI entities and the ambient vehicle logic will work the same regardless of which side of the road the traffic drives on. This architecture gave us the flexibility to allow left- or right-side driving in any city.

________________________________________________________

City People: Simulating Pedestrians