How would one determine the position of a participant in a racing game?

Question

Now, for the record, I'm currently not implementing any racing game whatsoever, but this problem just popped into my mind and now I'm curious.

So how would one go about finding out which participant of a race is currently the first one? It can't be something trivial like just sorting by distance to the finish line because that would be highly inaccurate on most courses. I've thought about doing something like separating the route into straight segments, each of which has a direction vector. The game would then check for when someone outruns somebody else by projecting their positions onto that vector and checking which one is ahead. If the position has changed, the game would increment/decrement them appropriately. But that does seem a little too complicated.

Does anybody know of any established methods or has any experience in implementing some?

Answer 1

Shawn Hargreaves describes how MotoGP used a special track-relative position system. Ignoring the vertical y position, the x/z Cartesian coordinates are translated to a track-relative system. This had many benefits for calculations involving the relative positions of participants in a racing game (for example for the AI):

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:

int distance = how far around the track, stored in 16.16 fixed point format

• 0 = starting line
• 0x8000 = half way around
• 0x10000 = looped back to the start
• 0x1C000 = three quarters of the way through the second lap

float cross = how far sideways across the track 0 = on the center line

• -1 = left edge of racing surface
• 1 = right edge of racing surface

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.

Answer 2

I guess I would use the fact that the road is generally built up by using splines, therefore every edge of the road has a corresponding spline position, and using that you could determine (approximately, or fine grained if you subdivide further) what the current spline position of each car is, and thus who is in the lead. So more or less the way you suggest, just using the spline.

Answer 3

You've more or less answered your own question, I think. Divide the track up into segments, track which segment each car is in, and project the cars onto a line through the middle of the appropriate segment (mathematically it's a simple dot-product, so not complicated at all). Very simple to give each car a "distance" which you can sort for position.

The segments give you some additional benefit - you can ensure that cars don't cut-corners (or general take short-cuts), go backwards, or other cheats.