Myself with a few other programmers are creating a racing game in the style of Wipeout, F-zero, etc. The tracks are made from Bezier curve surface patches therefore just about any sort of track can be made (think loops, twisting, tubes, etc). The problem is that AI for the game needs way-points in order to race, and I was wondering how I should generate those way-points programmatically, so that they follow the optimum racing line? Bear in mind that there are 4 cars that have different handling and acceleration and therefore a set of way-points needs to be created for each car to get the optimum racing line for that vehicle. Also the racing tracks can be generated by the end user therefore its not possible to put the way-points in manually. Basically I need some sort of algorithm to find out the quickest path around the race course taking into consideration; track curvature, handling physics of the cars, acceleration/deceleration of cars and maximum speed of the cars. I've briefly looked into neural networks (NN), A* path finding and particle swarm optimization (PSO). At the moment I'm preferring A* (used it before); NN's look too complicated to implement in the allotted time frame; although I'm liking PSO's I don't know how to really implement yet - anyone used them before? With A* I'm just unsure on how to weight the costs of car handling, car acceleration/deceleration and maximum speed of the car properly in order to produce the quickest racing line around a circuit. Sorry for the long post, what are your ideas on this? Thanks

It seems like you're making it more complicated than it needs to be. If you have a good path following steering behavior then you could stick the nodes right along the center/s of the path/s and get reasonable results. Design your steering behaviors with a set of constants, and adjust those for each car. Cars that turn slower or go faster could look further ahead along the path for their goals etc. I really don't see why it would be necessary to find a separate set of nodes for each car.

http://www.red3d.com/cwr/steer/PathFollow.html

If you really want THE optimal race line, look into Calculus of variations and the theory of Optimal Control.

You'll get to learn ton of fun stuff.

Thanks for the great link on steering behaviours Alrecenk. I think what I'm planning on doing is still working out an optimum path of some sort around a race track, but only 1 (therefore not one for each car). Then use steering behaviours combined with the optimum to get hopefully a competitive (and non-cheating) AI.

Thank you Steadtler too for the links, I think I'll have to read over them a few times to understand them properly, although I think it may be a bit over kill for what I'm planning.

This is an area where simple stochastic optimization methods such as simulated annealing can work well. Start with the center of the track as the racing line, then use simulated annealing to converge on the optimum line. The only tricky part is keeping the path smooth; you can use NURBS or other splines, or simply perform a smoothing step after each perturbation.

I think you can solve this kind of problem almost exactly using numerical optimization too. I'm not sure on the details, but they mention it in this video about applying AI to the TORCS racing framework:

http://www.ceet.niu.edu/faculty/coller/video.htm