I occasionally get requests to write about game AI, especially the AI from MotoGP. I have resisted this topic for the simple reason that I never worked directly on AI code, so I don't really know much about it. But hey, this is the Internet, right? You don't have to know anything about a subject in order to write about it on the Internet :-)
Disclaimer: what follows is mostly hearsay, filtered through a couple years of forgetfulness.
My previous post reminded me how many tasks can be simplified by choosing the right coordinate system. Anyone who works with 3D graphics will be familiar with the concept of moving back and forth between different coordinate spaces, common examples being object space, world space, view space, projection space, bone space, and tangent space. Many AI problems can also benefit from their own specialized coordinate systems.
A common simplification is to collapse 3D into 2D. Even though rendering and physics may be truly 3D, decision making logic need not treat all three axes equally. MotoGP tracks have few hills, so our AI was able to ignore the y component.
Next, we switched from x/z cartesian coordinates to a track-relative system. Positions were represented by a pair of values:
To convert between this and the cartesian coordinates used by our physics and rendering code, we stored a list of segments defining the shape of the racing surface:
struct TrackSegment { Vector CenterPoint; float DistanceToLeftEdge; float DistanceToRightEdge; }
We created several hundred of these structures, spaced evenly around the track, by tessellating the Bezier curves from which the tracks were originally created. This gave us enough information to write the necessary coordinate conversion functions.
With track-relative coordinates, many useful calculations become trivially simple:
if (abs(cross) > 1) // You are off the track and should steer back toward the center line if (this.distance > other.distance) // You are ahead of the other player (even though you may be // physically behind in 3D space if you have lapped them) short difference = (short)(this.distance - other.distance); if (abs(difference) < threshold) // These two bikes are physically close together, // so we should run obstacle avoidance checks
Because of the fixed point data format, casting the distance counter from 32 to 16 bits was an easy way to discard the lap number, so we could pick and choose which computations cared if two bikes were on different laps, versus wanting to know if they were close in physical space. Thanks to the magic of two's compliment, treating the difference as signed 16 bit gives the shortest distance regardless of which bike is in front (remember that in a modulo arithmetic system such as a looping racetrack there are two possible distances, as you can measure in either direction around the track). This works even when the two bikes are on opposite sides of the starting line, a situation which would require error prone special case logic in most other coordinate systems.
Flattening and straightening out this virtual gameplay area made it easy to reason about things like "am I on the racing line?" or "I'm coming up fast behind this other bike: do I have more room to pass them on the left or right?" which would have been tricky to implement in a full 3D world space. Once we decided to pass on the left, we would convert the resulting track-relative coordinate back into world space, at which point the curvature of the track gets taken into account, showing how we should steer to accomplish our chosen goal.
Pathfinding can also benefit from specialized coordinate systems, the London underground map being a classic example.