I have been theorizing lately about top down racing AI. I've Googled the subject and have read a couple of good articles on the topic. they seem to go a little deeper than I want into the realm of racing physics. I am a simple person and believe in simple solutions to problems. I am curious if anyone here has any high level tips for simply keeping computer cars on track, doing their best to complete laps, and recover from bumps by other cars.

I have considered using waypoints and sending them from one to the next. I have also considered hardwiring their paths with "room for error and recovery". Or maybe an invisible hardwired "carrot" that each car chases. They are always drawn to their carrot "magnetically" which would give the illusion of free will when bumbed. My main issue is that I've always programmed tile based games, and I am now trying to step outside the grid.

Hmm, anyway, any high level comments or ideas are welcome and appreciated.

I would go for waypoints myself. The advantage is that with waypoints you can "plot" an ideal path for the cars e.g. taking high-speed lazy arcs from the outside of a bend to the inside and outside again, if you know what I mean.

This also means that the AI-driven cars will doggedly aim for the "best" path even if you as a player, or the other cars are in the way.

The thing about waypoints that confuses me is that if AI car is halfway between waypoints and gets bumbed into the grass it will look for shortest route to next waypoint, rather than get back on the road first. I guess using many waypoints could solve this...

it seems that there could be a simpler way...

Closer waypoints is one way to improve the situation!

I would also suggest the following:

If not in the road, determine the shortest distance from the car to an immaginary line joining the last waypoint with the next. If this distance is shorter than a straight line to the next waypoint, aim for it, otherwise, proceed to the next waypoint (you were probably close to it anyway).

Before trying the above I would suggest you try more waypoints first.

Just to expand on what Nemesis was saying:

I believe a simple state machine would solve your problem, along with something like the Strategy design pattern. It should be straightforward enough to simply change to an "offroad" state that uses a strategy based on any combination of direction determination calculations that work best for your particular gameplay, i.e., simply aiming for the nearest midpoint of a road section then changing states to "onroad" and searching for the next waypoint, or better yet, using a weighted avereage favoring the midpoint of the road (or a point of your choosing) but factoring in the location of the next waypoint, etc. The states could also be expanded to take into account terrain, driver attributes, vehicle attributes and other factors.

Good ideas. I like the use of a state system because I do want 'on road' 'offroad of varying degrees' and 'obstacles'.

I am now struggling with curvy track problems. the waypoint system seems great for fairly straight areas, but how to get smooth driving through a variety of curves at an appropriate speed. Even with many waypoints, some arc of travel must be established based on "track radius info", which makes me wander if there's a way to make the track smart rather than the cars. Just brainstorming at this point. Obviously the cars would have characteristics like speed, handling. not sure best way to make cars take corners smoothly...

If you implement simple physics constraints on the car, e.g. they have a limited turning rate etc. then it shouldn't be too hard to get smooth paths.. the cars will simply have to start turning to face the next waypoint. Careful placement of waypoints should ensure that the the cars will look smart enough to pick the best path in the track.

I worked on a couple of PS1 racing titles, and they each used way points for the ideal path around the track. The tracks were enclosed, so there was no problem of the car getting off the track that "go to the next waypoint" didn't solve.

Using waypoints in combination with A* could solve the problem with computer cars bumping into other cars?

BTW. If you are one of those indies who will only spend 3 weeks on a game then do a simpler game ;)



Reminds me of Yes Primeminister (as remembered):

Humphrey: I foresee unforeseen problems.

PrimeMinister Hacker: What kind of unforeseen problems?

Humphrey: If I could tell you that then they would not for unforeseen now would they?

PrimeMinister Hacker: But you just said you could foresee them !!!

Found these articles pretty usefull:
http://www.red3d.com/cwr/steer/

There's a good article by Gari Biasillo on this in AI Game Programming Wisdom.

He describes a system using a chain of sectors to describe the track.
He uses a state machine to tell the AI when it's off the track, airborne, etc.

You can find it at Amazon (http://www.amazon.co.uk/exec/obidos/ASIN/1584500778/ref=sr_aps_books_1_2/026-3309412-6766804)

"AI Game Programming Wisdom" is a good resource book to have handy - lots of "solutions" to various problems with example sourcecode & workable solutions instead of pure theory.

A while ago I wrote an article on implementing a fuzzy control system to steer a car. You can find it at http://www.ronkes.nl/fuzzy/default.html. It was written in a bit of a hurry, so it's not as good as it was supposed to be, but maybe it's still helpful.

Another thing you could do (this is just from the top of my head, mind) is overlay your track with a grid and give each grid square a weight based on whether the car should go there: low weights indicate a good road to take and high weights indicate a bad road to take. Just use a shortest path algorithm to determine where to go.

This should also help with getting back on track, since it's the same calculation. To avoid bumping into other cars, give the square a car occupies a very high weight. You can also change conditions of the track by adjusting weights. Even learning is possible by letting the computer driver adjust the weights if necessary.

I'm getting all excited about this. Maybe I should just go and implement it. :-)

Wow. Great ideas guys. I knew Dexterity was the place to go for this question. I will visit all the links provided. At this point I am interested in this problem more out of general curiosty than the desire to go build a full blown racing game. I've spent so much time building tile based games, and when I downloaded a casual old style top down racing game demo, it reminded me that there is a whole world out there beyond tile based games about which I know very little.

It's interesting that grid systems and a* are coming up as ways to solve this problem. It would be ironic to go full circle with this problem and end up with a basically tile-based racing solution. At one point I even wandered if a tile-based turn based car game would could be interesting (I guess it'd be simliar to Car Wars, Steve Jackson Games) but along with trying to escape the grid, i am also trying to escape turn based gameplay.

I am also interested in non-linear tracks, shortcuts, multiple paths. Curious how adding this to the equation affects approach...

p.s. Ronkes, your link is broken...

Actually, it's parsed wrong. www.ronkes.nl/fuzzy/default.html