Shawn Hargreaves Blog
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:
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.
hmmm....I know that using 2's Complement, 16 bit numbers improves speed and uses less memory. But wanted to know since you are dealing with xna Framework should we still be bothered about 2'complement and 16 bit integers!!??
I am sure there would be few classes to convert between different co-ordinate system. Can you discuss these in your upcoming blogs
16 bit integer types are not generally a speed optimization. Depending on CPU, they are the same or sometimes slower than 32 bit integers.
Reducing 32 bit data to 16 bits can certainly save memory, which can provide an indirect speed boost by improving cache performance, but this is really only significant when dealing with large amounts of data as opposed to a single field.
In this example, though, we were taking advantage of specific mathematical properties of the integer data type. The important thing was not that it happened to be 16 bits in size, but how overflow behaves when performing arithmetic on these values. That can be useful in any language and on any platform: if you want to do math using modulo arithmetic, it is helpful to have a data type where this "just works" as opposed to having to implement your own modulo computations on top of conventional linear mathematics!
This is elegant stuff. I would urge anyone planning to implement code based on overflow and other mathematical properties to use small sensibly named methods, and adequate comments!
Terse code is dangerous, so if your going to implement something in as specialized a way as this then make sure you document it to the level that Shawn has in his article.
"You don't have to know anything about a subject in order to write about it on the Internet"
Those are words that I live by! Nice post though, it certainly _sounds_ like you know the subject :)
Shawn, how did you go about actually calculating the distance/cross values based on a racer's position? Did you just use temporal coherence to only look at track segments near the last lookup? Spatial partitioning? I can't imagine you just did a brute-force distance check against each segment.
> Did you just use temporal coherence to only look at track segments near the last lookup?
Basically yes, but it didn't work very well :-) There were a lot of corner cases where this tracking could go wrong (and in fact many of our LIVE leaderboard exploits were due to people discovering how to break this algorithm), so over time we added more and more workarounds and ended up falling back on brute force search more often than not.
The idea worked great, but the specific implementation of how we tracked the position wasn't one of my more successful pieces of code!
If you are talking about 2's complement, then you must be meaning that you use signed integers. If you do, overflows are undefined. You have a bug.
The only mitigation I see here that could save you, is that I'm not sure if the behavior is unspecified or undefined. The difference would be that you have a clear behavior given one compiler and one platform, that you can rely on deterministically checking asm output to be sure. (this is going really far, everybody knows how a usual cpu/compiler couple handles signed overflow, but still for rigor). otherwise, use unsigned overflow, this is perfectly specified.
The behavior of 2's compliment arithmetic is perfectly standard and well defined on every mainstream modern platform. It's entirely reasonable to take advantage of this unless one of:
a) You are targeting 70's era mainframe HW
b) You are targeting one of the more esoteric DSP architectures
c) You enjoy playing language lawyer with corners of the C++ spec that don't apply to modern CPU types