# How to find the optimum path, on a road, for a car?

For the moment I have an AI car, that follows points (let's call this Waypoints), that I built by myself.

Of course, it's not optimal because of my poor human hand, and car knowledge.

After this drawing, I put waypoints (about 80) on this red line, and my car is able to follow it (and dodge other cars, but that's another story).

But... It's not perfect: I read some articles, but I don't know how to implement the generation of the perfect path..

http://www.drivingfast.net/techniques/racing-line.htm (speaking about an 'Apex', but I don't know how to find this particular point)
"Searching for the Optimal Racing Line Using Genetic Algorithms" (too complicated for my little game)

• Check out Artificial Intelligence for games second edition by Millington and Funge. It has info on how it's done in other games and some potentially relevant example code like neural networks and genetic algorithms. Jul 21 '16 at 9:26

You're looking for two important properties here. The path must obviously be continuous (can't jump) but also the direction must be continuous (turning around a corner takes time). Since it's a racing game, there's also a third constraint: the turn radius probably should be larger at high speeds. However, you can probably fake that one.

The common techniques to calculate paths like this are splines / Bezier curves

• I already use Bezier curves to generate the graphic and physic road, but the problem is : What are the points for curves for the path? I can generate a path from a curve, and a curve from 3 points, but where are they is the problem Jul 21 '16 at 9:29
• In general, on the inside of each corner. For the example above, that gets you 6 points. However, if you used only those, you'd come out of the corners far too wide. So you need a few extra points in and out of each corner, on the outer edge of the straights - about 2R away from the corner itself. (This is not needed if there's another turn following) Here the curve is constrained not just in position but also in direction, onto the straight. If you look at the example above, that will give you a better path: it avoids the too-sharp turn on the bottom where your path stays on the inside. Jul 21 '16 at 9:37

Technique generally used on AAA games to find the best possible path for a given car (because car settings are often all different) is to run an AI that will improve its driving technique. After thousands (millions?) of runs, comparing the last one to the currently best one, the AI will be able to determine the best possible path for this given car setting.

• Is it that easy ? It seems so... I don't know, so 'easy', but I found some limits : 1/ I move one point, if best time is better, I keep, but we can imagine that it will not be optimal with another change 2/ It will be soooo long to run about 30 seconds of race, then a change, then 29.5 seconds... Jul 21 '16 at 8:43
• It's absolutely not that easy. But it's generally how it is made if you need to know the perfect path. Jul 21 '16 at 8:50
• Another way would be to know the characteristics of every vehicles and make assumptions for the best path: this car has a very limited turning radius -> the next curve has a raw angle of 25 degrees -> I deduce that the car should take this path with this velocity. Jul 21 '16 at 8:52
• you can't have "universal optimal points" when every car is different (in theory). In the car game I worked on we had a very complex customization system that made every car almost unique... we had to know the average characteristics of every parts to deduce the overall capacity of the car and then pre-compute paths. (heavy work) Jul 21 '16 at 8:55
• @NauticalMile I'm beginning to implement this, and with Unity, I just have to set the timeScale to increasse the speed. Basicly, it's just : 1/ One lap then stop 2/ If time > timeBestlap, we reset to the best path and if time < timeBestLap, we keep the changes 3/ Make a change (translation of point(s) by exemple) I can be wrong, but it's the naive way to go (I think) Jul 22 '16 at 8:53