day5 - race track coordinate concept

Yesterday I had some thoughts on the toughest challenges I will have to overcome during the development.  I think it is wise to reckon them before I start the work on technical aspects of the game.
Here is the first task that got me a little worried.

getting precise player positions in the race track space
This includes for AI and player to know its exact distance from start and finish and distance from both track sides. I want to avoid any ray-checks from car to do that. It is too expensive and not very accurate. One solution is to have loads of colliders (sensors) covering the track, so whenever car touches one of the sensors we know how far the car is from sides and finish then it is possible to compare it with other cars and we know which car is leader and so on. But it is just not very efficient to manually add them for a hundred kilometers long track. 
What I have in mind is to convert world space position to track-relative position. So it would switch from world xyz coordinates to track uv coords. U would correspond to travelled distance and range from 0.0 to 1.0 where 0.0 is start line and 1.0 is finish line (not sure about floating point precision here) and V would be track width ranging from -1.0 to 1.0 where 0.0 is middle of the track. This idea comes from THIS blog post about AI coordinate system used for MotoGP. I think it is very elegant and simplifies a lot of tasks especially AI behavior and keeping them on track without using bunch of waypoints and ray-check system.


How would that work?

Vector power!
Race tracks will be made of segments which I will deform by curve and multiply with array till the end of the length of curve. Lets assume that 1 track segment is a quadrilateral (tetragon) made of 4 points. To switch to track-realtive coordinates we need to know world position for each track segment. This means getting each point of track into an array and sort them to form lines, so each segments start & end line act as sort of check point. Then for each car we can get on which segment the car is on and calculate the fraction of the segment covered with point-quad or point-triangle intersection function.

I already got a chance to implement an efficient ray-quadrilateral intersection test in BGE and it works really nicely, though I have to check performance compared to point-triangle intersection functions.

Here is a simple illustration:



The tracks will have sharp turns, loops, banks, tilts and variety of configurations which makes the work on AI really hard, but converting all to track-relative coordinates "flattens" and "straightens" the track which makes work with AI ridiculously simple.
some examples:

if (player.distance > otherplayer.distance):
    #you are ahead of other player

difference = player.distance - otherplayer.distance
if (difference < treshold):
    #start collision avoidance
    #start the overtake process?

how to check on which side to overtake an opponent:

if(overtake = 1):
    #overtake in progress
    player_ahead.width > 0.0 ? go_left : go_right
    #see on which side is more space and go
    #here we can also override previous statement to check if car width is wide enough to fit in the narrowest side and so on..

this all is just a theory now how I imagine it to work in my game. I think many commercial racing games use similar approach and it works, but they have dedicated professional programmers up to the task. will see how I can handle this when I start the work. I am open for suggestions and perhaps there is even a better solution for this.

Now I take a few day rest from the project as I am moving from France to Belgium and then back to Latvia.

Edit:
I got working the basic concept of coordinate system:
https://dl.dropbox.com/u/11542084/get_track_position.blend
If this proves to be efficient enough for big tracks then I will use it in the game.

References:
1 - http://blogs.msdn.com/b/shawnhar/archive/2009/12/30/motogp-ai-coordinate-systems.aspx
2 - http://answers.unity3d.com/questions/25189/race-position-help.html
3 - http://gamedev.stackexchange.com/questions/2382/how-would-one-determine-the-position-of-a-participant-in-a-racing-game
4 - http://graphics.cs.kuleuven.be/publications/LD04ERQIT/