Hi, Assume a simple problem: pathfinding in a 3D level. Now, the first really _working_ solution I can think of would be: a) The level editor creates "pathfinding vertices" along the level. Then the path can be found within these vertices, and the only "hard" part for the bot is to figure its way from a single vertex to another (which is easy if the vertices are spread nicely). Now the question is, do REAL games use this kind "abstraction" methods. They seem rather time consuming, because it really assumes explicit work by the level designer. Then, a second, largely related question: b) Do racing games have preprogrammed track lines which the AI bots try to follow, while avoiding obstacles such as other cars? Sorry for still being in my "insecure" state of AI coding, and thanks for all the help. -- Mikko

as far as I know, every racing game uses more or less the ideal driving line, and gives some "range" around it. At least I never played a racing game that didn´t make that impression to me and most of them don´t even react when you bump into them... many racing-AIs just stay on their track, so avoiding obstacles could even be considered an "innovation" ;)
For 3D-shooters and the like it´s nearly the same, though I could think of another solution:
You could chop the level into concave primitives (quads for example) and save possible connecions between them, so the bot could choose for himself where to go next. But for this to work you have to give some goals for the bot, so that it knows, what room he wants to reach.
Just for self-defense: never done some real AI programming, but wrote a little java tool that found it´s way from point A to point B on a 2D map with obstacles. with this system and I think this could also be applied to 3D maps.

Somewhere I read that for example in Collin McRae they used pre-defined paths and pre-learned neural network which was taking care of steering/braking/accelerating.
And also when trying to avoid cars this AI swiched to normal "rules" for avoiding obstacles

a) It's called "waypoint navigation". Majority of games (esp.FPS) use this technique - it's fast and simple, straightforward to implement. Some engines (and AI SDKs) can generate waypoint maps automaticaly, while some other require a designer input (Unreal, HL). Another good point of this system : one can store much more info in a waypoint, not just coordinates (eg tactical information, hints about environment - light, sound exposure etc.) which can help making a "clever" pathfinder. Bad sides : No immediate knowledge about the surrounding (static) environment, like walls, tight corridors etc. It is, basically, just an ordinary graph.
Another method widely utilised is Navigation Mesh(es). Think of them as a carpet your NPCs walk on. Usualy created from physics-mesh, or hand-crafted. Very good for precise navigation and don't suffer from environmental "un-awareness". Providing carefull coding, your NPC is guarrantied never to get stuck against the wall or any other static obstacle.

Btw, never underestimate the importance of designer's input in setting-up a navigation representation. Automatic generation is fine, but the more information you need from it, the more important is the carefull and clever layout which can only come from a man, not an algorithm!

b) Racing games (or any other car-driving game) use different methods to navigate the track. Bear in mind that there are, usually, two distinctive "car-AI"s - traffic AI and racing AI.
The simplest track-navigation method consists of laying down the splines along the road and have the car follow it. More complicated traffic-AI can use a method similar to NavMeshes - having a road (which can contain more than one lane with traffic going in both directions) built as a geometry and using vertices as a steering-helpers (as implemented in Midtown Madness - you can find the article about it on Gamasutra).
Along with track-representation, Race-AI usually uses a spline to represent the most optimal path.